ThinkLab

1 分支预测器的实现挑战

现代计算机处于技术的前沿领域，其中宽指令获取 (Wide Instruction Fetch) 及其伴随的分支预测机制是提升性能的关键。分支预测器的实现面临着多项重大挑战：

1.1 预测延迟 (Latency of prediction)

大型混合预测器虽然预测结果准确，但其运行速度较慢，可能需要多个时钟周期才能完成一次预测。这就引出了时间层面的挑战 (Time-to-prediction)。

覆盖式预测器 (Overriding predictors)：为了缓解延迟，微架构通常会先使用一个快速且简单的预测器来生成初始预测。随后，使用更慢但更准确的预测器对初始结果进行确认或修正。如果两个预测器的结果产生分歧，则启动误预测恢复机制。
预测器流水线化 (Predictor pipelining)：分支历史寄存器 (BHR) 需要立即被更新，以便为下一次预测做好准备。采用多个预测器不仅仅是为了提升预测的准确率，也是为了能够更早地获得预测结果（尽管早期预测存在一定的误差，但可以在稍后阶段被修复）。

1.2 误预测恢复的延迟 (Latency of misprediction recovery)

当发生预测错误时，系统必须尽快消除错误推测 (Mis-speculation) 的影响。

状态清理：必须清理所有排在被误预测分支之后的较新指令。这包括清理重排序缓冲区 (ROB)、加载/存储队列 (LSQ)、映射表 (Map Table)、保留站 (RS) 以及获取与分发缓冲区 (Fetch/Dispatch buffers)。
重新启动正确路径：若原预测为不跳转 (Not Taken, NT)，则程序计数器 (PC) 将被重定向到计算出的分支目标地址；若原预测为跳转 (Taken, T)，则 PC 将被重定向到紧邻的下一个顺序地址。系统能够在遇到新的分支时再次进行推测。
误预测惩罚：分支误预测的惩罚是微架构设计的核心参数之一。能够多快重新启动执行直接影响到处理器的整体性能表现。

2 流水线深度与性能的权衡

关于流水线应该设计得多深，性能与开销之间存在着显著的关联。

性能评估：通过相对性能与分支未命中时的流水线深度 (Branch Miss Pipeline Depth) 曲线可以清晰展示两者关系。评估模型中测试了 50ps 到 90ps 等不同的开销情况。
开销分析：以 2GHz 的 Pentium 4 处理器为例，其周期时间为 500ps，其中一部分周期必然被用于处理时钟偏移 (Skew)、信号抖动 (Jitter)、锁存 (Latching) 以及其他流水线固定开销。
最佳深度：随着周期时间与上述开销比例的变化，流水线的最佳深度也会随之移动。
误预测的破坏性：流水线的平稳运行在每次发生分支误预测时都会遭到破坏。解决这一错误并从正确路径重新执行指令所需的时间，在极大程度上决定了处理器的整体性能以及该架构下的最佳流水线深度。

3 快速分支恢复机制 (Fast Branch Recovery)

为了应对高昂的误预测惩罚，微架构中引入了快速分支恢复机制。

3.1 分支栈 (Branch Stack) 与掩码寄存器

核心理念：在每个分支处，建立并复制所有用于状态恢复的必要信息。
分支栈的内容：分支栈中存储着恢复时需要的程序计数器 (Recovery PC)、ROB 与 LSQ 的尾指针、分支预测的修复信息 (BP repair) 以及空闲列表 (Free list)。
分支掩码寄存器 (b-mask reg)：用于追踪哪些分支栈条目正处于使用状态。
挂起分支追踪：保留站 (RS) 和功能单元 (FU) 流水线内部同样维护着分支掩码，用于指示所有尚未解析（挂起）的较早分支。系统会对所有指令进行追踪，以确定它们依赖于哪些尚未执行完毕的分支。

3.2 宏观微架构视图

在宏观的微架构视图中，包含了指令分发阶段 (Dispatch Stage)、保留站 (RS)、执行单元 (FU)、数据缓存 (D$)、物理寄存器文件 (Regfile)、重排序缓冲区 (ROB)、结构映射表 (Arch. Map)、空闲列表 (Free List) 以及加载/存储队列 (LSQ)。这些组件通过头/尾指针和分支相关的 T/T+ 状态紧密协同，支持指令的高效流转与回收。

3.3 分发阶段与误预测修复阶段的操作

分发阶段：如果分支栈已满，流水线必须暂停 (Stall)。若有空间，则分配一个栈条目并设置对应的 b-mask 位；系统会记录映射表、空闲列表、ROB 和 LSQ 尾指针的快照；保存 PC 及修复分支预测的细节；最后将 b-mask 复制到对应的 RS 条目中。
误预测修复：
- ROB 和 LSQ：直接从分支栈中恢复尾指针。
- 映射表和空闲列表：从早前保存的快照中恢复。
- RS 和 FU 流水线条目：如果检测到对应分支的 b-mask 位为 1，则将相关指令直接丢弃 (Squash)。
- 清理操作：清空该分支栈的条目及 b-mask 位。该设计机制完全支持处理复杂的嵌套式误预测。

3.4 掩码位的识别与循环处理追踪

系统通过记录各个分支特定对应的位掩码 (b-mask mask) 来识别当前的 b-mask 寄存器位。
预测正确时：如果某一分支被证实预测正确，系统会清除 b-mask 寄存器中的对应位（通过与 b-mask mask 进行异或操作），随后释放该分支栈条目，此时指令脱离了推测状态。
预测错误时：如果预测被证实为错误，所有携带该分支特定位标识的条目将被视作位于错误路径上并予以释放，随后系统恢复正确状态。
在带有内部比较和跳转的循环结构处理中，当遇到结构性冒险 (Structural hazard) 和错误预测时，如果在 8 个周期或 20 个周期内解析分支，系统均能通过掩码精准丢弃无效指令（例如所有携带 x1xx 掩码位的指令），并快速重定向至目标。

4 宽指令获取面临的挑战与解决方案

为了提升指令级并行度 (ILP)，处理器需要每周期获取更多指令。但仅仅增加缓存块的大小并不能解决根本问题。整数代码的平均基本块大小仅为 4 到 6 条指令，浮点代码也只有 6 到 10 条指令，这意味着其中频繁穿插着控制流改变。宽指令获取面临着三大主要挑战：多分支预测、多获取组并行处理以及指令的对齐与折叠。

4.1 获取顺序指令

同缓存块获取：如果需要获取的指令都位于同一个缓存块内，则无需多虑。这种情形更倾向于设计较大的缓存块大小（不受命中率的影响）。
跨缓存块获取：若指令跨越多个块（例如需要并行获取块 A 和块 A+1），则需要借助多体指令缓存 (Banked I$) 及组合网络。但这可能会增加延迟，微架构可能需要增加额外的流水线级数以避免降低处理器的整体时钟频率。
编译器辅助：编译器可以通过插入空指令 (noops) 将基本块与缓存行边界进行对齐，但代价是会显著降低指令缓存的有效容量并浪费获取带宽。

4.2 获取非顺序指令（多跳转分支处理）

核心问题：每个周期能够预测多少个分支？能否在单个周期内获取多个预判为跳转的指令目标？
基础策略的局限：最简单的方法是“每次预测 1 个分支”。如果预测为跳转，则简单丢弃分支后的同周期指令。这种方式严重降低了有效获取宽度与每周期指令执行数 (IPC)。
数据说明：假设代码中 20% 是分支指令，且其中 50% 会发生跳转，这意味着平均每 10 条指令就会遇到一次跳转。对于一个包含 10 条指令的循环主体，在具备 8 发射能力的处理器中，如果没有更智能的指令获取机制，其指令级并行度最高也只能被限制在 5 左右（公式运算参考：(8 + 2) / 2 = 5）。
编译器优化：可以通过循环展开 (Unroll loops) 来降低代码中跳转分支的出现频率，从而减轻硬件获取的压力。

5 多分支预测器设计

处理多个分支预测需要解决一系列复杂问题：连续预测带来的高延迟，以及后续预测不得不在陈旧或推测性的历史数据上进行。多层预测概率的连乘会使得整体准确率急剧下降（例如 0.95 × 0.95 × 0.95 = 0.85）。

多分支预测器架构：可以结合多个分支历史寄存器位 (从 bn 到 b0 BHR) 与模式历史表 (PHT) 进行设计。针对不同的可能路径（如预测序列为 NN, NT, TN, TT），系统必须明确在分支解析后如何对这些复杂的预测位进行准确更新。
多跳转并行处理问题：如果系统在一个周期内需要处理多个预测为跳转的分支，将会造成指令缓存需要被多次连续访问，从而引发长延迟。解决这一瓶颈的方案包括使用多端口指令缓存 (Multi-ported I-cache，但访问较慢)，或采用多体指令缓存 (Multi-banked I-cache) 来近似模拟多端口的并行读取效果。

6 指令对齐、折叠与跟踪缓存

6.1 对齐与折叠缓冲区

由于控制流的变化，获取组与缓存行之间常常存在不对齐的情况。微架构必须将大小可变的指令块打包塞入获取缓冲区中。通过引入折叠机制，系统可以从两个缓存块中读取内容并进行旋转，跳过那些已被预判为跳转的分支进行折叠压缩，从而向执行后端提供连续、紧凑的指令流。

6.2 跟踪缓存 (Trace Cache)

传统的指令缓存受到了固定缓存行边界的严格限制，而跟踪缓存则以不同的维度运作：

工作原理：跟踪缓存会将动态指令（例如执行轨迹 ABC 和 DFG）在它们提交到填充缓冲区时进行追踪和存储，从而在物理排布上将发生跳转的分支逻辑直接“折叠”出去。
显著优势：直接存储执行追踪路径 (Traces) 能极大改善代码密度，并保证指令获取的高度连续性。
理念转变：在具备跟踪缓存的架构中，预测的目标不再是单个分支指令，而是去预测整条追踪路径 (Predict traces, not individual branches)。

7 微操作缓存与循环缓冲区

7.1 微操作缓存 (Micro-op Cache)

背景与作用：微操作缓存最初被发明是为了节省解码复杂 x86 变长指令所需的时间和功耗。由于其优秀的特性，这一理念随后也被 RISC 处理器广泛采用。
映射机制：它将指令的基本块直接翻译并映射为对应的微操作序列 (uops)。
缓存特性：微操作缓存的每一行能够存储的微操作有严格的最大数量限制；行的部分空间可能会空置；此外，并非所有基本块的翻译结果都会被缓存。
三种运行模式：
- 过滤模式 (Filter mode)：判定当前的指令块是否应当被翻译。
- 构建模式 (Build mode)：执行具体的翻译过程。
- 获取模式 (Fetch mode)：代表翻译已就绪，可以直接从中提取微操作执行。

7.2 循环缓冲区 (Loop Buffer)

技术演进：这项技术源自于 AMD29K 架构上的分支目标缓存 (Branch Target Cache) 机制。
核心理念：它不再缓存目标地址本身，而是直接缓存目标处的前 4 条具体指令。
性能收益：这样能够有效避免在经历一次跳转分支之后，为了获取首个指令组而再去访问指令缓存。如果循环体的总指令数少于或等于 4 条，它在实际功能上就等同于一个完整的循环缓存 (Loop cache)。该缓冲区通常有足够的空间存放 32 到 64 个分支目标。在软件的控制下，这种设计在数字信号处理器 (DSP) 中也非常常见。