12.4. 指令调度

12.4.1. 指令流水线和流水线冲突

指令流水线把一条指令的执行过程拆分为若干阶段，使多条指令的不同阶段能够在同一周期并行推进，从而更充分地利用 CPU 核内功能部件，提高指令吞吐量。

以经典5级流水线为例，指令执行可划分为取指、读寄存器、执行、访问内存和写回5个阶段，如图10-1所示。

每个流水阶段通常占用固定时间，一般为一个处理器时钟周期。取指阶段根据程序计数器（PC）访问指令缓存和指令 TLB，将一条或多条指令取入指令存储器。读寄存器阶段读取源寄存器内容。执行阶段完成算术或逻辑运算。访问内存阶段负责读写数据缓存中的内存变量。写回阶段则把运算结果写回寄存器堆。

当第一条指令进入读寄存器阶段时，第二条指令可以同时进入取指阶段；当第二条指令读寄存器时，第三条指令又可以开始取指，后续指令依次进入流水线。因此，在同一个时钟周期内，多条指令可分别位于不同流水级。流水线技术能够提升指令吞吐量，并缩短程序整体执行时间。龙芯3号处理器的基本流水线包括 PC、取指、预译码、译码1、译码2、寄存器重命名、调度、发射、读寄存器、执行、写回和提交，共12级。

多数指令之间并非完全独立，常见相关性包括数据相关、控制相关和结构相关。若后一条指令需要使用前一条指令的结果，必须等待前一条指令完成，则称为数据相关。若当前指令是条件转移指令，后续指令地址取决于该转移结果，则称为控制相关。若两条指令竞争同一个功能部件，例如都需要使用 ALU 执行整数运算，或都需要使用 FPU 执行浮点运算，则称为结构相关。

这些相关性会引起流水线阻塞。以数据相关为例，假设第 N 条指令把结果写入 r1，第 N+1 条指令又要读取 r1 参与计算。在5级流水线中，第 N 条指令直到第五阶段才写回 r1，而第 N+1 条指令在第二阶段就要读取 r1。如果不采取措施，后一条指令可能读到旧值，导致结果错误。最直接的处理方法是等待，即让第 N+1 条指令在读寄存器阶段暂停3拍后再读取新值，但这种停顿会降低流水线效率。

流水线前递技术可以缓解数据相关问题。采用前递后，后续指令不必等前序指令把结果写回寄存器，就能提前获得计算结果。例如：

add.d r5, r4, r3
sub.d r6, r5, r3

这里第二条 sub.d 需要使用第一条 add.d 的结果，因此二者存在数据相关。使用前递后，sub.d 不必等待 add.d 完成写回；只要 r4 与 r3 的加法结果已经产生，就可以直接传递给 sub.d 的执行阶段。

不过，对于需要多拍完成的操作，前递的效果有限。前递通常只能减少1～2拍等待，而下面这类序列仍可能产生较长停顿：

load r1, addr
addi r1,r1,#2

由于 load 指令可能执行多拍，且耗时受缓存命中情况影响，前递很难完全消除等待。后文将介绍如何通过静态指令调度，把存在相关性的指令适当隔开，以降低流水线冲突。

控制相关和结构相关同样会造成停顿。对于控制相关，在条件转移指令完成之前，处理器无法确定下一条指令地址，因此不能可靠地把后续指令送入流水线，只能等待转移结果。现代处理器通常使用分支预测减少这类阻塞。结构相关的根源则是硬件资源有限。例如处理器只有一个乘法部件时，当前乘法指令尚未完成，后续乘法指令就只能等待。

12.4.2. 指令调度

指令调度是在不改变程序结果的前提下，重新安排指令顺序，以减少由指令相关引发的流水线阻塞，从而提升执行效率。调度方式可分为静态调度和动态调度。动态调度由硬件在运行时完成；静态调度则由汇编程序员或编译器在程序执行前完成指令重排。

进行静态调度前，需要了解处理器内部通常包含多个功能部件，不同指令会使用不同部件，执行拍数也不相同。例如，算术、逻辑和转移指令一般在定点 ALU 中执行，通常1拍完成；浮点运算在浮点 ALU 中执行，常需2～3拍；浮点乘除法至少需要5～6拍；访存指令由访存部件处理，耗时与 Cache 命中情况密切相关，通常也需要多拍。

假设存在数据相关的浮点加载指令与浮点运算指令之间需要间隔1拍，记为指令延迟为1；两条存在数据相关的浮点运算指令之间需要间隔2拍，记为指令延迟为2；其他存在数据相关的整型运算指令不产生额外延迟。若要实现数组中每个元素与一个定值相加，其指令序列及延迟信息如下：

i1  Loop:      fld.f     fa0,   0(r1)
| 1
i2             fadd.f  fa2,   fa0,   fa1
| 2
i3             fsd.f     fa2,   0(r1)
i4             addi.w    r1,     r1,     -4
i5             bnez      r1,    Loop          

这是调度前的指令序列，共5条指令（i1～i5）。i1 和 i2 之间的1表示两者存在数据依赖，且 i1 的延迟为1。i2 和 i3 之间也存在数据依赖，延迟为2。i4 与 i5 虽然存在数据依赖，但无额外延迟。按此顺序执行完5条指令需要8拍。通过调整指令顺序，可以利用空闲拍数减少等待，优化后如下：

i1  Loop:      fld.f     fa0,   0(r1)
| 1
i2             fadd.f  fa2,   fa0,   fa1
i4             addi.w  r1,     r1,     -4
i3             fsd.f   fa2,   4(r1)
i5             bnez    r1,    Loop          

优化后的序列交换了 i3 和 i4 的位置，并把 i3 的存储地址由 0(r1) 改为 4(r1)，以保持程序语义不变。此时执行完5条指令只需6拍，比调度前减少2拍。

总体来看，软件对控制相关的优化空间有限；但对于数据相关和结构相关，可以通过分析指令延迟和资源使用情况，合理安排指令顺序，提高程序执行效率。