处理器结构--分支预测(Branch Prediction)

背景

条件分支指令通常具有两路后续执行分支。即不采取(not taken)跳转,顺序执行后面紧挨JMP的指令;以及采取(taken)跳转到另一块程序内存去执行那里的指令。是否条件跳转,只有在该分支指令在指令流水线中通过了执行阶段(execution stage)才能确定下来。

如果没有分支预测器,处理器将会等待分支指令通过了指令流水线的执行阶段,才把下一条指令送入流水线的第一个阶段—取指令阶段(fetch stage)或者将后续流水线全部清空。这种技术叫做流水线停顿(pipeline stalled)或者流水线冒泡(pipeline bubbling)或者分支延迟间隙。最初的RISC体系结构处理器采用的应对分支指令的流水线执行的办法。

原因

分支预测器猜测条件表达式的两路分支中哪一路最可能发生,然后推测执行这一路的指令,来避免流水线停顿造成的时间浪费。如果后来发现分支预测错误,那么流水线中推测执行的那些中间结果全部放弃,重新获取正确的分支路线上的指令开始执行,这招致了程序执行的延迟。

在分支预测失败时浪费的时间是从取指令到执行完指令(但还没有写回结果)的流水线的级数。现代微处理器趋向采用非常长的流水线,因此分支预测失败可能会损失10-20个时钟周期。越长的流水线就需要越好的分支预测。

一条条件跳转指令第一次遇到,还没有任何信息可以去预测分支。此后保持这条指令是采取还是不采取跳转的历史记录,就可以作为再遇到这条指令时猜测最可能的分支。

实现

主要包括两类预测器:
静态预测器(Static Predictor)以及动态预测器(Dynamic Predictor)

静态预测器

预测条件跳转不发生,因此总是顺序取下一条指令推测执行。仅当条件跳转指令被求值确实发生了跳转,则非顺序的代码地址被加载执行。另外一种,则预测条件跳转总会发生,因CPU而异。对于这种静态预测如果产生错误,则惩罚就是清空后续的PipeLine中的指令。

而另外一个静态预测器就是LSD:Loop Stream Decoder

Loop Stream Decoder

传统的分支预测流程是:
分支预测-->取指-->解码


传统的分支预测流程

而LSD的目标就是检测CPU是否处于程序的Loop(for,while,do---while)中,如果处于Loop中,则会停止分支预测,并且为将LSD中的存储的指令流向ReoderBuffer。

其中分支预测和取指硬件将会被禁用,并且会将28条Micro-Ops保存在LSD中,并且将指令一遍遍传入ROB直到Loop完成或者跳出循环。

LSD工作时流程

动态预测器与BTB(Branch Target Buffer)

基于之前执行的分支信息,处理器对于正在执行的程序所做的决定。最简单的一种就是:1-bit动态预测,比如Alpha 21064 RISC处理器就使用这种。

原理:根据该指令上次是否跳转来预测此次是否跳转。如果上次跳转,则预测此次也会跳转。

而更好的一种方案是n-bit动态预测
例如2bit动态预测器。以下为2bit动态预测器工作原理:

  • 当处于处于00状态时候,预测顺序分支
    • 预测成功,仍处于00状态
    • 预测失败,则调整为01状态
  • 当处于01状态时,继续预测顺序分支
    • 预测成功,则调整为00状态
    • 预测失败,则调整为10状态
  • 当处于10状态时,预测其他分支
    • 预测成功,则调整为11状态
    • 预测失败,则调整为01状态
  • 当处于11状态时,预测其他分支
  • 预测成功,仍处于11状态
  • 预测失败,则回退到10状态


    2-bit动态预测器

而另外一种变种的2-bit动态预测器如下图所示:

变种2-bit动态预测器

标记分支状态以及分支历史的一段内存被称为BTB,这段内存非常小,仅仅只存储了分支指令地址,以及预测的目标地址,以及预测的位。

当一个分支指令第一次执行时,处理器为该指令分配一个Entry放入BTB中,当指令读取请求的时候,将该指令同步放到L1的Instruction Cache以及BTB中,如果在BTB中Match上该指令,Branch Target Address将会从BTB中被读取。当指令分支执行完毕后,它的Target Address也会在BTB中被更新,Prediction Statistics也同样会更新。

Branch Target Buffer

通常静态分支预测方法不需要太多硬件资源,不过它会提高编译器的复杂度,同理动态预测方法会增加硬件的复杂度,但是对编译器的要求不会太高。通常动态预测的结果会比较好,并且在编译期后决定分支,对面向对象的代码提供了更好的兼容性。

分支预测正确与错误的惩罚

参考资料

维基百科-分支预测
SSCE-Branch-Predict
Improved Loop Stream Detection

©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 198,030评论 5 464
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 83,198评论 2 375
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 144,995评论 0 327
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 52,973评论 1 268
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 61,869评论 5 359
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 46,766评论 1 275
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 36,967评论 3 388
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 35,599评论 0 254
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 39,886评论 1 293
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 34,901评论 2 314
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 36,728评论 1 328
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 32,504评论 3 316
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 37,967评论 3 302
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,128评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 30,445评论 1 255
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 42,018评论 2 343
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 41,224评论 2 339

推荐阅读更多精彩内容

  • 计算机系统漫游 代码从文本到可执行文件的过程(c语言示例):预处理阶段,处理 #inlcude , #defin...
    willdimagine阅读 3,547评论 0 5
  • 处理器发展历史 最开始的处理器比较简单,8086处理器是评估当前的指令指针(CS:IP)指向的指令,然后再执行解码...
    None_Ling阅读 3,842评论 0 1
  • 很多事情,知道的越早越好,因为知道了才会有意识,才能提前去规划。 理财,很多人觉得不关己事。刚毕业的,觉得钱不多没...
    三仙居士阅读 338评论 0 0
  • 童年趣事 文/吴多涵 大年初一,爸爸、妈妈,我还有妹妹,我们一起去了泉城济南的海洋世界,你们去过吗?让我来给你介绍...
    童声童话阅读 392评论 0 0
  • 郭相麟 每个人来到这个世界 总有自己独特的价值 在没有发现自己独特的价值时候 内心表面坚强 实则有着其脆弱的一面 ...
    郭相麟阅读 171评论 0 0