相关分支预测
Correlated branch prediction
我有这个与相关预测因子相关的练习,其中说明如下:
A: BEQZ R1, D
…
D: BEQZ R1, F
…
F:不是 R1,R1
G: 跳 A
预测的工作原理如下
获取当前指令
如果是分支,判断预测器当前状态,预测分支:
a.row 由分支地址决定(在本例中为 A 或 D)
b.column由当前全局移位寄存器决定
c.use 单元格中的值以确定状态机的预测(当前状态保存在单元格中)
执行分支,确定实际决策
(采取: 1, 未采取: 0):
a.update 基于当前状态的单元格和
实际决定
b.update全局移位寄存器(左移并向右添加实际决定位)
转到步骤 1
这就是解决方案
Solved exercise
我理解这个方案并且知道 2 位预测器意味着更少的错误,但我无法解决这个问题,而且我很难找到解决方案,任何帮助将不胜感激。
这是 Agner Fog's microarchitecture paper(第 15 页)中简要描述的 具有全局历史的两级自适应预测器 table 的变体。
在此变体中,历史寄存器在所有分支之间共享,但是模式历史 table 对分支而言是本地的1.
记住最后 n(n = 2,在您的情况下)分支的结果(0 = 未采用,1 = 采用),从左到右排序按时间顺序,形成 n 位的值,与分支地址 2 一起使用,以索引 2 的 table位饱和计数器。
如果采用分支则每个计数器递增,否则递减(这是规范的实现,任何 4 态 FSA 都可以)。
每个计数器值的含义是:
00b (0) Strongly not taken
01b (1) Weakly not taken
10b (2) Weakly taken
11b (3) Strongly taken
饱和意味着比 3+1(再次采用强烈采用的分支)= 3 和 0-1(再次不采用强烈不采用的分支)= 0 而寄存器上的正常算术是模 2n。
在你的练习中,假设是:
- 模式历史 table 以 2D-table 形式给出,其中行对应于分支的完整地址,列对应于全局历史寄存器的值。
- 所有计数器都以状态 01b(弱未采用)开始。
- 全局历史寄存器在复位时为 00b。
R1
开头是0。
我们只看第一次迭代。
第一次迭代
指令是BEQZ R1, D
(显然是一个分支),它的地址是A
.
由于 R1
为 0,分支将被 采取 (朝向 D
)。
索引到具有 00b 全局历史和地址 A
的 table 给我们计数器值 01b(弱未采用)因此预测是 未采用 。
一旦 CPU 执行了分支并清除了错误预测的阶段,table 必须更新。
由于采用了分支,计数器从 01b 增加到 10b。
最后,全局历史从 00b 变为 01b,因为分支被采用(1 从右边移入)。
请注意,黄色突出显示的条目是执行相应指令时读取的条目,而绿色条目是先前预测更新的条目。
因此,要看到计数器值已递增,您必须查看下一行。
因为分支被采取,CPU在D
(BEQZ R1, F
),这和之前完全一样,只是全局历史寄存器的值为01b。
这条指令执行后CPU在F
,所以R1
变成111..11b(解法只是表示为1),上面两个分支是重新执行。
1这是一个简化,table几乎总是一个缓存。为可以找到分支的每个可能的内存地址创建一个条目是不切实际的。
2地址的一部分作为缓存中的索引,一旦选择了一个集合,在集合的每一路中再次与标签进行比较.
我有这个与相关预测因子相关的练习,其中说明如下:
A: BEQZ R1, D
…
D: BEQZ R1, F
…
F:不是 R1,R1
G: 跳 A
预测的工作原理如下
获取当前指令
如果是分支,判断预测器当前状态,预测分支:
a.row 由分支地址决定(在本例中为 A 或 D)
b.column由当前全局移位寄存器决定
c.use 单元格中的值以确定状态机的预测(当前状态保存在单元格中)执行分支,确定实际决策 (采取: 1, 未采取: 0):
a.update 基于当前状态的单元格和 实际决定
b.update全局移位寄存器(左移并向右添加实际决定位)转到步骤 1
这就是解决方案 Solved exercise
我理解这个方案并且知道 2 位预测器意味着更少的错误,但我无法解决这个问题,而且我很难找到解决方案,任何帮助将不胜感激。
这是 Agner Fog's microarchitecture paper(第 15 页)中简要描述的 具有全局历史的两级自适应预测器 table 的变体。
在此变体中,历史寄存器在所有分支之间共享,但是模式历史 table 对分支而言是本地的1.
记住最后 n(n = 2,在您的情况下)分支的结果(0 = 未采用,1 = 采用),从左到右排序按时间顺序,形成 n 位的值,与分支地址 2 一起使用,以索引 2 的 table位饱和计数器。
如果采用分支则每个计数器递增,否则递减(这是规范的实现,任何 4 态 FSA 都可以)。
每个计数器值的含义是:
00b (0) Strongly not taken
01b (1) Weakly not taken
10b (2) Weakly taken
11b (3) Strongly taken
饱和意味着比 3+1(再次采用强烈采用的分支)= 3 和 0-1(再次不采用强烈不采用的分支)= 0 而寄存器上的正常算术是模 2n。
在你的练习中,假设是:
- 模式历史 table 以 2D-table 形式给出,其中行对应于分支的完整地址,列对应于全局历史寄存器的值。
- 所有计数器都以状态 01b(弱未采用)开始。
- 全局历史寄存器在复位时为 00b。
R1
开头是0。
我们只看第一次迭代。
第一次迭代
指令是BEQZ R1, D
(显然是一个分支),它的地址是A
.
由于 R1
为 0,分支将被 采取 (朝向 D
)。
索引到具有 00b 全局历史和地址 A
的 table 给我们计数器值 01b(弱未采用)因此预测是 未采用 。
一旦 CPU 执行了分支并清除了错误预测的阶段,table 必须更新。
由于采用了分支,计数器从 01b 增加到 10b。
最后,全局历史从 00b 变为 01b,因为分支被采用(1 从右边移入)。
请注意,黄色突出显示的条目是执行相应指令时读取的条目,而绿色条目是先前预测更新的条目。
因此,要看到计数器值已递增,您必须查看下一行。
因为分支被采取,CPU在D
(BEQZ R1, F
),这和之前完全一样,只是全局历史寄存器的值为01b。
这条指令执行后CPU在F
,所以R1
变成111..11b(解法只是表示为1),上面两个分支是重新执行。
1这是一个简化,table几乎总是一个缓存。为可以找到分支的每个可能的内存地址创建一个条目是不切实际的。
2地址的一部分作为缓存中的索引,一旦选择了一个集合,在集合的每一路中再次与标签进行比较.