第 8 章发射

书内第 230–274 页；PDF 第 242–286 页。原书疑点见校注。

8.1 概述
8.1.1 集中式 VS 分布式
8.1.2 数据捕捉 VS 非数据捕捉
8.1.3 压缩 VS 非压缩
8.2 发射过程的流水线
8.2.1 非数据捕捉结构的流水线
8.2.2 数据捕捉结构的流水线
8.3 分配
8.4 仲裁
8.4.1 1-of-M 的仲裁电路
8.4.2 N-of-M 的仲裁电路
8.5 唤醒
8.5.1 单周期指令的唤醒
8.5.2 多周期指令的唤醒
8.5.3 推测唤醒

8.1 概述

何为 “发射 (issue)”？简单来说，它就是将符合一定条件的指令从发射队列 (Issue Queue) 中选出来，并送到 FU 中执行的过程。对于一个 4-way 的超标量处理器来说，在寄存器重命名阶段每周期可以同时处理四条指令，重命名之后的指令被写到重排序缓存 (ROB) 的同时，也会被写到发射队列中，此时已经到达了超标量流水线的发射 (issue) 阶段，而发射队列正是这个流水段的关键部件。发射队列也可以叫做保留站 (Reservation Station,RS),不同的设计中称呼不同而已，在书中，统一称为发射队列，简称为 IQ。发射队列会按照一定的规则，选择那些源操作数都已经准备好的指令，将其送到 FU 中执行，这个过程称为发射，对于简单的顺序执行 (in-order) 的处理器，指令按照程序中原始的顺序写到发射队列中，此时发射队列就相当于是一个 FIFO, 只有最旧的那条指令的源操作数都准备好了，这条指令才会被发射，而这条指令如果没有发射，它后面的指令也无法继续发射，因此，这种设计是比较简单的。但是对于乱序执行 (out-of-order) 的超标量处理器来说，只有少数指令，例如 store 指令或分支指令，才会使用这种顺序执行的方法，而对于大多数的指令，都是按照乱序的方式进行发射，这种方式的设计难度相对是比较大的，也是本章重点介绍的内容。

指令到了发射队列中之后，就不会再按照程序中指定的顺序在处理器中流动，只要发射队列中的一条指令的操作数都准备好了，且满足了发射的条件 ( 具体的条件将在本章进行介绍 ),就可以送到相应的 FU 中去执行。因此，发射队列的作用就是使用硬件保存一定数量的指令，然后从这些指令中找出可以执行的指令，而不管指令之间原始的顺序，这就是指令的乱序执行，正是由于发射队列在这个过程中起到了关键的作用，因此它设计的好坏直接决定着处理器能够获得的并行度。在超标量处理器的流水线中，发射阶段的硬件比较复杂，一般它的时序都处于处理器当中的关键路径上 ^[32]，直接影响着处理器的周期时间，这个阶段的设计需要一定的折中，才能够在性能和复杂度之间找到一个可以接受的平衡点。

从发射阶段的作用可以看出，它是处理器从顺序执行转到乱序执行的分界线，在发射阶段之前的所有指令都在流水线中按照程序中指定的顺序流动，而在发射阶段之后，所有的指令都是乱序执行的，直到流水线最后的提交 (Commit) 阶段，才利用重排序缓存 (ROB) 将这些指令又拉回到程序中指定的原始顺序。

实际上，发射阶段是由一系列的硬件组成的，除了上面所说的发射队列用来存储所有等待调度的指令之外，还包括其他的一些部件，如图 8.1 所示。

图 8.1 发射 (issue) 阶段的执行过程

图 8.1 给出了流水线的发射阶段的执行过程，以及所涉及到的一些重要的部件，包括以下几个。

(1) 发射队列 (Issue Queue),用来存储已经被寄存器重命名，但是没有被送到 FU 执行的指令，通常也被称为保留站 (Reservation Station) ^[33]；

(2) 分配 (Allocation) 电路，用来从发射队列中找到空闲的空间，将寄存器重命名之后的指令存储到其中，不同的发射队列的设计方法，会直接影响这部分电路的实现，在后文会进行详细的介绍；

(3) 选择 (Select) 电路，也称为仲裁 (Arbiter) 电路，如果在发射队列中存在多条指令的操作数都已经准备好了，那么这个电路会按照一定的规则，从其中找出最合适的指令，送到 FU 中去执行，这部分电路是发射阶段比较关键的部分，会直接影响整个处理器的执行效率；

(4) 唤醒 (Wake-up) 电路，当一条指令经过 FU 执行而得到结果数据时，会将其通知给发射队列中所有等待这个数据的指令，这些指令中对应的源寄存器就会被设置为有效的状态，这个过程就是唤醒。如果发射队列中一条指令的所有源操作数都有效了，则这个指令就处于准备好 (ready) 的状态，可以向选择电路发出申请。

以图 8.1 为例，发射队列中存储着 A～G 这七条指令，指令 A 和 B 都已经处于准备好的状态，经过选择电路的仲裁，选择指令 B 送到 FU 中进行运算，它运算完成后，会将发射队列中和 B 指令的结果寄存器相同的所有源寄存器 (位于指令 C 和 D 中 ) 也置为有效，这样就将相关的指令进行了唤醒。

发射阶段的实现有很多种方式，而位于这个阶段中心位置的部件就是发射队列，它的实现方式直接决定了整个发射阶段的实现方式，它可以设计成集中式 (Centralized),也可以设计成分布式 (Distributed); 可以设计成压缩的方式 (Compressing),也可以设计成非压缩的方式 (Non-compressing); 可以设计成数据捕捉的方式 (Data-capture),也可以设计成非数据捕捉的方式 (Non-data-capture)。这些结构都正交的，它们之间可以互相组合，也就是说，发射队列可以设计成集中式，数据捕捉并且采用压缩方式，也可以设计成分布式、非数据捕捉并且采用非压缩方式，具体采用何种方式取决于处理器架构的设计。

8.1.1 集中式 VS 分布式

在超标量处理器中，为了并行执行指令，一般都有很多的 FU, 例如有些 FU 负责整数的加减，有些 FU 负责存储器访问，有些 FU 负责乘除法运算等。如果所有的这些 FU 都共用一个发射队列，称这种结构为集中式的发射队列 (Centralized Issue Queue,CIQ); 而如果每个 FU 都有一个单独的发射队列，称这种结构为分布式的发射队列 (Distributed Issue Queue, DIQ)。

CIQ 因为要负责存储所有 FU 的指令，所以它的容量需要很大，这种设计有着最大的利用效率，不浪费发射队列中的每一个空间，但是会使选择电路和唤醒电路变得比较复杂，因为需要从数量庞大的指令中选择出几条可以被执行的指令 (个数取决于每周期最多可以同时执行的指令个数，这个值通常称为 Issue Width),这些被选中的指令还需要将发射队列中所有相关的指令都进行唤醒，这都增加了选择电路和唤醒电路的面积和延迟。

DIQ 的设计方式，为每一个 FU 都配备一个发射队列，所以每个发射队列的容量可以很少，这样就大大简化了选择电路的设计 (每个发射队列都对应一个选择电路 )。但是当一个发射队列已经满了时，即使其他的发射队列中还有空间，也不能够继续向其中写入新的指令，此时就需要将发射阶段之前的所有流水线都暂停，直到这个发射队列中有空闲的空间为止。例如一段时间内执行了大量的加减法指令，则很可能因为加减法运算的 FU 对应的发射队列已经满了而无法继续接收新的加减法指令，这会阻碍这些指令的寄存器重命名，使后续的所有指令都无法继续通过寄存器重命名阶段 (指令需要按照程序中指定的顺序通过寄存器重命名阶段 )。即使此时其他 FU 的发射队列中还存在空间，也需要将发射阶段之前的流水线都暂停，这样就造成了发射队列利用效率的低下，而且，由于它的分布比较分散，进行唤醒操作时所需要的布线复杂度也随之上升。

正因为这两种方式各有优缺点，现代的处理器一般都结合使用上述的两种方法，使某几个 FU 共同使用一个发射队列，这也算是一种折中的方法，具体将哪些 FU 共用一个发射队列，是和指令集、设计目标等相关的，这属于处理器架构设计的内容。

8.1.2 数据捕捉 VS 非数据捕捉

对于超标量处理器来说，还需要考虑一个重要的事情，就是在流水线的哪个阶段读取寄存器的值，它直接决定了处理器中其他一些部件的设计。事实上，何时读取寄存器的值，这个事情对于整个处理器的架构都有着直接的影响，一般来说，有两个时间点都可以进行寄存器的读取，它们对应着两种实现方法。

(1) 在流水线的发射阶段之前读取寄存器，这种方法也称为数据捕捉 (Data-capture) 的结构，在这样的设计中，被寄存器重命名之后的指令会首先读取物理寄存器堆 (Physical Register File),然后将读取到的值随着指令一起写入发射队列中。如果有些寄存器的值还没有被计算出来，则会将寄存器的编号写到发射队列中，以供唤醒 (wake-up) 的过程使用，它会被标记为当前无法获得 (non-available) 的状态，这些寄存器都会在之后的时间通过旁路网络 (bypassing network) 得到它们的值，不需要再访问物理寄存器堆。在发射队列中，存储指令操作数的地方称为 payload RAM, 如图 8.2 所示。

图 8.2 使用 payload RAM 来存储发射队列中的源操作数

从图 8.2 中可以看到，在 payload RAM 存储了指令源操作数的值，当指令从发射队列中被仲裁电路选中时，就可以直接从 payload RAM 中对应的地方将源操作数读取出来，并送到 FU 中去执行。当一条指令从发射队列中被选中的同时，它会将目的寄存器的编号值进行广播，发射队列中其他的指令都会将自身的源寄存器编号和这个广播的编号值进行比较，一旦发现相等的情况，则在 payload RAM 对应的位置进行标记，当那条被选中的指令在 FU 中计算完毕时，就会将它的结果写到 payload RAM 这些对应的位置中，这是通过旁路网络 (bypassing network) 来实现的。这种方式就像是 payload RAM 在 “捕捉”FU 计算的结果，所以称为数据捕捉 (data-capture) 结构，发射队列负责比较寄存器的编号值是否相等，而 payload RAM 负责存储源操作数，并“捕捉”对应 FU 的结果。

在超标量处理器中，用 machine width 来标记每周期实际可以解码和重命名的指令个数，而用 issue width 来标记每周期最多可以在 FU 中并行执行的指令个数 ( 也就是每周期最多可以发射的指令个数 )。在一般的 CISC 处理器中，在处理器内部将一条 CISC 指令转化为几条 RISC 指令，而存储到发射队列中的是 RISC 指令，只有使 issue width 大于 machine width, 才能够使处理器的流水线比较平衡，避免出现 “ 进的多，出的少 ” 的情况；而在 RISC 处理器中，一般情况下这两个值都是相等的，但是考虑到由于指令之间存在相关性等原因，在超标量处理器中，即使每周期可以解码和重命名四条指令，在很多时候，也并不能得到每周期将四条指令送到 FU 中执行的这种效果。因此，只有使 issue width 大于 machine width, 才能够最大限度地寻找在 FU 中可以并行执行的指令，所以现代的高性能处理器都会采用很多个 FU,使每周期可以并行执行的指令个数 (也就是每周期可以发射的指令个数 ) 尽可能得多。

因为这种方法在流水线的发射阶段之前读取物理寄存器堆 (Physical Register File),所以物理寄存器堆需要的读端口的个数是 “$\mathrm{machine\ width}\times2$”( 假设每条指令只有两个源操作数 ),是直接和 machine width 相关的，这种方法的整个过程如图 8.3 所示。

图 8.3 在流水线的发射阶段之前读取物理寄存器堆

(2) 在流水线的发射阶段之后读取物理寄存器堆，这种方法也称为非数据捕捉 (Non-data-capture) 结构，在这样的设计中，被重命名之后的指令不会去读取物理寄存器堆，而是直接将源寄存器的编号放到发射队列中，当指令从发射队列中被选中时，会使用这个源寄存器的编号来读取物理寄存器堆，将读取的值送到 FU 中去执行。由于在发射队列中不需要存储源操作数的 payload RAM 了，所以它可以被“瘦身”, 也就增加了处理的速度。

由于指令在发射之后才会读取物理寄存器堆，所以寄存器堆需要的读端口个数是 $\mathrm{issue\ width}\times2$, 是直接和 issue width 直接相关的，因为这个值一般都比较大，所以这种方法对于寄存器堆的读端口个数的需求会更多一些，图 8.4 表示了这种方法的工作流程。

图 8.4 在流水线的发射阶段之后读取物理寄存器堆

通过上面的介绍可以看出，在流水线的发射阶段之前读取寄存器的这种方式，所需要的寄存器堆的读端口个数会比较少，但是由于需要在发射队列中存储操作数，所以发射队列所占用的面积会更大一些。而且，在这种方法中，很多源操作数都需要经历两次读和一次写的过程，即从寄存器中读取出来，写到发射队列中，然后再从发射队列中读取出来送到 FU 中执行，很显然，这会消耗更多的能量，不利于实现低功耗的处理器。而采用在流水线的发射阶段之后读取寄存器的方式，需要寄存器堆有着更多的读端口，但是在发射队列中不再需要存储源操作数，所以发射队列在面积和速度方面会好一些，源操作数也只需要读取一次就可以了，因此相比于另一种方法，它的功耗会低一些。这两种方法各有利弊，在现代的处理器中都有使用，如 Intel 的 P6 架构采用了方法一，而 MIPS R10000 和 Alpha 21264 等处理器则采用了方法二。

事实上，这两种方法的取舍直接决定了寄存器重命名的实现方式，当使用重排序缓存 (ROB) 进行寄存器重命名时，一般都会配合使用数据捕捉的发射方式，因为在这种方法中，指令在顺利地离开流水线的时候 (也就是退休的时候 ), 需要将它的结果从重排序缓存中搬移到 ARF 中，采用数据捕捉的方式可以不用关心这种指令结果的位置变化，而如果采用非数据捕捉的方式，指令结果的位置变化会带来很麻烦的事情，这样等于是人为地增加了不必要的设计复杂度，并不是一个明智的做法。

8.1.3 压缩 VS 非压缩

根据发射队列的工作方式，又可以将其分为压缩 (Compressing) 和非压缩 (Non-compressing) 两种结构，这两种结构直接决定了发射阶段的其他部件设计的难易，也影响着处理器的功耗。

(1) 压缩的发射队列 (Compressing Issue Queue)

图 8.5 压缩方式的发射队列的工作原理

这种方法如图 8.5 所示，每当一条指令被选中而离开发射队列时，会出现一个 “空隙”，这条指令上面所有的指令都会下移一格，将刚才那条指令的 “空隙”填上。想象一下，有 $m$ 本一模一样的书，一本压一本地放到桌子上，当从其中抽出某本书时，这本书上面的书都会下移，此时整体上这摞书的高度下降了，但是在这摞书中间并没有空隙。再看图 8.5 中的发射队列，想象有一个东西在向下压它，当一条指令离开而导致发射队列中出现空闲的空间时，在下压力的作用下，那个空闲的空间就会被 “挤走”, 这样发射队列当中所有的指令又都是紧紧地靠在一起了。而且发射队列当中的这些指令，从上往下看，是按照 “最新→最旧” 的顺序排列的，新来的指令会从发射队列上面的空闲空间开始写入。

在图 8.5 中，当指令 D 被选中而离开时，在发射队列中就会出现空闲的位置，经过压缩之后，这个空闲的位置会被 “挤掉”, 这样所有的指令又都靠在一起了，这就是压缩方式的发射队列。通过这种方式，可以保证空闲的空间都是处于发射队列的上部，此时只需要将重命名之后的指令写到发射队列的上部即可，例如图 8.5 中的指令 J 和指令 I。

要实现这种压缩的方式，需要发射队列中每个表项 (entry) 的内容都能够移动到其下面的表项中，因此需要在每个表项前加入多路选择器，用来从其上面的表项 (压缩时 ) 或自身 (不压缩时 ) 选择一个，如图 8.6 所示。

图 8.6 表示了每周期能够 “压缩”一个表项的发射队列的示意图，当然，如果发射队列每周期可以压缩两个表项，则每个表项的内容有三个来源，即上上面的表项、上面的表项以及自身，因此需要更多的多路选择器和布线资源，如图 8.7 所示。

图 8.6 每周期可以压缩一个表项的发射队列

图 8.7 每周期可以压缩两个表项的发射队列

而且，每周期从发射队列中离开的两条指令不是靠在一起时 (这种情况很常见 ),例如图 8.7 中指令 B 和指令 D 同时被选中而离开了发射队列，则在压缩时，指令 C 需要向下移动一个格，而指令 E需要向下移动两个格，因此还需要对不同表项的多路选择器产生不同的控制信号，这样也显著地增加了设计的复杂度。

当然，这种压缩的设计方法，一个比较大的优点就是其选择 (select) 电路比较简单，为了保证处理器可以最大限度地并行执行指令，一般都从所有准备好的指令中优先选择最旧 (oldest) 的指令送到 FU 中执行，这也称为 oldest-first 方法，而这种压缩方式的发射队列已经很自然地按照 “最新→最旧” 的顺序将指令排列好了，因此只需要简单地使用优先级编码器进行选择即可。如图 8.8 所示为每周期从压缩方式的发射队列中按照 oldest-first 的方式选择一条指令的示意图。

从图 8.8 可以看出，发射队列中每条指令发出的请求信号都受到它之前指令的影响，只有比它旧的所有指令都没有被选中时，这条指令才有被选中的资格，通过图 8.8 所示的与逻辑可以实现这个功能；如果有任何一条指令在当前周期被选中了，则比它新的所有指令都不能够在本周期被选中，这样就按照 oldest-first 的原则，从发射队列的所有指令中选择一条最合适的指令送到FU 中执行。

图 8.8 从压缩方式的发射队列中，按照 oldest-first 的方式选择指令

从图 8.8 可以看出，这样的设计方法，它的延迟和发射队列的容量是成正比的，发射队列中可以容纳的指令个数越多，延迟也就越大。图 8.8 中的虚线部分即表示了选择电路最长的路径，可以想象，当使用集中式的发射队列 (CIQ) 时，由于它的容量很大，所以选择电路的延迟会很大，这对于处理器的周期时间会带来很大的负面影响。

因此，总结起来，这种压缩方式的发射队列的优点如下。

① 分配 (allocation) 电路很简单，发射队列中的空闲空间总是处于上部，只需要使用发射队列的写指针，指向当前第一个空闲的空间即可。

② 选择 (select) 电路简单，因为这种方法已经使发射队列中的指令从下到上按照 “最新→最旧” 的顺序排列好了，此时很容易用优先级编码器 (priory encoder) 来从所有准备好的指令当中，找出最旧的那条指令，这样很容易实现 oldest-first 功能的选择电路。一般来说，在发射队列中最旧的指令，和它存在先写后读 (RAW) 相关性的指令也是最多的，先使这条最旧的指令送到 FU 中执行，可以最大限度地释放所有和它存在 RAW 相关性的指令，这样可以提高指令执行的并行度。

但是，这种方法的缺点也是很明显的。

① 实现起来比较浪费硅片面积，例如一个发射队列对应两个 FU 时，每周期要从中选择两条指令送到 FU 中执行，则发射队列需要支持最多两个表项 (entry) 的压缩，这需要复杂的多路选择器和大量的布线资源，增加了硬件的复杂度。

② 功耗大，因为每周期都要将发射队列当中的很多指令进行移动，相当于 “牵一发而动全身”, 这显然增大了功耗。

(2) 非压缩的发射队列 (Non-Compressing Issue Queue)

在这种方法中，顾名思义，就是每当有指令离开发射队列的时候，发射队列中其他的指令不会进行移动，而是继续停留在原来的位置，此时就没有了 “压缩”的过程。可以想象，在这种方法中，空闲空间在发射队列中的分布将是没有规律的，它可以位于发射队列中的任何位置，因此发射队列当中的指令将不再有 “最新→最旧”的顺序，不能够根据指令的位置来判断指令的新旧。当然，此时仍可以使用上面方法中使用的选择电路，从发射队列中最下面的指令开始寻找，直到遇到第一条准备好的指令为止，但是这种选择电路对于非压缩结构的发射队列来说，相当于是一种随机的选择，因为此时指令的年龄信息和它在发射队列中的位置是没有关系的。当然这种基于位置的选择电路实现起来很简单，也不会产生错误，但是由于没有实现 oldest-first 的功能，所以没有办法获得最好的性能。

图 8.9 以一个例子来解释这两种结构的发射队列的区别。

图 8.9 两种结构的发射队列的区别

在图 8.9 所示的两种发射队列中，都根据指令在发射队列中的位置对其进行选择 ( 称为 position based select),图 8.9(a) 的发射队列采用了压缩的结构，每次总是能保证选中最旧的指令，新来的指令只需要从发射队列的上部写入就可以了，如指令 E所示；图 8.9(b) 的发射队列采用了非压缩的结构，此时本质上是一种随机的选择，不能保证选中最旧的指令，新来的指令需要从发射队列中找到一个空闲的位置，例如指令 E。当然，这只是找到一个空闲的位置，相对还是比较容易的，当每周期需要找到几个空闲的位置时，实现起来就不是那么容易了。

总结起来，采用非压缩的发射队列，优点是其中的指令不再需要每个周期都移动，这样大大减少了功耗，也减少了多路选择器和布线的面积。当然这种方法的缺点也是很明显的，分别如下。

(1) 要实现 oldest-first 功能的选择电路，就需要使用更复杂的逻辑电路，这会产生更大的延迟；

(2) 分配 (allocation) 电路也变得比较复杂，无法像压缩方法中那样直接将指令写入到发射队列的上部即可，而是需要扫描发射队列中所有的空间，尤其是当每周期需要将几条指令写入时，需要更复杂的电路来实现这个功能。

这两种结构的发射队列各有优缺点，在现实世界的超标量处理器中也都有使用，例如 Alpha 21264 处理器采用了压缩结构的发射队列，而 MIPS R10000 处理器采用了非压缩结构的发射队列。

8.2 发射过程的流水线

8.2.1 非数据捕捉结构的流水线

进入到发射队列 (Issue Queue) 当中的一条指令要被 FU 执行，必须要等到下述几个条件都成立。

(1) 这条指令所有的源操作数都准备好了；

(2) 这条指令能够从发射队列中被选中，即需要经过仲裁电路的允许才能够进行发射；

(3) 需要能够从寄存器、payload RAM 或者旁路网络 (bypassing network) 中获得源操作数的值。

只有上述的三个条件都满足了，一条指令才会真正进入到 FU 中被执行，这三个条件是顺序发生的，对于一个源寄存器来说，如果它被写到发射队列中的时候，还处于没准备好的状态 (not ready),等到之后的某个时间，它变为了准备好的状态，这个过程就称为唤醒 (wake-up),这需要通过旁路网络才可以通知到发射队列中的每个源寄存器。唤醒的过程可以很简单，也可以很复杂，最简单的方法就是当一条指令在 FU 中得到结果时，将发射队列中使用这条指令计算结果的所有源寄存器都置为准备好的状态，这个过程如图 8.10 所示。

图 8.10 等到指令的结果被计算出来，才进行唤醒操作

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

在图 8.10 中，发射 (issue) 过程被分为了唤醒 (Wake-up) 和仲裁 (Select) 两个流水线阶段，在唤醒阶段，发射队列中的所有相关的寄存器会被置为准备好的状态，而在仲裁阶段，会使用仲裁电路从发射队列中选择一条最合适的指令送到 FU 中，这是发射过程最典型的流水线划分。从图 8.10 可以看出，两条存在先写后读 (RAW) 相关性的指令，不能获得背靠背的执行，它们的执行之间相差了三个周期，这样的执行效率显然还不是最高的。

其实，这种在指令执行完之后才对相关的指令进行唤醒的方法正是 tomasulo 算法 ^[36]，早在 20 世纪六七十年代已经在 IBM 的处理器中采用了，这种方法也是现代超标量处理器的基础。为了能够获得更高的性能，一般都会对上述的方法进行改进，将唤醒的过程进行提前，最终可以背靠背地执行上述两条存在 RAW 相关性的指令，如图 8.11 所示。

图 8.11 背靠背地执行两条存在 RAW 相关性的相邻指令

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

通过处理器中的旁路网络 (bypassing network),能够使唤醒的过程提前。在图 8.11 中，指令 A 在被仲裁电路选中后，在当前周期就会将发射队列中和指令 A 的目的寄存器相等的所有源寄存器都进行唤醒，将它们置为准备好 (ready) 的状态。假设此时指令 B 由于它的源寄存器被唤醒而可以向仲裁电路发出申请，并在下个周期被仲裁电路选中，当然，此时由于指令 A 还没有计算完成，指令 B 是无法从寄存器中读取到源操作数的，这没有问题，为什么呢？因为当指令 B 到达执行阶段 (execute) 的时候，可以从旁路网络中得到指令 A 的结果，此时指令 B 就可以顺利地进入到 FU 中执行了。

其实，在图 8.11 中，简化了一些东西，通过仔细观察可以知道，在同一个周期内执行的仲裁 (select) 和唤醒 (wake-up) 这两个操作是串行的。只有当仲裁电路选出可以发射的指令后，才可以对发射队列中相关的源寄存器进行唤醒，而只有当这两个步骤 (仲裁和唤醒 ) 在一个周期之内完成时，才可以背靠背地执行两条存在 RAW 相关性的指令，一个比较接近现实的流水线画法如图 8.12 所示。

图 8.12 比较接近现实的流水线——仲裁和唤醒是串行的

指令 A: add r1, r2, r3
指令 B: add r5, r1, r4
指令 C: add r7, r5, r6

在图 8.12 中，指令 A、B 和 C 依次存在先写后读 (RAW) 的相关性，通过将一条指令的仲裁 (select) 和唤醒 (wake-up) 两个操作放在一个周期之内完成，可以使这三条指令背靠背地执行。这里需要注意的是上述的这个过程，是在一个周期之内先使用仲裁电路从发射队列中选择出一条合适的指令 (这是仲裁阶段的工作 ),然后再将发射队列中相关的寄存器置为准备好的状态 (这是唤醒阶段的工作 ), 这里是有先后顺序的，发射队列中被唤醒的指令将在下个周期才参与仲裁电路的选择操作。图 8.13 所给出的仲裁和唤醒这两个操作在某些文献中称为“原子的”，只有将它们放到一个周期之内执行，才可以使存在先写后读 (RAW) 相关性的指令背靠背地执行。如果，将这两个操作 (仲裁和唤醒 ) 分布在两个周期完成，如图 8.13 所示。

图 8.13 将一条指令的仲裁和唤醒放在两个周期完成的流水线示意图

在图 8.13 所示的这种设计中，指令 A 在被仲裁电路选中之后的下个周期才对发射队列中相关的寄存器进行唤醒操作，使用指令 A 的结果作为源操作数的指令 B 需要在发射队列中等待一个周期，才可以被唤醒。由图 8.13 可以看出，指令 B 的执行和指令 A 的执行相差了一个周期，并没有连续地背靠背执行。因此，要想使存在先写后读 (RAW) 相关性的相邻指令可以背靠背地执行，就必须使流水线的仲裁 (Select) 和唤醒 (Wake-up) 两个操作在一个周期内完成，组成一个 “原子操作”。

因为仲裁电路和唤醒电路都是相对比较复杂的，将它们放在一个周期内执行，肯定会使时钟周期变长，从而使处理器的频率变低；而将这两个电路分开在两个周期的做法可以减少对时钟周期的负面影响，提高了处理器的频率，但是会影响超标量处理器每周期可以并行执行的指令个数 ( 这在计算机中用 IPC 来衡量 )。文献研究表明 ^[34][35],将流水线的仲裁 (Select) 和唤醒 (Wake-up) 这两个过程分开在两个周期之后，IPC 大约下降 10%～15%,下面通过计算来分析这种变化所带来的影响。

假设当流水线中的仲裁和唤醒这两个操作在一个周期内完成时，处理器的频率是 1GHz, 对应着时钟周期是 1ns, 并假设超标量处理器每周期可以最多执行两条指令，也就是 IPC 为 2( 理想情况 ), 则每秒执行的指令个数为 $1\mathrm{GHz}\times2=2\times10^9$,如图 8.14 所示。

图 8.14 理想情况时，每秒执行的指令个数是 2BIPS

理想情况下，假设将仲裁和唤醒这两个操作分开在两个周期执行后，处理器的频率提升了一倍，变为 2GHz,IPC 下降了 15%, 变为了 $2\times85\%=1.7$, 则在这种理想的情况下，每秒执行的指令个数为 $2\mathrm{GHz}\times1.7=3.4\times10^9$。

一切看起来很完美，速度提升了 $(3.4-2)/2=85\%$！

但是考虑到寄存器的建立时间 (setup time) 和保持时间 (hold time) 的要求，实际上当处理器的频率是 1GHz 时，每个时钟周期内留给逻辑电路的时间是小于 1ns 的，假设为 900ps，则将仲裁和唤醒操作放到两个周期之后，理想的情况是图 8.15 所示的样子。

图 8.15 将仲裁和唤醒分开在两个周期的理想时序

而在实际当中，再考虑到流水线划分不可能做到完全的平均，实际情况可能是图 8.16 所示的样子。

图 8.16 将仲裁和唤醒分开在两个周期的现实时序

此时，每秒执行的指令个数为 $1.5\mathrm{GHz}\times1.7=2.55\times10^9$，速度的提升变为 $(2.55-2)/2=27.5\%$。

这并不是说，处理器就绝对可以获得 27.5%的速度提升，在实际当中，由于增加了一级流水线，在提高了处理器频率的同时，还会带来如下的一些负面的影响。

(1) 分支预测失败时，惩罚 (mis-prediction penalty) 增加；

(2) Cache 访问的周期数增加 (Cache 访问需要的时间是固定的，周期时间变小，则需要的周期数就变多了 );

(3) 考虑到处理器的功耗可以表示为 $P=(1/2)CV^2f$，增加了一级流水线，会导致处理器需要更多的门数，使电容 C 变大，而且频率 $f$ 更快，这些都会导致功耗增大。

到目前为止，上面的所有描述，都假设一条指令在 FU 中只需要一个周期就可以得到结果，而在实际的超标量处理器中，存在多个 FU, 每个 FU 的执行时间都是不同的，即使是同一个 FU,对不同的指令所需要的执行时间也不一定相同，例如很多处理器的乘法器都可以提前将 16 位的乘法结果进行输出。当一条指令在 FU 中无法在一个周期内完成时，对应着流水线的执行 (execute) 阶段也需要占用多于一个周期的时间，此时上述的方法就不能够起作用了，如图 8.17 所示。

图 8.17 如果指令 A 马上进行唤醒操作，会导致指令 B 无法在执行阶段得到操作数

指令 A: mul r1, r2, r3  // 2 cycles latency
指令 B: add r5, r1, r4

由于指令 A 是乘法操作，假设在 FU 中需要两个周期才可以得到结果，如果仍按照上面所述的方式，在指令 A 被仲裁电路选中的那个周期就对发射队列 (Issue Queue) 中相关的寄存器进行唤醒操作，则指令 B 在到达 FU 中要执行的时候，指令 A 还没有将结果计算出来，此时指令 B 就不能够执行了。也就是说，指令 B 的唤醒早了一个周期。造成这种现象的原因是什么呢？这是由于指令 A 需要两个周期才能得到结果，当指令 A 被仲裁电路选中后，马上将指令 B 进行唤醒是不对的，需要将这个唤醒的过程延迟一个周期，这样才可以使指令 B 在到达 FU 的时候，正好可以从旁路网络 (bypassing network) 得到指令 A 的结果，

如图 8.18 所示。

图 8.18 将指令 A 的唤醒操作延迟一个周期

当然，事情远没有结束，在一般的指令集中，不同的指令需要的执行周期数是不一样的，普通的加减法、逻辑运算等比较简单的操作，需要一个周期就可以了，而乘除法这样的操作需要多个周期，还有比较特殊的 load 操作，其执行的周期数取决于 D-Cache( 或 Store Buffer) 是否命中等，对这些情况都需要进行处理，这样才可以使流水线顺利地流动，在本章的后文中会对如何处理这些情况进行详细的介绍。

8.2.2 数据捕捉结构的流水线

这种结构相比于上一种方法，最大的不同就是它在发射队列中采用了 payload RAM 来存储所有指令的源操作数，这样当指令离开发射队列的时候，可以直接得到操作数，而不需要再去读取物理寄存器堆 (Physical Register File),图 8.19 表示了采用数据捕捉结构 (data-capture) 的流水线。

图 8.19 数据捕捉结构的流水线

指令 A: add r1, r2, r3
指令 B: add r5, r1, 8
指令 C: add r7, r5, r1

这种设计的流水线和 8.2.1 节是类似的，发射过程也需要分为仲裁 (Select) 和唤醒 (Wake-up) 两个流水段，只不过指令在被仲裁电路选中之后，不需要去读取物理寄存器了，而是直接读取 payload RAM 即可以得到操作数。图 8.19 表示了一种可能的流水线设计，在指令被仲裁电路选中之后，在同一个周期也会对发射队列中其他的指令进行唤醒，同时还会去读取 payload RAM, 这两个操作是并行进行的，在本周期末就可以得到指令的所有源操作数，这样在下个周期就可以送到 FU 中执行。当然，不一定所有的指令都会从 payload RAM 中获得操作数，例如图 8.19 中的指令 B, 为了获得背靠背的执行，指令 B 必须要通过旁路网络 (bypassing network) 才可以得到指令 A 的结果；至于指令 C 在读取 payload RAM 的时候，指令 A 已经将结果写到其中了，所以指令 C 直接可以通过 payload RAM 得到指令 A 的结果。

图 8.19 中将指令的选择和读取 payload RAM 放到了一个流水段，在这个阶段还负责将 FU 的计算结果 “捕捉”到 payload RAM 中，很显然在这个周期做了很多事情，尤其是这个周期需要对 payload RAM 既进行读取、又进行写入，这个多端口的 payload RAM 会导致处理器的周期时间变得过大。同时，当 FU 的个数比较多时，FU 结果的旁路网络也会占用不菲的硬件资源和过多的时间，因此可以进一步对流水线进行细分，如图 8.20 所示。

为了保持相关指令之间可以背靠背地执行，仍然将仲裁 (Select) 和唤醒 (Wake-up) 两个操作放在一个周期内完成，因为多端口的 payload RAM 占据了过多的时间，因此将其单独放到一个流水段中，指令被仲裁电路选中之后，将发射队列中相关的所有寄存器都进行唤醒，然后在下一个周期进行 payload RAM 的读取。由于将其放在了单独的一个流水段，所以它对处理器的周期时间的影响小了很多。源操作数从 payload RAM 读取出来之后，在下个周期就可以送到 FU 中执行了，指令的结果在 FU 中被计算出来之后，并不会在当前周期马上进行旁路 (bypass),而是将旁路的过程放到下一个流水段，在流水线的旁路 (bypass) 阶段，FU 的结果会被送到 payload RAM 和 FU 的输入端。从图 8.20 可以看出，由于指令 C 的操作数来自于指令 A 和 B, 因此只有等到指令 A 和 B 都将指令 C 进行唤醒之后，指令 C 才可以向仲裁电路发出申请，从而被选中，然后通过旁路网络获得两个操作数。

一些更激进的流水线可能会把图 8.20 中的仲裁 (Select) 和唤醒 (Wake-up) 这两个操作放到两个周期，这样可以进一步减少处理器的周期时间，但是带来的代价就是相关指令之间不能背靠背地执行了，这会对处理器最大可以获得的并行度产生一定的负面影响，具体在现实中如何设计这部分流水线，需要根据实际的需求来决定。

图 8.20 数据捕捉结构的另一种流水线设计

指令 A: add r1, r2, r3
指令 B: add r5, r1, 8
指令 C: add r7, r5, r1

8.3 分配

当采用了非压缩 (non-compressing) 的方式来设计发射队列时，此时发射队列中的空闲空间是没有规律的，零散的分布在发射队列中，对于每周期可以解码和重命名四条指令的超标量处理器来说，最理想的状态就是每周期能够从发射队列当中找到四个空闲的表项 (entry),这需要分配电路能够 “扫描”整个发射队列，找到四个空闲的表项并将四条指令写入，如图 8.21 所示。

在图 8.21 中，发射队列的分配电路 (IQ Allocator) 会扫描发射队列中每个表项的空闲标志信号 (在图 8.21 中是 free),从中找出四个空闲的表项，这个过程类似于之前讲过的对 LDM/STM 指令的寄存器列表 (register_list) 的处理，可以采用拆分的方法，从发射队列中并行地找到四个空闲的表项，将重命名之后的指令写入到其中，尽管查找四个空闲表项的过程是并行进行的，但是仍旧需要一段时间才可以完成 (在前文讲过，这需要三级处理电路的延迟 )。其实，整个分配过程所需要的时间是和发射队列的容量，以及每周期需要写入的指令个数等成正比的。

图 8.21 需要从发射队列中找到四个空闲的位置

为了更快地在一个周期内完成上述查找的过程，可以借鉴寄存器重命名过程中使用的空闲列表 (free list) 的设计方法，使用一个表格来记录所有空闲表项的编号，这个表格按照 FIFO 的方式进行管理，这样只需要每周期从这个表格中读出四个编号，就可以完成上述分配电路的任务了。当然，这种方法本身仍具有一定的复杂度，产生的延迟也不会很小，为了提高速度，可以采用一种更折中的方法，例如，如果要在每周期内向发射队列中写入四条指令，可以简单地把发射队列分为四部分，从每部分中找到一个空闲的表项，如图 8.22 所示。

图 8.22 一种折中的方法——将发射队列分成四个段

图 8.22 将一个有着 12 个表项的发射队列分为了四个部分，每个部分称为一个段 (segment),每个段包括三个表项，并为每个段使用一个分配电路，这样每个分配电路只需要从三个表项中找到一个空闲的空间，通过四个分配电路并行工作，就可以实现从这个发射队列中找到四个空闲位置的功能了，整个分配电路的延迟就是每个段对应的分配电路的延迟，这显然是很小的，因为它只需要从三个表项中找到一个空闲的就可以了。

但是这种方法毕竟是一种折中的方法，它的缺点也是很明显的，如果恰好一个段中已经没有空闲的空间了，此时即使其他的段都是空闲的，这个段也不能够接收新的指令，因此整个发射队列也无法在一个周期内写入四条指令了。图 8.23 表示了一种可能的情况，指令 A 所属的那个段没有空闲的空间了，因此指令 A 不能够被写入到发射队列中，即使在它旁边的段中存在空闲的空间，也无济于事。而且，指令在寄存器重命名阶段是按照程序指定的顺序 (in-order) 进行的，指令 A 无法写入发射队列，会导致后面的指令 B、C 和 D 都无法写入到发射队列中，也就是说，在本周期没有一条指令能够写到发射队列中，即使此时在发射队列中有足够的空间来容纳它们。这样显然降低了处理器的性能，需要采取一些措施来避免这种情况的发生，例如可以使用缓存将那些不能写入到发射队列中的指令暂存起来，使它们不至于阻碍后面指令写发射队列的过程，当然这种做法会增加设计的复杂度，需要在实际设计中加以权衡。

图 8.23 指令 A 会阻碍后续指令写入到发射队列中

还需要注意的是，分配电路从电路严格意义上来讲，是处于流水线的分发 (Dispatch) 阶段的，它并不属于发射 (issue) 阶段的内容，但是考虑到它和发射队列的关系比较紧密，因此将其放到了这一章，从流程上来讲，分配 (allocate)、仲裁 (select) 和唤醒 (wake-up) 构成了发射阶段正常工作的三个主要步骤，每个步骤都需要做很多的事情，因此，发射阶段可以称得上是超标量处理器的流水线中任务量比较繁重的过程之一了。

8.4 仲裁

8.4.1 1-of-M 的仲裁电路

采用了非压缩方法设计的发射队列 (Issue Queue) 中，如果使用优先级编码器，依靠位置对指令进行选择，本质上是一种随机的选择方法，并不能获得最优的性能 ^[27]。如果要达到 oldest-first 的仲裁效果，就要采用一些的新措施，而不能简单地根据指令在发射队列中的位置来进行仲裁。

为什么要实现 oldest-first 功能的仲裁呢？这是考虑到越是旧的指令，和它存在相关性的指令也就越多，因此优先执行最旧的指令，则可以唤醒更多的指令，能够有效地提高处理器执行指令的并行度，而且最旧的指令还占据着处理器中其他的资源，例如重排序缓存 (ROB) 和 Store Buffer 等部件，越早地执行这些旧的指令，就可以越早地释放这些硬件资源，供后面的指令使用。

要识别出发射队列中哪些指令是最旧的，就需要知道这些指令的年龄信息，年龄信息即表示指令进入流水线的先后顺序。在普通的顺序执行 (in-order) 的处理器中，指令的年龄信息很容易被追踪，先执行的指令肯定要比它后面的指令要旧；在乱序执行 (out-of-order) 的超标量处理器中，指令在进入发射队列之前都是按照程序中指定的顺序执行的，因此它们的年龄信息容易被追踪，而到了发射队列中之后，这些年龄信息就打乱了，但是在处理器中还有一个地方，按照进入流水线的顺序记录着处理器中的所有指令，这个部件就是重排序缓存 (ROB,关于它的细节，会在后文进行详细说明 ),指令被重命名之后，会按照程序中指定的顺序写到 ROB 中，因此可以使用每条指令在 ROB 中的位置 (也就是寻址 ROB 的地址值 ) 作为这条指令的年龄信息。但是这样做有一个问题，因为 ROB 本质上是一个 FIFO, 因此直接使用它的地址是无法表达出年龄的真实信息的，以 ROB 中包括四个表项 (entry) 的简单例子来说明，如图 8.24 所示。

图 8.24 直接使用指令在 ROB 中的地址，无法表达年龄信息

在图 8.24 中，初始状态时，位于 ROB 底端的地址最小，为 0, 而位于 ROB 顶端的地址最大，为 3。指令从地址 0 开始写入到 ROB 中，因此 ROB 中地址较小的表项 (entry) 中的指令更旧。ROB 的写入由写指针控制，读取受到读指针的控制，因此每条指令在 ROB 中的位置是由写指针分配的，写指针会重复地出现 0、1、2、3, 每次写指针翻转时 (也就是从 3 到 0)，新的写指针值和旧的写指针值即出现了大小的混乱。其实这个问题在 FIFO 中也是存在的，可以采用下面的方法来解决上述问题。

ROB 的写指针和读指针在复位状态时都是指向地址 0, 这是最初始的状态，当有新的指令写入到 ROB 中时，写指针会增加，图 8.24(a) 表示了 ROB 中被写入三条指令后的样子，此时写指针和读指针都处于同一个 “面” 上，谁也没有翻转过，此时的 ROB 中，地址较小的指令会更旧。随着时间的推移，又有两条指令进入了 ROB, 同时 ROB 中也有两条指令离开了，此时写指针发生了翻转，变为了 1, 而读指针没有翻转，变为了 2。如图 8.24(b) 所示，此时 ROB 中地址较小的指令不再是旧的了。随着时间再次推移，ROB 中写入了两条指令，又有三条指令离开了，现在的写指针变为了 3,而读指针变为了 1, 读指针发生了翻转，此时写指针和读指针又都到了一个 “面”上，此时可以看出，ROB 中地址较小的指令会更旧。

通过上面的分析可以知道，写指针和读指针在一个 “面” 上时，可以根据指令在 ROB 中的地址值来判别指令的年龄；而当它们不在一个 “面” 上时，无法直接通过地址值来确定年龄信息，为了解决这个问题，可以在 ROB 的地址前面再加入一位，称为位置值 (position bit)。这样相当于将写指针和读指针都增加了一位，每次当它们 “翻转”时，最高位的位置值也会随之翻转，如图 8.25 所示。

图 8.25 当写指针 / 读指针翻转时，最高位的位置值也会翻转

由于在图 8.25 的 ROB 中，最多只会存在四条指令，因此，如图 8.26 所示的各种情况都是可能存在的。

图 8.26 在 ROB 中各种可能的情况

从图 8.26 可以看出如下的规律。

(1) 位置值 (position bit) 相同时，ROB 的地址值越小，对应的指令越旧；

(2) 位置值 (position bit) 不同时，ROB 的地址值越大，对应的指令越旧。

使用上述两条规律，就可以判断 ROB 中指令的真实年龄信息了，这就为实现 oldest-first 的仲裁电路提供了基础。前文说过，指令在流水线的分发 (Dispatch) 阶段，会将重命名之后的指令写到 ROB 和发射队列中，为了记录下年龄信息，需要将每条指令在 ROB 中的地址值也一并写到发射队列中，这样在发射队列中的每条指令就有了年龄信息，仲裁电路根据这个信息，从所有准备好的指令中找到最旧的那条指令。如果发射队列中有 M 个表项 (entry),这个仲裁电路就称为 1-of-M 的仲裁电路，它按照 oldest-first 的原则实现，这个过程如图 8.27 所示。

图 8.27 1-of-8 的仲裁电路

图 8.27 中的发射队列 (Issue Queue) 有 8 个表项，需要经过 “8→4→2→1” 共三级比较电路才能最终获得最旧的指令对应的地址值，可以观察出，所需比较电路的级数 N 和发射队列中表项的个数 M 之间存在关系 $N=\log_2M$, 因此，如果发射队列的容量很大时，就需要更多的比较器级数，也就是延迟会更大。

当然，图 8.27 所示的仲裁电路只是给出了一个实现的思路，实际当中还需要考虑下面的两个问题。

(1) 如何屏蔽掉发射队列中那些还没有准备好的指令，使这些指令的年龄信息不会对仲裁电路的结果产生影响？

在图 8.27 中，将那些还没有准备好的指令对应的年龄信息置成了无穷大，这样在比较时就可以忽略这些年龄值了，但是在实际电路实现时，没有办法实现真的无穷大，可以采用图 8.28 所示的方式进行。

发射队列中的每条指令都由一位来表示它是否准备好了 (ready 位 ),每次两条指令进行年龄信息的比较时，这两条指令的 ready 位用来控制比较结果的选择。当两个 ready 位都为 1 时，选择年龄信息比较小的那个；当只有一个 ready 位有效时，选择这个 ready 位有效的指令；当两个 ready 位都为 0 时，此时选择哪条指令都是无所谓的，因为比较的结果不会被下一级比较器使用。考虑到两条指令中，只要有一条指令处于准备好的状态，那么就会输出有效的年龄值到下一级比较电路，所以将两条指令的 ready 位相或之后输送到下一级比较电路，用来表示本次比较是否会得到一个有效的结果。每一级的比较电路都是完成相同的工作，直到最后一级比较电路将年龄值最小的那条指令 (也就是最旧的指令 ) 挑选出来。

图 8.28 1-of-M 的仲裁电路的实现原理图

(2) 如何根据仲裁电路挑选出的年龄值，在发射队列中找到对应的指令？

经过上述一系列的比较电路之后，会得到一个最小的年龄值，它对应着最旧的那条指令。如何根据这个年龄值，从发射队列中将对应的指令找出来呢？因为只有找出了这条指令，才可以将其送到 FU 中执行，当然最直接的方法就是将仲裁电路得到的这个年龄值和发射队列中所有指令的年龄值进行比较，即在发射队列中为年龄信息加入 CAM 电路，这样就可以找出最小的年龄值对应的那条指令了。很显然，这样做额外引入了 CAM 电路，增加了处理器的面积和延迟，不是一个很明智的做法。实际上，可以使每条指令在发射队列中的地址这个信息，随着上述的比较过程而流动，上述每一级的比较电路除了将比较小的年龄信息送到下一级比较电路之外，还会将这个年龄值对应的发射队列的地址值也送到下一级的比较电路，这只需要在之前的电路上增加如图 8.29 所示的内容。

图 8.29 使指令在发射队列中的地址也经过仲裁电路

在原来比较电路的基础上，增加对地址的选择电路，增加的部分在图 8.29 中用虚线进行了标记，因为增加的多路选择器和原来选择年龄信息的多路选择器是并行工作的，所以不会对电路的延迟产生负面的影响。

通过上述的方法，可以从表项个数为 M 的发射队列中选择出一条最旧的指令，这就是 1-of-M 的仲裁电路。

8.4.2 N-of-M 的仲裁电路

前文说过，现代的处理器一般都会对发射队列采用集中式和分布式互相折中的方法，使几个 FU 共用一个发射队列，这个发射队列需要在一个周期内为每个 FU 都选择出一条指令，这样就要求它有一个 N-of-M 的仲裁电路 (假设 FU 的个数为 N, 发射队列的容量为 M)。举例来说，如果需要遵循 oldest-first 的方式，每周期从发射队列中选择两条指令，则需要两级仲裁电路，第一级仲裁电路选择一条指令之后，会将这条指令进行标记，这样在第二级仲裁电路中就可以排除掉上一级的影响了，但是这样实现的 2-of-M 的仲裁电路，它的延迟是 1-of-M 的仲裁电路的两倍，当使用这种方式扩展到 N-of-M 的仲裁电路时，会产生很大的延迟，显然无法在实际当中使用。

要设计一种在实际当中可以使用的 N-of-M 的仲裁电路，仍然需要使用折中的方法，在性能、电路面积和速度之间找到一个平衡点，可以采用如图 8.30 所示的方法。

图 8.30 N-of-M 的仲裁电路

图 8.30 中存在四个 FU: ALU0、ALU1、Mul/Div0 和 Mul/Div1,它们共用一个发射队列，发射队列的容量为 M, 每个 FU 都有一个专属的 1-of-M 的仲裁电路。当指令被写到发射队列中的某个表项时，根据这条指令的类型，将这条指令分配给一个对应的 FU, 如果存在功能相同的 FU, 则会按照轮流或者随机的顺序进行分配，这个分配的过程本质上可以通过一个多路分配器 (demultiplexer) 来实现，它将每个表项的 ready 信号根据指令的类型分配给不同的仲裁电路，因为发射队列中的每个表项都有可能存放不同类型的指令，所以每个 FU 的仲裁电路都会有 M 个输入，执行完整的 1-of-M 的仲裁过程，这样，整个 N-of-M 的仲裁电路的延迟就只有 1-of-M 的仲裁电路的延迟了 (多路分配器电路的延迟很小，可以不用考虑 )。

这种设计之所以称为折中的方案，是因为它无法实现理想的 N-of-M 功能，例如图 8.31 所示的例子，本周期在发射队列中有五条已经准备好的指令：SUB、ADD、DIV、MUL 和 LOAD, 但是每个 FU 对应的仲裁电路只能选择一条属于它的指令。所以，经过仲裁电路的选择之后，本周期就只能有一条 SUB 指令、一条 DIV 指令以及一条 LOAD 指令可以被选中，也就是说，本周期只选择了三条指令，由此可见，虽然有五条已经准备好的指令，但是并不能使用图 8.31 所示的 4-of-M 的仲裁电路选出四条指令送到 FU 中执行。

图 8.31 使用 4-of-M 的仲裁电路所遇到的问题

为了解决上面的问题，可以增加 FU 的数量，例如可以使用两个一样的 ALU: ALU0 和 ALU1, 这样设计的初衷就是为了提高指令执行的并行度，但是却又引入了一个新的问题，一个 ALU 类型的指令要分配给两个 ALU 的哪一个呢？

这个问题在图 8.31 的实现方式中，没有一个太完美的答案，可以采用一种轮换分配法，在本周期将所有写入到发射队列中的 ALU 类型的指令，分配给 ALU0; 在下个周期将所有写入到发射队列中的 ALU 类型的指令，分配给 ALU1, 这可以通过一个 1 位的信号来指示当前周期的分配状态，这个 1 位的信号每周期都翻转。当这个信号是 0 时，写入到发射队列中的 ALU 类型的指令属于 ALU0; 当这个信号是 1 时，写入到发射队列中的 ALU 类型的指令属于 ALU1。当然，这种做法也并不能保证严格的 oldest-first 的原则，例如图 8.32 所示的例子。

图 8.32

在图 8.32 中，发射队列最右边的值表示当前指令被分配给哪个 ALU,0 表示分配给 ALU0,1 表示分配给 ALU1。SUB 和 ADD 这两条指令在同一个周期被写入发射队列，分配给了 ALU0; 下个周期的 XOR 和 AND 指令在写入到发射队列时被分配给了 ALU1,再下个周期的 ADD 和 CMP 指令被分配给了 ALU0。在图 8.32(a) 中，有四条指令 (ADD， SUB,AND 和 XOR) 都已经准备好了，它们属于两个仲裁电路，经过选择后，ADD 指令和 AND 指令被选中，而比 AND 指令更旧的 SUB 指令虽然也已经准备好了，却并没有被选中，由此可以看出，这并没有实现严格意义上的 oldest-first 的功能；而图 8.32(b) 中，有三条指令都已经准备好了 (ADD,SUB 和 CMP),但是这三条指令都属于同一个 ALU0, 那么在本周期只有 ADD 指令被选中，虽然此时的 ALU1 也可以用来进行计算，但是却不能被使用，这显然是浪费资源了。

为了避免图 8.32 所示的情况发生，需要更复杂的指令分配算法，这样肯定导致电路面积增大，而且也会对电路的延迟和功耗造成一定的负面影响，找到一种最优化的方法是比较困难的，需要根据实际的需求，在电路面积、速度和执行效率之间进行折中。

对于现代的很多处理器来说，一般最多能够在每周期执行 4～6 条指令，但是处理器所支持的运算的种类是很多的，典型的包括如下运算。

加法／减法 (Add/Sub)
逻辑运算 (Logic)
移位操作 (Shifter)
乘法运算 (Multiply)
除法运算 (Divider)
访问存储器 (Load/Store)
访问协处理器
单指令多数据操作 (SIMD)
浮点加法／减法 (FP Add/FP Sub)
浮点乘法 (FP Mul)
浮点除法 (FP Div)

在处理器每周期最多只能执行 4～6 条指令的情况下，需要将上面所述的运算类型进行合并，使几个运算类型共用一个发射队列，一般来讲，会将加减法、逻辑运算和移位运算合在一个 FU 中，这就传统意义上的 ALU,它们共用一个发射队列；将整数的乘法和除法操作合并在一起；将访问存储器和访问协处理器合并在一起；将所有的浮点运算合并在一起；这就形成了四个比较大的 FU。当然，这只是最简单的情况，在实际的设计中，需要对不同的指令集，甚至是不同的程序进行分析，才能对 FU 进行合理的归类，得到相对优化的分配结果。

在前文中说过，仲裁电路的延迟和发射队列容量的对数值是成正比的，因此当更多的 FU 共用一个发射队列时，这个发射队列的容量也需要相应增加，这样就增大了仲裁电路的延迟；如果使更少的 FU 共用一个发射队列，那么就需要数量更多的发射队列，这时唤醒 (wake-up) 操作就需要更多的布线资源和比较器电路，也就是增大了唤醒电路的延迟和功耗，因此如何配置发射队列的分配情况并没有一个合适的答案，需要根据实际需求，具体的进行分析。

8.5 唤醒

8.5.1 单周期指令的唤醒

在前文已经对唤醒 (wake-up) 的过程进行了简单的介绍，概括来说，唤醒是指被仲裁电路选中的指令将其目的寄存器的编号 (简称为 dst_tag) 和发射队列中所有的源寄存器的编号进行比较，并将那些比较结果相等的源寄存器进行标记的过程 (标记为 ready 状态 )。因为要将被选中指令的目的寄存器的编号送到发射队列当中的所有的地方，当发射队列的容量比较大或者个数比较多时，这个目的寄存器的编号就需要走很长的路。每个仲裁电路都会送出这样一个编号值，发射队列中的每个源寄存器都会和所有仲裁电路送出的编号值进行比较，一般情况下，仲裁电路的个数等于 issue width 的值。

图 8.33 给出了当仲裁电路的个数为四时，发射队列中每个表项 (entry) 的唤醒电路的实现图，为了便于进行描述，假设四个仲裁电路共用一个发射队列，这样发射队列当中的每个表项都需要向四个仲裁电路发出请求信号 (在图 8.33 中称为 Request),同时也会从四个仲裁电路收到四个响应信号 (在图 8.33 中称为 Grant)。当然这四个响应信号中，只有其中的一个是有效的，这个有效的响应信号会将这条指令的目的寄存器编号送到指定的总线上 (在图 8.33 中称为 tag bus),图 8.33 表示了这个过程。

图 8.33 唤醒电路

为了便于说明，图 8.33 只给出了对发射队列当中的一个表项进行唤醒的示意图，其中包括的内容如下。

① ValL: 指令中是否存在第一个源寄存器，如果指令中并没有第一个源寄存器，那么也就不需要对这个源寄存器进行唤醒了。

② SrcL: 指令中的第一个源寄存器的编号。

③ RdyL: 指令中的第一个源寄存器是否已经被唤醒而处于准备好的状态。

④ ValR、SrcR 和 RdyR: 指令中的第二个源寄存器的状态，具体的功能参见 ValL、SrcL 和 RdyL。

⑤ Dest: 目的寄存器的编号。

⑥ Issued: 一条指令被仲裁电路选中后，可能不会马上离开发射队列，因此需要将它进行标记，这样的指令将不会向仲裁电路发出请求信号。

发射队列中的每个表项都会根据四个响应信号的值，将自身的目的寄存器编号送到对应的总线上，每个仲裁电路都会对应一个总线。例如图 8.33 中，四个仲裁电路 (Select0～Select3) 分别对应着四条总线 (Tag bus0～Tag bus3),发射队列中的每个表项都会根据收到的响应信号来决定采取何种动作。

① 收到仲裁电路 0(Select0) 给出的响应信号，表示要将自身的目的寄存器编号送到 tag_bus0；

② 收到仲裁电路 1(Select1) 给出的响应信号，表示要将自身的目的寄存器编号送到 tag_bus1；

③ 收到仲裁电路 2(Select2) 给出的响应信号，表示要将自身的目的寄存器编号送到 tag_bus2；

④ 收到仲裁电路 3(Select3) 给出的响应信号，表示要将自身的目的寄存器编号送到 tag_bus3。

虽然发射队列中的每个表项都会向所有的仲裁电路发出请求信号，但是只有一个请求信号是有效的，因此也只会从一个仲裁电路收到有效的响应信号，否则就无法保证正常的工作流程了。

在图 8.33 所示的例子中，所有的仲裁电路共用了一个发射队列，在实际的设计中，为了提高速度，需要减少发射队列的容量，此时可以使用多个容量更小的发射队列，例如在一个有着四个 FU 的处理器中 (两个 ALU,一个 Mul/Div, 一个 Load/Store),可以使两个 ALU 共用一个发射队列，其他两个 FU 各使用一个发射队列，此时虽然仍旧需要对每个 FU 都使用一个仲裁电路，不能够减少唤醒电路的复杂度，但是由于每个发射队列的容量更少，可以加快仲裁电路的速度，从而在整体上减少仲裁和唤醒两个过程对处理器周期时间的影响。

本节所讲述的唤醒过程是针对单周期的指令来说的，在一个 RISC 指令集中，大部分的 ALU 类型的指令都是单周期的，这样的指令在被仲裁电路选中的当前周期就可以对发射队列中的其他指令进行唤醒，被唤醒的指令可以通过旁路网络 (bypassing network) 获得源操作数，从而实现背靠背的执行，现在对单周期指令的唤醒过程做一个梳理。

第一步：被仲裁电路选中的指令会将它的目的寄存器的编号送到对应的总线上 (tag bus)。

第二步：每一条总线 (tag bus) 上的值会和发射队列中所有指令的源寄存器的编号进行比较，如果发现相等，则将这个源寄存器标记为准备好的状态。

第三步：当发射队列中的某条指令的所有操作数都准备好了，并且还没有被仲裁电路选中过，它就可以向对应的仲裁电路发出请求信号。

第四步：如果仲裁电路发现有更高优先级的指令 (例如年龄更老的指令 ) 也发出了请求信号，则当前的这条指令将不会得到有效的响应信号，这条指令将在下个周期继续向仲裁电路发出请求信号。在这里需要注意的是，在一些设计中，一条指令可以轮流向两个仲裁电路发出请求信号，如果其中一个仲裁电路几次都没有给出响应信号的话，可以将这条指令的请求信号送至另外一个仲裁电路，因为另一个仲裁电路很可能此时是空闲的，这种平衡的算法有时候会起到一定的作用。如果从仲裁电路得到了有效的响应信号，则这个响应信号会将这条指令标记为 “已经被选中”的状态，这条指令在下个周期就不会向仲裁电路继续发送请求信号了。为什么不直接让这条已经被选中的指令马上离开发射队列呢？这是因为一条指令如果使用了 load 指令的结果的话，即使它被仲裁电路选中，也不可以马上离开发射队列，这在后文会有解释。

第五步：发射队列中的这条指令根据收到的响应信号，将它的目的寄存器的编号送到对应的总线上，用来唤醒发射队列中所有相关的源寄存器，同时这条指令就可以送到对应的 FU 执行了。

单周期指令的唤醒过程相对是比较简单的，但是在 RISC 指令集中，很多的指令不能够在一个周期内执行完，例如乘法操作，需要多个周期才可以完成，这种类型指令的唤醒过程需要考虑更多的事情，增加了设计的复杂度。

8.5.2 多周期指令的唤醒

前文说过，一条被仲裁电路选中的指令，能够在本周期内，对发射队列 (Issue Queue) 中其他的源寄存器进行唤醒，前提就是这条被选中的指令能够在一个周期之内被 FU 执行完毕，例如加减法指令，而当一条指令无法在一个周期之内执行完毕时，就不能在被仲裁电路选中的当前周期对发射队列中其他的指令进行唤醒，而需要根据它在 FU 中执行的周期数，将这个唤醒过程进行延迟。

根据前面的介绍可以知道，唤醒过程其实可以分为两个主要的阶段，第一阶段是将被选中指令的目的寄存器的编号值送到总线上，第二阶段是将总线上的值和发射队列中所有源寄存器的编号进行比较，因此要将唤醒过程进行延迟，也就是将这两个阶段进行延迟，这也就产生了两种方法，一种称为延迟广播 (delayed tag broadcast), 另一种称为延迟唤醒

(delayed wake-up)。

延迟广播的方法是指如果发现被仲裁电路选中的指令执行周期大于 1, 则在选中的当前周期，并不将这条指令的目的寄存器的编号送到总线上，而是根据这条被选中指令所需要执行的周期数 (假设执行周期为 N),延迟 $N-1$ 个周期之后，才将它送到总线上，如图 8.34 所示。

图 8.34 延迟广播 (delayed tag broadcast)

MUL R1 = R2 × R3
XOR R5 = R1 ^ R4

在图 8.34 中，乘法指令的执行周期数是 3, 因此乘法指令被仲裁电路选中后，需要延迟 2 个周期，然后才将它的目的寄存器的编号送到总线上，对发射队列中相关的寄存器进行唤醒操作。当乘法操作专用一条总线时，这种做法没有问题，但是，当乘法操作和其他的操作共用一条总线时，例如前文讲述的 Mul/Div 类型的 FU,乘法和除法操作会共用一条总线来对其他指令进行唤醒，则有可能出现这样的情况：当乘法指令的目的寄存器编号延迟几个周期送到总线的时候，其他的指令 (例如除法指令 ) 也要使用这条总线，这就产生了冲突，如图 8.35 所示。

图 8.35 延迟广播可能导致 tag bus 产生冲突

MUL R1 = R2 × R3
XOR R5 = R1 ^ R4
ADD R3 = R2 + R4

在图 8.35 中，假设乘法操作和加法操作共用同一个 FU( 很多 ALU 都是这样做的 ),使用同一条总线 (tag bus), 则在乘法操作延迟进行唤醒，将它的目的寄存器的编号送到总线上的那个周期，还有另外一条加法指令也要将它的目的寄存器的编号送到总线上进行唤醒操作，此时却只有一条总线，显然就产生了冲突。为了解决这个问题，可以增加这个 FU 对应的总线 (tag bus) 的个数，但是，当处理器中存在很多这样的情况时，会导致需要大量的总线，这会极大地增加唤醒电路的复杂度，在实际的设计中是无法接受的。如果不增加总线的数量，那么就需要在处理器中记录下每条指令的执行周期数，例如使用一个表格来记录当前在 FU 中执行的指令所需要的周期数，后续被仲裁电路选中的指令，如果从这个表格中发现了冲突，那么这条被选中的指令将不会送到 FU 中执行，而是在下个周期继续参与仲裁的过程，如图 8.36 所示。

图 8.36 使用表格记录 tag bus 的使用情况

在图 8.36 中，指令 A 在 FU 中需要执行三个周期，所以它被仲裁电路选中后，会延迟两个周期才进行唤醒操作，也就是在第二个周期 (cycle 2) 将目的寄存器的编号送到它对应的 tag bus 上，进行唤醒的操作；而指令 B 在 FU 中的执行需要两个周期，它在下个周期即使被仲裁电路选中了，通过查询图 8.36 中的表格可以知道，指令 B 会和指令 A 同时使用 tag bus( 都是在 cycle 2),也就是存在冲突，因此指令 B 是不允许在这个周期被选中的，它会在下个周期继续参与仲裁的过程，此时就不存在 tag bus 冲突的情况了，指令 B可以被仲裁电路选中。

图 8.36 的这种做法中，访问表格和仲裁电路是并行工作的，因此指令 B 即使被仲裁电路选中，也可能被表格否决掉，这种做法的优点是没有增加仲裁电路的延迟，但是却造成了性能的损失：指令 B 被否决的这个周期，指令 C 本来是可以被仲裁电路选中的，因为指令 C 并不会产生 tag bus 冲突，但是指令 C 比指令 B 要新，因此仲裁电路此时并不会选择指令 C, 也就是说，这个周期被浪费掉了，这样当然会造成处理器性能的下降，如何解决这个问题呢？可以让指令向仲裁电路发出请求之前，首先查询表格，如果表格否决了它，那么这条指令就不会向仲裁电路发出有效的请求信号，这样就可以将机会留给其他的指令，在一定程度上缓解了 tag bus 冲突对处理器性能的负面影响，但是这种做法由于需要串行的访问表格和仲裁电路，所以会增大处理器的周期时间，因此究竟采用何种方法，需要在实际的设计中进行折中和权衡。

延迟广播的方法是对唤醒过程的第一阶段进行延迟，相比较之下，延迟唤醒 (delayed wake-up) 则是对唤醒过程的第二阶段进行延迟，下面看一下这种方法是如何工作的。

在这种方法中，被仲裁电路选中的指令会按照正常的流程，在当前周期就将它的目的寄存器编号送到对应的总线上，并和发射队列 (Issue Queue) 中所有的源寄存器进行比较。但是，此时比较结果相等的寄存器并不一定马上被置为准备好的状态 (也就是 ready 状态 ),而是根据这条进行广播的指令所需要的执行周期数，进行相应周期的延迟，然后再改变发射队列中源寄存器的状态，这就相当于延迟进行了唤醒。这种方法不会影响唤醒过程的第一个阶段，被选中指令的目的寄存器的编号会按照正常的流程送到总线 (tag bus) 上，因此这种方法并不会增加对总线的需求，避免了上面方法中出现的问题，这种方法的示意图如图 8.37 所示。

图 8.37 延迟唤醒的原理图

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

在图 8.37 中，假设乘法操作需要执行 4 个周期才可以得到结果 R3,在发射队列中，所有的源寄存器 R3 需要等待 3 个周期后才能变为准备好的状态 (也就是 ready 状态 ),这种设计只需要将寄存器比较的结果，也就是 1 位的信号进行延迟，需要的寄存器资源比较少，在一定程度上降低了硬件的复杂度。

在图 8.37 中，指令 B 使用了指令 A 的结果，它们之间存在先写后读 (RAW) 的相关性，将比较结果延迟多少个周期，是和指令 A 在 FU 中执行的周期个数相关的，它们之间关系的推算过程如下。

当指令 A 的执行周期数是 1 时，指令 B 不需要将比较的结果进行延迟；

当指令 A 的执行周期数是 2 时，指令 B 需要将比较的结果延迟 1 个周期；

当指令 A 的执行周期数是 3 时，指令 B 需要将比较的结果延迟 2 个周期；

……

当指令 A 的执行周期数是 N 时，指令 B 需要将比较的结果延迟 $N-1$ 个周期。

这样就得到了一般性的规律，图 8.38 给出了指令 A 的执行周期数为 4 时，流水线的示意图。

图 8.38 延迟唤醒的流水线

在这种延迟唤醒的方法中，本质就是要在发射队列 (Issue Queue) 中，每条指令对应的 ready 状态位之前加入延迟功能的寄存器，当然，这只是一个概念，在实际的设计中，需要加入控制电路来控制延迟的周期数，具体的实现方式有很多种，本书介绍一种参考的设计方法。

这种方法采用移位寄存器的方式来实现延迟唤醒的效果，因为在流水线的解码阶段，每条指令需要的执行周期数就可以知道了，将每条指令的这个执行周期数进行编码，编码之后的值称为 DELAY, 由于每条存在目的寄存器的指令都会被分配一个新的物理寄存器，这样每个物理寄存器都会对应一个 DELAY 值。每条指令在写到发射队列 (Issue Queue) 中的时候，都会将这条指令的 DELAY 值也一并写入，此时发射队列中的每个表项的内容被修改为如图 8.39 所示。

图 8.39 延迟唤醒方法中的发射队列表项 (Issue Queue Entry)

当一条指令被仲裁电路选中之后，除了将它的目的寄存器的编号送到总线之外，还需要将它的 DELAY 值也一并送到总线上，称这个总线为 DELAY bus。一般来说，每个 FU 都会对应一个 DELAY bus。根据寄存器编号的比较结果，将对应 DELAY bus 的值 “捕捉” 到发射队列相应的表项 (entry) 中，然后再将这个 DELAY 值进行移位的处理，完成延迟唤醒的过程。在图 8.39 中，发射队列中的每个表项包括的内容如下。

① Freed: 表示这个表项是否是空闲的，当一条指令写入其中时，这个表项就不再是空闲的；而这条指令被仲裁电路选中，并且确定不会有问题时，这条指令就可以离开发射队列，这个表项也就可以变为空闲的状态。需要注意的是，一条指令被仲裁电路选中之后，并不一定保证这条指令就一定会得到想要的操作数，当这条指令的操作数来自于 load 指令时，处理器可能会采用推测唤醒 (speculative wake-up) 的方法来加快执行效率，这时候即使一条指令被仲裁电路选中了，它也有可能在之后的时间重新参与仲裁的过程，因此管理发射队列中的一个表项是否空闲并不是一件很直接的事情，最容易的方法就是当一条指令顺利地离开流水线 ( 也就是退休 ) 的时候，才使它在发射队列中占据的表项变为空闲的状态，但是这会导致很多无效的指令占据着发射队列，使其可用的容量变小，降低了处理器可能获得的并行度，因此现实当中的处理器会采用一些更高级的方法，这些内容将在后文介绍。

② Issued: 表示一条指令是否已经被仲裁电路选中，被选中的指令可能不会马上离开发射队列，因此需要对这种指令加以标记，以使它不再向仲裁电路发出请求信号。

③ SrcL: 指令的第一个源寄存器的编号值，它会和所有的总线上的目的寄存器的编号进行比较。

④ SrcL_M: 当寄存器编号的比较结果相等时，这一位会被置 1(M 表示 match); 当这条指令接收到仲裁电路给出的响应信号时，这一位会被清 0, 它是移位寄存器 (SrcL_SHIFT) 进行算数右移的使能信号，当它为 1 时，移位寄存器每周期都会算术右移一位。

⑤ SrcL_SHIFT: 移位寄存器，当寄存器编号的比较结果相等时，会将对应的 DELAY 值写到这个移位寄存器中，然后它在移位使能信号 (SrcL_M) 的控制下，每周期都会算术右移一位，通过这种方式实现延迟唤醒的功能，这个移位寄存器最低位的值用来表示当前的源寄存器 (SrcL) 是否已经处于准备好的状态 (ready 状态 )。

⑥ Rdy: 表示指令的第一个源寄存器是否已经准备好了 (ready 状态 ), 它本质上就是移位寄存器 (SrcL_SHIFT) 的最后一位。

上面所讲述的 SrcL、SrcL_M 和 SrcL_SHIFT 都在描述指令的第一个源寄存器，同理， SrcR、SrcR_M 和 SrcR_SHIFT 都用来描述指令的第二个源寄存器，它们的内容是一样的。

⑦ SrcR_imm_valid: 表示指令的第二个操作数是否是立即数。

⑧ DELAY: 用来记录每条指令需要在 FU 中执行的周期数，在一条指令被仲裁电路选中，将它的目的寄存器的编号送到总线 (tag bus) 上的同时，也会将这个 DELAY 值送到对应的总线上 (DELAY bus),发射队列中的每个源寄存器都会根据比较的结果，选择合适的 DELAY 值写到图 8.39 中的 SrcL_SHIFT( 或 SrcR_SHIFT) 区域中。因为这个值会被进行算数右移，所以对 DELAY 值采用 1 和 0 进行编码，DELAY 值的位宽由所有 FU 中，最多需要的周期数来决定，而 DELAY 值最右边将被填充 0, 对于一条在 FU 中需要执行 $L$ 个周期的指令来说，0 的位数等于 $L-1$, 表示这条指令需要将唤醒信号进行延迟的周期数。举例来说，对于一个 8 位的 DELAY 值，当一条指令需要在 FU 中执行的周期数为 4 时，这条指令的 DELAY 值会被编码为 11111000, 当发射队列中的某个源寄存器 “捕捉”到这个 DELAY 值之后，经过 3 个周期的算数右移，它的最低位就是 1 了，也就是表示这个源寄存器已经被唤醒，处于准备好的状态。

⑨ ROB ID: 这条指令在 ROB 中的位置，这个值作为指令的年龄信息，使仲裁电路 (Select) 可以实现 oldest-first 的指令选择。

一旦发射队列中的某个源寄存器的编号和总线上的目的寄存器的编号相等时，例如 SrcL 和某个总线上的值相等，则 SrcL_M 位就会被置为 1, 直到接收到仲裁电路给出的响应信号 ( 即 grant 信号), 才会将 SrcL_M 位清零，也就是说，SrcL_M 位会保持很多个周期都为 1,而这一位作为移位寄存器 (SrcL_SHIFT) 的使能信号。当其为 1 时，移位寄存器在每周期都会算术右移一位，当移位寄存器右边的 0 全部被移掉时，整个值就全是 1 了，所以即使它继续算数右移，其最右边的位也会一直为 1, 表示这个源操作数一直处于准备好的状态，直到某一个时刻，这条指令被仲裁电路选中而收到了有效的响应信号 (grant 信号), 才会将这条指令对应的移位寄存器 (SrcL_SHIFT 和 SrcR_SHIFT) 和移位使能信号 (SrcL_M 和 SrcR_M) 都清零，这条指令就不会继续向仲裁电路发出请求信号了。

8.5.3 推测唤醒

到目前为止，前文讲述的唤醒方法都是建立在一个前提下，即指令在 FU 中执行的周期数是可以预知的，这样才可以为这条指令分配一个确定的 DELAY 值，但是在实际的处理器中，很多指令需要的执行周期数是没有办法提前知道的，这些情况如下。

(1) Load 指令，它在 FU 中执行的周期数取决于 D-Cache 是否命中，在一个有着 L1 Cache、L2 Cache、L3 Cache 和 DRAM 的典型处理器中，load 指令需要的执行周期数 ( 用 latency 表示 ) 可以表示如下。

\[\mathrm{Latency}\in\{\mathrm{L1\_latency},\mathrm{L2\_latency},\mathrm{L3\_latency},\mathrm{DRAM\_latency}\}\]

其中，L1_latency 表示当 L1 D-Cache 命中时，load 指令需要的执行周期数，其他的以此类推。而且，DRAM 由于自身结构的原因 (例如 queuing delay), 从其中读取数据需要的时间并不是一个固定的值，这在一定程度上也使问题变得更复杂了一些。

(2) 在某些处理器中，定义了一些特殊的情况，例如 PowerPC 603 处理器中，当被乘数的位数比较小时，乘法的结果可以提前得到，这称为 early out; Intel 的 Core2 架构中，对于除法操作也存在 early out 的情况，这些情况都导致指令在 FU 中需要的周期数不是一个固定的值。

对于这些执行的周期数不确定的指令，可以采用最简单的方式进行处理。当这条指令执行完时，才对其他相关的指令进行唤醒的操作，例如对于 load 指令来说，它的执行情况如图 8.40 所示。

如果 L1 D-Cache 命中，则当指令 A (load 指令)执行完毕，得到需要的数据时，才将这条指令的目的寄存器的编号送到对应的总线上，对发射队列中相关的寄存器进行唤醒操作。由图 8.40 可以看出，指令 B 使用了指令 A 的结果，它们的执行相差了 5 个周期，如果硬件在这些周期内无法找到其他不相关的指令来执行，那么就会导致处理器执行效率的下降。

图 8.40 等到 load 指令执行完毕时，才对发射队列中的相关指令进行唤醒

指令 A: R1 = 16[SP]
指令 B: R3 = R1 + R2

上面的设计可以做一些小的改进，例如在设计 D-Cache 时，Cache 是否命中的信息是可以先于数据得到的，例如 load 指令执行的第一个周期进行地址的计算，第二个周期访问 Tag SRAM 进行是否命中的判断，第三个周期将读取到的数据写到 load 指令的目的寄存器中，在这样设计的 D-Cache 中，执行的第二个周期就可以知道 Cache 是否命中了，所以可以将流水线改进如图 8.41 所示。

图 8.41 对 Cache 进行改进，使其更早地得到是否命中的信息

指令 A: R1 = 16[SP]
指令 B: R3 = R1 + R2

通过这种改进措施，当 L1 Cache 命中时，指令 A 和指令 B 之间的执行相差了 3 个周期，相比于前一种设计已经有了改进，但是仍旧不完美。其实，按照设计的意图，D-Cache 的命中率应该是很高的，否则 D-Cache 就失去意义了，所以，可以假设 D-Cache 是一直命中的，这样流水线就按照如图 8.42 所示的形式执行。

图 8.42 假设 D-Cache 一直命中的流水线

指令 A: R1 = 16[SP]
指令 B: R3 = R1 + R2

图 8.42 即是以前所讲述的延迟唤醒 (delayed wake-up) 的情况，只不过对于 load 指令来说，还需要额外考虑更多的事情，因为一旦指令 A 发生了 D-Cache 缺失，此时指令 B 就不能通过旁路网络 (bypassing network) 获得操作数，也就无法在 FU 中执行，而且，指令 B 也不能就此停住而等待操作数，因为这样会使 FU 无法接收其他新的指令，严重影响处理器的性能。最好的方法就是将指令 B 重新放回发射队列 (Issue Queue) 中，因为 load 指令在 D-Cache 缺失之后，会到 L2 Cache 中寻找数据，此时可以假设 L2 Cache 是命中的，并按照它的命中的时间重新对发射队列中相关的寄存器进行唤醒的操作，这样就使 FU 可以继续执行其他的指令，提高了处理器执行的效率，这个过程如图 8.43 所示。

图 8.43 假设 L2 Cache 命中的流水线

指令 A: R1 = 16[SP]
指令 B: R3 = R1 + R2

由于读取 L1 Cache、L2 Cache 甚至是L3 Cache 需要的周期数都是确定的，所以可以使用图 8.43 所示的延迟唤醒的方式，但是对于读取时间不确定的情况，例如 DRAM 的访问，只能等到从 DRAM 中真正得到数据的时候，才对发射队列中相关的寄存器进行唤醒，这种方式相比于图 8.43 所示的方法，会多出几个周期的延迟，在超标量处理器中可能会引起性能的下降。当然，如果处理器可以找到其他的不相关指令来填充这些周期，就可以避免这种性能的损失，这也是超标量处理器的一个优势，它可以充分地使用硬件资源，实时地对指令进行调配，这一点是那些依靠编译器调度的 VLIW 处理器所不能比拟的，所以对于通用的处理器，超标量的结构是很合适的，而对于专用的一些领域，VLIW 处理器的优势才可以体现出来。

其实在早期的 tomasulo 算法中 ^[36],只有当 FU 将结果运算出来之后，才会将目的寄存器的编号进行广播，对其他的指令进行唤醒操作，这样做不能够使有着先写后读 (RAW) 相关性的连续指令背靠背地执行，造成了性能的下降。因此现代的处理器都是在指令被仲裁电路选中的同时，根据这条指令所需要的执行周期数，来对其他的相关指令进行唤醒，这样当这条被选中的指令计算出结果的时候，被它唤醒的指令正要进入执行阶段，可以通过旁路网络 (bypassing network) 获得操作数，从而实现背靠背的执行，这个过程可以简单地使用图 8.44 进行表示。

图 8.44 通过旁路网络可以实现背靠背的执行

对于一般的算术类型的指令，其执行周期都是 1, 这种指令可以在被仲裁电路选中的同时马上对相关的指令进行唤醒操作，从而可以实现背靠背的执行；而对于那些执行周期数大于 1 的指令，例如乘除法指令，需要根据它的执行周期，延迟进行唤醒，如图 8.45 所示。

对于执行周期数是一个确定值的指令，可以使用这种延迟唤醒的方法，而对于本节介绍的 load 类型的指令，它的执行周期是不确定的，而 load 指令多处于相关性的顶端，如果等到它的结果被计算出来的时候才进行唤醒操作，会损失一些潜在的并行执行的机会，从而降低处理器的性能，因此需要使用预测的方法预测指令执行的周期数，在指令得到结果之前，就对相关的指令进行唤醒操作，这种方法就称为推测唤醒 (speculative wake-up),或称为预测唤醒。

图 8.45 延迟唤醒

既然是预测的方法，那么就会出现预测错误的情况，此时就需要进行状态恢复，对于 load 指令来说，由于它要访问 D-Cache, 而当 D-Cache 命中 /缺失时，会造成不同的执行周期。考虑到 D-Cache 的命中率是很高的，所以可以在流水线的发射阶段假设所有 load 指令的 D-Cache 都是命中的，这样当 load 指令被仲裁电路选中时，就可以按照最短的执行周期数，对相关的指令进行唤醒操作，当 load 指令真正访问 D-Cache 时，如果此时发现了缺失，那么就说明之前的预测是错误的，需要进行状态恢复，那些被 load 指令唤醒的所有寄存器都应该重新被置为非准备好 (not ready) 的状态，如果一些指令已经离开了发射队列，那么还需要将其从流水线中抹掉，重新放回到发射队列中，这就完成了状态恢复的过程，这些指令会等待 load 指令重新将它们唤醒。此时 load 指令可以继续预测 L2 Cache 是命中的，并按照这个周期数对相关指令进行唤醒，当然，如果发现这个预测也是不正确的，那么就继续按照这种方法进行状态恢复。

Load 指令在执行阶段，需要计算指令所携带的地址，如果在处理器中使用了虚拟存储器，则此时计算出的地址只是虚拟地址，还需要将其转换为物理地址，然后才能够访问 D-Cache( 这部分内容不是绝对的，如果采用了完全的虚拟 D-Cache, 则不需要转换成物理地址，直接使用虚拟地址就可以访问 D-Cache 了 ),这样的流水线可以用图 8.46 来说明。

图 8.46 Load 指令的流水线，以及将相关指令进行唤醒的过程

Load R1, 8[R2]
ADD R4, R3, R1

在图 8.46 中，load 指令在执行阶段被分为了三个流水段，Cal Addr 阶段用来计算指令所携带的地址，TLB/Tag 阶段会同时访问 TLB 和 D-Cache, 在这个周期会得到虚拟地址对应的物理地址，同时会得到 D-Cache 是否命中的信息，在 Data 阶段就可以从 D-Cache 中得到需要的数据，并将其写到目的寄存器中。需要注意的是，TLB 的缺失也会造成 load 指令执行周期数的变化，此时仍旧需要采用预测的方法，假设 TLB 总是命中的，当在执行阶段发现 TLB 缺失的时候，就发生了预测错误，需要进行状态恢复，如果采用软件处理 TLB 缺失，就需要按照异常 (exception) 的处理方式，等到 load 指令变为流水线中最旧的指令的时候，将流水线中所有的指令 (包括 load 指令 ) 都抹掉，在对应的异常处理程序中对 TLB 缺失的这个情况进行处理，然后重新将 load 指令以及后面的指令取到流水线中，此时 load 指令访问 TLB 就不会产生缺失了，这就相当于完成了状态恢复的过程，这和上面讲述的 D-Cache 缺失时的恢复过程是不同的，在 D-Cache 缺失时的状态恢复中，load 指令并不需要从流水线中被抹掉，也不需要重新参与仲裁的过程 (D-Cache 的缺失是由硬件自动解决的 ),并且 load 指令后面的相关指令也只需要重新放回到发射队列中，并不需要从流水线中被抹掉，称这种方式是基于发射队列的状态恢复；而采用软件处理 TLB 缺失时的状态恢复，需要将 load 指令以及它后面所有的指令都从流水线中抹掉，然后重新从 I-Cache 中将这些指令取出来放到流水线中，这种方式称为基于 I-Cache 的状态恢复。

当然，如果采用硬件处理 TLB 缺失，那么就不需要将 load 指令重新取到流水线中执行了，load 指令后面的相关指令也只需要重新放回到发射队列中就可以，这就是基于发射队列的状态恢复，因此如果采用硬件处理 TLB 缺失的方式，就可以将它的恢复过程和 D-Cache 缺失时的恢复过程放到一起来处理，这样节约了硬件资源。

采用不同结构的 D-Cache, 对于推测唤醒 (speculative wake-up) 的过程是有影响的，如果采用了 virtually-indexed,physically-tagged 的方式，则在访问 TLB 的同时，也可以使用虚拟地址来访问 D-Cache, 这种并行的方式会增加执行的效率，这就是图 8.46 中的 TLB/Tag 阶段所完成的事情，从 D-Cache 中会读取到对应的 tag 值，同时从 TLB 中也会得到对应的物理地址，这时候可以进行比较，以判断 D-Cache 是否命中，这个过程可以在 TLB/Tag 的这个周期完成，也可以将其放到下一个周期，这样可以缩短处理器的周期时间。采用其他方式的 D-Cache 会使流水线略有不同，例如当使用 physically-indexed, physically-tagged 的方式时，就必须先访问 TLB 而得到物理地址，然后才能访问 D-Cache, 这种方式将 D-Cache 的访问过程完全的串行化，因此需要更长的执行时间；而如果使用 virtually-indexed， virtually-tagged 的方式，则不需要访问 TLB, 直接只使用虚拟地址访问 D-Cache 就可以了，只有当 D-Cache 缺失的时候才需要访问 TLB( 因为 L2 Cache 都是使用物理地址来访问的 ),不需要访问 TLB 也就意味着这种方式会缩短 D-Cache 访问的时间，但是访问 L2 Cache 需要的时间就会更长一些。

在图 8.46 中，load 指令被仲裁电路选中之后，需要等待两个周期才可以将相关的指令进行唤醒，在这两个周期内，仲裁电路可以选择那些和 load 指令不存在相关性的指令，称这两个周期为 Independent Window( 简称 IW)。而从 load 指令开始将相关的指令进行唤醒，直到它发现自身是否会 D-Cache 命中 /缺失，中间也间隔了两个周期，称这两个周期为 Speculative Window( 简称 SW),示意图如图 8.47 所示。

图 8.47 Independent Window 和 Speculative Window

需要注意的是，SW 窗口中的指令不一定就和 load 指令存在相关性，例如那些被 load 指令唤醒的指令并没有马上被仲裁电路选中，就会使 SW 窗口中的指令其实并没有使用 load 指令的结果；而 IW 窗口中的指令也并不一定就和 load 指令无关，因为它可能和其他 load 指令的 SW 窗口是重合的，这可以用图 8.48 来表示。

图 8.48 Load3 指令的 IW 窗口和 load1 指令的 SW 窗口是重合的

在图 8.48 中，load1 指令的 SW 窗口和 load3 指令的 IW 窗口是重合的，在这两个周期被仲裁电路选中的指令未必在执行阶段能够获得操作数，这取决于 load1 指令是否 D-Cache 命中。在图 8.48 中，假设在流水线的 TLB/Tag 阶段就可以得到 D-Cache 命中 /缺失的结果了，当发现缺失时，在这条 load 指令对应的 SW 窗口中，相关的指令就需要从流水线中被抹掉。由图 8.48 可以看出，这样的相关指令只会处于流水线的 select 或 wake-up 两个阶段，只需要将这两个阶段中相关的指令抹掉就可以了，所有这些被抹掉的指令会重新被放回到发射队列 (Issue Queue) 中，等待重新被唤醒，不同的 D-Cache 设计会导致 IW 和 SW 窗口中指令的个数发生变化，但是处理的方式是一样的。

由于发现 D-Cache 缺失时，那些和 load 指令存在相关性的指令都需要重新被放回发射队列中并等待被唤醒，这就需要这些指令重新在发射队列中变为 not ready 的状态，并重新向仲裁电路发出申请，这个过程称为 replay。而前面说过，一条指令被仲裁电路选中之后，它可以马上离开发射队列，也可以继续停留在发射队列中，直到被允许时才离开，这些不同的设计方法会导致不同的状态恢复的方法，产生不同的执行效率和硬件消耗。本节介绍两种常用的方法：Issue Queue Based Replay 和 Replay Queue Based Replay, 这两种方法在现代的处理器中都有使用，它们的硬件消耗、执行效率和功耗也是各不相同的。

1. Issue Queue Based Replay

在这种方法中，指令被仲裁电路选中之后，不会马上离开发射队列 (Issue Queue), 只有当这条指令被确认已经正确执行之后，才会允许这条指令离开发射队列。这种方法需要在发射队列中增加一个标志位，用来指示这条指令已经被仲裁电路选中但还没有离开发射队列，称其为 issued 标志位，当这个标志位为 1 时，这条指令就不会再向仲裁电路发出请求信号了；当这条指令需要 replay 时，会将 issued 标志位清零，这样它就可以继续向仲裁电路发出请求信号，这种方法的示意图如图 8.49 所示。

其实，前文介绍的 load 指令的 D-Cache 缺失只是可以引起 replay 的一种情况，在真实的处理器中，有很多情况都可能引起指令进行 replay, 例如采用交叠 (interleaving) 结构的 D-Cache 中的 bank 冲突，store/load 指令的违例 ( 即按照程序中规定的顺序，load 指令比拥有相同地址的 store 指令先执行了 ),甚至是 load/load 指令的违例 ( 即按照程序中规定的顺序，load 指令比拥有相同地址的 load 指令先执行了，在某些多核应用环境中要求保持这种顺序 ) 等，都需要将相关的指令进行 replay, 这时候最简单的处理方法就是让所有的指令在被仲裁电路选中的时候，都不要马上离开发射队列，只有当这条指令确认自己可以正确执行的时候，才会离开发射队列，那么，什么时候才能够知道一条指令的执行是否正确呢？这其实是和处理器采用的微架构 (microarchitecture) 相关的，如果采用完全乱序 (out-of-order) 的方式来执行 load/store 指令，那么即使 load 指令是 D-Cache 命中，甚至 load 指令都已经执行完毕，但是只要 load 指令没有顺利地离开流水线 ( 即退休 ), 都有可能由于 store/load 指令违例而导致 load 指令的执行结果是错误的，此时需要将 load 指令以及所有和它存在直接或者间接相关性的指令，都重新在发射队列中参与唤醒 (wake-up) 和仲裁 (select) 的过程。因此在这种处理器的架构中，只有一条指令顺利地离开流水线 ( 即退休 ) 的时候，才可以保证它是正确执行的，此时才会允许它离开发射队列。而如果采用完全顺序或者部分乱序的方式 ( 关于这些内容将在后文进行介绍 ) 来执行 load/store 指令，则不会存在上述的违例现象，此时只有那些和 load 指令存在相关性的指令才有可能被 replay, 更精确地说，是那些处于 SW 窗口中的指令才有可能被 replay, 等到 load 指令得到了 D-Cache 是否命中的结果之后，就可以决定 SW 窗口中的指令是否可以离开发射队列了。

图 8.49 Issue Queue Based Replay

这种基于发射队列进行 replay 的方法，它的设计复杂度相对不高，因此需要的硬件资源也就比较少，但是却造成了发射队列实际可用容量的减少，考虑到 D-Cache 命中的概率是很高的，同时，发生 store/load 等违例情况的概率并不高，所以大部分指令在被仲裁电路选中之后，其实就已经不会 replay 了，但是这部分指令仍旧占据着发射队列中的空间，降低了它实际可以使用的容量，而发射队列的作用是寻找程序的并行性，所以这样相当于降低了处理器的性能，如果提高发射队列的容量，又会造成仲裁电路和唤醒电路延迟的增大，使本来就处于关键路径的这部分电路的时序更加紧张。

为了解决这种矛盾，需要一些适当的折中，例如，可以只对 load 指令采取这种基于发射队列进行 replay 的方法，一旦 load 指令在它的执行阶段得到了 D-Cache 命中的结果，就可以将发射队列中相关的指令进行释放，这样就最大限度地减少了多余的指令对于发射队列的占用。采用这种设计方法之后，一旦发生了 store/load 指令违例，或者 load/load 指令违例的这些情况，很多需要 replay 的指令可能早就离开了发射队列，这时候已经没有办法将这些指令再次放回到发射队列中了，因为在发射队列中可能已经没有空间再容纳这些指令，这时候就会有产生死锁的可能：在发射队列中的指令等待被它前面的指令唤醒，而前面的指令由于发射队列中没有空间而无法进行 replay, 也就无法将其他指令进行唤醒，这就产生了死锁。因此，对于 store/load 指令违例，或者 load/load 指令违例的这些情况，是没有办法依靠发射队列进行 replay 的，这时候需要将那些需要 replay 的指令从流水线中抹掉，从 I-Cache 中重新将这些指令取出来放到流水线中，当然这样会损失一些性能，这就是一种折中了，Alpha 21264 处理器就采用了这种方法。

然而对于 load 指令来说，仍旧需要使用发射队列进行 replay, 这个过程也是可繁可简，当 load 指令在执行阶段发现了 D-Cache 缺失时，一种比较简单的方法是将所有在 load 指令之后被仲裁电路选中的指令都重新 “放回”到发射队列中 (注意，并不是真的将指令放回到发射队列中，因为这些指令还都没有离开发射队列，只需要更改对应的状态位就可以了 ),这些指令会重新等待被唤醒 (wake-up) 和选中 (select)。这种方法当然不会产生错误，但是，考虑到 IW 窗口的存在，甚至是在一条 load 指令的 SW 窗口中，未必所有的指令都是和 load 指令相关的，所以这种方法将很多本来可以不需要 replay 的指令也进行了 replay, 在一定程度上损失了一些性能，但是实现起来相对是比较简单的，这种方法被称为 Non-Selective Replay, 它是一种无差别的选择指令的方法，它的示意图如图 8.50 所示。

图 8.50 Non-Selective Replay

在图 8.50 中，假设 load 指令在执行的最后一个周期，即 Data 阶段，才得到 D-Cache 是否命中的信息，如果发现没有命中，则将所有在 load 指令之后被仲裁电路选中的指令，也就是在流水线的 Data 阶段和 wake-up 阶段之间的所有指令，都从流水线中抹掉。图 8.50 中灰色部分的指令都是需要从流水线中被抹掉的，它们会重新在发射队列 (Issue Queue) 中等待被唤醒，但是从图中可以看出来，在所有被抹掉的指令中，只有 OR 指令和 SUB 指令才真正和 load 指令存在相关性，应该进行 replay, 而其他的指令其实都没必要进行 replay。因此这种无差别选择指令的方法浪费了一些处理器的时间，换来了硬件复杂度的降低，在现实世界的处理器中，例如 Alpha 21264 处理器，就采用了这种方法。

这种方法在一定程度上可以进行改进，前面说过，处于 IW 窗口中的指令，是肯定和对应的 load 指令不存在相关性的。在图 8.50 中，当 load 指令在流水线的 Data 阶段发现 D-Cache 缺失时，处于 Cal Addr 和 TLB/Tag 这两个流水段的指令，是不需要进行 replay 的，因此只需要将 RF 和 Select 这两个流水段的指令从流水线中抹掉，重新在发射队列中等待被唤醒就可以了，这样可以在一定程度上减少性能的损失，可以称为是改良版的 Non-Selective Replay 的方法。

不管是不是改良版的设计，在将图 8.50 中灰色部分的指令重新 “放回”到发射队列的同时，还需要将发射队列中所有和 load 指令存在相关性的寄存器都置为 not ready 的状态，这样那些和 load 指令不存在相关性的指令即使被重新 “放回”到发射队列中，由于它们仍然处于准备好的状态，因此马上可以向仲裁电路发出申请，只有那些和 load 指令存在相关性的指令才需要等待被重新唤醒。这要求在发射队列中能够识别出哪些寄存器是和 load 指令存在相关性的，这个相关性包括两个方面，一是直接的相关性，例如图 8.50 中的 OR 指令；

二是间接的相关性，例如图 8.50 中的 SUB 指令。这两种相关性的指令 (确切地说，是存在相关性的寄存器 ) 都需要在发射队列中被识别出来，为了达到这个目的，可以采用一种比较直接的方法，使用一个值来记录流水线中所有的 load 指令，其中的每一位表示一条 load 指令，这个值的宽度等于流水线中能够最多存在的 load 指令的个数，这个值称为 load-vector，这种方法的示意图如图 8.51 所示。

图 8.51 使用 load-vector 来记录哪些寄存器和 load 指令存在相关性

load-vector   指令
       Load R1 = 8[R2]
       ADD R1 = R1 + 12
       Load R3 = 4[R1]
       SUB R4 = R3 - 4
       Load R5 = 4[R10]
       ADD R7 = R5 + R4

在处理器中的每个通用寄存器 (如果采用寄存器重命名，就是每一个物理寄存器 ) 都有一个 load-vector 值 ( 为了便于描述，下面称之为向量值 )。对于非 load 指令的其他指令来说，如果它存在目的寄存器，则它的向量值来自于两个源寄存器的向量值相或的结果；而对于 load 指令的向量值来说，除了来自于源寄存器，它还会占用向量值的一个新的位，通过这种方式，每个通用寄存器都分配了一个向量值，这样每个通用寄存器和 load 指令的直接或者间接关系都会记录在它的向量值中，所有寄存器的向量值就形成了一个表格，对于采用了寄存器重命名的处理器来说，这个表格中表项 (entry) 的个数等于物理寄存器的个数。指令在被寄存器重命名之后，会使用源寄存器来读取这个表格，得到每个源寄存器对应的向量值；同时为了得到目的寄存器对应的向量值，还需要将读取到的源寄存器的向量值进行或操作，对于 load 指令来说，还需要额外占用向量值的一个新的位，这样就可以得到目的寄存器对应的向量值，并将其更新到这个表格中，供以后的指令读取。指令在被重命名之后，就可以将每个源寄存器对应的向量值也一并写到发射队列中，每当发现一条 load 指令产生 D-Cache 缺失时，根据这条 load 指令在向量值中对应的位，就可以从发射队列中找出哪些寄存器和它存在直接或者间接的关系，然后就可以将这些寄存器置为 not ready 的状态，等待重新被唤醒。

当处理器的流水线比较浅，并且并行度不高时，能够同时存在于流水线中的 load 指令不会很多，所以这种 load-vector 的设计方法还是可以接受的，但是对于流水线比较深，并且并行度很高的处理器来说，需要的向量值的宽度也随之增加，否则就会因为向量值经常没有空间而导致流水线暂停，降低了处理器的性能。而过宽的向量值会导致更多的硬件消耗，同时也会增大发射队列的延迟，因此需要其他更好的方法来解决这个问题。

前面说过，对于一条 load 指令来说，只有处于它的 SW 窗口中的指令才有可能和它存在相关性，此处加 “有可能”是表示即使在一条 load 指令的 SW 窗口中，也可能存在和 load 指令不相关的指令。为了识别出发射队列中哪些寄存器和 load 指令存在相关性，对于每条load 指令都使用一个 5 位的值，用来表示出这条 load 指令处于流水线的哪个位置 (Select、 RF、Cal Addr、TLB/Tag 和 Data), 称这个值为 Load Position Vector(LPV)。每当一条 load 指令被仲裁电路选中时，都会将它的 LPV 置为 10000, 表示这条 load 指令处于流水线的 Select 阶段，在这个周期，load 指令会使用它的目的寄存器编号和发射队列中所有的源寄存器进行比较 (在当前周期只是进行比较，真正的唤醒是在两周期之后，即延迟唤醒 ), 所有比较结果相等的源寄存器都会得到这条 load 指令的 LPV 值，然后在之后的每个周期，发射队列中所有源寄存器的 LPV 都会逻辑右移一位，用来追踪 load 指令在流水线中的状态。例如，发射队列中的一个源寄存器的 LPV 是 10000, 表示它所依赖的 load 指令处于流水线的 Select 阶段，01000 表示 load 指令处于流水线的 RF 阶段，00100 表示 load 指令处于流水线的 Cal Addr 阶段，00010 表示 load 指令处于流水线的 TLB/Tag 阶段，00001 表示 load 指令处于流水线的 Data 阶段。为了能够识别出发射队列中，哪些源寄存器和 load 指令存在间接的相关性，每条指令在被仲裁电路选中之后，对其他的指令进行唤醒时，都会将它的目的寄存器的 LPV 值也赋给那些被唤醒的寄存器，这样就能够识别出哪些指令和 load 指令存在间接相关性了。同理，load 指令的 LPV 值也会在每周期逻辑右移一位，记录它在流水线中的位置，这样当 load 指令到达流水线的 Data 阶段，发现 D-Cache 缺失时，在发射队列中那些 LPV 的最低位是 1 的所有源寄存器，都会和这条 load 指令存在直接或者间接的相关性，需要被置为 not ready 的状态，然后等待重新被唤醒，下面以图示的方法表达了这个过程。

(1) Load 指令被仲裁电路选中之后，会在当前周期，使用它的目的寄存器编号和发射队列中所有的源寄存器的编号进行比较，并将比较结果相等的寄存器进行标记。由于在本节假设 load 指令需要在 FU 中执行三个周期，所以直到流水线的 Cal Addr 阶段，才可以对发射队列中相关的指令进行真正的唤醒。注意此处为了表示方便，并没有表达出 “load 指令将 XOR 指令的一个操作数进行了唤醒”, 而是表达了 “load 指令将 XOR 指令进行了唤醒”这个意思，在实际中，load 指令只会将一条指令的某一个操作数进行唤醒。

Load 指令在流水线的 Select 阶段，它的 LPV 是 10000, 所以发射队列中所有被唤醒的寄存器都会得到这个 LPV 的值，如图 8.52 所示。

图 8.52 XOR 指令被 load 指令唤醒，并得到 LPV 值

(2) 当 load 指令到达流水线的 Cal Addr 阶段时，根据延迟唤醒方法中的约定，此时 XOR 指令可以真正地被唤醒，在下个周期就可以向仲裁电路发出申请了。假设在下个周期 XOR 指令可以被仲裁电路选中，此时 load 指令处于流水线的 TLB/Tag 阶段，XOR 指令和 load 指令的 LPV 值都是 00010。在 XOR 指令被仲裁电路选中的同时，它又对发射队列中的其他指令进行了唤醒。在图 8.53 中，ADD 和 SLL 指令被唤醒了，这两条指令会同时获得 XOR 指令的 LPV 值，因此 ADD 和 SLL 指令的 LPV 也变为了 00010, 直接反映了它们所依赖的 load 指令此时在流水线中的位置，当然，这是一种间接的相关性。

图 8.53 ADD 和 SLL 指令都从 XOR 指令中获得了 LPV 的值

LD  R2, 8[R1]
XOR R3, R2, 0x30
ADD R4, R3, 0x55
SLL R5, R3, 0x08

(3) 在下个周期，假设 ADD 和 SLL 指令都被仲裁电路选中，同时会对发射队列中的相关指令进行唤醒。在图 8.54 中，ADD 指令将 AND 指令的一个操作数进行了唤醒，同时 AND 指令的另一个操作数被 load 指令唤醒 ( 即图 8.54 中的 LD2 指令 ),这样 AND 指令的两个源操作数的 LPV 分别来自于 ADD 和 LD2 指令，它们分别是 00001 (来自于 ADD 指令，表示了第一条 load 指令此时在流水线中的位置 ) 和 00100( 来自于第二条 load 指令，表示了这条 load 指令在流水线中的位置 ),本质上来说，AND 指令和两条 load 指令都是相关的。由于 AND 指令在唤醒其他的指令时，需要将它属于哪些 load 指令的信息传递给被唤醒的指令，所以这条 AND 指令的 LPV 值，是来自于它的两个源操作数的 LPV 相或的结果，即 00001 | 00100 = 00101, 被 AND 指令唤醒的其他指令可以得到这个 LPV 值，从而知道自己和哪些 load 指令是相关的，这个过程如图 8.54 所示。

在图 8.54 中，第一条 load 指令已经到了执行的最后一个阶段，即 Data 阶段，所有和它存在相关性的源寄存器，LPV 值的最后一位都是 1。如果发现 D-Cache 命中 (假设在 load 指令执行的最后一个阶段才可以得到命中 /缺失的结果 ),那么继续执行就可以了；但是如果发现了 D-Cache 缺失，那么在发射队列中，LPV 值的最后一位是 1 的所有源寄存器都需要被置为 not ready 的状态，同时将流水线中，处于这条 load 指令的 SW 窗口中的所有指令都置为无效。当然，这样有可能将一些本来不相关的指令也抹掉了，但是这些指令在发射队列中仍旧都是 ready 的状态，因此只要将这些指令在发射队列中的 issued 状态位清零 ( 当指令被仲裁电路选中后，需要将这些指令在发射队列中标记为 issued 状态，防止这些指令继续向仲裁电路发出申请 ),那么这些指令就马上又可以参与仲裁的过程了。

图 8.54 AND 指令和两条 load 指令都存在间接相关性

LD  R2, 8[R1]
XOR R3, R2, 0x30
ADD R4, R3, 0x55
SLL R5, R3, 0x08
LD  R6, 4[R10]
AND R7, R4, R6

这种方法中，LPV 的位数并不会随着流水线中指令个数的增多而显著地变大，它只和 load 指令执行的流水线级数有关，因此这种方法相比之前讲述过的 load-vector 的方法，对硬件的需求会少一些，速度也会快一些。

到目前为止，上述的 Load Position Vector 的处理方法都是针对每周期只能执行一条 load 指令来说明的，在这样的 LPV 值中，任何一个位只会对应唯一的一条 load 指令。当每周期可以同时执行的 load 指令多于一条时，例如每周期可以从发射队列中选择两条 load 指令，那么上述的方法就需要改进，发射队列中的每个源寄存器都需要两个 LPV 值，用来分别记录同一个周期内的两条 load 指令在流水线中的位置。这相当于将上述的电路复制了一份，不过现代的处理器受到 D-Cache 端口限制，每周期可以同时执行的 load 指令的个数并不会很多，所以这种方法不会造成太多的硬件消耗。

上面所述的内容即是 Non-Selective Replay 的方法，这种方法的过程可以简单地描述为在 load 指令的执行阶段发现 D-Cache 缺失时，将它的 SW 窗口中的所有指令都从流水线中抹掉，这些指令会重新被 “放回”到发射队列中，同时将发射队列中和这条 load 指令直接或间接相关的所有源寄存器都置为 not ready 的状态，等待重新被唤醒。这样在发射队列中，那些和 load 指令无关的指令由于仍然是处于准备好的状态，它们很快会再次被仲裁电路选中，当然这样的重复执行会浪费一些性能，而那些和 load 指令存在相关性的指令需要等待被唤醒之后才可以参与仲裁的过程。

如果发现 load 指令发生 D-Cache 缺失时，只将它的 SW 窗口中，和 load 指令存在相关性的指令抹掉，其他不相关的指令可以继续执行，则可以提高处理器执行的效率，使用这种方法之后，之前在 Non-Selective Replay 方法中使用的例子就可以按照如图 8.55 所示的方法执行。

图 8.55 Selective Replay

在图 8.55 中，只有和 load 指令存在相关性的 SUB 和 OR 指令会从流水线中被抹掉，重新被 “放回”到发射队列中，而其他的指令则可以继续执行。为了达到这种效果，需要能够识别出流水线的 Select 阶段和 RF 阶段中的哪些指令是和 load 指令相关的，这可以通过前面讲述过的 LPV 来实现。因为在发射队列中，每条指令的 LPV 都记录着这条指令和哪条 load 指令是相关的，如果指令在被仲裁电路选中的时候，让这条指令的 LPV 值也随着进入后续的流水线，这样当 load 指令发现 D-Cache 缺失时，只需要从流水线中找到 LPV 符合要求的指令进行抹掉就可以了，这就实现了有选择的 replay, 因此这种方法称为 Selective Replay。

不管是 Non-Selective Replay 还是 Selective Replay, 它们都是基于发射队列进行 replay 的方法，很多指令在被仲裁电路选中之后不能马上离开发射队列，因此这种方法最大的缺点就是降低了发射队列实际可用的容量，造成处理器无法最大限度地寻找程序的并行性。为了解决这种问题，现代的一些处理器采用了指令在被仲裁电路选中的时候马上离开发射队列的方法，当然这样需要额外的机制来处理指令的 replay 问题，这就是下一节介绍的方法。

2. Replay Queue Based Replay

在这种方法中，指令被仲裁电路选中之后，会马上离开发射队列，但是它并不会消失，而是进入另外一个部件 Replay Queue(RQ),这种设计方法的示意图如图 8.56 所示。

图 8.56 Replay Queue Based Replay

由于指令被仲裁电路选中之后，会马上离开发射队列，所以这种方法大大减轻了对发射队列的压力，提高了它的利用效率，这些离开的指令会进入到 RQ 中。当一条指令被验证为执行正确时，例如当一条指令顺利地离开流水线的时候 ( 也就是退休的时候 ), 它就可以离开 RQ, 使用这种方法可以支持由于 load 指令的 D-Cache 缺失引起的 replay, 也可以支持由于 store/load 违例、load/load 违例等引起的 replay。举例来说，当发现 load 指令的 D-Cache 缺失时，除了将和它相关的指令从流水线中抹掉，还需要将这些指令重新在 RQ 中唤醒，并向仲裁电路发出申请，而且它们相比于发射队列中的指令有着更高的优先级，这样可以将那些需要 replay 的指令重新送入 FU 中执行。一般情况下，从流水线的 Select 阶段到执行阶段 (Execute) 需要的周期数越多 ( 称这个时间为 S→E的时间 ),需要 replay 的指令个数也就越多，因此对于数据捕捉 (data-capture) 结构的发射队列来说，由于它的 S→E时间比较短，所以需要 replay 的指令个数相对就不多，可以简单地采用基于发射队列进行 replay 的方法；而对于非数据捕捉 (non-data-capture) 结构的发射队列来说，考虑到要读取物理寄存器堆 (Physical Register File), 它的 S→E时间会比较长一些，采用基于发射队列进行 replay 的方法会造成发射队列实际可用容量变得很小，所以都会配合使用基于 RQ 进行 replay 的方法，以降低对发射队列的压力。但是 RQ 需要的容量可能会很大，由于 RQ 也要参与仲裁和唤醒的过程，所以过大的 RQ 也会对处理器的速度产生负面的影响。在 Intel 的 Pentium 4 系列的处理器中就采用了这种基于 RQ 进行 replay 的方法，以应对 Pentium 4 处理器令人夸张的流水线级数。

即使在基于发射队列进行 replay 的方法中，在使用了 Load Position Vector 之后，并不是所有的指令都需要在被仲裁电路选中的时候继续停留在发射队列中，可以根据这条指令的 LPV 值来决定。如果一条指令的 LPV 值存在 1,说明这条指令和 load 指令相关，此时不能使这条指令被仲裁电路选中的时候离开发射队列；而如果一条指令的 LPV 值全是 0, 则此时说明这条指令和任何的 load 指令都无关，这条指令如果被仲裁电路选中，就可以马上离开发射队列了。

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

第 8 章 发射