11
NT T NT T
10
Predict Taken
T Predict Not Taken
01
NT
00
Predict Not Taken
NT
8
T
11
NT
10
T
01
T NT
00
例子
NT NT
T
Actual: State: 1-bit 2-bit Predicted: State: Predicted:
�冒险导致处理器指令调度的问题
2
Branch Penalty ） 分支代价（ 分支代价（Branch Penalty）
� 分支代价（Branch penalty）: 在没有特殊措施的情况下，处理器流水线 由于等待分支指令结果（方向）和目标地址所需的停顿时间 � 在现代处理器中，分支代价非常高昂
3
推测式执行
− 采用程序计数器PC的一部分作为访问BHT的索引 − 一个BHT表项为一个bit，存储上次映射到该表项的分支指令的实际方向（若 taken则为1，否则为0），本次的预测结果则有存储的内容决定 − 别名效应（Alias effect）: 会有多个分支指令映射到同一个BHT表项，造成 当前查询该BHT表项的分支指令，得到的可能是别的分支指令上一次的结果
25
的局限性 BHT BHT的局限性
虽然可预测方向，但对于预测为跳转的情况，需要等到指令取指和译 码完成，而且目标地址已经知道的前提下，才可重导指令流
26
推测式执行
� 推测式执行（speculative execution）: 由硬件推 测分支指令的结果来克服控制相关，分为3个部分
1. 方向预测（Direction prediction）: 预测分支指令的方 向是跳转（taken）还是顺序执行（not taken） 2. 目标地址预测（Target address prediction）: 在预测 分支方向为跳转的情况下，对跳转目标地址的推断 3. 推测式执行（Speculative execution）: 在控制相关解 决之前，允许流水线按推测的方向和目标地址获取和执 行指令；若发现推测错误，则及时终止错误推测的指令 取指和执行，并消除（undo）由于执行错误指令造成 的后果
高等计算机体系结构 （Advanced Computer Architecture）
第八讲 指令级并行：超标量处理器 -B 指令级并行：超标量处理器-B （Instruction Level Parallelism: Superscalar Processors -B） Processors李险峰 （lixianfeng@） 北京大学深圳研究生院
− 如果上一条分支指令为非跳转, 则使用和更新 predictor p0 − 如果上一条分支指令为非跳转, 则使用和更新p1
� 那么，这种被称为(1,1)型的协同分支预测器，在初 始化为[0,0]的情况下会有怎样的表现？
16
协同分支预测器的通用形式
�(m, n) 形式
− 采用最近m条分支指令的“全局”历史结果参与分支预测器的索引
− 以SPEC中的eqntott为例
14
分支指令的协同性
� 若该代码片段被反复执行多次
− d的值在2与0之间交替
� 对于初始状态为0的1-bit predictor来说，其 行为会怎样？
15
一个简单的协同分支预测器
� 每一条分支指令对应一对1-bit predictors [p0, p1], 具体选择哪一个预测器进行预测和更新，则取决于 上一条分支指令的结果
�根据剖视（profile）结果，在编译时刻确定分支指令的预测 方向
− 需要ISA的支持：指令域中需要专门的分支指令方向预测域 − 预测失效率从5%到22%不等
5
: 最简单的动态分支预测 最简单的动态分支预测: 1-Bit Branch Prediction
� 分支历史表 Branch History Table (BHT)
eqntott
gcc
19
Two-level Predictors ） 两级分支预测器（ 两级分支预测器（Two-level Predictors）
�第一级：采用最近k条分支指令的历史结果为索引
− Global: 整个程序中，最近执行的k条分支指令 − Per-address: 当前要预测的分支指令的最近k次执行结果
Hazards ） 冒险ቤተ መጻሕፍቲ ባይዱ 冒险（Hazards Hazards）
�3种冒险
− 结构冒险 多条指令在同一时间访问同一硬件资源 − 数据冒险 由于相近的指令操作数之间存在的相关 (寄存器或存储器) 所引起 (RAW, WAW, WAR) − 控制冒险 一条分支指令的后续执行指令依赖于该分支指令的结果所 引起
所基于的假设: 同一分支指令，倾向于与上一次分支方向一样
6
1-Bit Branch Prediction
�例 1: 一个循环体的循环判断分支指令，先有9次结果为 跳转，最后一次为非跳转结束循环。那么对于该分 支指令，1-bit predictor的预测正确率是多少？ −答案: 80%. 因为存在这两次mispredictions：一 次是循环体首次执行，另一次是最后一次执行。 �例 2: 一个前向分支指令，多数时间为跳转，少数时间为 非跳转
� 推测式执行（speculative execution）: 由硬件推 测分支指令的结果来克服控制相关，分为3个部分
1. 方向预测（Direction prediction）: 预测分支指令的方 向是跳转（taken）还是顺序执行（not taken） 2. 目标地址预测（Target address prediction）: 在预测 分支方向为跳转的情况下，对跳转目标地址的推断 3. 推测式执行（Speculative execution）: 在控制相关解 决之前，允许流水线按推测的方向和目标地址获取和执 行指令；若发现推测错误，则及时终止错误推测的指令 取指和执行，并消除（undo）由于执行错误指令造成 的后果
n-bit
10
: 4K-entry 2-bit 表 vs 无限容量表 预测失效率 预测失效率: 2-bit表
11
一些重要结论
�分支预测正确率大致在82%到99%之间，也就是失效率大 致在1%至18% �整点程序(gcc, espresso, eqntott, li)的分支预测失效率明 显高于浮点程序(nasa7, matrix300, tomcatv, doduc, spice, fppp) �分支预测代价包括预测失效率和分支指令频率两个因素， 而在浮点程序中，这两者都要显著低于整点程序 �分支预测正确率随着分支预测表的容量增加而改善，但超 过4K项之后就很难再有提高
� 多达2m 种可能的结果 � 可保存在一个m-bit 的以为寄存器中
− 采用n-bit计数器记录该分支指令的 “局部”历史结果用于方向预测
�BHT的结构为一个二维数组，对其访问索引方法为
− 分支指令部分低位地址作为行选择 − m位全局历史结果作为列选择 − 每个BHT表项保存对应分支指令在某一具体全局历史结果下（执行至 该分支指令的一条具体路径）的前n次分支结果
27
BTB 分支目标缓冲器 分支目标缓冲器BTB
�分支目标缓冲器(Branch Target Buffer, BTB)
T T N T … N … N … N …
7
2-Bit Branch Prediction
� 1-bit branch predictor: 不稳定, 受“噪声”干扰 � 解决方案: 采用2-bit方案，当一个预测只有连错两次的情况下，才会发生改变 � 一个4态摩尔机
T Predict Taken
�在这种结构下，别名效应（Aliasing）仍是不可避免的，因 为BHT不足够大，只能使用程序计数器的部分地址信息对其 进行索引 �如果m = 0，就变成普通的BHT
17
(2, 2) Predictor
18
不同配置下的预测失效率
20% 18% 16%
18%
4096 Entries 2-bit BHT Unlimited Entries 2-bit BHT 1024 Entries (2,2) BHT
1 = branch was last taken 0 = branch was last not taken 1 0 prediction bit a31a30…a11…a2a1a0 branch instruction
1K-entry BHT 10-bit index 1 Instruction memory
13
Correlating Predictors ） 协同分支预测器（ 协同分支预测器（Correlating Predictors）
�到目前为止，基于历史的分支预测器都是根据被预测分支指 令自身的历史 �一个改进的办法:
− 一条分支指令的结果，常常与它之前的k条分支指令的结果存在较强 的相关性
� 也就是说，该分支指令的方向与行进至该分支指令的路径有关
T
1
N
1
T
0
T
1
T
1
N
1
T
0
N
1
T
0
T
1
T
11
T
11
N
10
T T N
1
T T T
0
T
11
N T T
0
T T N
1
N T T
0
T T N
1
11 11
10 11
10 11
T T
1
T N
1
T T
0
T N
1
Actual: State: 1-bit 2-bit Predicted: State: Predicted: