第 9 章 执行

全书目录 · 本章学习辅助

书内第 275–320 页；PDF 第 287–332 页。原书疑点见校注。

• 9.1 概述
• 9.2 FU 的类型
• 9.2.1 ALU
• 9.2.2 AGU
• 9.2.3 BRU
• 9.2.4 其他 FU
• 9.3 旁路网络
• 9.3.1 简单设计的旁路网络
• 9.3.2 复杂设计的旁路网络
• 9.4 操作数的选择
• 9.5 Cluster
• 9.5.1 Cluster IQ
• 9.5.2 Cluster Bypass
• 9.6 存储器指令的加速
• 9.6.1 Memory Disambiguation
• 9.6.2 非阻塞 Cache
• 9.6.3 关键字优先
• 9.6.4 提前开始

9.1 概述

在超标量处理器的流水线中，执行 (Execute) 阶段负责指令的执行，在流水线的之前阶段做了那么多的事情，就是为了将指令送到这个阶段进行执行。在执行阶段，接收指令的源操作数，对其进行规定的操作，例如加减法、访问存储器、判断条件等，然后这个执行的结果会对处理器的状态进行更新，例如写到物理寄存器堆 (Physical Register File) 中，写到存储器中 (在超标量处理器中，对存储器的更新可能会延后 ),或者从指定的地址取指令等，同时这个执行结果可以作为其他指令的源操作数 ( 这就是旁路 ),在处理器中，负责执行的部件在本书中称为 Function Unit(FU)。当然，不同的处理器可能会对此有不同的称呼，例如 Intel 就将这些执行部件称为 Execute Unit(EU)。

一个处理器中包括的 FU 的类型取决于这个处理器所支持的指令集，在指令集中定义了各种需要的运算，概括来讲，一般的 RISC 指令集都包括下面的操作类型。

(1) 算术运算，例如加减法、乘除法、逻辑运算和移位运算等。

(2) 访问存储器的操作，例如从存储器中读取数据 ( 即 load 指令 ) 和写数据到存储器中 (即 store 指令)。

(3) 控制程序流的操作，包括分支 (branch)、跳转 (jump)、子程序调用 (CALL)、子程序返回 (Return) 等类型的指令，主要是对 PC 的控制。

(4) 特殊的指令，用来实现一些特殊功能的指令，例如对于支持软件处理 TLB 缺失的架构，需要有操作 TLB 的指令；对于存在协处理器的架构，由于无法在指令集中对协处理器中的寄存器进行编码，因此还需要访问协处理器的特殊指令；现代的处理器为了保证访问存储器指令的正确执行，还使用了存储器隔离 (memory barrier) 类型的指令等，这些指令的类型取决于具体的指令集。

不同类型的指令有着不同的复杂度，因此在 FU 中的执行时间也是不同的，这称做不同的 latency, 并且在现代的处理器当中，为了获得更大的并行度，一般都会同时使用几个 FU 进行并行的运算，例如有的 FU 进行算术运算、有的 FU 进行存储器的访问、有的 FU 控制程序流的方向、有的 FU 进行浮点运算等。每个 FU 都有不同的延迟时间，FU 的个数决定了每周期最大可以并行执行的指令个数，也就是前文中所说的 issue width。FU 在运算完成后，并不会使用它的结果马上对处理器的状态进行更新 (这个状态称为 Architecture State),例如它不会马上将结果写到逻辑寄存器堆 (ARF) 中，而是将结果写到临时的地方，例如写到物理寄存器堆 (PRF) 中，这些状态称为推测状态 (Speculative State),等到一条指令顺利地离开流水线的时候 ( 也就是退休的时候 ), 它才会真正地对处理器的状态进行更新。

不同的处理器，在流水线的执行阶段的设计也是大不相同的，不过有一条可以确定的是，不管是顺序执行 (in-order) 还是乱序执行 (out-of-order) 的处理器，都会使用多个 FU 来提高程序执行的并行度，哪怕是像 ARM11 这样的 “single issue” 的处理器，在流水线的执行阶段也是使用了多个 FU,那些真正的超标量处理器更是如此。一般来说，执行阶段在超标量处理器的流水线中，位置如图 9.1 所示。

图 9.1 执行阶段在超标量流水线中的位置

图 9.1 中的执行阶段包括了所有的 FU, 是处理器中可以使用的计算资源，其中，FPU (Floating-Point Unit) 用来对浮点数进行运算；ALU(Arithmetic Logic Unit) 用来对整数进行算术和逻辑运算；AGU(Address Generation Unit) 用来计算访问存储器的地址，当使用虚拟存储器时，AGU 计算的地址只是虚拟地址，还需要将它转换为物理地址；BRU(Branch Unit) 用来对控制程序流的指令计算目标地址。当然，这些都是很典型的 FU, 在现实的处理器中还有很多其他功能的 FU,用来处理各种千奇百怪的指令，这些内容不在本书讨论的范围之内。

执行阶段另一个重要的部分就是旁路网络 (bypassing network), 它负责将 FU 的运算结果马上送到需要它的地方，例如物理寄存器堆、所有 FU 的输入端，Store Buffer 中等。在现代的超标量处理器中，如果想要背靠背地执行相邻的相关指令，旁路网络是必需的，但是随着每周期可以并行执行的指令个数的增多，旁路网络变得越来越复杂，已经成为处理器中制约速度提升的一个关键部分。

假设先不考虑旁路网络 (这部分内容将在后文介绍 ),那么指令的操作数可以来自物理寄存器堆 ( 对应于非数据捕捉的结构 ),也可以来自于 payload RAM( 对应于数据捕捉的结构 ),那么此处仍需要考虑的一个问题是：每个 FU 和物理寄存器堆 (或者 payload RAM) 的各个读端口之间是怎样对应起来的呢？

其实，这是通过之前讲过的仲裁电路联系起来的，每个 FU 都和一个 1-of-M 的仲裁电路是一一对应的，每个仲裁电路如果选择了一条指令，这条指令就会读取物理寄存器堆 ( 或者 payload RAM),从而得到对应的操作数，然后就可以将这条指令送到对应的 FU 中执行了。由于每个仲裁电路和物理寄存器堆 ( 或者 payload RAM) 的读端口是一一对应的，因此每个 FU 和物理寄存器堆 (或者 payload RAM) 的读端口也是存在一一对应关系的，如图 9.2 所示。

图 9.2 FU 和物理寄存器堆的读端口有固定的对应关系

图 9.2 表示了处理器中使用四个 FU 的例子，每个 FU 都有一个 1-of-M 的仲裁电路，这个仲裁电路对应着物理寄存器堆 (PRF) 固定的读端口，这样就使设计得到了简化。由图 9.2 还可以看出，物理寄存器堆总共需要的读端口个数和 issue width 是直接相关的，如果对处理器追求更大的并行度，那么就需要更大的 issue width, 也就意味着物理寄存器堆需要更多的读端口 (payload RAM 由于和发射队列绑定在一起，使用分布式的发射队列可以减少对 payload RAM 读端口的需求 ),这样又会制约处理器速度的提高，因此现代的处理器为了解决这个矛盾，多采用 Cluster 结构，这部分内容将在本章进行介绍。

9.2 FU 的类型

9.2.1 ALU

这是一种最普通的 FU, 所有的处理器都会有这个部件，它负责对整数类型的数据进行计算，得到整数类型的结果，它一般被称做 ALU(Arithmetic and Logic Unit)。整数的加减、逻辑、移位运算，甚至是简单的乘除法、数据传输指令，例如 MOV 指令和数据交换 (byte-swap) 类型的指令、分支指令的目标地址的计算、访问存储器的地址计算等运算，都会在这个 FU 中完成，具体的运算类型取决于处理器微架构 (microarchitecture) 的设计。

加减法是最普通的算术运算了，但是不同的指令集直接影响着加减法的硬件实现，例如在 MIPS 指令集中，如果加减法发生了溢出 (overflow),那么就需要产生异常 (exception)，在异常处理程序中对这个溢出进行处理。而 ARM 指令集则直接定义了状态寄存器 (在 ARM 中称为 CPSR 寄存器 ), 当加减法指令发生溢出时，会在 CPSR 中将相应的位置 1,后续的指令可以直接使用 CPSR 寄存器，从而可以不用产生异常。在 CPSR 寄存器中还包括了运算结果的其他状态位，如表 9.1 表示。

表 9.1 CPSR 寄存器中的状态标志位

标志位	全称	产生的条件
N	Negative 标志位	等于 result[31]，其中 result 表示运算的结果，通常用于有符号数的运算
Z	Zero 标志位	如果运算结果为 0，则设为 1，否则为 0；通常用于比较两个数是否相等
C	Carry 标志位	通常用于无符号数的运算，其为 1 的条件是： (1) 加法的结果大于等于 $2^{32}$ (2) 减法的结果大于等于 0
V	Overflow 标志位	通常用于有符号数的运算，其为 1 的条件是： (1) 正＋正＝负 (2) 负＋负＝正 (3) 负－正＝正 (4) 正－负＝负

表 9.1 原表

相应的，在 ARM 指令集中定义了四种类型的算术操作。

(1) 不带进位的加法操作，可以表示为 $X+Y=X+Y+0$；

(2) 带进位的加法操作，可以表示为 $X+Y+C_{\mathrm{in}}$；

(3) 不带借位的减法操作，可以表示为 $X-Y=X+(\sim Y)+1$, 在处理器内部都是采用二进制补码的形式来表达数据的，两个正常数据相减，对应到补码中就是这种加法运算；

(4) 带借位的减法操作，可以表示为 $X-Y-1=X+(\sim Y)+1-1=X+(\sim Y)$。

上面的四种运算可以使用一个普通的加法器，再配合一些控制逻辑就可以实现了，在实际的处理器中，是没有减法器的，都是使用加法器来实现减法的功能，如图 9.3 所示。

图 9.3 可以实现加法和减法运算的 ALU

而且，细心的读者可能发现在表 9.1 中，当两个数做减法产生借位的时候 ( 减法结果小于 0), 借位标志位 C 竟然是 0, 这和平时的思维是正好相反的。之所以会发生这样的情况，是由于减法的硬件实现决定的，当借位确实存在时，带借位的减法实际上就是 “$X-Y-1=X+(\sim Y)+1-1=X+(\sim Y)$”，由图 9.3 可以看出，要实现 $X+(\sim Y)$ 的功能，借位 $C_{\mathrm{in}}$ 就需要为 0, 也就是上一次的减法运算如果有借位，需要将 $C_{\mathrm{in}}$ 置为 0, 这样下一次的减法运算才可以真正地将这个借位减掉，这也就是为什么真正产生借位的时候 ( 减法结果小于 0), 需要将 C 置为 0 的原因了。

一些处理器的 ALU 还实现了比较简单的乘除法功能，这些乘除法可能需要比较长的时间才可以完成，本书重点讨论的是超标量处理器的架构，对于如何实现乘除法不再进行介绍，读者可以自行参考其他的书籍。在 ALU 中加入乘除法操作后，会使 ALU 的执行时间是一个变化的值，例如执行普通的加减法指令需要一个周期，而执行乘除法需要 32 个周期，这样会给旁路 (bypass) 的功能带来一定的麻烦，在本章会进行详细的介绍。

一个比较典型的 ALU 可能是图 9.4 所示的样子。

图 9.4 一个典型的 ALU

在图 9.4 中，ALU 中的所有计算单元都会接收到同一条指令的操作数，因此它们都会进行运算，最后需要根据这条指令的类型来选择合适的结果，由于一条指令只需要一个计算单元进行计算，但是实际上所有的计算单元都进行了运算，这样会浪费一部分功耗，可以在每个计算单元之前都加入寄存器来锁存指令的操作数，根据指令的类型来选择性地更新这些操作数寄存器，这样可以节省一定的功耗。

在 MIPS 指令集和 ARM 指令集中，还有一条比较特殊的指令 CLZ (Counting Leading Zero),用来判断一个 32 位的寄存器中，从最高位算起，连续的 0 的个数，在某些场合的应用中，例如任务优先级的判断，使用这种指令可以快速地获得结果，否则就需要使用软件来实现这个功能，浪费了时间和功耗，从这个角度来看的话，CLZ 指令可以理解为一条硬件加速指令。当然，要实现这条指令，需要消耗一定的硬件资源，图 9.5 给出了这条指令的一种实现方法。

图 9.5 CLZ 指令的一种实现方法

需要注意的是，CLZ 指令对于数据是有要求的，对于一个 32 位的寄存器 RS 来说，要使用 CLZ 指令，它其中的数据就不能够全为 0, 这在 MIPS 指令集中进行了明确的定义 ^[14]。这需要在使用 CLZ 指令之前，使用一段小程序对数据进行判断，因此对于参与 CLZ 指令的寄存器 RS 来说，最多有 31 个 0, 所以需要 5 位的数据才可以表达。图 9.5 使用了 Bit[4:0] 来表示寄存器中从高位开始连续 0 的个数，首先需要判断寄存器 RS 的高 16 位 (RS[31:16]) 和低 16 位 (RS[15:0]) 是否全为 0, 如果高 16 位全是 0, 则表示 RS 中从高位开始连续 0 的个数最少有 16 个，则将 Bit[4] 置为 1, 此时需要将低 16 位送到后一级电路继续进行判断；而如果高 16 位中存在 1, 那么从高位开始连续 0 的个数肯定就小于 16 个了，此时需要将 Bit[4] 置为 0, 同时将高 16 位送到下一级电路继续进行判断，低 16 位此时就不需要考虑了。下一级电路就需要对一个 16 位的数据判断从高位开始连续 0 的个数，判断的过程和上一级电路是一样的，这样经过 5 级电路之后，就可以最终得到寄存器 RS 中从高位开始连续 0 的个数，并将其存储在 Bit[4:0] 中。在实际的指令集中，使用了一个通用的 32 位寄存器来记录这个结果，实际上只使用了这个寄存器的低 5 位，其余的 27 位并没有使用到。

在 MIPS 指令集中还有 CLO 指令 (Counting Leading One),用来判断一个 32 位的通用寄存器中从高位开始连续的 1 的个数，这个指令实际上可以使用 CLZ 指令的硬件来实现，只需要将一个寄存器的内容全部按位取反，然后再使用图 9.5 所示的电路就可以实现了，所以在硬件上实现 CLO, 是完全可以和 CLZ 共用一套硬件电路的，除非是要在每周期内并行地执行 CLZ 和 CLO 指令，此时才需要使用两套上述的硬件电路。

很多处理器在 ALU 中也实现了比较简单的乘法功能，用来支持乘法指令 (大部分处理器不支持除法指令 ),当然，为了追求比较高的并行度，高性能的处理器都会选择将乘法器单独使用一个 FU 来实现，并且在这个 FU 中支持乘累加的功能，这样可以快速地执行指令集中乘累加类型的指令，例如 MIPS 中的 MADD 指令。有些处理器出于功耗和成本的考虑，会将整数类型的乘法功能在浮点运算的 FU 中完成 ( 浮点运算必须有硬件乘法器 ),Intel 的 Atom 处理器就采用了这种方法 ^[37]。举例来说，如果要进行整数的乘法，首先需要将进行运算的操作数转换为浮点数，然后使用浮点运算 FU 中的乘法器进行乘法运算，最后将浮点的乘法结果转换为整数，这样就完成了两个整数的乘法运算，当然，这样肯定导致乘法指令需要的执行周期数 ( 也就是 latency) 变大，但是考虑到这种做法会节省面积 (也就相当于节省了功耗 ),而且很多应用并不会使用太多的乘除法指令，所以这种方法也是一种可以接受的折中方案。

9.2.2 AGU

顾名思义，AGU(Address Generate Unit) 用来计算地址，访问存储器类型的指令 (一般指 load/store 指令 ) 通常会在指令中携带它们想使用的存储器地址，AGU 负责对这些指令进行处理，计算出指令中所携带的地址。其实，在普通流水线的处理器中，都是在 ALU 中计算这个地址，但是在超标量处理器中，由于需要并行地执行指令，而且访问存储器类型指令的执行效率直接影响了处理器的性能，所以单独使用了一个 FU 来计算它的地址。AGU 的计算过程取决于指令集，对于 x86 这样的复杂指令集的处理器，其访问存储器指令的寻址模式很复杂，所以它的 AGU 也相对比较复杂，而对于本书重点介绍的 RISC 指令集，访问存储器所需要的寻址模式很简单，例如对于 MIPS 处理器来说，load/store 指令的地址等于 $\mathrm{Rs}+\mathrm{offset}$, 其中 Rs 是指令携带的源寄存器，offset 是指令携带的立即数，AGU 只需要将两者进行加法运算就可以得到指令所携带的地址了。

如果处理器支持虚拟存储器，那么经过 AGU 运算得到的地址就是虚拟地址，还需要经过 TLB 等部件转化为物理地址，只有物理地址才可以直接访问存储器 (在一般的处理器中， L2 Cache 以及更下层的存储器都是使用物理地址进行寻址的 ), 因此在支持虚拟存储器的处理器中，AGU 只是完成了地址转换的一小部分，它只是 “冰山的一角”, 真正的 “重头戏” 是从虚拟地址转化为物理地址，以及从物理地址得到数据的过程 ( 即访问 D-Cache)。这个过程直接决定了处理器的性能，尤其是对于 load/store 指令也采用乱序执行的处理器，需要一套复杂的硬件来检测各种违例情况，例如 store/load 违例或者 load/load 违例，并且还需要对它们进行修复，这些任务都增加了设计的复杂度，使访问存储器类型的指令成为了超标量处理器中最难以处理的指令，这部分内容涉及到 load/store 指令的相关性处理，在计算机的术语中称为 Memory Disambiguation,在本章会进行介绍。

9.2.3 BRU

BRU (Branch Unit) 负责处理程序控制流 (control flow) 类型的指令，如分支指令 (branch)、跳转指令 (jump)、子程序调用 (CALL) 和子程序返回 (Return) 等指令，这个 FU 负责将这些指令所携带的目标地址计算出来，并根据一定的条件来决定是否使用这些地址，同时在这个 FU 中还会对分支预测正确与否进行检查，一旦发现分支预测失败了，就需要启动相应的恢复机制。在 RISC 指令集中，程序控制流类型的指令是一种比较特殊的指令，因为它的目的寄存器是 PC,能够改变指令的执行顺序，对于 RISC 处理器的 PC 寄存器来说，它的来源有三种。

(1) 顺序执行时，$\mathrm{next_PC}=\mathrm{PC}+N$，$N$ 等于每次取指令的字长。

(2) 直接类型的跳转时 (Direct),$\mathrm{next_PC}=\mathrm{PC}+\mathrm{offset}$，offset 是指令所携带的立即数，它指定了相对于当前分支指令的 PC 值的偏移量，由于这个立即数不会随着程序的执行而改变，因此这种类型指令的目标地址是比较容易被预测的。

(3) 间接类型的跳转时 (Indirect),指令中直接指定一个通用寄存器 (例如 Rs) 的值作为 PC 值，$\mathrm{next_PC}=\mathrm{GPR[Rs]}$, 这种类型的指令也称做绝对跳转 (absolute) 类型的指令。由于随着程序的执行，通用寄存器的值会变化，所以这种类型指令的目标地址不容易被预测，如果可以使用直接类型的跳转指令实现同样的功能，就尽量不要使用这种间接类型的跳转指令。

如图 9.6 所示为 BRU 运算单元的实现原理图，这个 FU 其实主要完成了两部分工作，即计算分支指令的目标地址，并判断分支条件是否成立。

图 9.6 BRU 的原理图

一般来说，分支指令可以分为两种，一种是有条件的，例如 MIPS 中的 BEQ 指令，另一种是无条件的，例如 MIPS 中的 J 指令。有条件的分支指令一般根据一个条件来决定是否改变处理器中的 PC 值，例如 MIPS 指令集中，一般在分支指令中都会携带一个条件，分支指令在执行的时候需要对这个条件进行判断，例如 BEQ 指令对两个寄存器是否相等进行判断，只有相等时才会跳转到指令所指定的目标地址；BLTZ 指令对寄存器的内容是否小于 0 进行判断，只有小于 0 时才会跳转到目标地址。简而言之，MIPS 处理器使用了在分支指令执行的同时判断条件的方法，在 MIPS 指令集中，只有分支类型的指令才可以条件执行。

而 ARM 和 PowerPC 等处理器则使用了不同的方法，在每条指令的编码中都加入了条件码 (condition code),根据条件码的值来决定指令是否执行。因为每条指令都有这个条件码，所以每条指令其实都可以条件执行，而不仅限于分支类型的指令，这样相当于把程序中的控制相关性 (control dependence) 用数据相关性 (data dependence) 替代了，下面的例子如图 9.7 所示。

图 9.7 一段 C 程序可以编译为两种不同的汇编程序

C 代码：

if(a==0)
    x=b+c;
else
    x=b-c;

y=x;

Conditional branch（控制相关性）：

    BNE r1, #0, L1
    ADD r2, r3, r4
    B   L2
L1: SUB r2, r3, r4
L2: ADD r5, r2, #0

Conditional execution（数据相关性）：

CMP   r1, #0
ADDEQ r2, r3, r4
SUBNE r2, r3, r4
ADD   r5, r2, #0

对每条指令都使用条件执行的好处是可以降低分支指令使用的频率，而在超标量处理器中，只要使用分支指令，就有可能存在预测错误的风险，因此从这个角度来看，这种条件执行的实现方式可以获得更好的性能，但是它也是一把双刃剑，因为条件码占据了指令编码的一部分，导致指令中实际可以分配给通用寄存器的部分变少了。例如在 ARM 处理器中，条件码占据了四位的空间，导致 ARM 只能使用 $32-4=28$ 位的空间对指令进行真正的编码，所以 ARM 使用四位空间对通用寄存器进行编码，支持的通用寄存器个数也就是 16 个，而 MIPS 则是 32 个，更多的通用寄存器可以降低指令访问存储器的频率，也就增加了处理器的执行效率。而且，从上面的例子可以看出，使用条件执行会导致所有的指令都进入流水线中，当需要条件执行的指令很多时，流水线会存在大量无效的指令，这样反而使效率降低了，从这些角度来看，对每条指令都使用条件执行是降低了性能的。因此，孰优孰劣是很难有定论的，MIPS 处理器是最干净纯粹的 RISC 处理器，而 ARM 处理器是商业模式最成功的处理器，它们都是 RISC 阵营优秀的代表。

在超标量处理器中使用条件执行，会给寄存器重命名的过程带来额外的麻烦，仍以图 9.7 为例，按照正常流程对条件执行的代码进行重命名，会得到图 9.8 所示的结果。

图 9.8 对条件执行的指令采用寄存器重命名引起的问题

CMP   r1, #0
ADDEQ r2, r3, r4
SUBNE r2, r3, r4
ADD   r5, r2, #0

重命名后：

CMP   P5, #0
ADDEQ P6, P10, P11
SUBNE P7, P10, P11
ADD   P15, P7, #0

在流水线的寄存器重命名阶段，还不知道条件指令的条件是否成立，因此，如果按照现有的重命名流程，就会得到图 9.8 所示的结果，可以看出，如果 SUBNE 这条指令的条件不成立，那么图 9.8 中 ADD 指令会使用错误的寄存器 r2 的值：r2 应该对应物理寄存器 P6，而非 P7。这就是条件执行的指令给寄存器重命名的过程带来的额外麻烦。图 9.8 中，由于 ADDEQ 指令和 SUBNE 指令在寄存器重命名阶段无法得到需要的条件值，因此无法有选择地对寄存器进行重命名，导致发生了问题。

因此，在超标量处理器中如果实现条件执行，就需要解决上面的这个问题，当然最简单的解决方法就是停止流水线，一旦在流水线的寄存器重命名阶段遇到需要条件执行的指令，就暂停流水线，一直等到这条指令的条件被计算出来，才对它以及后面的指令进行重命名，这样做虽然不会发生错误，但是显然效率是不高的。当然，也可以采用预测的方法来解决这个问题，先假设所有的条件执行指令都会执行，使它们都经过寄存器重命名而进入后续的流水线阶段，当在后续的某个时间得到了对应的 CPSR 值，并且发现一个条件执行的指令不满足条件时，那么就出现了预测错误，需要对处理器的状态进行恢复，这需要将这条出错的条件执行指令以及在它后面进入到流水线的所有指令都从流水线中抹掉，并将这些指令对 RAT 的更改进行修复，然后重新将这些指令取到流水线中，例如对于图 9.8 中的指令来说，如果发现 SUBNE 指令的条件不成立，那么就将它和 ADD 指令都从流水线中抹掉，并对 RAT 进行状态恢复，此时寄存器 r2 对应的物理寄存器就是 P6 了，当 SUBNE 指令和 ADD 指令再次被取到流水线中时，由于此时的 CPSR 寄存器已经被计算出来，SUBNE 指令就会发现自身的条件是不成立的，也就不会通过寄存器重命名的阶段了，而 ADD 指令则会从 RAT 中读取到正确的映射关系。这样的处理方式虽然没有问题，但是考虑到条件执行指令自身的特点，显然会经常的预测错误，这样导致处理器的执行效率不会很高。Intel 在它的 x86 处理器中提出了一种解决方法 ^[38]：使用硬件插入额外的指令 ( 称为 select-uOP 指令 )，来选择正确的结果，这个过程如图 9.9 所示。

图 9.9 通过硬件插入 select-uOP 指令来解决问题

通过硬件自动插入有选择功能的 select-uOP 指令，可以根据条件对两个条件执行指令的结果进行选择，这种方法要求条件执行指令必须两两成对出现，否则就没有办法使用这种方法了，这对于编译器或者手动编写汇编程序的程序员都有一定的约束。由于 x86 处理器的架构定义和开发工具 (如编译器、汇编器等 ) 都掌握在 Intel 手中，所以它可以采用这种方法，但是如果要开发一款兼容的处理器，例如兼容 ARM 指令集的处理器，由于不能够保证条件执行指令成对地出现，那么上述的方法就不能够使用，需要采用其他的方法来解决这个问题。举例来说，可以采用一种比较直接的方法，对每个条件执行的指令，硬件都自动在后面都插入一条这样的 select-uOP 指令，如图 9.10 所示。

图 9.10 为每个条件执行的指令都插入 uOP

CMP   r1, #0
ADDEQ r2, r2, r4
SUBNE r2, r2, r4
ADD   r5, r2, #0

重命名后：

CMP   P5, #0
ADDEQ P6, P2, P11
uOP   P8, P6, P2
SUBNE P7, P8, P11
uOP   P9, P7, P8
ADD   P15, P9, #0

图 9.10 所示的做法，相当于将每个条件执行的指令都变成了两条指令，这样对于条件执行指令来说，就不再局限于两两成对的出现了，当然这也造成了执行效率在一定程度上有所降低。其实这种方法可以进行部分的改进，例如可以首先对条件执行的指令采用每两条插入一条 select-uOP 指令的方法，最后如果剩余一条指令，再对这条指令插入图 9.10 所示的 select-uOP 指令，这样可以在一定程度上降低 select-uOP 指令的个数，使执行效率有所提高。

条件执行的指令需要根据条件寄存器的值来决定是否执行，例如在 ARM 处理器中，每个条件执行的指令都需要读取条件寄存器 CPSR,将 CPSR 和指令自身所指定的条件进行对比进而得知条件是否成立，仍是以图 9.10 中的 ADDEQ 指令为例，如果 CPSR 寄存器中的Z 标志位是 1, 则表示 ADDEQ 指令的条件成立，否则就是不成立的。

对于每一条要修改 CPSR 寄存器的指令来说 (在 ARM 中这样的指令以 S 结尾 ),CPSR 寄存器都相当于这条指令的一个目的寄存器，这条指令后面所有的条件指令都会使用这个 CPSR 寄存器的值，直到遇到下一条修改 CPSR 寄存器的指令为止。从这个角度来看，其实 CPSR 寄存器完全就可以认为是一个普通的寄存器，在超标量处理器中，也需要对 CPSR 寄存器进行寄存器重命名的操作，后续的条件执行指令都会将 CPSR 寄存器作为一个源寄存器来看待。不过，由于 CPSR 寄存器的宽度小于普通的通用寄存器，所以一般会为 CPSR 寄存器的重命名过程单独使用一个物理寄存器堆，使用以前讲述的方法对 CPSR 寄存器进行重命名。这相当于在普通的指令上增加了一个目的寄存器 (对于以 S 结尾的指令 ) 和一个源寄存器 (对于条件执行指令 ),使寄存器重命名的复杂度有所上升，也导致了功耗的增大。

总体来看，在普通流水线的处理器中，每条指令都可以条件执行的这种做法，确实可以提高一些效率，但是在超标量处理器中，要处理这种情况需要增加额外的硬件，这种额外的付出是否值得是有待商榷的，不过这并不是影响一个指令集是否成功的关键因素，像 x86 指令集这种最难在超标量处理器中实现的指令集，Intel 都能将它做得风生水起，可见一个指令集的成功是取决于很多因素的，性能最好的未必就一定会成功，就像成功的人未必都是最聪明的人，只是他们找对了方法而已。

无条件的分支指令总是将跳转地址写到 PC 中，用来进行子程序调用的 CALL 指令和子程序返回的 Return 指令就是两个典型的例子。不同的指令集未必都会称做 CALL 和 Return 指令，但是功能一定是相似的，例如 MIPS 指令集中，使用 JAL 作为 CALL 指令，使用 JR $31 作为 Return 指令。

对于实现了分支预测功能的超标量处理器来说，BRU 功能单元还有一个更为重要的功能，那就是负责对分支预测是否正确进行检查。在流水线的取指令阶段 ( 或解码阶段 ) 会将所有预测跳转的分支指令按照程序中指定的顺序保存到一个缓存中，这个缓存可以称为分支缓存 (branch stack),由于每个 Cache line 可能含有多条分支指令，有些分支指令可能并没有被预测到，那么这些指令就按照预测不发生跳转 (not taken) 来进行处理，这样在分支缓存中存储了所有预测跳转的分支指令。当 BRU 功能单元中得到一条分支指令的结果时，就会在分支缓存中进行查找，以检查分支预测的正确性，这个检查会有四种情况。

(1) 一条分支指令在 BRU 功能单元中得到的结果是发生跳转，并且在分支缓存中找到了这条分支指令，跳转地址也是相同的，则说明分支预测正确；

(2) 一条分支指令在 BRU 功能单元中得到的结果是发生跳转，但是在分支缓存中没有找到这条分支指令，则说明分支预测失败；

(3) 一条分支指令在 BRU 功能单元中得到的结果是不发生跳转，并且在分支缓存中没有找到这条分支指令，则说明分支预测正确；

(4) 一条分支指令在 BRU 功能单元中得到的结果是发生跳转，但是在分支缓存中找到了这条分支指令，则说明分支预测失败。

如果发现分支指令预测失败，那么就需要启动处理器的状态恢复流程，这个流程已经在前文进行了介绍，此处不再赘述；如果发现分支指令预测正确，并且这条分支指令之前所有的分支指令都已经正确地执行，那么只需要释放这条分支指令所占据的资源就可以了，例如 Checkpoint 资源或者分支缓存中的空间等。

对于分支指令，还需要考虑的一个问题是分支指令需要乱序 (out-of-order) 执行吗？

在流水线中可以同时存在多条分支指令，这些分支指令都会被进行分支预测，然后统一地放到 BRU 功能单元对应的发射队列 (Issue Queue) 中，由于分支指令有如下两个主要的源操作数。

(1) 条件寄存器，分支指令根据条件寄存器的值来决定是否进行跳转，条件寄存器的值在分支指令进入到发射队列时可能还没有被计算出来。

(2) 源操作数，对于直接跳转 (PC-relative) 类型的分支指令，目标地址的计算来自于 $\mathrm{PC}+\mathrm{offset}$, 其中 offset 一般以立即数的形式存在于指令当中，而 PC 总是可知的；对于间接跳转 (absolute) 类型的分支指令，目标地址一般来自于通用寄存器，该寄存器的值在分支指令写人到发射队列时可能还没有被计算出来。

所以，进入到发射队列中的所有分支指令，有可能出现的情况是后进入到流水线中的分支指令的所有源操作数都已经准备好了，可以进入 BRU 功能单元进行计算，而先进入流水线中的分支指令的源操作数还没有准备好，这就为分支指令的乱序执行提供了可能性。从这个方面来说，对分支指令采用乱序执行是可以提高一些性能的，但是，后进入到流水线中的分支指令又严重依赖于前面分支指令的结果，如果前面的分支指令预测失败了，后续的分支指令都需要从流水线中被抹掉。所以，即使后面的分支指令的源操作数先于前面的分支指令而准备好了，并提前进入了 BRU 功能单元中执行，但是，一旦前面的分支指令发现自己的分支预测失败了，后续的这些分支指令在 BRU 中被执行的这些过程就是做了无用功，浪费了功耗。

综合看起来，如果将性能放在第一位，那么可以使用乱序的方式来执行分支指令，而如果要顾及功耗，那么顺序执行 (in-order) 分支指令是一个明智的选择，具体采用哪种方式，需要根据具体的需求进行折中选择。

9.2.4 其他 FU

在处理器中，还包括其他很多类型的 FU, 例如处理器如果支持浮点运算，那么就需要浮点运算的 FU; 很多处理器还支持多媒体扩展指令，例如单指令多数据 (SIMD) 类型的指令，则也需要相应的 FU 来处理它们，这些 FU 的架构和指令集是息息相关的，它不是本书关注的重点，当然这并不表示这些内容是不重要的，只是这些内容已经超出了本书讨论的范围了。

9.3 旁路网络

一条指令经过 FU 计算之后，就可以得到结果了，但是由于超标量处理器中的指令是乱序执行的，而且存在分支预测，所以这条指令的结果未必是正确的，此时称这个计算结果是推测状态的 (speculative),一条指令只有在顺利地离开流水线的时候 ( 即退休的时候 ), 才会被允许将它的结果对处理器进行更新，此时这条指令的状态就变为了正确状态 (在处理器中，这称为 Architecture State), 此时可能距离这个结果被计算出来已经很久了 (例如这条指令之前存在一条 D-Cache 缺失的 load 指令 ),后续的指令不可能等到这条指令顺利地离开流水线的时候才使用它的结果，这样虽然能够保证正确性，但是执行效率太低；如果等到指令将结果写到物理寄存器堆之后 (假设采用统一的 PRF 进行重命名 ),后续相关的指令才从物理寄存器堆中读取数据，这样会提高一些执行效率，但是仍然不是完美的解决方法。事实上，一条指令只有到了流水线的执行阶段才真正需要操作数，到了执行阶段的末尾就可以得到它的结果，因此只需要从 FU 的输出端到输入端之间架起一个通路，就可以将 FU 的结果送到所有 FU 的输入端。当然，在处理器内部的很多其他地方可能也需要这个结果，例如物理寄存器堆、payload RAM 等，因此需要将 FU 的结果也送到这些地方，这些通路是由连线和多路选择器组成的，通常被称为旁路网络 (bypassing network), 它是超标量处理器能够在如此深的流水线情况下，可以背靠背执行相邻的相关指令的关键技术。

其实，在所有的处理器中，为了获得指令背靠背的执行，旁路网络都是必需的，不管是普通的标量处理器还是超标量处理器都是如此，如图 9.11 所示为在一个普通的标量处理器的流水线中进行旁路 (bypass) 的示意图。

图 9.11 简单流水线中的旁路

指令 A: ADD r1, r2, r3
指令 B: ADD r5, r1, r4

在超标量处理器中，流水线会变得比较复杂，但是在前文已经讲过，只要指令在被仲裁电路选中的那个周期，对发射队列中相关的指令进行唤醒的操作，仍旧可以保证背靠背地执行相邻的相关指令，如图 9.12 所示。

图 9.12 将仲裁和唤醒放到同一个周期的超标量流水线

指令 A: ADD r1, r2, r3
指令 B: ADD r5, r1, r4

在更现实的超标量处理器中，对于一条指令来说，它的源操作数从物理寄存器堆中读出来后，还需要经过一段很长的布线，才能到达 FU 的输入端，而且 FU 的输入端还有大量的多路选择器，用来从不同的旁路网络 (bypassing network) 或者物理寄存器堆的输出中选择合适的操作数，因此为了降低对处理器的周期时间的影响，源操作数从物理寄存器堆读取出来后，还需要经过一个周期的时间，才能够到达 FU 的输入端，这个周期在流水线中称为 Source Drive 阶段。同理，FU 将一条指令的结果计算出来之后，还需要经过复杂的旁路网络才能到达所有 FU 的输入端 ( 或者 PRF 的输入端 ), 因此将这个阶段也单独做成流水线的一个阶段，称为 Result Drive 阶段，此时的流水线如图 9.13 所示。

图 9.13 一个更为复杂的流水线

指令 A: ADD r1, r2, r3
指令 B: ADD r5, r1, r4

由图 9.13 可知，只要保证在指令被仲裁电路选中的同一个周期，对发射队列中的相关指令进行唤醒的操作，则下一条指令在 FU 的输入端仍然可以从上一条指令的 Result Drive 阶段获得操作数，也能够实现背靠背的执行。当然，从图 9.13 还可以看出，如果从一个 FU 的输出端到另一个 FU 的输入端经过的时间很长，例如需要经过很长的布线，那么留给第二条指令的执行阶段 (Execute) 的时间就不多了，这样对处理器的周期时间就造成了负面的影响，现代的很多处理器采用了 Cluster 的方法来解决这个问题，在后文会进行介绍。

到现在可以知道，要使两条存在先写后读 (RAW) 相关性的相邻指令背靠背地执行，必须有两个条件，指令被仲裁电路选中的那个周期进行唤醒操作，还有就是旁路网络 (bypassing network)。在前文已经讲过，一个周期内进行仲裁和唤醒的操作会严重地制约处理器的周期时间，而现在又引入了旁路网络，需要将 FU 的结果送到每个可能需要的地方，在真实的处理器当中，旁路网络需要大量的布线和多路选择器，已经成为现代处理器当中的一个关键的部分，它影响了处理器的面积、功耗、关键路径和物理上的布局。但是尽管如此，现代的大多数处理器都实现了旁路网络，目的就是为了获得更高的指令并行度。在超标量处理器中，如果不能够背靠背地执行相邻的相关指令，那么理论上来讲，硬件可以找到其他不相关的指令来填充这些空隙，但是这些不相关的指令不一定总是存在的，因此即使在超标量处理器这种硬件调度指令的情况下，背靠背地执行相邻的相关指令仍然可以获得更好的性能。但是仍旧有少数例外的情况，例如 IBM 的 POWER4 ^[39] 和 POWER5 ^[40] 处理器，并没有实现旁路网络，这样可以使处理器获得很高的频率 (因为复杂度降低了 ),从而达到以快制胜的目的，在这样的处理器中，两条相邻的相关指令在执行的时候，它们之间会存在气泡 (bubble),但是这些气泡可以使用其他不相关的指令来代替，因为它们都是乱序执行的处理器，只要能够找到不相关的指令，就能够缓解这样的设计对性能的负面影响。

9.3.1 当处理器的 FU 的个数比较少，对频率要求也不高时，旁路网络 (bypassing network) 可以相对比较简单地实现，图 9.14 表示了一个处理器包括两个 FU 时，实现和不实现旁路网络的结构图。

图 9.14

图 9.14 所示的两幅图，其实对应着上一节讲过的简单流水线 (IF、ID、EX、MEM、WB)，图 9.14(a) 表示了不实现旁路网络的示意图，FU 的操作数直接来自于物理寄存器堆，FU 的结果也直接送到物理寄存器堆中，一个 FU 想使用另一个 FU 的计算结果只能通过物理寄存器获得；图 9.14(b) 表示了实现旁路网络的设计，每个 FU 的操作数可以有三个来源，即物理寄存器、自身 FU 的结果、其他 FU 的结果，因此FU 的每个操作数都需要一个 3:1 的多路选择器进行选择，同时，每个 FU 的输出除了送到物理寄存器堆之外，还需要通过一个总线送到所有FU 输入端的多路选择器中。

由图 9.14 可以看出，在只有两个 FU 的比较简单的处理器中加入旁路网络，已经增加了设计的复杂度，可以想象，当 FU 的个数比较多时，就会出现如图 9.15 所示的样子。

图 9.15 FU 的个数很多时的旁路网络

在图 9.15 中，很多 FU 都有多个功能，也就是有多个计算单元，例如一个 FU 可以计算加减法，也可以进行移位运算，对这样的 FU 需要使用一个多路选择器，从不同的计算单元中选择出合适的结果输送到旁路网络 (bypassing network) 上，这样的设计称为 bypass sharing。如果一个 FU 中，所有的计算单元需要的周期数 ( 也就是 latency) 都相等，例如图 9.15 中的第一个 FU 中，加减法运算和移位运算都可以在一个周期内完成，那么这样的设计当然没有问题。但是，当一个 FU 中，不同的计算单元需要的周期数不同时，例如图 9.15 中的第二个 FU 中，乘法操作需要 32 个周期，而逻辑操作需要 1 个周期，此时如果采用正常的执行，就可能出现同一个 FU 中两个计算单元的结果在同一个周期都被计算出来，都想通过这个 FU 对应的旁路网络进行传送，这样就产生了冲突，图 9.16 所示的流水线表示了这种情况。

图 9.16 旁路网络上的冲突

图 9.16 所示的这种冲突该如何进行处理？最简单的方法就是按照推测唤醒 (speculative wake-up) 一节所讲述的思路，先假设不会存在冲突，按照正常的流程进行唤醒 (wake-up) 和仲裁 (select) 操作，一条指令在到达 FU 中被执行之前，首先检查当前的 FU 是否可以被自己使用，例如这个 FU 在上个周期执行了一条 $\mathrm{latency}=3$ 的指令，那么本周期就不能够再接收 $\mathrm{latency}=2$ 的指令了。如果本周期到达 FU 的指令不幸正好是 $\mathrm{latency}=2$ 的指令，那么这条指令就需要放回到发射队列 (Issue Queue) 中，重新参与仲裁的过程，这样可以在基本不增加硬件消耗的情况下解决这个问题，但是会造成一些本可以执行的指令被白白地浪费了机会，例如上面的过程中，如果事先可以知道不能够执行 $\mathrm{latency}=2$ 的指令，那么仲裁电路就可以选择 latency 为其他值的指令，FU 此时可以马上执行这样的指令，如图 9.17 所示 ( 假设马上选择一条 $\mathrm{latency}=1$ 的指令 )。

图 9.17 两条不会产生旁路网络冲突的指令

因此，如果仲裁电路在进行选择的时候，那些 latency 为某些值的指令不参与仲裁的过程，那么就可以在不降低性能的情况下解决上述的问题。其实在前面设计发射队列的时候，每次当一条指令产生请求信号送到仲裁电路时，并没有考虑到一个情况，当前仲裁电路对应的 FU 是否可以使用？

在很多情况下，例如 FU 的设计不是流水线的，那么当 FU 在执行指令的时候，就不能够再接收新的指令；或者像上面所述，当一个 FU 执行 $\mathrm{latency}=2$ 的指令之后，就不能在下个周期执行 $\mathrm{latency}=1$ 的指令等，这些情况都是需要判断 FU 当前的资源是否可以使用，因此在本节需要将这个过程加入到发射队列的设计当中。

假设一个仲裁电路对应的 FU 可以计算三种类型的指令，所以在这个 FU 中就有三种计算单元，它们的 latency 分别是 1、2 和 3, 则：

(1) 当本周期执行 $\mathrm{latency}=3$ 的指令时，在下个周期不允许执行 $\mathrm{latency}=2$ 的指令，在下下个周期不允许执行 $\mathrm{latency}=1$ 的指令；

(2) 当本周期执行 $\mathrm{latency}=2$ 的指令时，在下个周期不允许执行 $\mathrm{latency}=1$ 的指令；

(3) 当本周期执行 $\mathrm{latency}=1$ 的指令时，没有限制。

由上面的规律可以看出，$\mathrm{latency}=1$ 或 $\mathrm{latency}=2$ 的指令在向仲裁电路发出申请的时候，需要考虑 FU 当前的资源是否可用，例如 FU 在当前周期不允许执行 $\mathrm{latency}=2$ 的指令时，发射队列中所有 $\mathrm{latency}=2$ 的指令向仲裁电路产生的请求信号都应该被置为无效。为了达到这个功能，对每一个仲裁电路都设置一个位宽为两位的控制寄存器，高位用来拦截所有 $\mathrm{latency}=2$ 的指令，低位用来拦截所有 $\mathrm{latency}=1$ 的指令，这个两位的控制寄存器每周期都会逻辑右移一位。相应的，在发射队列中的每个表项 (entry) 都增加两个信号，分别用来指示它其中的指令的 latency 值是 1 还是 2, 图 9.18 所示为具体的实现图。

图 9.18 利用一个两位的寄存器，对参与仲裁的指令进行选择

case ({latency_is_1, latency_is_2, latency_is_3})
    3'b100: req_out0 = request_0 & (~bit0);
    3'b010: req_out0 = request_0 & (~bit1);
    3'b001: req_out0 = request_0;
    default: req_out0 = 1'b0;
endcase

case ({latency_is_1, latency_is_2, latency_is_3})
    3'b100: req_outn = request_n & (~bit0);
    3'b010: req_outn = request_n & (~bit1);
    3'b001: req_outn = request_n;
    default: req_outn = 1'b0;
endcase

这个 FU 可以执行 latency 为 1、2 和 3 的三种指令，但是只需要对 latency 为 1 和 2 的两种指令向仲裁电路所产生的请求信号进行处理就可以了，下面根据各种情况进行说明。

(1) 本周期被仲裁电路选中的是 $\mathrm{latency}=3$ 的指令时，在下个周期，仲裁电路不允许选择 $\mathrm{latency}=2$ 的指令，在下下个周期，仲裁电路不允许选择 $\mathrm{latency}=1$ 的指令，如图 9.19 所示。

在下个周期，需要将仲裁电路对应的控制寄存器设为 2'b10, 它的高位为 1, 就表示此时不允许所有 $\mathrm{latency}=2$ 的指令参与仲裁的过程，因此所有 $\mathrm{latency}=2$ 指令产生的请求信号将会被拦截住，不会送到仲裁电路，而这个两位的控制寄存器在每周期都会进行逻辑右移一位，因此到了下下个周期的时候，这个控制寄存器的值就会变为 2'b01, 它的低位为 1, 就表示在本周期，不允许所有 $\mathrm{latency}=1$ 的指令参与仲裁的过程，因此所有 $\mathrm{latency}=1$ 的指令所产生的请求信号就会被拦截住，不会送到仲裁电路。

图 9.19 旁路网络会产生冲突的情况之一

从上面的过程可以知道为什么让仲裁电路对应的控制寄存器每周期都逻辑右移一位了，因为 $\mathrm{latency}=3$ 的指令会在接下来的两个周期之内连续拦截 $\mathrm{latency}=2$ 和 $\mathrm{latency}=1$ 的两种指令，通过将两位的控制寄存器逻辑右移，可以实现这个功能。

如果仲裁电路在当前周期选中了 $\mathrm{latency}=3$ 的指令，在下个周期仍然选中了 $\mathrm{latency}=3$ 的指令，那么这个两位的控制寄存器仍旧在下个周期要被写入 2'b10, 而此时在寄存器中已经存在 2'b01 这个值了，为了避免将原来的值覆盖，应该使要写入到控制寄存器的值和寄存器中原来的值进行或操作，然后将或操作之后的结果写入到控制寄存器中，图 9.20 表示了这个原理。

图 9.20 需要和原来的值进行或操作

(2) 本周期被仲裁电路选中的是 $\mathrm{latency}=2$ 的指令时，则在下个周期，不允许仲裁电路选择 $\mathrm{latency}=1$ 的指令，如图 9.21 所示。

图 9.21 旁路网络会产生冲突的情况之二

在下个周期，应该将仲裁电路对应的控制寄存器的值设为 2'b01, 它的最低位是 1, 就表示不允许所有 $\mathrm{latency}=1$ 的指令参与仲裁的过程，因此所有 $\mathrm{latency}=1$ 的指令所产生的请求信号在本周期就会被拦截住了，不会送到仲裁电路中。

(3) 当本周期被仲裁电路选中的是 $\mathrm{latency}=1$ 的指令时，对下个周期参与仲裁过程的指令没有任何的限制，因此只需要将两位的控制寄存器的值设为 2'b00 就可以了。

当 FU 中执行的所有类型指令中，latency 的最大值为 3 时，所有 $\mathrm{latency}=3$ 的指令总是可以执行的，不必进行拦截。

对于 FU 是由其他不同周期数的计算单元组成的情况，这种设计方法也是适用的，本质上来讲，这种方法相当于在指令参与仲裁电路选择的时候，同时要考虑执行该指令的 FU 是否在当前可以被使用，当然，从简化设计的考虑，最好使一个 FU 中执行的所有类型的指令都耗费同样的周期数，这可以避免引入上述的逻辑电路。

9.3.2 复杂设计的旁路网络

在前文讲述的比较复杂的流水线中，数据从物理寄存器被读取出来之后，需要经过一个周期 ( 即 Source Drive 阶段 ) 才可以到达 FU 的输入端，而 FU 输出的结果也需要经过一个周期 ( 即 Result Drive 阶段 ) 才能够到达需要的地方，这些变化导致了旁路网络 (bypassing network) 也需要进行相应的变化，为了更好地表述这个过程，流水线如图 9.22 所示。

图 9.22 在复杂的流水线中，旁路网络的各种情况

在上述的流水线中，只考虑指令 A 到其他指令的旁路网络。

(1) 指令 B 只能在流水线的 Execute 阶段，从指令 A 的 Result drive 阶段获得操作数。

(2) 指令 C 可以在流水线的 Source drive 阶段，从指令 A 的 Result drive 阶段获得操作数；或者指令 C 也可以在流水线的Execute 阶段，从指令 A 的 Write back 阶段获得操作数。

(3) 指令 D 可以在流水线的 Source drive 阶段，从指令 A 的 Write back 阶段获得操作数。

(4) 指令 E 在流水线的 RF Read 阶段读取物理寄存器堆 (PRF) 时，就可以得到指令 A 的结果了，因此它不需要从旁路网络中获得操作数，这里假设物理寄存器堆可以在前半个周期写入，后半个周期读取。

在复杂的流水线中加入旁路网络，会使设计的复杂度增大，对处理器的周期时间造成一定的负面影响，如图 9.23 所示为在复杂流水线中使用和不使用旁路网络的示意图。

图 9.23(a) 表示了没有旁路网络时的设计，和原来简单的设计相比，只是增加了寄存器，没有引起复杂度的上升；图 9.23(b) 表示了带有旁路网络的复杂流水的设计，从之前的流水线可以看出，在流水线的执行 (Execute) 阶段，其操作数除了来自于上一级流水线，还可以来自于两个 FU 计算的结果，它们来自于流水线的 Result Drive 阶段；而在流水线的 Source Drive 阶段，其操作数除了来自于上一级流水线，还可以来自于以前指令的结果，从之前的流水线示意图可以看出，这些结果分布在流水线的 Result Drive 阶段和 Write Back 阶段，要实现这样的旁路网络，需要复杂的布线资源和多路选择器的配合才可以完成，从图 9.23 可以明显地看出，在复杂的流水线中加入旁路网络，会严重地增大设计的复杂度。

图 9.23 复杂流水线中使用 /不使用旁路网络的示意图

图 9.24 以更直观的方式表示了在复杂流水线中使用旁路网络的过程。

一条指令从 FU 中将结果计算出来，需要经过流水线的两个阶段 Result Drive 和 Write Back, 才可以写到通用寄存器中，在这两个周期内，这条指令的结果都可以输出到旁路网络 (bypassing network) 上面；而一条指令从读完通用寄存器之后，直到真正到 FU 中执行之前的两个阶段 Source Drive 和Execute, 都可以接收旁路网络送过来的值，图 9.25 形象地表示了这个规律。

图 9.24 在复杂的流水线中使用旁路网络的示意图

图 9.25 可以使用旁路网络的流水段

当一条指令处于流水线的 Data Read 阶段，需要读取物理寄存器时，而产生它的操作数的指令此时正处于流水线的 Write Back 阶段时，这种情况不需要使用旁路网络，因为这条指令可以直接从物理寄存器中读取到所需要的操作数 ( 假设物理寄存器是前半个周期写，后半个周期读 )。而当一条指令读取物理寄存器时，产生其源操作数的指令还没有到流水线的 Write Back 阶段写寄存器，则这条指令就不能够通过寄存器得到它的源操作数了，只能通过旁路网络来获得这个操作数。

从之前的流水线示意图可以看出，当两条指令之间相隔的指令超过两条时，就不再需要通过旁路网络获得操作数了，而是可以直接通过寄存器获得操作数。当两条存在相关性的指令间隔的周期数不同时，旁路网络的使用情况也是不一样的，下面分别进行说明 ( 假设流水线的执行阶段只需要一个周期就可以得到结果 )。

(1) 当两条相关的指令处于相邻周期，也就是一条指令使用它前面的那个周期执行的指令的结果时，旁路网络会跨越相邻的两个周期，对流水线经过分析得到，这个旁路的路径只能发生在流水线的 Execute 和 Result Drive 两个阶段之间，其他所有紧挨着的两个周期之间都无法满足这个条件，如图 9.26 所示。

(2) 当两条相关指令之间相差了一个周期时，一条指令使用它前面的前面那个周期 ( 即前两个周期 ) 的指令的结果，因此这个旁路的路径可能发生在流水线的 Source Drive 和 Result Drive 两个阶段之间，也可以发生在Execute 和 Write Back 两个阶段之间，在这两种情况下发生旁路都可以满足要求，如图 9.27 所示。

图 9.26 相邻的两条相关指令之间的旁路情况

图 9.27 间隔一个周期的相关指令之间的旁路情况

(3) 当两条相关指令之间相隔了两个周期时，一条指令使用它前面的前面的前面那个周期 ( 即前三个周期 ) 的指令的结果，因此这个旁路的路径只可能发生在流水线的 Source Drive 和 Write Back 这两个阶段之间，只有在这两个阶段之间发生的旁路才可以满足要求，如图 9.28 所示。

图 9.28 间隔两个周期的相关指令之间的旁路情况

由上面的分析可以看出，流水线增加了两级，导致此时旁路网络的复杂度已经很高，除了需要数量比较多的多路选择器之外，还需要更多和更长的总线用来传输需要旁路的值，随着现代处理器的工艺尺寸越来越小，连线的延迟已经变得越来越大，所以这种复杂旁路网络的设计对于处理器性能和功耗的影响是很明显的。如果继续增大流水线的级数，会导致更复杂的旁路网络，制约了处理器速度的提高，并增大了功耗。现代的处理器都追求很快的速度，很高的并行度，也就是需要更多的 FU, 因此不可能在任意的 FU 之间都设置旁路的路径，这样会需要大量的布线资源，造成严重的连线延迟。

实际上，并不需要在所有的 FU 之间都设置旁路网络，例如，AGU 进行地址计算的时候，一般都会使用 ALU 的结果，但是反之，ALU 不会使用 AGU 计算的结果，因此在 ALU 和 AGU 之间的旁路网络就是单向的，只从 ALU 到 AGU 就可以了。同时，load/store 单元中，只有 load 指令的结果才会被其他指令所使用，store 指令则不会有这种需求，也就不需要进行旁路。浮点单元一般都有自己专用的旁路网络，整数指令不会直接使用浮点运算的结果，因此从浮点 FU 到整数 FU 的旁路网络也并不需要。这样的情况可以在一定程度上缓解旁路网络的压力，但是不能从本质上改变它的复杂度，随着流水线级数的增大，旁路网络无法继续跟随下去，这也是无法任意妄为地增加流水线级数的一个原因。

9.4 操作数的选择

在 9.3 节说过，在 FU 的输入端，需要从物理寄存器的输出或者所有的旁路网络 (bypassing network) 中进行选择 (其实还包括立即数 ),找到 FU 的真正需要的源操作数，这个任务是由多路选择器来完成的，既然有这么多的源头可供选择，就需要有对应的信号来控制这个多路选择器，那么这个控制信号来自于何处呢？

对于采用了寄存器重命名的处理器来说，一个物理寄存器在它的生命周期内，会有多种状态，它会首先从 FU 中被计算出来，然后被写到物理寄存器堆中 (PRF),如果不采用统一的 PRF 进行重命名，还需要在指令顺利的离开流水线 ( 也就是退休 ) 的时候将其写到指令集定义的 ARF 中。所有物理寄存器的这些信息可以保存在一个表格中，这个表格就是 ScoreBoard,在这个表格中，记录了一个物理寄存器在它的生命周期内经过的地方，这个表格可以如图 9.29 所示。

图 9.29 用来记录物理寄存器存放地点的 ScoreBoard

其实，在真实的处理器中，ScoreBoard 远比图 9.29 所示的复杂，当然，如果只是针对 FU 的操作数选择这一个功能来说，图 9.29 所示的内容就足够了，在这个表格中，对每个物理寄存器来说，记录了两个内容。

(1) FU#：这个物理寄存器会在哪个 FU 中被计算出来，当需要从旁路网络中取得这个物理寄存器的值时，需要知道它来自于哪个 FU, 这样可以控制多路选择器来选择对应的值，当一条指令被仲裁电路选中的时候，如果这条指令存在目的寄存器，就将这条指令在哪个 FU 中执行的这个信息写到上面的表格中。

(2) R: 表示这个物理寄存器的值已经从 FU 中计算出来，并且被写到了物理寄存器堆 (PRF) 中，后续的指令如果要使用这个物理寄存器，就可以直接从 PRF 中读取，由于只需要表示这个寄存器是否在 PRF 中，使用一位的信号就可以了，0 表示这个物理寄存器不在 PRF 中，需要从旁路网络中取得这个值，1 表示可以从 PRF 中读取这个值，很显然，如果这一位是 1, 那么就不需要关心 FU# 的值了。

在流水线中加入这个表格，会对流水线造成一定的负面影响，图 9.30 表示了在简单的流水线中加入这个表格的示意图。

图 9.30 在流水线中，ScoreBoard 的使用情况

指令 A: r1 = r2 + r3
指令 B: r4 = r1 + r2
指令 C: r6 = r1 + r5

在图 9.30 中，指令 A 在流水线的 Select 阶段，会将它在哪个 FU 中执行的信息写到这个表格 (ScoreBoard) 的状态位 FU# 中，在流水线的 Write Back 阶段，会将计算的结果写到物理寄存器堆 (PRF) 中，同时会对 ScoreBoard 也进行更新，将其中对应的状态位 R 置为 1; 后续的相关指令 B 在进入流水线的Execute 阶段时，会读取这个表格，就可以得到指令 A 在哪个 FU 中执行的这个信息了，也就可以从对应的旁路网络中选择合适的值。而对于指令 C 来说，它在流水线的 Execute 阶段读取 ScoreBoard 的时候，指令 A 已经将结果写到了 PRF 中，并且也更新了这个表格中的状态位 R, 此时指令 C 通过读取这个表格就可以知道，它的操作数应该来自于 PRF,这样就可以控制多路选择器来选择合适的值了，图 9.31 表示了这种实现方法。

图 9.31 将 ScoreBoard 的读取放在流水线的执行阶段

由于读取 ScoreBoard 的过程发生在流水线的 Execute 阶段，这会对处理器的周期时间造成一定的负面影响，当处理器的频率要求比较高时，这种做法可能就无法满足要求，如果为了提高频率，可以将读取 ScoreBoard 的过程放到流水线的 RF Read 阶段，使 ScoreBoard 和 PRF 同时进行读取，这样可以将 ScoreBoard 的读取时间进行隐藏，从这个表格中读取的值会随着流水线到达 Execute 阶段，此时就可以对多路选择器进行控制了，这种方法的示意图如图 9.32 所示。

图 9.32 将 ScoreBoard 的读取放到流水线的 RF Read 阶段

图 9.32 所示的这种方法虽然可以减少对处理器周期时间的影响，但是却引入了新的问题，如图 9.33 所示。

按照之前的讲述，指令 C 本来应该从 PRF 中就可以得到指令 A 的结果，但是从图 9.33 所示的流水线可以看出，指令 C 在流水线的 RF Read 阶段读取 ScoreBoard 的时候，指令 A 对 ScoreBoard 的更新还没有完成，这样指令 C 会错误地认为自己需要从旁路网络中取得操作数，也就会得到错误的控制信号送给多路选择器。要解决这个问题，就需要在读取和写入 ScoreBoard 的地方加入比较逻辑，当发现写入 ScoreBoard 所使用的物理寄存器的编号和当前正在读取 ScoreBoard 的物理寄存器的编号相同时，就需要将多路选择器的控制信号设置为从 PRF 中取得操作数，这样才可以避免上述错误的发生。随着流水线复杂度的提高，需要更复杂的控制逻辑来处理 ScoreBoard 加入之后引入的问题，这增加了设计的复杂度，而且，ScoreBoard 对于端口的需求是非常多的，假设处理器每周期可以并行执行 N 条指令，由于所有的源寄存器都需要在送到 FU 之前读取 ScoreBoard, 所以这个表格需要 $2N$ 个读端口。同时所有的目的寄存器在两个时间点都需要更新 ScoreBoard,一是在流水线的 Select 阶段，需要将指令在哪个 FU 执行的这个信息写到其中，这需要 $N$ 个写端口；二是在流水线的 Write Back 阶段，需要将这个目的寄存器已经被写到 PRF 的这个信息写到表格中，这也需要 $N$ 个写端口。因此 ScoreBoard 总共需要 $2N$ 个读端口和 $2N$ 个写端口，如此多的端口，很容易使这个表格的延迟过大，从而成为关键路径，当它无法满足处理器的周期时间的要求时，就需要使用多周期的 ScoreBoard, 但是这会在这个表格周围增加更多的比较电路，用来对当前写入和读取这个表格的寄存器进行比较，这使流水线的设计变得异常复杂，不是一件容易实现的事情。

图 9.33 写入和读取 ScoreBoard 会发生在同一个周期

指令 A: r1 = r2 + r3
指令 B: r4 = r1 + r2
指令 C: r6 = r1 + r5

有没有一种更好的方法呢？有时候，最简单直接的办法反而是好的方法，因为每个 FU 在将一条指令的计算结果进行广播，送到旁路网络 (bypassing network)、物理寄存器堆等部件的同时，也会将这条指令的目的寄存器编号进行广播，这个编号值会用来作为写入到物理寄存器堆的地址，此时就可以利用这个编号值，在每个 FU 输入端的多路选择器旁边加入比较电路，将输入到 FU 的源寄存器编号和 FU 进行广播的目的寄存器编号进行比较，将比较的结果作为多路选择器的控制信号，如图 9.34 所示。

在图 9.34 中，每个 FU 在将一条指令的计算结果 (Result Value) 进行广播的同时，也将这条指令的目的寄存器编号 (Result Tag) 一并跟随进行广播。每条指令在需要从旁路网络中选择操作数的两个周期，即流水线的 Source Drive 和 Execute 阶段，都将这条指令的源寄存器编号和 FU 送出的目的寄存器的编号进行比较，如果存在相等的情况，就说明此时要从对应的旁路网络中选择操作数，否则就只需要使用从物理寄存器堆 (PRF) 中读出的值就可以了。

采用图 9.34 所示的这种设计，在 FU 输入端的多路选择器旁边增加了很多比较器 ( 比较器一般用异或门实现 ), 相应地会增大一些面积和功耗，但是这样的设计结构简单，不需要任何控制逻辑，在一定程度上也能够减少设计的复杂度，进而减少面积和功耗，因此这种方法也不失为一个很好的折中方案。

随着流水线的加深，需要从旁路网络中接收数据的流水段，以及可以将数据送到旁路网络的流水段都会越来越多，这些需要从旁路网络中接收数据的流水段都要使用多路选择器来进行选择。相应的，随着可以产生旁路数据的流水段的增多，这些多路选择器的输入源也会随之增加，这样就在每个多路选择器旁边产生了大量的比较逻辑，这也是深流水线带来的负面影响。纵观当代的处理器，在 Intel 的 Pentium 4 处理器之后，已经都不再追求使用更深的流水线来提高处理器的性能了，因为这不是一个可持续发展的方法，现代的处理器提高频率的一大利器就是依靠工艺尺寸的缩小，同时处理器性能的提高主要依靠一些架构方面的改进，例如使用更准确的分支预测算法、使用更灵活的 Cache 结构或者使用一些更高级的预测算法，包括数值预测、load/store 相关性预测等。预测算法是超标量处理器提高性能的一个方向，通过预测，可以将很多东西提前知道，这种 “预知未来”的能力使得处理器的执行能够更有效率，但是一旦预测失败，所付出的代价也是很昂贵的，每个预测算法都需要对应的恢复机制，而且恢复到正常状态也是需要时间的，因此对预测算法的准确度有着很高的要求，否则它在处理器中就没有存在的意义了。

图 9.34 利用比较器来产生多路选择器的控制信号

9.5 Cluster

随着现代处理器的并行度和流水线级数的不断提高，上面所讲述的传统的超标量设计方法会导致硬件越来越复杂，例如需要更多端口的物理寄存器堆和存储器、更多的旁路网络 (bypassing network) 等，这些多端口的部件会导致处理器的面积和功耗显著地增大，也严重地制约了处理器频率的提高，需要其他的方法来解决这个问题，因此就产生了一种设计理念——Cluster 结构。

在前文中，其实已经使用了这种设计方式，例如在发射队列 (Issue Queue) 的设计中，通过将一个统一的发射队列分开为多个独立的发射队列，能够减少仲裁电路等部件的设计复杂度，并加快速度。在 FU 的设计中，将浮点 FU 和整数 FU 的旁路网络分开，可以大大减少旁路网络的复杂度等。Cluster 结构将上面的这种理念进行了扩展，应用到处理器内部的物理寄存器堆、发射队列、旁路网络等各种部件，这样就相当于在处理器中引入了 Cluster 结构。这种结构在使用时的粒度是可变的，有着多种多样的实现方式，下面对这种结构的实现思路进行逐步的讲解。

9.5.1 Cluster IQ

其实本节还包括对寄存器堆 (Register File) 采用 Cluster 结构，因为这部分内容和发射队列 (Issue Queue) 是紧密相关的，所以将它们放在一节进行讲述。

在前面已经讲过，随着处理器每周期可以并行执行的指令个数的增多，对于采用集中式的发射队列来说，要求更多的读写端口和更大的容量，导致面积和延迟都会增大，再加上发射队列本来就处于处理器内部的关键路径上，所以使用集中式的发射队列很难满足现代处理器对性能的要求。通过将它分成多个小的分布式发射队列，每个发射队列只对应一个 (或少数的几个 ) 仲裁电路和 FU,这样每个分布式的发射队列中只需要存储对应的 FU 中能够执行的指令，使复杂度得以降低，这种方法本质上就是将集中式的发射队列采用了 Cluster 结构，通过这种改变，带来的优点有如下几点。

(1) 可以减少每个分布式发射队列的端口个数；

(2) 每个分布式发射队列的仲裁电路只需要从少量的指令中进行选择，因此可以加快每个仲裁电路的速度；

(3) 由于分布式发射队列的容量比较小，它其中的指令被唤醒的速度也会比较快。

但是将发射队列采用 Cluster 结构的缺点也是有的，一个分布式发射队列中，被仲裁电路选中的指令对其他发射队列中的指令进行唤醒时，由于需要经过更长的走线，所以这部分的延迟会增大。例如图 9.35 中，当 Cluster0( 使用 Cluster 来称呼分布式发射队列 ) 中被仲裁电路选中的指令，对 Cluster3 中的指令进行唤醒时，就需要经过很长的走线，因此当处理器的频率要求比较高时，跨越不同的 Cluster 之间进行唤醒的这个过程可能需要增加一级流水线，这样当两条存在相关性的相邻指令恰巧属于两个不同的 Cluster 时，它们就不能背靠背地执行了，而是在流水线中引入了一个气泡 (bubble),这是将发射队列采用 Cluster 结构的一个负面影响。

图 9.35 对发射队列采用 Cluster 结构

图 9.35 表示了将一个使用数据捕捉 (data-capture) 结构的集中式发射队列分成四个分布式发射队列的设计，此时每个发射队列，也就是每个 Cluster, 都对应一个 FU 和 Payload RAM, 当没有使用 Cluster 结构时，集中式发射队列需要的容量和端口数都很多，严重制约了仲裁电路和唤醒电路的速度，而且 Payload RAM 的容量也需要很大，同时还需要支持多个读端口。采用 Cluster 结构之后，每个 FU 对应的 Payload RAM 的容量都可以很小，而且只需要支持一条指令的读端口就可以了，当然缺点就是当一个 Cluster 中被仲裁电路选中的指令对其他 Cluster 中的指令进行唤醒时，由于连线的延迟增大，可能需要增加一个周期来完成这个工作，于是就造成了两个存在相关性的相邻指令处于两个不同的 Cluster 时，不能背靠背地执行。

不过，这种 Cluster 结构所带来的缺点其实是可以通过一定的方法避免的，举例来说，有如图 9.36 所示的五条指令，它们都只需要一个周期就可以从 FU 中得到结果 (也就是 latency 都是 1),它们之间存在的相关性如图 9.36 所示。

图 9.36 指令 A～E之间存在的相关性

在前文讲述的集中式发射队列的设计中，假设指令的仲裁 (select) 和对其他指令的唤醒 (wake-up) 这两个过程可以在一个周期内完成，则指令 A 和 B 可以在第一个周期被仲裁电路选中，然后在第二个周期，指令 C 和 D 就可以继续被仲裁电路选中了，到了第三个周期，指令 E 也可以被仲裁电路选中，因此总共需要三个周期，就可以将这五条指令都送到 FU 中执行。

而在采用了分布式发射队列的这种 Cluster 结构之后，假设跨越 Cluster 之间的唤醒需要额外消耗一个周期，那么此时这五条指令的执行周期会有什么变化呢？下面列举两种情况。

(1) 指令 A、B、E 都分到了同一个 Cluster 中，而指令 C、D 分到了另一个 Cluster 中，由于跨不同的 Cluster 之间进行唤醒需要延迟一个周期，指令 A 和 B 在被仲裁电路选中之后，需要等待一个周期才能够将指令 C 和 D 进行唤醒，同理指令 D 在被仲裁电路选中之后，也需要等待一个周期才能够将指令 E进行唤醒，因此总共需要五个周期才能将这五条指令全部送到 FU 中执行，这个过程如图 9.37 所示。

图 9.37 需要五个周期才可以将指令 A～E送到 FU 中

(2) 指令 A、C 分到了同一个 Cluster 中，指令 B、D、E 分到了另一个 Cluster 中，此时尽管跨越不同的 Cluster 之间进行唤醒需要延迟一个周期，但是最终的结果却和上面的有所不同，指令 A 和 B 在被仲裁电路选中之后，在当前周期就可以将指令 C 和 D 进行唤醒，这是因为指令 A 和 C 属于同一个 Cluster, 指令 B 和 D 也属于同一个 Cluster, 一条指令对自身的 Cluster 内的指令进行唤醒是可以在一个周期内完成的。当指令 C 和 D 都被仲裁电路选中之后，在当前周期就可以对指令 E进行唤醒，到了下个周期，指令 E 也可以被仲裁电路选中了，这样总共需要三个周期就可以将所有的指令送到 FU 中执行，这个过程如图 9.38 所示。

图 9.38 需要三个周期可以将指令 A～E送到 FU 中

由上面的例子可以看出，对发射队列使用 Cluster 结构之后，它的执行效率和指令在不同 Cluster 之间的分配是很有关系的，要想使处理器取得比较高的执行效率，就需要仔细地规划这种分配算法，使处理器的硬件资源得到有效的利用。

对于采用非数据捕捉 (non-data-capture) 结构的超标量处理器来说，指令在被仲裁电路选中之后会首先读取物理寄存器堆 (PRF),这就需要 PRF 支持多个读端口，而多端口的寄存器堆也是很浪费面积的，速度也比较慢，此时也可以对寄存器堆也采用 Cluster 结构，对每个采用 Cluster 结构的发射队列使用一个物理寄存器堆，Alpha 21264 处理器即采用了这种设计方法 ^[41]，如图 9.39 所示。

图 9.39 对寄存器堆采用 Cluster 结构

如果不采用 Cluster 结构的设计，整个处理器有 4 个 FU, 物理寄存器堆 (PRF) 需要 8 个读端口和 4 个写端口 (假设每条指令都有 2 个源寄存器和 1 个目的寄存器 ); 采用 Cluster 结构之后，整个处理器分为两个 Cluster, 每个 Cluster 有两个 FU,并且每个 Cluster 内都有一个完整的物理寄存器堆，这相当于将物理寄存器堆复制了一份，这样对于每个 Cluster 内的指令来说，都可以直接从物理寄存器堆中读取操作数，每个 FU 都在自己所属的 Cluster 内使用旁路网络 (bypassing network),这样就减少了旁路网络的复杂度。当然，这样的设计要求两个物理寄存器堆的内容要保持一致，这要求每个 FU 在更新自身 Cluster 内的寄存器堆的同时，还需要更新另一个 Cluster 内的寄存器堆，因此总体看起来，这样的设计可以将寄存器堆的读端口个数减少一半，变为 4 个读端口，但是寄存器堆的写端口个数并没有节省，因为还需要为每个 FU 都配备一个写端口，所以此时每个寄存器堆的写端口仍旧是 4 个。但是，这种只节省读端口个数的方法仍旧可以减少寄存器堆的面积，粗略地说，可以假设寄存器堆 ( 或者 SRAM) 的面积近似和它的端口个数的平方成正比 (当然，这种说法不完全正确，应该是布线所占面积随着端口的平方而增加，晶体管是线性增加的 ), 即：

\[\mathrm{Area\ of\ register\ file}=(\mathrm{number\ of\ ports})^2\]

对于一个有着 8 个读端口，4 个写端口的寄存器堆来说，其面积等于 $(8+4)^2=144$；而读端口个数减半之后，每个寄存器堆的面积为 $(4+4)^2=64$, 两个寄存器堆的面积等于 $64\times2=128$, 因此还是要小于 144 的，而且通过减少每个寄存器堆的端口个数，还可以获得更快的速度，避免一个过于臃肿的寄存器堆成为处理器中的关键路径，这些都是为什么要将寄存器堆复制两份的原因。

当然，这种设计的缺点也是很明显的，为了减少复杂度，旁路网络不能跨越 Cluster, 当两个存在相关性的连续的指令属于两个不同的 Cluster 时，后续的指令需要等到前面的指令更新完寄存器堆之后，才能够从寄存器堆中读取操作数。虽然在乱序执行 (out-of-order) 的处理器中，硬件会将一些不相关的指令调度到两条指令之间来执行，但是当流水线比较深时，这两条指令之间的相隔的周期数也是比较多的，硬件无法调度到这么多的不相关指令，因此会在流水线中引入比较多的气泡 (bubble),降低了处理器的性能，造成 “高频低能”的结果。

9.5.2 Cluster Bypass

要提高处理器的性能，需要每周期可以并行执行更多的指令，也就需要更多的 FU 来支持，这会导致旁路网络 (bypassing network) 的复杂度也随之显著地增大，使其严重地影响处理器的周期时间，因此，可以在旁路网络上引入 Cluster 结构，如图 9.40 所示。

图 9.40 采用 Cluster 结构之前及之后的示意图

图 9.40(a) 使用了正常的旁路网络，这样的设计在前面已经介绍过了，由于在流水线中增加了 Source Drive 和 Result Drive 两个流水段，导致旁路网络的复杂度很高；而在图 9.40(b) 中，对旁路网络使用了 Cluster 结构，将两个 FU 分布在两个 Cluster 中，每个 FU 不能将它的结果送到其他的 FU 中，只能送到自身的旁路网络中，也就是说，旁路网络只分布在每个 Cluster 内部。其实，在前文介绍过完全没有旁路网络的设计方法，也介绍过上面图 9.40(a) 所示的这种完全使用旁路网络的设计方法，而这种对旁路网络采用 Cluster 结构的设计方法则是介于这两者之间 ( 完全没有旁路和完全使用旁路 ) 的一种方法。当两条连续的相关指令都使用同一个 FU 时，它们可以背靠背地执行；而当两条连续的相关指令使用不同的 FU 时，就不能背靠背地执行了，因此图 9.40(b) 所示的这种对旁路网络采用 Cluster 结构的设计方法，它的执行效率和复杂度都是介于这两种方法之间的。

由图 9.40 还可以看出，由于旁路网络的复杂度降低了，因此流水线中的 Source Drive 和 Result Drive 两个流水段此时都可以去掉了，这样相当于节省了两级流水线，加快了跨越不同的 Cluster 之间的相关指令执行的速度，因为只有同属于一个 Cluster 的相关指令才可以背靠背地执行，如果相关指令属于不同的 Cluster, 则只能通过寄存器堆传递操作数，当流水线中没有了 Source Drive 和 Result Drive 两个流水段之后，两条属于不同 Cluster 的相关指令之间只需要间隔一个周期就可以了，如图 9.41 所示。

图 9.41 采用 Cluster 结构之后的流水线

指令 A: R3 = R1 + R2
指令 B: R5 = R3 + R4

采用本节所讲述的这种 Cluster 结构可以简化旁路网络的设计，所以可以将流水线中的 Source Drive 和 Result Drive 两个流水段节省掉，缩短流水线的好处是很明显的，它仅仅造成了两条相关指令之间的执行间隔一个周期，如图 9.41 所示，在乱序执行的处理器中，硬件很容易找到一条不相关的指令插入到这个周期来执行，这样简化了旁路网络的同时，并没有造成性能的明显下降。但是随着处理器并行度的提高，寄存器堆的端口数也在随着增加，同时处理器主频的提高又要求周期时间越来越小，这两方面的综合作用，可能导致寄存器堆并不能像图 9.41 所示的那样，在前半个周期写入、在后半个周期读取，这样就导致相邻的相关指令需要间隔的周期数有所增加，在超标量处理器中使用纯硬件的调度方法很难找到这么多的不相关指令插入到这些间隔的周期中，这样就会影响到处理器的执行效率了。

综合看起来，这种将旁路网络采用 Cluster 结构的设计方法在乱序执行的超标量处理器中是可以被接受的，这是由于即使两条相邻的相关指令属于不同的 Cluster 而不能够背靠背地执行，硬件也可以调度不相关的指令插入到这些间隔的周期中。但是在顺序执行 (in-order) 的处理器中，由于硬件无法调度不相关的指令，所以这种非完全的旁路网络所引入的时间间隔会带来很大的负面影响，因为在这段时间内做不了任何事情，只能产生流水线的气泡 (bubble),这样显然降低了处理器的性能，所以在顺序执行的处理器中，一般都不会对旁路网络采用很激进的 Cluster 结构，而是尽量会采用完全的旁路网络，以降低相邻的相关指令所引入的流水线气泡，一个明显的例子就是 Intel 的 Atom 处理器，这个兼容 x86 指令集的顺序执行的超标量处理器拥有复杂的旁路网络，当然，这对于面向低功耗应用的 Atom 处理器来说并不是一个值得夸耀的地方。

即使在乱序执行的超标量处理器中，这种无法跨越 FU 进行旁路的设计方法，虽然降低了硬件消耗，但是在一定程度上也会降低处理器的执行效率。如果这种折中方法无法接受，仍旧想要实现跨越 FU 进行旁路的效果，那么就只能借鉴对发射队列采用 Cluster 结构所采用的方法，在那种方法中，对跨越发射队列之间的唤醒过程加入了一级流水线，类比过来，也可以在跨越 FU 进行旁路的路径上加入一级流水线来降低这些路径上的延迟，如图 9.42 所示。

图 9.42 在跨越 FU 的旁路网络上加入流水线

和 Cluster IQ 所采用的方法类似，对于一个 FU 来说，将它的结果送到自己的输入端所经过的路径是很短的，故可以在一个周期之内完成；而将它的结果送到其他 FU 的输入端所经过的路径是很长的，在一个周期之内可能无法完成，因此需要为这个过程增加一个周期，也就是增加一级流水线，但是相比于跨越 FU 之间没有旁路网络的情况，这样的方法仍然是占据优势的。当然这样的设计也会导致复杂度的上升，可能会对处理器的功耗和周期时间造成一定的负面影响，究竟要采用哪种设计，这需要对处理器的性能、功耗、应用领域等方面进行综合考虑才可以作出决定。

到目前为止，在 9.5.1 节讲述的 Cluster IQ 的设计方法中，如果两条相邻的相关指令属于两个不同的发射队列，则跨越发射队列间的唤醒过程会引入一个周期的延迟，而在本节讲到的，如果两条相关的指令属于两个不同的 Cluster FU, 则跨越 FU 之间的旁路网络也需要一个周期的延迟，那么综合看起来，是不是这两个延迟会进行叠加呢？

答案是否定的，举例来说，如图 9.43 所示的例子。

图 9.43 Cluster IQ 和 Cluster bypass 所产生的延迟并不会叠加

指令 A 和 B是相邻的相关指令，它们属于两个不同的 Cluster IQ, 则在流水线的唤醒阶段会引入一个周期的延迟，但是到了流水线的执行阶段，需要将结果进行旁路 (bypass) 时，并不会再引入额外的延迟。由图 9.43 可以看出，跨越不同的 Cluster FU 之间进行旁路而产生的一个周期的延迟，正好和跨越不同的 Cluster IQ 进行唤醒而产生的一个周期延迟相 “叠加”了，因此尽管跨越 Cluster IQ 进行唤醒需要一个周期的延迟，跨越 Cluster FU 的旁路网络也需要一个周期的延迟，但是放到流水线中之后综合来看，指令 A 和 B之间的延迟也只有一个周期而已。

9.6 存储器指令的加速

9.6.1 Memory Disambiguation

在前文讲述的寄存器之间存在的相关性，即先写后读 (RAW)、先写后写 (WAW) 和先读后写 (WAR),都是在流水线的解码阶段可以发现并解决的，因为这些相关性都是和寄存器名字相关的。而对于访问存储器类型的指令来说 (主要是 load/store 指令 ),访问存储器的地址是在指令执行过程中被动态地计算出来的，只有经过流水线的执行阶段，才可以得到访问存储器的真正地址，举例来说，有下面的两条指令。

ST R0, #15[R1];  //Store 指令，将寄存器 R0 的内容保存在 memory[R1 + 15]
LD R3, #10[R2];  //Load 指令，将 memory[R2 + 10] 的内容读取到寄存器 R3 中

Store 指令将数据存储在地址 “R1+15” 的地方，load 指令从地址 “R2+10” 的地方取数据，只有当这两个地址不相等，也就是 “$\mathrm{R1}+15\ne\mathrm{R2}+10$” 时，这两条访问存储器的指令才不存在先写后读 (RAW) 的相关性。但是，这在流水线的解码阶段是不可能知道的，只有经过了流水线的执行阶段，当这两条指令的地址都被计算出来之后，才可以知道它们之间是否存在相关性。一般来说，访问存储器的指令之间也存在 RAW、WAW 和 WAR 这三种相关性，它们如图 9.44 所示。

图 9.44 访问存储器的指令之间存在的相关性

在超标量处理器中，虽然可以使用寄存器重命名来解决普通指令之间存在的 WAW 和 WAR 这两种假相关性，但是对于访问存储器的指令来说，是没有办法对这些地址也进行重命名来消除 WAW 和 WAR 这两种相关性的，这是为什么呢？因为对于通用寄存器来说，它的个数是有限的，例如只有 32 个，因此对它们进行重命名是可以实现的，但是对于存储器地址来说，它存在无数种可能性，对这些地址进行重命名是一件很难的事情，因此在超标量处理器中，对于访问存储器的指令来说，这三种相关性 (WAW、WAR 和 RAW) 都是需要考虑的，虽然从理论上来说，访问存储器的指令之间也可以乱序执行 (out-of-order), 但是一旦发现这三种相关性有任何一种发生了违反，那么就需要进行处理，这在一定程度上增加了设计的复杂度。为了降低设计难度，也为了保持处理器中存储器的正确性，大部分处理器中的 store 指令都是顺序执行的 (in-order),这样可以避免 WAW 相关性，但是 load 指令可以有不同的实现方式，概括来讲，主要可以分为三种。

(1) 完全的顺序执行，此时 load 指令和 store 指令都按照程序中指定的顺序来执行，很明显，这是最保守的一种方法了；

(2) 部分的乱序执行，顺序执行的 store 指令将程序划分成了不同的块，每当一条 store 指令的地址被计算出来之后，这条 store 指令和它后面的 store 指令之间的所有 load 指令可以乱序执行，这种方式可以避免先读后写 (WAR) 相关性的发生，同时也可以降低对先写后读 (RAW) 相关性的检测难度；

(3) 完全的乱序执行，在这种方法中，load 指令不再受到 store 指令的限制，只要 load 指令的操作数准备好了，它就可以送到 FU 中执行，在这种情况下，先读后写 (WAR) 和先写后读 (RAW) 这两种相关性都是需要在流水线中进行处理的。

1. 完全的顺序执行

这种方法中，load 指令和 store 指令都是严格按照程序中指定的顺序执行的，这是最保守的一种做法，由于 load 指令一般处于相关性的顶端，这种方法不能使 load 指令尽可能地提前执行，导致所有相关指令的执行都比较晚，使用这种方法的处理器，性能自然就比较低了，尤其是在超标量处理器中，基本上是不会采用这样保守的设计方法的。

2. 部分的乱序执行

这种方法中，虽然 store 指令仍旧是按照程序中指定的顺序 (in-order) 执行的，但是处于两条 store 指令之间的所有 load 指令却可以乱序执行，当一条 store 指令被仲裁电路选中之后，位于它后面的所有 load 指令 (直到下一条 store 指令 ) 就有资格参与仲裁的过程了，而且这些 load 指令可以按照乱序的方式被仲裁电路选中，这样可以使 load 指令尽可能地提前执行。

这个方法的本质就是当一条 store 指令所携带的地址被计算出来之后，在它之后进入到流水线的所有 load 指令就可以具备条件去判断先写后读 (RAW) 的相关性了，每条 load 指令将它携带的地址计算出来之后，需要和前面所有已经执行的 store 指令所携带的地址进行比较。为了实现这个功能，就需要一个缓存来保存那些已经被仲裁电路选中，但是还没有顺利地离开流水线 ( 也就是退休 ) 的 store 指令，可以将这个缓存称为 Store Buffer。如果load 指令在这个缓存中发现了地址相等的 store 指令，则说明发现了先写后读 (RAW) 的相关性，此时直接从这个缓存中就可以得到 load 指令所需要的数据；如果在这个缓存中没有发现地址相等的 store 指令，则 load 指令需要访问 D-Cache, 或者更下层的物理存储器，才可以得到需要的数据。

在这种方法中，每条 store 指令可以看作是 “一扇门”, 一条 store 指令所携带的地址被计算出来时，就相当于把这扇门打开了，这样门后面的所有 load 指令就有资格参与仲裁的过程，当然，load 指令是否真正能够参与仲裁的过程，还需要看自己的源操作数是否已经准备好了。而且，一条 store 指令其实没必要等到将它所携带的地址真正计算出来之后，才允许它后面的 load 指令参与仲裁的过程，根据前文对仲裁 (select) 和唤醒 (wake-up) 过程的介绍可以知道，当 store 指令被仲裁电路选中之后，就可以 “打开门”了，允许它后面的 load 指令参与仲裁的过程，这样已经可以保证，当 load 指令将它携带的地址计算出来之后，它前面的 store 指令肯定已经将携带的地址也计算出来了，此时就可以进行地址的比较，以判断它们之间是否存在先写后读 (RAW) 的相关性，图 9.45 给出了一个例子。

图 9.45 部分的乱序执行

当 store 指令 A 被仲裁电路选中之后，load 指令 B、C 和 D 就有资格参与仲裁的过程了，仲裁电路按照乱序的方式来选择它们。但是，当这三条 load 指令没有全部被仲裁电路选中完毕时，例如只有指令 C 被选中，而指令 B 和 D 都还没有被选中的时候，store 指令 E又被仲裁电路选中了，它会使 load 指令 F 和 G 也有资格参与仲裁的过程，仲裁电路可以按照乱序的方式来选择所有的这些 load 指令。

这种执行方法会遇到一个问题，当 load 指令 B 和 D 被仲裁电路选中的时候，Store Buffer 中除了它们前面的 store 指令 A 之外，还有了它们后面的 store 指令 E，当进行地址比较来检查 RAW 相关性时，即使 load 指令 B( 或 D) 所携带的地址和 store 指令 E所携带的地址相等，它们之间也并没有 RAW 相关性，load 指令 B( 或 D) 所需要的数据不应该来自于 store 指令 E，所以这就需要一种机制。当 load 指令和 Store Buffer 中的 store 指令进行地址比较时，需要知道哪些 store 指令在自己前面，哪些 store 指令在自己后面，对于 RAW 相关性检查来说，只需要关注那些在自己前面的 store 指令就可以了，因此需要对这些 load/store 指令前后顺序进行标号，可以作为这个标号的来源有如下几种。

(1) PC 值，但是当 store 指令之后有一个向前跳转指令时，通过 PC 值就无法辨别出真实的先后顺序了，如图 9.46 所示。

此时，load 指令的执行顺序是在 store 指令之后，但是 load 指令的 PC 值是要小于 store 指令的，直接使用 PC 值来标记它们之间执行的先后顺序，是无法满足要求的。

图 9.46 无法直接通过 PC 值来判断 load/store 指令之间的先后顺序

L1: load
    ⋮
    store
    B L1

(2) ROB 的编号，在 ROB 中记录着所有指令进入流水线的先后顺序，因此指令在 ROB 中的地址是可以用来表示它们之间的先后顺序的。但是，由于 ROB 中存储着所有的指令，这其中只有一部分是 load/store 指令，如果使用这个标号，必然是很稀疏的，而这些标号要参与大小比较，因此这样做就造成了比较器使用比较大的位宽，浪费了面积和功耗。

(3) 在流水线的解码阶段，为每一条 load/store 指令分配一个编号，这个编号的宽度需要根据流水线中最多支持的 load/store 指令的个数来决定，编号的分配和大小比较的过程可以参见前文中对分支指令分配编号的方法。

在实际当中，后两种方法都是可以采用的，当然，它们都会给处理器带来更高的复杂度。退一步来想，在上述的例子中，如果只有当 store 指令 A 及其后面的 load 指令 B、C 和 D 都被仲裁电路选中之后，才允许 store 指令 E向仲裁电路发出请求的话，就可以避免上述问题了。每一条 load 指令在寻找 Store Buffer 时，只会遇到比自己先进入流水线的 store 指令，而不会遇到在自己之后进入流水线的 store 指令，这样就不需要比较它们之间的先后顺序了，简化了 RAW 相关性的检查过程。不管怎么说，这种部分地将 load 指令进行乱序执行的方法虽然可以提高一些性能，但是在很多时候仍然不能够最大限度地挖掘程序之间存在的并行性，例如图 9.47 所示的例子。

图 9.47 指令 F 不能先于指令 B 而提前执行

指令 A: LOAD  r5, MEM[r3]  ← D-Cache miss
指令 B: STORE r7, MEM[r5]  ← RAW for address generate, stalled
        ⋮
指令 F: LOAD  r8, MEM[r9]  ← Independent load, stalled

当第一条 load 指令 A 发生 D-Cache 缺失时，和它存在寄存器之间的 RAW 相关性的 store 指令 B( 指令 B 使用指令 A 的目的寄存器 r5) 就不能参与仲裁的过程了，那么即使后面的 load 指令 F 和指令 B 不存在任何的相关性，也不能向仲裁电路发出请求而参与仲裁的过程，这就无形之中浪费了提高并行执行的机会。

3. 完全的乱序执行

在这种方法中，store 指令仍然会按照程序中指定的顺序 (in-order) 来执行，但是 load 指令将不再受限于它前面的 store 指令，只要 load 指令的操作数准备好了，就可以向仲裁电路发出申请，仲裁电路会按照一定的原则，例如 oldest-first 原则，选择一条合适的 load 指令送到 FU 中执行。在这种方法中，可以使 load/store 指令共用一个发射队列 (Issue Queue), 采用每周期只选择一条 load/store 指令的设计，也可以采用每周期同时选择一条 load 指令和一条 store 指令的设计，考虑到 load/store 指令在一般的程序中占据的比例比较大，所以最好能够尽可能地增加每周期可以并行执行的 load/store 指令的个数，当然这样也会增加设计的复杂度，例如 D-Cache 就需要更多的端口来支持这种特性。不过，load 指令和 store 指令的处理过程毕竟有所不同，如果使它们共用一个发射队列，则仍旧需要使用互相独立的仲裁电路，当指令被写入发射队列中时，需要根据指令的类型 (load 还是 store) 将其对应到各自的仲裁电路上。对于 store 指令的仲裁电路来说，需要根据指令的年龄信息，找到最旧的那条 store 指令，如果发现它还没有准备好，则一直等待；而对于 load 指令的仲裁电路来说，仍旧需要使用它们的年龄信息，但是对于那些还没有准备好的 load 指令来说，只需要在进行年龄比较时忽略它们即可。总结起来就是 store 指令按照程序中指定的顺序 (in-order) 进行选择，而 load 指令采用 oldest-first 策略，按照乱序 (out-of-order) 的方式进行选择。

其实，还可以使 load/store 指令使用独立的发射队列，也就是说，load 指令单独使用一个发射队列，store 指令也单独使用一个发射队列，这样 store 指令的发射队列可以简单地使用 FIFO 结构，它将不必使用年龄比较类型的仲裁电路，此时只需要判断 FIFO 中最旧的那条指令是否已经准备好，就可以达到按照程序中指定的顺序 (in-order) 进行选择的效果了，这样简化了 store 指令的仲裁电路的设计。

在这种完全乱序执行 load 指令的方式中，load 指令的操作数只要准备好了，就可以参与仲裁的过程，不需要等待它前面的 store 指令是否已经计算出了地址。之所以敢于采用这种方法，是有依据的，对于 RISC 处理器来说，有数量丰富的通用寄存器，所以程序当中的很多变量可以直接放到寄存器当中，这样在实际的程序当中，store/load 指令之间存在先写后读 (RAW) 的相关性的情况并不是很多，而且，通过提前执行 load 指令，可以尽快地唤醒更多的相关指令，这样使处理器获得更大的并行性。

但是反观 CISC 处理器，因为可用的寄存器很少，所以需要经常和存储器打交道，在程序当中，许多的操作数都需要放到存储器中，这样 STORE/LOAD 之间存在先写后读 (RAW) 相关性的情况就很多了，一旦发现一条提前执行的 LOAD 指令和后面的 STORE 指令所携带的地址相等，那么就产生了错误，需要进行恢复，如图 9.48 所示。

图 9.48 STORE/LOAD 指令的违例

LOAD  r8, MEM[r9]
STORE r7, MEM[r5]
⋮
LOAD  r8, MEM[r9]

在图 9.48 的这种情况中，不仅被提前执行的 LOAD 指令得到了错误的结果，所有和这条 LOAD 指令有直接或者间接关系的指令，都需要从流水线中被抹掉，重新执行，这样造成处理器执行效率的降低，这种情况称为 STORE/LOAD 指令的违例，应该尽量避免这种情况的发生，这时候最好有一种预测机制，来预测哪些 LOAD 指令是和前面的 STORE 指令存在先写后读 (RAW) 的相关性而不能提前被执行，通过这样的一些比较精确的预测算法，可以大大降低 STORE/LOAD 指令违例发生的频率，从而避免对处理器性能造成影响，这样的预测算法称为 LOAD/STORE 相关性的预测。这种预测方法在当代的处理器中已经逐渐地被采用，例如 Intel 的 Core2 系列处理器就采用了这种预测算法，要想提高处理器的性能，就应该重视这种 LOAD/STORE 相关性的预测算法。

其实，LOAD 指令和 STORE 指令之间存在先写后读 (RAW) 的相关性，是程序固有的一种属性，如果程序中，在 STORE 指令之后，很快就使用 LOAD 指令来访问刚才存储的数据，那么出现 STORE/LOAD 指令违例的概率就很大了，通过使用 LOAD/STORE 相关性的预测，一旦发现一条 LOAD 指令和它之前的 STORE 指令存在先写后读 (RAW) 的相关性，就将其记录下来，那么以后再遇到这条 LOAD 指令时，就不能使它提前执行，而且，需要从 Store Buffer 中获得 LOAD 指令需要的数据。

使用 LOAD/STORE 相关性的预测，还有一个好处是只有那些预测和 STORE 指令存在先写后读 (RAW) 相关性的 LOAD 指令才会访问 Store Buffer, 这样可以减少 Store Buffer 所需要的端口个数和比较电路的个数，从而降低设计的复杂度和功耗。

在 RISC 处理器中，即使 LOAD/STORE 指令之间存在先写后读 (RAW) 相关性的情况很少，但是一旦发现，就需要将这条 LOAD 指令以及和它相关的所有指令都从流水线中抹掉，并且使它们重新参与仲裁的过程，在第 8 章已经介绍了如何使用硬件的方法处理这种情况，此处不再赘述。

使用硬件来处理 STORE/LOAD 指令的违例，总是要付出硅片面积和功耗的代价，这是超标量处理器不能避免的，因为很多指令集在设计之初，并没有考虑到它在超标量处理器中会有这么复杂的情况发生。但是，一些比较新的指令集考虑到了这些情况，它能够充分地利用编译器，配合指令集来处理 STORE/LOAD 指令违例的情况，在 VLIW 处理器领域，很多都采用了这种方法，Intel 的 Itanium 架构就是一个明显的例子。

如图 9.49 所示为一段有可能产生 STORE/LOAD 指令违例的一段程序，对于 VLIW 处理器的编译器来说，会尽量地将 LOAD 指令提前执行，以获得比较高的并行执行度，但是编译器并不确定图 9.49 中的 LOAD 指令和它之前的 STORE 指令是否使用同样的地址，这需要在程序实际执行时才可以发现，所以在 Itanium 的编译器中，在对程序进行优化调度、将 LOAD 指令放到 STORE 指令前面的同时，会对这条 LOAD 指令进行标记，如图 9.50 所示。

图 9.49 有可能产生 STORE/LOAD 指令违例的一段程序

Inst1
Inst2
STORE

LOAD r1
Use  r1
Inst3

图 9.50 对提前执行的 LOAD 指令进行标记

一旦 LOAD 指令被编译器放到 STORE 指令之前执行，则这条 LOAD 指令会被变为指令 LOAD.a, 这条新的指令在执行的时候，除了完成普通的 LOAD 指令所具备的功能，还会将 LOAD 指令计算出来的地址放到一个表格 ALAT(Advanced Load Address Table) 中，这个表格的样子如图 9.51 所示。

图 9.51 ALAT(Advanced Load Address Table)

因为在一般的 RISC 指令集中，可以支持全字 (word)、半字 (halfword) 和字节 (byte) 的存取，所以需要将这个信息也保存在 ALAT 的 Size 表项中，每当执行 store 指令时，都会使用 store 指令计算出来的地址来查找 ALAT, 这需要 ALAT 中的 Address 表项支持内容寻址 (CAM) 的功能。如果在 ALAT 中发现了携带地址相同的 load 指令，则会将这条 load 指令 “踢出”ALAT,store 指令会占据这个位置，这就表示出现了 load 指令的违例，需要进行处理，这个处理发生在什么时候呢？这就需要使用 “load.c” 指令，这条指令放在 load 指令被调度之前的位置上，也就是说，对于被编译器提前调度的 load 指令，除了使用 “load.a”指令之外，还会在原来的位置放上 “load.c” 指令。当执行 “load.c” 指令时，这条指令会查找 ALAT，如果发现自己已经不在 ALAT 中了 (在之前被 store 指令踢走了 ),那么就表示发生了 store/load 指令的违例，需要进行修复。在 VLIW 处理器中，一般使用一段固定的程序完成这个修复的过程，这段程序称为 fixup code。如果 “load.c” 指令在执行的时候，发现自己仍旧存在于 ALAT 中，那么就表示没有发生 load 指令违例，此时正常执行就可以了。这种方法通过编译器和指令集的配合来解决 load/store 指令之间的先写后读 (RAW) 相关性，降低了硬件的复杂度，是一种比较高效的方法。当然，由于需要更改指令集，这种方法不适合当今通用处理器的设计，而开发一套新的指令集，就像 Intel 的 Itanium 处理器那样，是要面临很多的风险和问题的，这就相当于一切从零开始，需要重新培养整套的生态环境，也需要使软件人员能够接受这个 “新家伙”。不管怎么说，Itanium 失败了，这个失败使 Intel 在后续的处理器产品中，再也不敢尝试新的指令集，即使是面向低功耗移动领域的 Atom 处理器，也仍然固执地采用了 x86 指令集，可能 Intel 很清楚，这个臃肿的指令集并不适合低功耗领域，但是 “一朝被蛇咬”的伤疤阵痛仍在，再冒一次风险？恐怕 Intel 已经没有这种勇气了。

9.6.2 非阻塞 Cache

从广义上来讲，处理器除了流水线内核之外，还包括了片内的 Cache, 它们统一构成了一个完整的处理器，与处理器内核离得最近的 Cache 称为第一级 Cache, 简称 L1 Cache, 由于超标量处理器一般采用哈佛结构，所以 L1 Cache 分为存储指令用的 I-Cache 和存储数据用的 D-Cache。I-Cache 由于只需要读取，而且取指令要求串行的顺序，所以对它的处理是比较特殊的，不能简单地使用非阻塞的方式，故本节只针对 D-Cache 进行讲述。在 RISC 处理器中，只有访问存储器的指令，例如 load/store 指令，才可以访问 D-Cache, 对于 load/store 指令来说，这两种类型的指令都有可能引起 D-Cache 发生缺失 (miss),它们分别如下。

(1) 对于 load 指令来说，如果需要的数据不在 D-Cache 中，就发生了缺失，需要从下一级的物理存储器 (physical memory) 中取得数据 (为了简化流程，本节假设 L1 Cache 的下一级存储器就是物理存储器 ),并在 D-Cache 中按照某种算法，找到一个 Cache line 进行写入，如果被写入的 Cache line 是脏 (dirty) 状态的，还需要将这个 line 中的数据块 (data block) 先写回到物理内存中。

(2) 对于 store 指令来说，如果它携带的地址不在 D-Cache 中，那么对于 “write back＋write allocate” 类型的 Cache 来说，需要首先从物理内存中找到这个地址对应的数据块 (data block),将其读取出来，和 store 指令所携带的数据进行合并，并从 D-Cache 中按照某种算法，找到一个 Cache line, 将合并之后的数据写入到这个 Cache line 中；如果被替换的这个 Cache line 已经被标记为脏 (dirty) 的状态，那么在被写入之前，还需要先将这个被覆盖的 line 中的数据块 (data block) 写回到物理内存中，这样才能够放心地将合并之后的数据写到这个 Cache line 中。

这两种情况都称为 D-Cache 的缺失，由上面的描述可以看出，不管是 load 指令还是 store 指令，当发生 D-Cache 缺失时，D-Cache 和物理内存之间都是需要交换数据的，这个过程一般需要多个周期才能完成，如果在这些周期之内，又发生了 D-Cache 缺失，该如何进行处理？

最简单的方法就是在 D-Cache 发生缺失并且被解决之前，使 D-Cache 与物理内存之间的数据通路被锁定，只处理当前这个缺失的数据，处理器不能够再执行其他的 load/store 指令。这是最容易实现的一种方式，但是考虑到 D-Cache 缺失的处理时间相对是比较长的，如果这段时间阻塞了其他 load/store 指令的执行，而一般情况下，load 指令总是处于相关性的最顶端，希望它尽早地执行，这样的阻塞就大大减少了程序执行时可以寻找的并行性，使处理器的性能无法提高，这个过程的示意图如图 9.52 所示。

图 9.52 发生 D-Cache 缺失时，不能够执行后续的 load/store 指令

在图 9.52 所示的这种方法中，产生 D-Cache 缺失的 load/store 指令阻塞了后面的 load/store 指令的执行，所以称这种设计方法为阻塞 (Blocking)Cache, 在发生阻塞的这段时间内，处理器只能暂停执行，无法做其他有用的事情。

如果在发生 D-Cache 缺失的时候，处理器可以继续执行后面的 load/store 指令，这种设计方法就称为非阻塞 (Non-blocking)Cache, 也称做 lookup-free Cache。非阻塞的 Cache 允许处理器在发生 D-Cache 缺失的时候继续执行新的 load/store 指令，如图 9.53 所示。

从图 9.53 可以看出，非阻塞 Cache 在一定程度上掩盖了 D-Cache 缺失时所占用的时间 (在图 9.53 中这段时间称为 Miss Penalty),因此对于处理器性能的提升是非常有效果的。其实，非阻塞 Cache 并不是乱序执行的超标量处理器的专属品，在顺序执行 (in-order) 的处理器中也可以采用这种方法，不过这需要在处理器内的 ScoreBoard 中，将发生 D-Cache 缺失的 load 指令的目的寄存器标记为暂时不可获得的状态 (non-available)。例如，指令 “load r1, #8[r2]”发生了 D-Cache 缺失时，会在 ScoreBoard 中将目的寄存器 r1 标记为当前暂时不可以获得的状态，这样后续使用寄存器 r1 作为源操作数的指令就不会继续执行了。

图 9.53 发生 D-Cache 缺失时，可以继续执行后续的 load/store 指令

非阻塞 Cache 的概念最初由美国人 David Kroft 提出 ^[42],采用这种方法之后，load/store 指令的 D-Cache 缺失被处理完的时间可能和原始的指令顺序已经不一样了，举例来说，两条顺序的指令 load1 和 load2 都发生了 D-Cache 缺失，但是 load1 指令可能需要到物理内存中才能够找到需要的数据，而 load2 指令在 L2 Cache 中就可以找到所需的数据了，因此 load2 指令会更早地得到需要的数据，也就是它们完成的顺序已经和原始的指令顺序不一样了。处理器要处理这个问题，就需要保存那些已经发生缺失的 load/store 指令的信息，这样当这些缺失的 load/store 指令被处理完成，将得到的数据写回到 D-Cache 时，仍然可以知道 “who am I”, 即哪条 load/store 指令需要这个数据。

在前面说过，不管是 load 指令还是 store 指令，只要发生了 D-Cache 缺失，都需要从下级存储器中读取整个数据块 (data block),对于 load 指令来说，可以直接将这个数据块写到 D-Cache 中；而对于 store 指令来说，需要将要存储的数据和这个数据块进行合并，然后将合并之后的数据写到 D-Cache 中，因此从本质上来说，load 指令和 store 指令的处理过程是基本上一样的。

要支持非阻塞 (Non-Blocking) 的操作方式，在处理器中就需要将那些已经产生 D-Cache 缺失的 load/store 指令保存起来，在 Kroft 的原始设计中，这个部件称为 MSHR (Miss Status/information Holding Register),在 Intel 的设计术语中，一般也用 MSHR 来称呼这个部件，但是在 Alpha 处理器中，使用 MAF(Miss Address File) 来称呼这个部件，本书采用 MSHR 这个名称。MSHR 主要由两部分组成，如图 9.54 所示。

在解释 MSHR 的工作原理之前，需要先定义如下的几个名词 (以下都是针对 D-Cache 来说的 )。

(1) 首次缺失 (Primary Miss): 对于一个给定的地址来说，访问 D-Cache 时第一次产生的缺失称为首次缺失。

(2) 再次缺失 (Secondary Miss): 在发生了首次缺失并且没有被解决完毕之前，后续的访问存储器的指令再次访问这个发生缺失的 Cache line, 这时就称为再次缺失，这里需要注意两点，一是再次缺失并不仅仅是指单独的一次缺失，在这个 Cache line 被取回到 D-Cache 之前，后续访问这个 Cache line 的所有 load/store 指令都会产生再次缺失；二是再次缺失使用的地址未必和首次缺失使用的地址是一样的，只要它们属于同一个 Cache line 就可以了。

知道了上面的定义，再来看图 9.54 中的 MSHR, 它主要由两部分组成。

图 9.54 MSHR

(1) 图 9.54(a) 称为 MSHR 的本体，用来保存所有产生首次缺失的 load/store 指令的信息，它包括三项内容。

① V: valid 位，用来指示当前的表项 (entry) 是否被占用，当首次缺失发生时，MSHR 本体中的一个表项会被占用，此时 valid 位会被标记为 1, 当所需要的 Cache line 从下级存储器中被取回来时，会释放 MSHR 本体中被占用的表项，因此 valid 位会被清零。

② Block Address: 指的是 Cache line 中数据块 (data block) 的公共地址，假设物理地址是 32 位，对于一个大小为 64 字节的数据块来说，需要 6 位的地址才能找到数据块中的某个字节，因此数据块的公共地址就需要 $32-6=26$ 位。每次当 load/store 指令发生 D-Cache 缺失时，都会在 MSHR 的本体中查找它所需的数据块是否处于正在被取回的过程中，这需要和 Block Address 这一项进行比较才可以知道，通过这种方式，所有访问同一个数据块的指令只需要处理一次就可以了，这样可以避免存储器带宽的浪费。

这里为什么说 Cache line 中数据块的大小是 64 字节，而不是其他的值呢？这是有原因的，因为这个数据块的大小一般要考虑更低层次的存储器的特性，例如在 DDR3 SDRAM 中，一次基本的突发操作 (burst) 访问的数据大小就是 64 字节，所以在支持 DDR3 SDRAM 的处理器中一般会将 Cache line 中数据块的大小设为 64 字节。

③ Issued: 表示发生首次缺失的 load/store 指令是否已经开始处理，即是否已经开始从下一级存储器中取回数据的过程，由于存储器的带宽有限，占用 MSHR 本体的首次缺失不一定马上就会被处理，而是要等到条件满足的时候，才会向下一级存储器发出读数据的请求。

(2) 图 9.54(b) 称为 LOAD/STORE Table, 不管是发生首次缺失还是再次缺失的 load/store 指令，都会将自身的信息写到这个表格中，它包括五项内容。

① V: valid 位，表示一个表项是否被占用，不管一条 load/store 指令发生了首次缺失还是再次缺失，都会占据这个表格中的一个表项，这样就可以保证这条指令的信息不会丢失。

② MSHR entry: 表示一条发生缺失的 load/store 指令属于 MSHR 本体中的哪个表项，由于产生 D-Cache 缺失的许多 load/store 指令都可能对应着同一个 Cache line, 为了避免重复地占用下级存储器的带宽，这些指令只会占据 MSHR 本体中的一个表项，但是它们需要占用 LOAD/STORE Table 中不同的表项，这样才能够保证每条指令的信息都不会丢失，同时也会记录下这些指令在 MSHR 本体中占据了哪个表项，这样当一个 Cache line 被从下级存储器取回来时，通过和 MSHR 本体中的 block address 进行比较，就可以知道它在 MSHR 本体中的位置，然后就可以在 LOAD/STORE table 中找到哪些 load/ store 指令属于这个 Cache line。

③ Dest. register: 对于 load 指令来说，这部分记录目的寄存器的编号 (如果采用了寄存器重命名，就需要记录物理寄存器的编号 ), 当所需要的数据块从下级存储器中被取回来时，就可以将对应的数据送到这部分所记录的寄存器中；而对于 store 指令来说，这部分用来记录 store 指令在 Store Buffer 中的编号，前面说过，对于超标量处理器来说，必须保证流水线中的所有指令按照程序中指定的顺序来改变处理器的状态，因此 store 指令在顺利地离开流水线之前，都会将它的信息保存在 Store Buffer 中，当 store 指令变为流水线中最旧的指令，此时可以将它的数据写到 D-Cache 中，如果发现了缺失，那么它不会离开 Store Buffer，直到所需要的数据块被从下级存储器中取回来的时候，它才会将要存储的数据合并到这个数据块中，然后将合并后的数据块写到 D-Cache, 此时才可以从 Store Buffer 中释放掉这条 store 指令所占据的空间，因此对 store 指令来说，这部分用来记录它在 Store Buffer 中的编号，它的作用有两个，一是找到 store 指令的所携带的数据，以便和下级存储器中取出的数据块进行合并；二是能够释放 store 指令所占据的 Store Buffer 中的空间。

④ Type: 记录访问存储器指令的类型，这部分取决于具体指令集的实现，对于 MIPS 指令集来说，访问存储器的指令类型包括 LW(Load Word)、LH (Load Half word)、LB (Load Byte)、SW (Store Word)、SH (Store Half word) 和 SB(Store Byte),通过记录指令的类型，才能够使 D-Cache 缺失被解决之后，能够继续正确地执行指令。

⑤ Offset: 访问存储器的指令所需要的数据在数据块中的位置，例如对于大小是 64 字节的数据块来说，这部分的位宽需要 6 位，它和上面的 Type 部分配合，可以从下级存储器取回的数据块中找出哪部分是指令所需要的。

通过 MSHR 本体和 LOAD/STORE Table 的配合，可以支持非阻塞的操作方式，当一条访问存储器的指令发生 D-Cache 缺失时，首先会查找 MSHR 的本体，这个查找过程是将发生 D-Cache 缺失的地址和 MSHR 中所有的 block address 进行比较，根据比较的结果，处理如下。

(1) 如果发现有相等的表项存在，则表示这个缺失的数据块正在被处理，这是再次缺失 (secondary miss),此时只需要将这条访问存储器的指令写到 LOAD/STORE Table 中就可以了。

(2) 如果没有发现相等的项，则表示缺失的数据块是第一次被处理，也就是首次缺失 (primary miss),此时需要将这条访问存储器的指令写到 MSHR 本体和 LOAD/STORE Table 两个地方。

如果 MSHR 本体或者 LOAD/STORE Table 中的任意一个已经满了，则表示不能够再处理新的访问存储器指令，此时应该暂停流水线继续选择新的 load/store 指令送到FU 中执行，等待之前的某个 D-Cache 缺失被解决完毕，此时 MSHR 或者 LOAD/STORE Table 中就会有空闲的空间了，允许流水线继续执行。在现实世界中的处理器一般出于硅片面积和功耗的考虑，MSHR 本体的容量不会很大，多为 4～8 个，也就是处理器同时支持 4～8 个 D-Cache 缺失同时进行处理，这可能会造成 MSHR 本体全被占用的情况发生，不过这种情况发生的概率不是很高，不会对处理器的性能造成过多的负面影响。

当一个缺失的数据块被从下级存储器中取回来时，对于 load 指令来说，需要将数据送到对应的目的寄存器中，并将这个数据块写到 D-Cache 中；而对于 store 指令来说，则会从 Store Buffer 中找到对应的数据，并将其和这个数据块进行合并，然后写到 D-Cache 中，并释放 Store Buffer 中对应的空间。每当一个缺失被解决时，MSHR 本体和 LOAD/STORE Table 中对应的空间也都会被释放，对于 LOAD/STORE Table 来说，可能会释放掉多个表项，因为很多访问存储器的指令所需要的数据可能都在当前被取回来的数据块中。

使用非阻塞 Cache 可以提高处理器的性能，代价就是占用不菲的硅片面积，举例来说，如果 MSHR 本体中有 8 个表项，LOAD/STORE Table 有 16 个表项，则它们占用的存储资源为：

\[8\times(1+26+1)+16\times(1+3+7+3+6)=544\ \mathrm{Bits}\]

原式及字段说明

如果再加上 MSHR 周边所需要的比较电路和控制电路，所需要的硬件资源还会更多，那么有没有一种方法，能够不过多地占用硬件资源，又能够实现非阻塞 Cache 的功能呢？Franklin 和 Sohi 在他们的论文中提出了 in-Cache MSHR 的方法，通过观察处理器的运行过程，发现在 D-Cache 缺失而从下一级存储器中取数据时，在 D-Cache 中，这个缺失的地址对应的 Cache line 此时是空闲的，并没有起到任何的作用，因此可以将这个 Cache line 作为存储 MSHR 的地方，不过这需要在每个 Cache line 中再加上 1 位，称之为 transient bit, 用来表示这个 Cache line 中的数据正在从下一级存储器被取回，当一个 Cache line 处于这种模式时，它其中的 tag 部分用来存储上面的 block address 部分，而其他部分用来保存 MSHR 的信息。但是这样做有一个比较大的缺点，因为对于 D-Cache 来说，其读端口的宽度要远小于 Cache line 中数据块的大小，例如在一个每周期可以并行执行四条指令的超标量处理器中，D-Cache 的读端口的个数一般小于四个，每个读端口的宽度都是 32 位，则整个读端口的宽度不会大于 16 字节，而一般的 Cache line 中数据块的大小为 64 字节。很显然，读端口的宽度远小于数据块的大小，这样需要耗费多个周期才能够从 D-Cache 中将 MSHR 的信息读取出来，使处理器无法高效地执行，从而降低了性能。关于 in-Cache MSHR 的方法，感兴趣的读者可以自行阅读相关的论文 ^[43]。

在超标量处理器中，非阻塞 Cache 的实现要更复杂一些，由于采用了分支预测和乱序执行，一些引起 D-Cache 缺失的 load/store 指令可能处于分支预测失败 (mis-prediction) 的路径上，因此需要一种机制，能够有选择地放弃掉一些正在处理的 D-Cache 缺失，为了更直观地说明这个问题，考虑按照程序原始顺序的三条指令 load1、br( 分支指令 ) 和 load2,并且假设 load1 和 load2 指令都访问同一个数据块，并且分支指令预测为不发生跳转。由于乱序执行的原因，load1 和 load2 指令都在分支指令之前送到 FU 中执行了，并且它们对应的数据块不在 D-Cache 中，这会引起 D-Cache 缺失，处理器需要从下一级存储器中取出这个数据块，但是在这个取数据的过程完成之前，分支指令被发现了分支预测失败，它实际应该是发生跳转的。为了进行状态恢复，需要将 load2 指令从流水线中抹掉 (当然其他所有处在分支预测失败路径上的指令都需要被抹掉 ),这样当这个数据块最终从下一级存储器中被取回来时，load1 指令的目的寄存器可以被写入，而 load2 指令的目的寄存器则不应该被写入，因此，需要从 LOAD/STORE Table 中将 load2 指令删除，这样即使这个数据块被取回来，也不会再执行 load2 指令了。

还有一点需要注意，对一个发生缺失的数据块来说，如果访问这个数据块的所有 load/ store 指令都处于分支预测失败 (mis-prediction) 的路径上，那么即使这个数据块被从下一级存储器中取出来，也不应该被写到 D-Cache 中，这样可以保护 D-Cache 不会受到这些预测错误的分支指令的影响。

但是，非阻塞 Cache 这种技术并不是没有负面的影响，在超标量处理器中，由于乱序执行的原因，可能会导致过多的 load/store 指令处于分支预测失败的路径上，这样增加了 D-Cache 缺失的概率，导致有比实际更多的 D-Cache 缺失需要处理，一定程度上降低了处理器的性能，但是这点负面的影响和它实际带来的优点比起来，基本上是可以忽略的，因此现代的处理器都采用了非阻塞的 D-Cache。

9.6.3 关键字优先

当执行一条访问存储器的指令而发生 D-Cache 缺失时，会将这条指令所需要的整个数据块 (data block) 都从下一级存储器中取出来，如果考虑到预取 (prefetching),还需要将相邻的下一个数据块也取出来，通常一个数据块中包括的数据是比较多的，例如 64 字节，而且这些数据的读取过程是顺序进行的，如图 9.55 所示。

图 9.55 从下级存储器中读取的数据按照顺序写到 Cache line 中

Cache line 中数据读取的顺序：0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15。

如果等到数据块中所有的数据都写到 D-Cache 之后才将所需要的数据送给 CPU,这可能会让 CPU 等待一段时间，为了加快执行速度，可以对 D-Cache 的下一级存储器进行 “改造”，使数据的读取顺序发生改变，如图 9.56 所示。

图 9.56 关键字优先 (Critical Word First)

Cache line 中数据读取的顺序：6,7,8,9,10,11,12,13,14,15,0,1,2,3,4,5。

如果访问存储器的指令所需要的数据位于数据块中的第 6 个字，那么此时可以使下一级存储器的读取从第 6 个字开始，当读取到数据块的末尾时，再从头开始将剩下的第 0～5 个字读取出来，这样做的好处是当下级存储器返回第一个字的时候，CPU 就可以得到所需要的数据而继续执行了，而 D-Cache 会继续完成其他数据的填充工作，这相当于将 CPU 的执行和 Cache 的填充这两部分工作进行了 “重叠”, 提高了整体的执行效率，这就是关键字优先 (Critical Word First)。当然，下级存储器系统需要增加硬件才能够支持这种特性，这在一定程度上增大了硅片面积和功耗。

9.6.4 提前开始

关键字优先 (Critical Word First) 的方法由于需要改变数据读取的顺序，因此要在存储器系统中增加额外的硬件才能够实现，如果不想付出这些成本，那么可以采用提前开始 (Early Restart) 的方法，这种方法不会改变存储器系统对于数据的读取顺序，因此不需要在存储器系统中付出额外的硬件，当发生缺失的存储器指令所需要的数据被取出来之后， CPU 可以马上开始继续执行，如图 9.57 所示。

图 9.57 提前开始 (Early Restart)

Cache line 中数据读取的顺序：0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15。

在图 9.57 中，当指令所需要的数据，也就是第 6 个字，被从下一级存储器中取出来时，就可以让 CPU 恢复执行了，此时数据块中剩余的数据可以继续进行读取，这部分时间和 CPU 的执行时间进行了 “交叠”, 这样提高了 CPU 的执行效率。但是，这种方法不同于关键字优先的方法，它不能够改变下一级存储器读取数据的顺序，因此当需要的数据位于数据块中比较后面的位置时，这种方法并没有很明显的优势，例如当需要的数据位于数据块中第 14 个字的位置时，使用这种方法只会缩短一个周期的时间，带来的性能提升是很有限的。

到目前为止所介绍的加速方法，即非阻塞 Cache、关键字优先和提前开始这三种方法，都可以应用于 D-Cache 中，而对于 I-Cache 来说，由于指令执行的顺序性，没有办法越过当前的指令而直接取下一条指令，从这一点来看，I-Cache 是没有必要实现非阻塞功能的，但是考虑到在超标量处理器中都使用了分支预测，根据当前指令的地址就可以对下一条指令的地址进行预测，当使用一个地址访问I-Cache 而发生缺失，同时预测这个地址对应的指令是分支指令时，如果不采用非阻塞结构的 I-Cache, 那么 CPU 就必须等待当前的这条分支指令被从I-Cache 中取出来之后，才可以继续使用预测的目标地址从 I-Cache 中取指令。如果这是一个预测发生跳转的分支指令，此时再次发生 I-Cache 缺失的概率是很高的，因为即使采用预取 (prefetching) 的方法，也很难将分支指令的目标地址对应的指令提前预取到 I-Cache 中，这样相当于将两次 I-Cache 缺失进行了串行化的处理，很显然耗费的时间是很长的，这个过程如图 9.58 所示。

图 9.58 两次 I-Cache 缺失进行了串行的处理

如果使用非阻塞结构的 I-Cache，那么就可以将这两个 Cache 缺失进行“重叠”，如图 9.59 所示。

图 9.59 采用非阻塞结构的 I-Cache, 使两次缺失的处理进行交叠

很显然，即使取指令必须按照顺序进行，但是从图 9.59 可以看出，使用非阻塞结构的I-Cache 可以隐藏一部分缺失的处理时间，从而提高 CPU 的执行效率。当然，指令毕竟不同于数据，如果后续发生的缺失指令先被取回来了 (例如后续的指令从 L2 Cache 中就可以找到，而先前的指令需要到物理内存中才能找到 ), 它也不能够提前进入到流水线中，需要等待先前的指令被取回来，也就是说，要保证指令进入到流水线的顺序是按照程序中指定的顺序进行的。考虑到对于取指令来说，在大部分情况下，连续的 I-Cache 缺失其实都是指向同一个数据块的，因此不需要对 I-Cache 使用太大的 MSHR 容量，例如在 MIPS R10000 处理器中，在 MSHR 本体中使用了 4 个表项 (entry) 来供 D-Cache 缺失时使用，使用了 1 个表项来供 I-Cache 缺失时使用，因此 MSHR 本体中共有 5 个表项而已。

而关键字优先和提前开始这两种方法，都是可以应用于 I-Cache 的，但是需要保证指令的原始顺序，即使后面的指令已经被取出来了，如果它前面还有指令没有被取出来，那么就必须等待，直到前面的指令被取出来为止，这一点是不同于 D-Cache 的。

本站所有文章转发 CSDN 将按侵权追究法律责任，其它情况随意。