关联分支预测（Correlated branch prediction）习题求解求助

嘿，我来帮你把这道题的推导过程拆得明明白白——核心就是逐轮模拟关联预测器的「预测-执行-更新」全流程，咱们一步步来：

先明确前提条件 #

首先得把题目里的关键信息拆解清楚：

1. 指令序列与实际分支行为：
   • 分支指令只有两个：A: BEQZ R1, D 和 D: BEQZ R1, F
   • F: NOT R1, R1 会翻转R1的值，所以分支的实际决策是周期性循环的：
     • 当R1=0时：A分支跳转（Taken=1）、D分支跳转（Taken=1）
     • 当R1=1时：A分支不跳转（Not Taken=0）、D分支不跳转（Not Taken=0）
   • G: JUMP A 让整个流程循环往复
2. 关联预测器的核心规则：
   • 用**分支地址（A/D）**对应状态表的行，**全局分支历史移位寄存器（GBHR）**对应列
   • 每个表项是2位饱和计数器状态机（通用规则）：

     状态值	状态名称	预测结果	更新逻辑
     00	强不跳转（SN）	不跳转	实际不跳转保持，实际跳转变01
     01	弱不跳转（WN）	不跳转	实际不跳转变00，实际跳转变10
     10	弱跳转（WT）	跳转	实际不跳转变01，实际跳转变11
     11	强跳转（ST）	跳转	实际跳转保持，实际不跳转变10

   • GBHR更新：左移一位，右侧追加当前分支的实际决策位（1=Taken，0=Not Taken）

模拟推导（假设初始状态） #

默认这类习题的初始设定：

• GBHR初始为00（2位，对应两个分支的历史长度）
• 状态表所有表项初始为强不跳转（00）

第1轮循环（R1=0，分支均跳转） #

1. 执行A分支：
   • 分支地址A，GBHR=00 → 取状态表[A行, 00列]，状态00→预测不跳转
   • 实际决策：跳转（1）→ 预测错误
   • 更新状态：00→01（弱不跳转）
   • 更新GBHR：左移加1 → 01
2. 执行D分支：
   • 分支地址D，GBHR=01 → 取状态表[D行, 01列]，状态00→预测不跳转
   • 实际决策：跳转（1）→ 预测错误
   • 更新状态：00→01（弱不跳转）
   • 更新GBHR：左移加1 → 11
3. 执行F翻转R1为1，G跳回A

第2轮循环（R1=1，分支均不跳转） #

1. 执行A分支：
   • 分支地址A，GBHR=11 → 取状态表[A行, 11列]，状态00→预测不跳转
   • 实际决策：不跳转（0）→ 预测正确
   • 更新状态：保持00（强不跳转）
   • 更新GBHR：左移加0 → 10
2. 执行D分支：
   • 分支地址D，GBHR=10 → 取状态表[D行, 10列]，状态00→预测不跳转
   • 实际决策：不跳转（0）→ 预测正确
   • 更新状态：保持00（强不跳转）
   • 更新GBHR：左移加0 → 00
3. 执行F翻转R1为0，G跳回A

第3轮循环（R1=0，分支均跳转） #

1. 执行A分支：
   • 分支地址A，GBHR=00 → 取状态表[A行, 00列]，状态01→预测不跳转
   • 实际决策：跳转（1）→ 预测错误
   • 更新状态：01→10（弱跳转）
   • 更新GBHR：左移加1 → 01
2. 执行D分支：
   • 分支地址D，GBHR=01 → 取状态表[D行, 01列]，状态01→预测不跳转
   • 实际决策：跳转（1）→ 预测错误
   • 更新状态：01→10（弱跳转）
   • 更新GBHR：左移加1 → 11
3. 执行F翻转R1为1，G跳回A

第4轮循环（R1=1，分支均不跳转） #

和第2轮完全一致，预测全部正确，状态表[A行,11列]、[D行,10列]保持00，GBHR回到00

第5轮循环（R1=0，分支均跳转） #

1. 执行A分支：
   • 分支地址A，GBHR=00 → 取状态表[A行, 00列]，状态10→预测跳转
   • 实际决策：跳转（1）→ 预测正确
   • 更新状态：10→11（强跳转）
   • 更新GBHR：左移加1 → 01
2. 执行D分支：
   • 分支地址D，GBHR=01 → 取状态表[D行, 01列]，状态10→预测跳转
   • 实际决策：跳转（1）→ 预测正确
   • 更新状态：10→11（强跳转）
   • 更新GBHR：左移加1 → 11
3. 执行F翻转R1为1，G跳回A

后续循环（收敛到无错误） #

从第5轮之后，所有预测都会完全正确：

• 当R1=0时：A分支在GBHR=00时状态11（强跳转），预测正确；D分支在GBHR=01时状态11（强跳转），预测正确
• 当R1=1时：A分支在GBHR=11时状态00（强不跳转），预测正确；D分支在GBHR=10时状态00（强不跳转），预测正确

关键推导逻辑总结 #

你只要记住这三步，就能搞定所有这类习题：

1. 先理清分支的实际决策序列：这是一切的基础，必须先明确每个分支什么时候跳、什么时候不跳
2. 严格遵循预测器的工作流：找状态→出预测→对比实际→更新状态→更新GBHR，一步都不能少
3. 理解2位状态机的饱和更新规则：状态只会往实际决策的方向移动，不会溢出（比如00遇到Not Taken还是00）

为什么关联预测器比普通2位预测器错误率低？因为它能捕捉到分支之间的相关性——这道题里A和D的分支决策完全同步（都由R1决定），关联预测器用全局历史记录之前的分支行为，能更快匹配到当前分支的决策模式，收敛到正确预测。

内容的提问来源于stack exchange，提问作者Joe