Ch-3 指令级并行及其应用

1. 浮点流水线

1.1 浮点流水线架构

浮点运算比整型运算要消耗更多的时间，在流水线中有以下两种直观选择：

• 延长时钟周期时长，使得在一个时钟周期内足以完成浮点运算，但是整型运算速度更快，会浪费计算完成后等待时钟周期结束的时间；
• 在时钟周期时长不变的情况下，通过在浮点运算单元中 集成更多的计算逻辑 来增强其计算能力，使其能在一个时钟周期内完成，但是制造困难且成本高昂。

显然，两种选择都具有明显的缺点。为了便于制造，我们需要在速度要求上作出妥协，也就是说浮点运算不一定必须在一个时钟周期内完成，执行阶段可能超过一个时钟周期。遵循这一设计原则，浮点流水线与证书流水线相比有两处改动：

• 重复执行 EX 阶段：负责 EX 的组件可在每个时钟周期内被重复使用，例如加法运算会被拆成“指数对齐”、“尾数相加”、“规格化”、“舍入”等几个阶段，EX 阶段就变成了多级流水线，这样既提高了主频，又能让多条浮点指令重叠执行；
• 使用多个浮点功能单元：每个单元专门负责某种特定类型的运算，例如加法和除法。它不会简单地将所有类型的计算逻辑混入一个组件中，从而简化了制造过程。同时，由于不同的浮点运算的电路复杂度和延迟差很多，独立单元可以让不同的浮点指令并行执行。

由于现在一个功能单元 (FP) 的操作可能需要重复执行 EX 指令多次才能完成（尤其是浮点除法器等 内部没有做流水化的功能单元），因此无法允许后续指令在 EX 指令执行后的下一个时钟周期内进入 EX。这要求 EX 指令不能采用流水线处理，在上一条指令离开 EX 之前，任何其他使用该功能单元的指令 都不能发出。

1.2 延迟与发射间隔

• 延迟 (Latency)：指产生结果的指令和使用该结果的指令之间必须间隔的时钟周期数；
• 发射间隔/重复间隔 (Initiation/Repeat Interval)：连续发射两条同类型指令之间，必须间隔的时钟周期数，即同一个功能单元，多久能发下一条指令。

如果两条指令隔的周期数小于延迟，就会触发 RAW (Read-After-Write) 数据冒险，必须停顿流水线。本质上反应的是数据依赖的等待时间。

例如，某浮点乘法器的发射间隔为 \(1\) 说明乘法器是完全流水化的，每一排都能进一条新指令，而某浮点除法器的发射间隔为 \(35\) ，说明除法器几乎没有流水，一条除法指令要占 \(35\) 哥周期，期间下一条除法指令必须等它完全结束才能发射。因此发射间隔本质上反应的是功能单元的 吞吐能力，决定了同类型指令的峰值执行速度，解决的是 资源冲突 问题。

流水线延迟比执行流水线深度少 \(1\) ，流水线深度是指从 EX 阶段到产生结果之间的阶段数。即延迟表示要在流水线中 插入的 stall 数量，发射间隔则表示下一条指令和当前指令发射的 周期间隔数量。下表式浮点加法在发生 RAW 数据冒险时流水线内各阶段的变化。

【注】浮点指令中的指令助记符 .d 后缀表示双精度浮点运算，如 add.d、mul.d。

2. 冒险及其检测

2.1 结构冒险

• 浮点除法器 不是完全流水化的，这与 EX 阶段其他完全流水化的单元不同；
• 指令执行时间各不相同，可能导致同一周期内需要完成 多次寄存器写操作。

下表展示了浮点流水线中 乱序完成指令 在 WB 阶段抢寄存器写端口的结构冒险，同时也说明，虽然多条指令同时处于 MEM 阶段，但只要不是都真的访问内存，就不会发生冲突。

发射前互锁检测 (Interlock Detection)：在译码阶段跟踪写端口的使用情况，并在指令发出前对其进行暂停，以提前预防，其核心机制是维护一个 移位寄存器 (shift register)：

• 硬件组件：一个固定长度的移位寄存器，长度由流水线中最长指令延迟决定；
• 时序逻辑：每一个时钟周期寄存器内容整体向右移动一位，相当于倒计时；
• 记录操作：当一条指令在 ID 阶段准备发射时，根据其预估的写回延迟，在寄存器对应的位置标记为 \(1\) ，例如浮点乘法指令在 EX 阶段需要 \(7\) 个周期，就将第 \(7\) 位置 \(1\)；
• 冲突检测：当新指令进入 ID 阶段，硬件检查移位寄存器对应的位置是否已经被置 \(1\) ，如果有，说明此时发射指令会与之前的指令写回冲突，当前指令就会 stall 直至冲突消除。

发射前互锁检测 (Interlock Detection) 具有以下优缺点：

• 优点：逻辑清晰，所有的冲突检测和停顿控制都集中在 ID 阶段完成，指令一旦通过 ID 阶段发射，后续就不会因为写回冲突而被卡住，降低了流水线后续阶段的控制复杂度；
• 缺点：需要额外的移位寄存器和复杂的比较逻辑电路，是一种保守发射策略，即使后续有可能通过其他方式避开冲突也会停顿，导致一些不必要的空转，降低吞吐率。

导致空转的例子：假设有一条指令 A 发生了写回冲突而停顿，但后续的指令都没有写回冲突，如果先计算指令 A 并将写回延迟一个周期，后续的指令就可能可以提前运行加速。

事后补救互锁检测 (Reactive Stall Detection)：不提前预判冲突，允许指令正常向前运行，直到冲突发生时才在后端进行干预：

• 核心逻辑：仅在指令尝试进入 MEM 或 WB 阶段抢占资源时进行实时检测；
• 冲突处理：若多条指令在同一周期冲突，硬件决定 stall 其中一条，常用准则为 长延迟指令优先 (Longest Latency First) 即优先放行执行时间长的指令，尽早解除后续指令可能存在的 RAW 数据依赖。

事后补救互锁检测 (Reactive Stall Detection) 具有以下优缺点：

• 优点：硬件开销小，仅需检测当前周期的实时冲突，消除了预判导致的不必要空转；
• 缺点：控制逻辑复杂，stall 信号可能在多个阶段（MEM 和 WB）触发，增加了控制单元的处理复杂度，并可能触发 反向连锁停顿 (back-pressure)，执行单元被占用的指令阻塞，拖累整条流水线的进度。

2.2 WAW 冒险

不同功能单元指令执行时间差异太大，如果两条指令都要写一个寄存器，但它们的 写回顺序 乱了，就会导致寄存器里的值被错误覆盖。在下表中，如果 fld 指令提前一个时钟周期发出，它会比 fadd.d 指令提前一个时钟周期写入 f2 ，产生 WAW 冒险。

需要注意的是，这种冒险仅在 add.d 的结果被覆盖且没有任何指令曾使用该结果时才会发生，如果在 fadd.d 和 fld 之间有对 F2 的访问，则流水线需要因为 RAW 冒险而停顿。

指令发射 (issue)：是指指令通过 ID 阶段的依赖性检查，从 ID 阶段流水线寄存器进入执行单元的过程，在支持变长延迟的流水线中，发射阶段必须完成 WAW 冒险的检测与拦截。

延迟指令发射法 (delay issuing) 解决 WAW 冒险：

• 检测时机：在指令离开 ID 阶段进入功能单元之前，必须确认目标寄存器状态；
• 判定条件：检查当前目标寄存器是否存在于任何已发射但尚未完成的功能单元中；
• 停顿策略：若检测到目标寄存器冲突，硬件必须在 ID 阶段停顿，直到先前指令完成写回或清空相关状态（此处与前文的互锁优化不同）。

写控制置零法 (nullifying write control) 解决 WAW 冒险：

• 核心机制：当检测到 WAW 冒险时，硬件不再通过 Stall 停顿后续指令，而是允许其继续执行，同时废弃先前已发射指令的写回结果；
• 实现逻辑：在指令 \(I_2\) 的 ID 阶段，检测其目标寄存器是否与已在执行路径中的指令 \(I_1\) 冲突，如果存在冲突，硬件逻辑向 \(I_1\) 所在的功能单元发送干预信号，将 \(I_1\) 的寄存器写使能信号强制置为 \(0\) 进入无效状态；
• 执行结果：\(I_1\) 虽然继续完成计算但计算结果在 WB 阶段被禁止写入寄存器堆，\(I_2\) 正常执行并在 WB 阶段将最新值存入寄存器堆，最终寄存器堆保存的是程序最后一条的结果。

2.3 RAW 冒险

在浮点流水线中，因 RAW 数据依赖引发的停顿频率远高于整数流水线。根本原因在于：指令本身的计算时间过长，超出了前递 (Forwarding) 的覆盖极限：

• 整数流水线：整数计算通常在 EX 阶段 \(1\) 个时钟周期即可出结果。前递机制直接将刚算完的数据前递给下一条指令，填补了写回前的时间差，基本无需 stall；
• 浮点流水线：浮点运算本身的流水级极深，前递只能搬运已经算出来的结果无法预支还在计算中的数据，流水线只能强制进行长时间的 stall 等待计算结果。

【注】上表中 fsd 在 MEM 前要 stall 三次而非两次，是因为这套基准架构为了节省硬件成本和降低电路复杂度，并没有设计从浮点运算单元直接连向数据内存入口的旁路连线，所有浮点指令算完后只有传递到 MEM 之后才能通过前递网络送到后面的指令。由于 fadd.d 指令实际上并不需要使用 MEM 资源，所以此处并 不属于结构冒险。

2.4 ID 冒险检测

一、结构冒险检测：确保指令在执行和写回时，所需的物理硬件资源时空闲的。

• 功能部件空闲检查：
  • 主要针对非流水线化或执行周期极长的部件。在这个特定的流水线中，仅针对除法单元；
  • 如果当前 ID 阶段的指令是一条除法指令，硬件必须检查除法器是否处于被占用状态。如果是，则当前指令必须在 ID 阶段停顿等待；
• 写回端口预占检查：
  • 不同指令在流水线中驻留的周期数不同，它们可能在同一个时钟周期请求写入寄存器堆；
  • 硬件需要根据当前指令的预期延迟，提前检查当该指令到 WB 阶段时，寄存器的写端口是否已经被先前发射的指令“预定”。如果发生档期冲突，当前指令推迟发射。

二、RAW 数据冒险检测：确保当前指令读取源寄存器时，拿到的是最新计算出的正确值。

• 匹配逻辑：检查当前指令的源寄存器是否与流水线寄存器中已发射指令的目的寄存器相同；
• 时序与旁路条件： 停顿与否不仅取决于寄存器号是否匹配，还取决于产生数据的源指令何时结果可用，以及当前指令何时真正需要该数据。若数据在需要时不可用，则必须停顿；
• 实现的权衡：为了提高效率，理论上可以允许像除法这种长周期指令在最后几个周期与后续指令重叠执行。但在实际工程设计中，由于处理这种临近完成状态的逻辑过于复杂，设计者通常会放弃这种优化，转而采用更简单的发射测试逻辑以降低硬件复杂度。

三、WAW 数据冒险检测：防止后发射的短周期指令比先发射的长周期指令更早完成写回，导致目的寄存器最终保存了旧的错误数据。

• 简化预测法
  • 检查当前指令的目的寄存器，是否此前正在处理的任何指令的目的寄存器相同；
  • 若存在相同目标，直接停顿 ID 阶段的指令发射；
  • 连续对同一寄存器进行两次写入且中间无读取操作的指令序列在实际中极其罕见。采用这种目标一致就强制停顿的保守策略，对整体性能影响极小且简化了硬件设计。
• 精确预测法
  • 需要准确判断两条指令的写回顺序是否会发生实质性颠倒；
  • 当系统检测到当前 ID 阶段的新指令会比已经发射的旧指令更早完成时，才进行停顿；
  • 该方案需要硬件确切知道流水线各分支的绝对长度，并实时追踪已发射指令当前所处的精确位置，逻辑开销极高。

3. 异常检测与处理

3.1 精确异常

精准异常 (precise exception) 指当异常发生时，处理器的可见状态如寄存器等必须与程序顺序执行流中的某个特定点完全对齐，使得操作系统能够识别故障并能安全恢复：

• 状态快照 (State Snapshot)：异常发生时的指令流状态必须是程序逻辑顺序的一个清晰快照，不允许出现状态交叉；
• 指令执行准则 (Execution Rules)：
  • 向前兼容：所有在异常指令之前发射的指令必须已经全部执行完成并写回状态；
  • 向后隔离：所有在异常指令之后发射的指令必须完全没有执行或没有写回任何可见状态；
• 异常定位 (Exception Localization)：CPU 必须能够准确识别出是哪一条指令导致了异常，并将程序计数器 PC 指向该指令地址，以便操作系统精确定位问题；
• 副作用限制 (Side Effect Control)：未完成指令的副作用必须被严格限制，禁止修改寄存器或内存等用户可见状态，防止程序逻辑因状态泄露而产生混乱。

精确异常 带来的 优缺点：

• 优点：为操作系统提供了一致的编程模型，异常处理程序可以修复问题后从断点直接恢复执行，不会破坏程序逻辑，并保证了调试和错误恢复的可预测性；
• 缺点：在乱序执行流水线中，为了维持精确性，硬件需要引入重排序缓冲区 (ROB) 等复杂机制暂存结果。又是必须牺牲吞吐量，强制某些指令按序写回。

精确异常 在浮点流水线中面临的挑战在于指令的 乱序完成：

• 延迟差异：整数指令、浮点加法通常执行快，而浮点乘法、除法执行慢。
• 状态污染：先发射的慢速指令还在执行中尚未触发异常，而后发射的快速指令已经写回并修改了寄存器状态；此时慢速指令突然触发异常，程序无法回退到异常指令之前的纯净快照。

3.2 异常处理

针对 乱序完成 导致的 异常状态污染，体系结构有四种处理方案：

1. 允许不精确异常 (Imprecise Exceptions)
   • 放弃硬件层面的精确状态保证。异常发生时直接冻结当前乱序的流水线状态。
   • 完全依赖操作系统进行复杂的推导与恢复。因无法满足现代虚拟内存和 IEEE 浮点标准对异常恢复的强制要求，已被现代通用微架构淘汰。
2. 结果缓冲与按序提交 (Buffer the results)
   • 允许指令乱序执行，但将写回结果截流至硬件缓冲区。仅当确认指令流中 所有前序指令均无异常完成 后，当前结果才按程序原顺序提交至主寄存器堆。
   • 是现代乱序处理器 重排序缓冲区 (ROB) 的设计基础。完美保证精确异常，但需要庞大的缓冲阵列与极复杂的旁路网络，硬件开销巨大。
3. 硬件追踪与软件级恢复 (Track operations and PCs)
   • 硬件不实施保守停顿或结果缓冲，仅维护一个追踪队列，记录当前运行指令的类型与 PC 值。异常时，硬件将追踪序列抛出，由操作系统的异常处理例程通过纯软件模拟来撤销或补齐状态。
   • 简化了底层硬件设计，但将恢复开销完全转移给软件导致异常处理周期极其漫长。
4. 基于异常确认的保守发射 (Conservative Issue Control)
   • 在发射阶段设立强约束：必须在确认所有已发射的前序指令 绝对不会 引发异常的前提下，才允许当前指令脱离译码阶段向后发射。
   • 以最小的硬件变更维持了精确异常。代价是不可避免地产生大量流水线气泡，严重牺牲了处理器的指令级并行度与吞吐率。

4. 案例：MIPS R4000

4.1 流水线结构

MIPS R4000 处理器采用的是 八级流水线：

4.2 访存延迟

在流水线中，Load 指令从内存读数据，再被后面的指令使用时，中间需要插入多少个 stall 周期，就是 访存延迟 (Load Delay)。在 MIPS R4000 中，数据在 DS 阶段就已经有效可以被用于前递操作了，因此在该流水线中的访存延迟为 \(2\) stall 。

4.3 分支延迟

在上述 MIPS R4000 处理器架构中，分支指令的条件判定与目标地址计算会导致 \(3\) 个时钟周期的 分支延迟 (Branch Delay) ，为了隐藏这三个周期的流水线气泡，该架构采用了一种软硬协同的混合策略。

延迟槽技术 (Delay Slot)：编译器负责掩盖 \(3\) 个延迟周期的第 \(1\) 个周期：

• 标准延迟分支：编译器在分支指令之后的第一个位置调度一条与分支结果无关的有效指令，无论分支是否跳转，该延迟槽指令都会被无条件执行，这在逻辑上违背了程序的串行外观，但从物理执行面上成功隐藏了 1 个周期的延迟；
• 分支可能指令：仅当分支实际发生跳转时，延迟槽内的指令才会被执行；若分支未跳转，该指令在流水线中会被动态作废（Annulled）。此机制降低了编译器寻找绝对安全指令填充延迟槽的难度。

静态预测与流水线冲刷 (Static Prediction and Squashing)：硬件负责处理剩余的 2 个延迟周期，采用最基础的静态分支预测技术：

• 预测不跳转策略：硬件默认所有分支均不跳转。在分支结果计算出的前序周期内，流水线会继续推测性地提取分支指令之后的顺序指令；
• 预测失败的处理：在逻辑层面上，一旦检测到预测失败，控制逻辑会立即剥夺这两条指令的有效位，阻止它们进入后续的执行与访存阶段，这两条指令后续的执行周期常被标记为 stall。这里的 stall 并非指取指部件物理上的停机，而是表示这些指令已被逻辑冲刷，转化为不产生任何架构状态改变的流水线气泡。

4.4 浮点单元

MIPS R4000 的浮点单元不是一条固定的流水线，而是把运算过程拆成了 8 个独立的阶段，不同的浮点指令可以按自己的需要，以不同的顺序组合这些阶段，完成计算：

• 浮点加法：\(U\rightarrow S\rightarrow A\rightarrow R\)
• 浮点乘法：\(U\rightarrow M\rightarrow N\rightarrow A\rightarrow R\)
• 浮点乘法：\(U\rightarrow D\rightarrow\cdots\rightarrow A\rightarrow R\)

下表中，在进行浮点乘法操作后连续进行浮点加法操作。为了避免与浮点乘法操作的操作阶段发生冲突，浮点加法操作在特定位置上也要 stall。浮点指令的延迟差异，会导致即使没有数据依赖，也会因为 共享硬件资源而产生结构冒险 stall。后面的几张表也是同理。

5. 指令集并行

5.1 技术路线

基于编译器的静态并行 (Compiler-Based Static Parallelism) 将提取并行性的负担完全交由软件（编译器）承担。在程序编译阶段，通过静态代码分析，提前发现无依赖关系的指令并对其进行重排与打包调度。目前，该路线仅在特定领域环境，或具备大量规则循环、具有显著数据级并行性的高度结构化科学计算应用程序中才能发挥有效作用。

基于硬件的动态并行 (Hardware-Based Dynamic Parallelism) 依赖处理器内部的微架构控制逻辑，在程序运行时动态地检测指令间的数据/控制依赖，并利用硬件调度器实时提取并行指令进行乱序发射与执行。该路线是现代通用计算的主流。

5.2 依赖指令

并行指令 (parallel instructions)：两条指令可以在任意深度的流水线中同时执行，且不会引起任何停顿，前提是资源充足不存在结构冒险。

依赖指令 (dependent instructions)：两条指令存在依赖关系，由于数据或控制上的关联，指令无法完全同时执行，后一条指令必须等待前一条指令的结果产出后才能继续。虽然需要按序，但在流水线技术下，执行过程可以部分交叠，无需完全串行。

指令的依赖关系分为三类：数据依赖 (data dependence)、名字依赖 (name dependence)、控制依赖 (control dependence)。

指令 \(j\) 数据依赖 于指令 \(i\) 通常满足以下任一条件：

• 直接依赖：指令 \(i\) 产生的结果可能被指令 \(j\) 使用，即 \(i\rightarrow j\)；
• 传递依赖：指令 \(j\) 依赖于指令 \(k\) ，而指令 \(k\) 又依赖于指令 \(i\) ，即 \(i\rightarrow k\rightarrow j\Rightarrow i\rightarrow j\) 。

本质上是 \(\text{Write}\rightarrow\text{Read}\) ，即前指令写，后指令读， RAW 关系构成了程序底层逻辑顺序。

需要注意的是单条指令不存在数据依赖，例如 add x1,x1,x1 虽然它同时读写 x1，但是在体系结构定义中这不被视为指令间的依赖，因为不存在指令间的流水线冲突。

Loop: fld    f0, 0(x1)
	  fadd.d f4, f0, f2   # fadd.d 依赖于 fld 取出的 f0
	  fsd    f4, 0(x1)    # fsd 依赖于 fadd.d 计算的 f4
	  addi   x1, x1, -8
	  bne    x1, x2, Loop # bne 依赖于 addi 对 x1 的更新
	

当两条指令使用相同的寄存器或内存位置，但这两条指令之间并没有真实的数据流动时就发生了 名字依赖 (name dependence) ，名依赖可以分为以下两种类型：

• 反依赖 (antidependence)：后面的指令 \(j\) 写入了一个寄存器或内存位置，而这个位置正是前面的指令 \(i\) 需要读取的。必须保持原有的执行顺序，确保在 \(j\) 覆盖之前指令 \(i\) 能够读取到正确的值（本质上是 \(\text{Read}\rightarrow\text{Write}\)）；
• 输出依赖 (output dependence)：前面的指令 \(i\) 和后面的指令 \(j\) 都要写入同一个寄存器或内存位置。必须保持指令间的执行顺序，确保寄存器或内存位置最终保留的值是程序顺序中排在后面的指令 \(j\) 所写入的那个值（本质上是 \(\text{Write}\rightarrow\text{Write}\)）。

Loop: fld    f0, 0(x1)
	  fadd.d f0, f1, f2 # f0 的值输出依赖于 fld
	  fsd    f4, 0(x1)
	  addi   x1, x1, -8 # x1 的值反依赖于 fsd 的 f4
	  bne    x1, x2, Loop

反依赖不是真正的数据依赖，可以通过 寄存器重命名 (register renaming) 来解决反依赖。在上例中，编译器或硬件可以把 addi 里的 x1 临时重命名为一个新的寄存器如 x1_new ，这样 fsd 读的还是原来的 x1 ，addi 写的是 x1_new，两者就没有冲突了，两条指令就可以并行执行，完全消除了 stall 。

Loop: fld    f0, 0(x1)
	  fadd.d f0, f1, f2
	  fsd    f4, 0(x1)
	  addi   x1_new, x1, -8 # 将原来的 x1 更改为 x1_new
	  bne    x1_new, x2, Loop

当且仅当以下三个条件同时满足时，系统中就会存在 数据冒险：

• 存在依赖：指令之间存在数据依赖或名字依赖；
• 举例够近：这些依赖指令在执行时间或空间上够近，会同时处于流水线中；
• 执行重叠改变了访问顺序：重叠导致程序改变对相关操作的实际访问顺序。

控制依赖 (control dependence) 是由程序中的控制流指令引起的，它决定了某条指令 \(i\) 与分支指令之间的执行顺序，以确保指令 \(i\) 仅在程序逻辑要求其执行时才被执行。

if p1 S1; # S1 对 p1 存在控制依赖
if p2 S2; # S2 对 p2 存在控制依赖
 

在流水线处理器中，实际的平均每条指令的时钟周期数 (CPI) 等于理想 CPI 与各类冒险停顿造成的额外周期数之和，有公式：

5.3 属性约束

在优化流水线性能时，为了保证程序的正确性，必须遵守两大关键 属性约束 (property constraints)：异常行为和数据流。通常系统通过维护数据相关和控制相关保证它们不受破坏。

异常行为 (exception behavior) 指对指令执行顺序所做的任何改变，都不能改变程序中异常的触发方式（即原来会触发的异常依然要精准触发，原来不触发的绝对不能触发）。实际的高级流水线实现中经常被适当放宽为：指令执行的重排序绝对不能在程序中引发任何新的异常。

add x2, x3, x4
beq x2, x0, L1
ld  x1, 0(x2)
L1: ...

在上例中，如果 x2 为零，beq 会跳转到 L1 ，按照逻辑 ld 本不该执行，但此时 ld 已经执行了，如果 x2 是非法地址（如 0 ），就会出发内存访问异常，这种异常被称为 伪异常 (false exception) ，会破坏程序的精确异常模型。

数据流 (data flow) 指数据值在产生结果的指令与消耗该结果的指令之间的实际流动过程，无论底层指令如何重排序或并行执行，指令之间真实的数据依赖和传递关系必须得到严格维护。

   add x1, x2, x3
   beq x4, x0, L
   sub x1, x5, x6
L: ...
   or x7, x1, x8

在上例中，or 指令的 x1 值同时受数据依赖（add/sub）和控制依赖（beq）的影响，只处理数据依赖不足以保证程序正确执行，必须同时控制依赖分支路径上的指令，避免提前修改状态。

5.4 静态并行

静态并行 (static scheduling) 有以下两种技术：

• 流水线调度 (pipeline scheduling)：指令重排来避免流水线停顿；
• 循环展开 (loop unrolling)：将循环体复制多次以增加相对于分支和开销指令的指令数量。

for(int i=999;i>=0;i--)
	x[i]=x[i]+s;

# 8cc per loop
Loop: fld    f0, 0(x1)   
	  fadd.d f4, f0, f2  # 1cc latency
	  fsd    f4, 0(x1)   # 2cc latency
	  addi   x1, x1, -8
	  bne    x1, x2, Loop

# 7cc per loop after pipeline scheduling
Loop: fld    f0, 0(x1)   
	  addi   x1, x1, -8
	  fadd.d f4, f0, f2  
	  fsd    f4, 8(x1)  # 2cc latency
	  bne    x1, x2, Loop 

# 26cc per four ops after loop unrolling	  
Loop: fld    f0, 0(x1)
      fadd.d f4, f0, f2
      fsd    f4, 0(x1)   # 6cc per fld+fadd.d+fsd
      fld    f6, -8(x1)
      fadd.d f8, f6, f2
      fsd    f8, -8(x1)
      fld    f10, -16(x1) 
      fadd.d f12, f10, f2  
      fsd    f12, -16(x1)
      fld    f14, -24(x1)
      fadd.d f16, f14, f2
      fsd    f16, -24(x1)
      addi   x1, x1, -32
      bne    x1, x2, Loop
	  
# 14cc per four ops after pipeling scheduling and loop unrolling
Loop: fld    f0, 0(x1)
	  fld    f6, -8(x1)
	  fld    f10, -16(x1)
	  fld    f14, -24(x1)
	  fadd.d f4, f0, f2
	  fadd.d f8, f6, f2
	  fadd.d f12, f10, f2
	  fadd.d f16, f14, f2
	  fsd    f4, 0(x1)
	  fsd    f8, -8(x1)
	  fsd    f12, -16(x1)
	  fsd    f16, -24(x1)
	  addi   x1, x1, -32
	  bne    x1, x2, Loop

5.5 轨迹调度与超块

轨迹 (trace) 是程序执行中极有可能发生的一系列基本块序列，可以利用轨迹将原本分散在多个基本块中的操作组合在一起，通过重新排序和压缩，将它们放入更少更宽的指令槽中。

轨迹选择 (trace selection) 指在控制流图中找到那条最经常执行的路径 (frequent critical path) ，编译器利用静态分支预测或性能分析数据来确定概率。

轨迹压缩 (trace compaction) 指将选定路径上的指令压缩进更少更宽的指令字中，包含指令重排、并行化等手段。

在轨迹调度的基础上，通过 循环展开 可以进一步扩大调度范围。

• 轨迹出口 (trace exit)：执行流由于分支预测失败，跳离了预期的高频路径；
• 轨迹入口 (trace entrance)：执行流从外部跳转进入轨迹的中间位置；
• 局限性：轨迹调度允许多入多出。虽然它增加了并行度，但多个入口点会让编译器生成补偿代码变得极其复杂，难以评估成本。

为了解决轨迹调度中多入口带来的复杂性，引入了 超块 (superblock) 的概念。超块是一种特殊的扩展基本块，它具有唯一入口点，但允许有多个出口点：

• 它是一条长长的、顺序的指令序列；
• 可以从头进入，但在执行过程中可能会因为某个条件不满足而中途从不同的出口跳出；
• 没有外部跳转可以进入超块的中间。

for(int i=0;i<1000;i++)
{
	A[i]=A[i]+B[i];
	if(A[i]>0) // 90% true
		C[i]=C[i]*2;
}

# basic
Loop:
    fld    f0, 0(x1)       # A[i]
    fld    f1, 0(x2)       # B[i]
    fadd.d f0, f0, f1      # f0=A[i]+B[i]
    fsd    f0, 0(x1)
    flt.d  x3, f31, f0     # f31=0
    beqz   x3, Skip        
    fld    f2, 0(x4)       # C[i]
    fadd.d f2, f2, f10     # C[i]=C[i]+f10
    fsd    f2, 0(x4)
Skip:
    addi   x1, x1, 8      
    addi   x2, x2, 8
    addi   x4, x4, 8
    bne    x1, x5, Loop  

# trace scheduling
Loop:
    fld    f0, 0(x1)
    fld    f1, 0(x2)
    fld    f3, 0(x3)           # C[i]
    fadd.d f0, f0, f1
    flt.d  t0, f31, f0
    beqz   t0, TraceExit      
    fmul.d f3, f3, f2        
    fsd    f3, 0(x3)
    fsd    f0, 0(x1)

Next:
    addi   x1, x1, 8
    addi   x2, x2, 8
    addi   x3, x3, 8
    bne    x1, x4, Loop
    j      Done

TraceExit:                    
    fsd    f0, 0(x1)  
    j      Next

# superblock
Superblock_Loop:
    fld    f0, 0(x1)
    fld    f1, 0(x2)
    fld    f3, 0(x3)
    fld    f10, 8(x1)
    fld    f11, 8(x2)
    fld    f13, 8(x3)
    fadd.d f0, f0, f1
    fadd.d f10, f10, f11
    fmul.d f3, f3, f2
    fmul.d f13, f13, f2
    flt.d  t0, f31, f0
    flt.d  t1, f31, f10
    fsd    f0, 0(x1)
    fsd    f10, 8(x1)
    fsd    f3, 0(x3)
    fsd    f13, 8(x3)
    beqz   t0, SideExit1
    beqz   t1, SideExit2
    addi   x1, x1, 16
    addi   x2, x2, 16
    addi   x3, x3, 16
    blt    x1, x4, Superblock_Loop
    j      Done

SideExit1:
    fsd    f0, 0(x1)
    addi   x1, x1, 8
    addi   x2, x2, 8
    addi   x3, x3, 8
    j      ScalarLoop

SideExit2:
    fsd    f10, 8(x1)
    addi   x1, x1, 16
    addi   x2, x2, 16
    addi   x3, x3, 16
    j      ScalarLoop

ScalarLoop:
    bge    x1, x4, Done
    fld    f0, 0(x1)
    fld    f1, 0(x2)
    fadd.d f0, f0, f1
    fsd    f0, 0(x1)
    flt.d  t0, f31, f0
    beqz   t0, SkipScalar
    fld    f3, 0(x3)
    fmul.d f3, f3, f2
    fsd    f3, 0(x3)
SkipScalar:
    addi   x1, x1, 8
    addi   x2, x2, 8
    addi   x3, x3, 8
    j      ScalarLoop

Done:

【注】在一些激进的编译器在 SideExit 处理完特殊情况后，如果剩余元素还很多，会尝试重新跳回 Superblock 的头部以求进一步加速。

5.6 分支冒险

• 冻结或冲刷流水线：流水线会进入等待状态，直到确定下一条该执行哪条指令。在这种方案下，分支指令带来的性能损失是固定的；
• 预测不跳转：假设分支永远不会发生。流水线始终按顺序抓取下一条指令。如果分支真的没发生，流水线完全没有性能损失；如果分支最后确定要跳转，必须清空流水线中错误的指令，并从跳转的目标地址重新取指；
• 预测跳转：为了让这种预测有意义，硬件必须在流水线的早期（通常是 ID 阶段）就计算出目标地址。对于循环结构非常有效，因为循环底部的跳转指令通常是发生的；
• 延迟分支 (delayed branch)：改变分支指令生效的时间点。规定分支指令后面紧跟的那条指令无论分支最终是否跳转都必须执行，若能找到合适的指令，那么分支惩罚就变成了零，否则填入一条空指令会浪费一个时钟周期。

上图是 动态分支预测 的原理图，具体组成如下：

• 上方的小表是 Branch History Table, BHT 记录历史倾向，通常由 1~2 位状态机组成（强跳转、弱跳转、弱不跳转、强不跳转），输出预测信号 taken? 表示预测是否跳转；
• 下方的大框是 Branch Target Table, BTB 是一个特殊的 Cache，一行存储两个信息，即分支指令的地址和跳转的目标地址，输出信号 hit? 判定 PC 是否能够在 BTB 中找到对应的记录，并输出相应的目标地址。

只有当一条指令既是已知的跳转指令，并且根据历史经验这次也要跳转时，硬件才会预测跳转，否则预测不跳转，继续执行下一条指令。