Branch Prediction & Multi-issue Processor

本文内容基于 2025 秋季《计算机体系结构》双语班课程讲述，如有差错，欢迎指正

Branch Prediction#

回忆一下解决Control Hazard的几种方法：

• Stall
• 把分支决策计算提前到ID阶段
• Delay Decision
• 分支预测Bp

分支预测的核心思想是：在不知道真实结果的情况下，猜测分支的去向，并提前执行后续指令

当分支预测出错时，需要把已经进入流水线的指令flush掉，并且保证这些指令不会修改寄存器和内存的状态（Mem和WB阶段），这在五级流水线上是很显然的

静态分支预测#

Always Not Taken

每次都假设不会进行跳转，总会进行下一条指令（$PC=PC+4$）

硬件不需要进行修改。准确率$30\%-40\%$

Always Taken

每次都假设会进行跳转，跳转到目标地址。因为循环等结构的使用，这种方式的准确率可以达到$60\%-70\%$

需要额外的硬件来计算目标地址

动态分支预测#

通过记录一些历史信息来对未来的分支走向进行预测

分支预测需要知道两个信息：是否进行跳转以及跳转到哪里。对于不同的分支指令，预测的难度也不同

• 直接跳转，函数调用：总是跳转，跳转目标容易计算
• 条件跳转：需要根据条件来判断是否跳转，跳转目标容易计算
• 间接跳转，函数返回：总是跳转，跳转目标难以计算

1-bit Predictor

每个BHT表项记录1比特信息。$0$代表 Not Taken；$1$代表 Taken

PC经过Hash后索引到BHT表项，读取该表项的值进行预测。如果预测正确，则不做任何修改；如果预测错误，则将该表项的值取反

2-bit 饱和计数器

1-bit 预测器对于状态改变过于敏感，每次预测错误都会改变预测结果。 2-bit 饱和计数器引入了一些滞后性，即需要连续两次预测错误才会改变主要的预测方向

该机制包含四个状态：

• 11：Strongly Taken
• 10：Weakly Taken
• 01：Weakly Not Taken
• 00：Strongly Not Taken

一个简单的状态机描述：

这种机制使得预测器能够容忍循环退出时的那一次异常，从而在下次进入循环时依然保持正确的预测方向

Branch Target Buffer#

我们已经了解了如何预测分支是否会被采取，但还需要知道跳转的目标地址

Branch Target Buffer (BTB) 存储了分支指令的目标地址，一个经典的结构类似于一个全相联的Cache

• Tag：存储分支指令的 PC 值
• Target：存储预测的跳转目标地址

在 Fetch 阶段，将当前 PC 与 BTB 中的 Tag 进行匹配。 如果Hit，说明这是一条曾经执行过的分支指令，直接使用 BTB 中存储的 Target 地址去取下一条指令

Return Address Stack#

对于函数返回指令，同一个函数可能被多处调用，返回地址很难计算或预测

解决方法：利用返回地址栈 (RAS)

• Function Call时：将当前的 $PC+4$（返回地址）压入 RAS
• Function Return时：从 RAS 中弹出栈顶元素，作为预测的跳转地址

一般情况下8-16级的RAS就足够使用

Multi-Issue Processor#

Super-pipeline#

理想情况下流水线的加速比应当等于流水线的级数。然而在实际应用中，由于各个阶段执行时间的不均衡（例如乘法或访存通常耗时较长），导致流水线无法达到理想的加速比

为了进一步提高性能，一种自然的思路是增加流水线的深度，将其划分为更多的级，这就是super-pipline

super-pipline将原本耗时较长的阶段拆分为更细、时间更均匀的小阶段。 这种设计带来的主要收益是时钟频率的大幅提升。由于每个阶段的逻辑深度变浅，信号传播所需的时间变短，处理器可以运行在更高的频率下

与此同时，super-pipeline有很多缺点：

• 当流水线切分得过细时，流水线寄存器的开销在整个时钟周期中的占比会显著增加
• 更深的流水线会增加分支预测失败和数据依赖引起的惩罚

现代工业界通常将流水线深度控制在14 到 15 级左右（如 Intel Core 系列）

Super-scalar#

除了在时间维度上加深流水线，另一种提升性能的方法是在空间维度上增加并行度，即Multi-issue（多发射）

super-scalar是一种多发射处理器架构，在运行时动态地从指令流中找出可以并行执行的指令，并分配到不同的执行单元

为了支持多条指令同时执行，超标量处理器在硬件资源上必须进行扩充：

• Data Memory 和Instruction Memory需要支持同时取指和访存，一般会配备多个端口
• 由于多条指令可能同时读取或写入寄存器，Register File必须具备多个读端口和写端口
• ALU不再是单一的，需要复制多份以支持并行计算

相比于super-pipeline，super-scalar虽然时钟频率较低，但可以多条指令一起执行，可以达到很好的性能

如果一个 $N$ 路的超标量处理器能够总是跑满，其加速比应该是单发射处理器的 $N$ 倍。然而，其瓶颈在于指令间的依赖关系

如果所有的指令间都有依赖关系，超标量流水线会退化为单发射流水线。因此，超标量设计的核心在于：如何找出并解除依赖关系

超标量处理器执行指令的策略需要考虑以下两方面：

• 指令发射的顺序 (In Order/Out of Order)
• 指令完成（写回内存或寄存器）的顺序 (In Order/Out of Order)

在超标量执行时，必须保证结果和顺序执行是一致的

下面我们考虑一个例子，在这个例子的基础上看一下各种策略

设每次允许同时Issue 2条指令，ALU中有一个加法单元，一个乘法单元和一个浮点运算单元

ADDF R12,R13,R14 	# R12 ← R13 + R14 (float. pnt.) 
ADD R1,R8,R9 		# R1 ← R8 + R9 
MUL R4,R2,R3 		# R4 ← R2 * R3 
MUL R5,R6,R7 		# R5 ← R6 * R7 
ADD R10,R5,R7 	# R10 ← R5 + R7 
ADD R11,R2,R3 	# R11 ← R2 + R3

• 其中第一条指令是浮点数操作，需要两个周期完成
• I3和I4由于要使用相同的FU（都是乘法），因此不能同时执行
• I5要依赖于I4的结果(R5)
• I2,I5和I6要使用相同的FU（都是加法），不能同时执行

策略1：In Order Issue, In Order Complete

所有的指令按照顺序发射，结果也顺序写回

最终指令执行的顺序如下图

• I3必须在I1执行结束后执行

在这种严格按照顺序执行的策略下，并行性很依赖于程序写的顺序/编译的顺序（静态调度）

比如将I3和I6换一下位置，可以避免FU的冲突，程序可以缩短到6周期内完成

策略2：Out of Order Issue, Out of Order Complete

处理器会预先查看已解码的指令集，并以任意顺序发出任何指令，只要程序执行结果正确即可。 如果前一条指令被阻塞，后一条指令只要操作数准备就绪且有空闲的执行单元，就可以越过前者先执行

• Out of Order Issue不需要I3等待I1完成，可以直接发射
• 在Cycle 4，由于I5依赖I4的结果，I6可以先发射
• 完成顺序也类似，I2可以先于I1完成写回

Hazard in super-scalar#

在五级流水线中，我们主要关注写后读（RAW）问题。但在乱序执行的超标量处理器中，冲突的情况变得更加复杂，必须处理所有三种数据冲突：

• RAW (Read After Write)：真数据依赖，必须等待前序指令产生结果。
• WAR (Write After Read)：如果后序指令先执行并写入了寄存器，而前序指令读取的是旧值，乱序执行可能导致前序指令读到错误的新值。
• WAW (Write After Write)：如果两条指令写入同一个寄存器，乱序执行可能导致最终保留的是旧值而非新值。

为了解决 WAR 和 WAW 这类由名字重复而非实际数据流向引起的假冲突，现代处理器引入了寄存器重命名技术（后续讨论）

Control Hazard的影响在超标量中被放大。如果分支预测错误，已经乱序执行并计算出的大量结果都需要被丢弃

以及为了避免BP错误对结果正确性的影响，还有一些如Reorder buffer之类的技术，我们同样在后续讨论

VLIW#

VLIW(Very Long Instruction Word)是一种静态多发射处理器，由编译器在编译时做出决策（现在基本上不再使用）

VLIW 的基本思想改变了指令的封装形式。在传统的 RISC 架构中，一条指令通常占据 32 bits（4 bytes），仅包含一个操作。而在 VLIW 中，一条指令非常长，它由多个常规指令拼接而成。 其核心逻辑在于：编译器将若干个互相之间没有依赖关系、可以并行的操作打包进一条超长指令中。硬件在读取这一条超长指令后，会在同一个时钟周期内将包里的多个操作分发给不同的执行单元并行执行

VLIW的指令包允许存在空缺，比如五条指令，两两打包，最后一条指令单独成包

在执行层面，VLIW 处理器是严格的 In-Order 执行。处理器依次取出超长指令，按顺序执行

我们看一个简单的VLIW处理器架构：

• 有四种类型的指令，每种指令的周期数不同，比如图中4-Cycle Y-pipe，1-Cycle X-pipe
• 如果某条指令完毕后其他指令还未完毕，则该执行单元会一直等待

编译器会找出可以同时执行的这四种指令，把它们拼起来同时执行。硬件不会做任何的依赖检查以及调度工作

编译器做这些优化的一些策略：

• 尽可能避免出现control flow，因为硬件根本就没有BP之类的机制
• 优化一些常见的code path

Compile Technique1: Loop Unrolling

展开循环体，减少分支指令的数量

Compile Technique2: Predicated Execution

谓词执行：尝试把Control dependency转换为Data dependency

• 在指令前面加了谓词，指令序列变成了顺序执行。处理器会同时读取并（可能）执行这两条指令
• 在写回阶段，硬件会检查谓词寄存器：如果 $P1$ 为 True，则 $B=0$ 生效，$B=1$ 变为 NOOP。如果 $P1$ 为 False，则 $B=1$ 生效，$B=0$ 变为 NOOP

这种技术的优势在于消除了分支跳转，避免了流水线冲刷的惩罚。其代价是无论分支走向如何，CPU 都必须执行所有路径的代码（虽然错误路径的结果会被丢弃）。

因此，它主要适用于分支体较短的情况。如果分支内部代码很长，执行所有路径的代价将超过分支预测错误的代价，此时传统的 BP 可能更优

VLIW’s pros and cons：

• 硬件更简单，功耗更低，容易规模化
• 严重依赖编译器优化，且由于指令更长需要更多的memory bandwidth
• 代码兼容性差，不同的VLIW处理器可能有不同的指令包格式
• 锁步运行：一旦出现冲突，后续所有发射都将暂停，直到该冲突被解决
• 代码膨胀：需要noop填充以及loop unrolling增大代码体积

Static Scheduling#

编译器通过静态调度来重新排列指令顺序，以掩盖指令延迟并避免流水线停顿

编译器优化主要会影响 Instruction Count 和 CPI。编译器会将代码分解为 Control Flow Graph（CFG，控制流图），然后对代码进行优化分析。比如针对 Load-Use Hazard，编译器会尝试将与加载数据无关的指令插入到 Load 指令与其使用指令之间，从而填补延迟槽，避免 NOP 或 Stall

Register Renaming#

在编译器层面，也可以进行寄存器重命名以消除依赖。假设代码如下：

R1 = R2 + R3
R5 = R1 - R4
R1 = lw 0(R6)

指令 3 复用了 R1，导致它与指令 2 产生了 WAR。编译器可以通过分配新的寄存器（如R8）来消除这种依赖

R8 = R2 + R3
R5 = R8 - R4
R1 = lw 0(R6)

这样指令 3 就可以在指令 2 甚至指令 1 之前执行（假设没有其他数据依赖）

Loop Unrolling#

对于循环结构，编译器可以将循环体复制多次，形成一个更大的基本块

优点：

• 消除了多次循环控制指令（比较和跳转）
• 扩大了代码基本块的大小，编译器更容易对指令进行调度和优化

缺点：代码体积膨胀；对于迭代次数未知或非整数倍的循环处理较为复杂

Function Inlining#

将函数调用处的代码直接替换为函数体本身，消除了函数调用和返回的开销，减少了栈操作的延迟

容易导致代码膨胀，降低了代码的模块化和可调试性

Tree Height Reduction#

重组表达式，缩短关键路径的长度

经过结合律变换后，前两条指令可以进行并行

Global Scheduling#

之前我们考虑的是编译器如何通过基础块（Basic Block）内的优化来影响指令数。由于一个Basic Block内的指令数较少，能做的优化也很有限。为了提高指令的并行度，我们要跨越基本块的边界对指令进行调度

Global Scheduling 中一种相对直观且易于理解的技术称为基于迹的调度（Trace Scheduling）

Trace Scheduling 的目标是找出程序执行中最常走的路径（Common Case），并针对这条路径进行优化。编译器假设程序总是执行这条高频路径，可以将多个基础块拼接在一起，便于进行指令调度。如果运行时偏离了预测，CPU需要进入补救代码来处理异常情况

• 有$90\%$的概率if条件为真，将这部分变成一个更大的Basic Block
• 对于$10\%$的错误情况，需要执行补救代码fixit

Global Scheduling虽然能够带来加速，但是也要注意补救代码的开销。如果补救代码过于复杂，可能会抵消优化带来的收益

Software Pipelining#

软件流水线是另一种提升循环执行效率的技术，它是 Loop Unrolling的一种变体。

传统的循环展开是将循环体复制多次，使得多个迭代的指令在同一个基础块中顺序排列，它可能导致资源冲突。例如，展开 4 次循环可能会导致代码中连续出现 4 个 Load 指令，随后是 4 个 Add 指令。这会瞬间塞满处理器的 Load 单元或 ALU，导致硬件资源争抢，而其他功能单元（如 Store）却处于空闲状态

Software Pipelining的策略是将不同迭代的指令交错执行，即在当前循环迭代结束前启动下一轮迭代，使不同迭代重叠执行

例如在同一个时钟周期内，CPU 正在执行：

• 第 $k$ 次迭代的 Store 操作
• 第 $k+1$ 次迭代的 Add 操作
• 第 $k+2$ 次迭代的 Load 操作

FU之间都在同时工作，互不干扰