第 7 章 寄存器重命名
书内第 195–229 页；PDF 第 207–241 页。原书疑点见校注。
- 7.1 概述
- 7.2 寄存器重命名的方式
- 7.2.1 使用 ROB 进行寄存器重命名
- 7.2.2 将 ARF 扩展进行寄存器重命名
- 7.2.3 使用统一的 PRF 进行寄存器重命名
- 7.3 重命名映射表
- 7.3.1 基于 SRAM 的重命名映射表
- 7.3.2 基于 CAM 的重命名映射表
- 7.4 超标量处理器的寄存器重命名
- 7.4.1 解决 RAW 相关性
- 7.4.2 解决 WAW 相关性
- 7.5 寄存器重命名过程的恢复
- 7.5.1 使用 Checkpoint
- 7.5.2 使用 WALK
- 7.5.3 使用 Architecture State
- 7.6 分发
7.1 概述
在一个程序的不同指令之间，存在很多的相关性 (dependency),所谓相关性，是指一条指令的执行依赖于另外一条指令的结果，可以将相关性分为下面的几类。
(1) 数据相关性 (Data Dependence), 这部分内容已经在前文进行了介绍，包括以下几种。
① Output dependence, 又称为先写后写 (Write After Write,WAW) 相关性，表示两条指令都将结果写到同一个目的寄存器中；
② Anti-dependence, 又称为先读后写 (Write After Read,WAR) 相关性，表示一条指令的目的寄存器和它前面的某条指令的源寄存器是一样的；
③ True dependence, 又称为先写后读 (Read After Write,RAW) 相关性，表示一条指令的源寄存器来自于它前面的某条指令计算的结果。
数据相关性是和寄存器直接相关的，只要在解码阶段得到了寄存器的名字，就可以找到这些相关性，它是本章介绍的重点。
(2) 存储器数据的相关性 (Memory Data Dependence),表示访问存储器的指令 ( 即 load 和 store 指令 ) 之间存在的相关性，这些相关性是和访问存储器的地址相关的，也可以分为先写后写 (WAW)、先读后写 (WAR) 和先写后读 (RAW) 三种类型，例如一条 load 指令的地址和它之前的一条 store 指令的地址相等，则它们之间就存在 RAW 相关性，这种相关性的解决方法将在以后的章节进行介绍。
(3) 控制相关性 (Control Dependence),由于分支指令而引起的相关性，使用分支预测可以解决，在前文已经进行讲述。
(4) 结构相关性 (Structure Dependence )，指令必须等到处理器当中某些部件 (structure) 可以使用的时候才可以继续执行，例如需要等到发射队列 (Issue Queue) 和重排序缓存 (ROB) 中有空闲的空间，或者功能单元 (FU) 的计算资源是空闲的等。
数据相关性的三种类型 WAW、WAR 和 RAW, 只有 RAW 是真的相关性，其他两种相关性都是和寄存器的名字有关的，可以通过使用不同的寄存器名字而解决，例如，图 7.1 表示了如何使用不同的寄存器名字解决 WAW 相关性。
图 7.2 表示了如何使用不同的寄存器名字解决 WAR 相关性。
图 7.1 通过更换寄存器来解决 WAW 相关性
R1 = R2 + R3 → R1 = R2 + R3
R1 = R4 × R5 → R6 = R4 × R5
图 7.2 通过更换寄存器名字来解决 WAR 相关性
R1 = R2 × R3 → R1 = R2 × R3
R2 = R4 + R5 → R6 = R4 + R5
由上面的两种情况可以看出，通过更换寄存器的名字，就可以解决 WAW 和 WAR 相关性了，因此这两种相关性也称为假的相关性，它之所以存在，是由于下述的原因。
(1) 有限个数的寄存器，导致必须在某些地方重复地使用寄存器。现在的 RISC 处理器一般都有 32 个通用寄存器，而 32 位的 x86 指令集只有 8 个通用寄存器，因此在 Intel 的处理器中很早就实现了寄存器重命名，使用更多的物理寄存器来弥补指令集上的短板。
(2) 程序中的循环体 (loop),如果在一个循环体中向寄存器 R1 写入了值，那么每次循环的时候都会向 R1 中写入值，这就产生了大量的 WAW 类型的相关性，虽然可以使用拆解循环体 (loop unrolling) 的方法来解决这个问题，但是由于有限个数的寄存器，在循环体拆解到某一个时刻，总会有寄存器都用完的那个时候，此时出现 WAW 相关性就是不可避免的了，而且这样还会导致程序变得很大，需要占用更多的存储空间，也导致了 I-Cache 缺失率的升高。
(3) 代码重用 (code reuse),例如一些很小的函数 (function),在一段时间内被频繁调用的话，那么这就和上述的循环体中的情况是一样的了，例如在函数中，向寄存器 R1 写入了值，那么如果频繁地调用这个函数，处理器中就存在大量的指令都向 R1 寄存器中写入值，即存在 WAW 相关性。虽然可以通过将函数程序嵌入到调用程序中 ( 即 inlining) 的方法来解决这个问题，但是仍旧会遇到上述的情况，寄存器会在某个时刻被用光，此时 WAW 相关性就不可避免，而且程序会变得很大，占用更多的存储空间，也导致了 I-Cache 缺失率的升高。
既然是由于有限个数的寄存器导致了上述假相关性的存在，这时候有一个很明显的解决办法，那就是增加指令集中寄存器的个数，但是这样做会导致处理器无法再兼容以前的程序，而向前兼容是处理器能够成功的一个重要条件 ( 当然这个也是包袱，最明显的例子就是 x86 指令集 ),如果增加了寄存器的数量，那么以前所有的程序都需要重新进行编译 ( 即 recompile),这显然是一项浩大的工程；而且，即使增加指令集中寄存器个数，也无法解决由于代码重用 (code reuse) (例如循环和子程序调用 ) 而产生的 WAW 相关性。
所以，最好的解决办法就是使用硬件管理的寄存器重命名 (Register Renaming), 处理器中实际存在的寄存器个数要多于指令集中定义的通用寄存器的个数，这些在处理器内部实际存在的寄存器称为物理寄存器 (Physical Register),与之对应的，指令集中定义的寄存器称为逻辑寄存器 (Logical Register, 或 Architecture Register)。逻辑寄存器指的是在指令集中定义的通用寄存器，例如 MIPS 处理器定义了 R0～R31 这 32 个通用寄存器，它们就是逻辑寄存器，而物理寄存器是指经过寄存器重命名之后使用的寄存器，它才是在处理器中真正存在的寄存器，例如一个处理器中有 128 个物理寄存器，就表示程序可以真正使用的寄存器个数是 128 个，一般情况下，物理寄存器的个数要多于逻辑寄存器的个数，这样才可以使寄存器重命名得以发挥作用。
处理器在进行寄存器重命名的时候，会动态地将逻辑寄存器映射到物理寄存器，这样可以解决 WAW 和 WAR 的相关性，图 7.3 表示了使用寄存器重命名的方法来解决 WAW 和 WAR 相关性的过程。
图 7.3 使用寄存器重命名解决 WAW 和 WAR 相关性
原始的程序：
r5 = r3 + r2
r6 = r4 + r2
r4 = r7 × r1
r6 = r6 - 1
经过寄存器重命名之后的程序：
p8 = p5 + p4
p9 = p3 + p4
p10 = p1 × p2
p11 = p0 - 1
图 7.3 给出的例子中，有 r0~r7 共 8 个逻辑寄存器，有 p0～p20 共 21 个物理寄存器，在编写程序的时候 (或者编译器编译的时候 ),会直接使用指令集中定义的逻辑寄存器，如图 7.3 中给出的原始程序，箭头表示了指令之间存在的 WAW 和 WAR 相关性，这些假的相关性制约了原始的程序可以获得的并行性，需要通过寄存器重命名的方法将它们消除掉。图 7.3 中的重命名映射表 (Register Renaming Table, Intel 也将其称为 Register Alias Table,RAT) 和空闲寄存器列表 (Free Register List) 用来完成这个过程，其中重命名映射表用来保存已经存在的映射关系，例如一个逻辑寄存器映射到了哪个物理寄存器。对于程序中的指令来说，它的源寄存器通过读取重命名映射表，就可以得到它们对应的物理寄存器了，顾名思义，重命名映射表是一个表格，它可以基于 SRAM 来实现，也可以基于 CAM 来实现；空闲寄存器列表用来记录哪些物理寄存器是空闲的，在进行寄存器重命名时，会通过这个表格来获得空闲的物理寄存器的编号。图 7.3 中的右边部分就是将原始程序经过寄存器重命名之后得到的程序，这个程序将真正地在处理器内部被执行，经过重命名之后的程序已经不存在 WAW 和 WAR 的相关性了，因此在超标量处理器中，这个程序可以获得最大的并行性，从而尽快地执行完毕。
7.2 寄存器重命名的方式
寄存器重命名 (Register Renaming) 只是提出了一个概念，具体的实现方式是有很多种的，这就像 ISA 只是定义了处理器的一种行为，具体如何实现是千差万别的，同样是基于 x86 指令集，Intel 和 AMD 的处理器就是截然不同的。对于寄存器重命名来说，概括起来，有三种方式都可以实现它，这三种方式分别如下。
(1) 将逻辑寄存器 (Architecture Register File,ARF) 扩展来实现寄存器重命名；
(2) 使用统一的物理寄存器 (Physical Register File,PRF) 来实现寄存器重命名；
(3) 使用 ROB 来实现寄存器重命名。
上面的三种寄存器重命名的实现方式，各有其优点和缺点，在现代的处理器中均有采用，例如 Intel 多采用第 (3) 种方法，而 MIPS 则采用第 (2) 种方法等。这三种方法的本质都是要将指令集中定义的逻辑寄存器，在处理器的执行过程中，动态地映射到处理器内部实际使用的物理寄存器上，使用这些物理寄存器来代替逻辑寄存器，从而可以增加寄存器的个数。要实现寄存器重命名，一般都要考虑下面的内容。
(1) 什么时候占用一个物理寄存器？这个物理寄存器来自于哪里？
(2) 什么时候释放一个物理寄存器？这个物理寄存器去往何处？
(3) 发生分支预测失败时 (mis-prediction),如何进行处理？
(4) 发生异常时 (exception),如何进行处理？
解决了上面的内容，也就完成了寄存器重命名的设计，上面讲述的三种寄存器重命名的方法对这几个问题都有对应的解决方法，下面分别进行介绍。
7.2.1 使用 ROB 进行寄存器重命名
这种方法将重排序缓存 (ROB) 作为了物理寄存器，在其中存储着所有推测状态 (speculative) 的结果，而使用逻辑寄存器 (ARF) 存储所有正确的结果，因此在使用这种方法的处理器中，有 ROB 和 ARF 两个地方都可以存储寄存器的结果。在普通流水线的标量 (scalar) 处理器中，其实在硬件上都有 ARF, 这种方法就相当于使用 ROB 对 ARF 进行了扩展。为什么会想到使用 ROB 进行寄存器重命名呢？这其实是一件很自然的事情，在超标量处理器中，每条指令都会将自身的信息按照程序中原始的顺序存储到 ROB 中，当一条指令将结果计算出来之后，会将其写到 ROB 中，但是由于分支预测失败 (mis-prediction) 和异常 (exception) 等原因，这些结果未必就是正确的，它们的状态被称为推测的 (speculative)。在一条指令离开流水线之前 (也就是退休之前 ), 它都会一直待在 ROB 中，只有当指令变为流水线中最旧的指令，并且被验证为正确的时候，才会离开 ROB, 并使用它的结果对处理器的状态进行更新，例如将结果写到 ARF 中，这种方式相当于将物理寄存器 (PRF) 和 ROB 集成到了一起，如图 7.4 所示。
当一条指令被写到 ROB 中一个表项 (entry) 的同时，这个表项在 ROB 中的编号也就成为了这条指令的目的寄存器对应的物理寄存器，这样就将一个逻辑寄存器和 ROB 中一个表项的编号建立了映射关系，完成了对一条指令的目的寄存器进行重命名的过程，所以使用这种方式可以简化寄存器重命名的过程，只要 ROB 中有空闲的空间，寄存器重命名就可以一直进行。由于一条指令在推测状态 (speculative) 的时候，只是将结果写到 ROB 中，所以在 ROB 中存储着所有没有离开流水线的指令结果；而逻辑寄存器 (ARF) 中存储着所有 “最新”离开流水线的指令结果，这里使用 “最新”这个词，是为了表示，如果一条指令离开了流水线，将其结果更新到 ARF 之后，又执行了另外一条指令，也使用了同样的目的寄存器 (例如这两条指令都向寄存器 R1 中写入值 ),那么此时 ARF 中存储内容的就不是这个逻辑寄存器 “最新”的值了，这需要使用重命名映射表 (mapping table) 来指示每个逻辑寄存器的值是位于 ROB 中还是位于 ARF 中，这个过程如图 7.5 所示。
图 7.4 将 PRF 和 ROB 集成在一起，进行寄存器重命名
图 7.5 基于 ROB 进行寄存器重命名
在图 7.5 所示的方法中，如果一个逻辑寄存器的值还在 ROB 中，那么重命名映射表会给出这个逻辑寄存器在 ROB 中所占用表项的编号；当一条指令计算完毕，它的结果被存储到这条指令在 ROB 中对应的空间内；当这条指令要离开流水线，也就是退休 (retire) 的时候，它的结果会从 ROB 中搬移到 ARF 中，这个位置变动的信息也需要随之更新到重命名映射表中，这样，一个寄存器在它的生命周期内，会有两个存放的位置，这会对指令的操作数读取产生负面的影响，因此在实际的处理器当中，都会配合数据捕捉 (data-capture) 的发射 (issue) 方式，并采用 payload RAM 来存储需要的操作数，具体的内容将在后文进行介绍。
使用这种基于 ROB 进行寄存器重命名的方式，虽然便于管理，但是它也有一些缺点，主要可以概括为两个方面。
(1) 很多指令并没有目的寄存器，因此也就不需要对目的寄存器进行重命名，但是每条指令都需要占用 ROB 中的一个表项 (entry),也就是说，一条指令即使没有目的寄存器，它在 ROB 中对应的表项也没有办法将物理寄存器省掉，但是这部分资源并没有被有效地利用，这样导致了硅片面积的浪费。
(2) 对于一条指令来说，它既可以从 ROB 中读取源操作数，也可以从 ARF 中读取源操作数，所以 ROB 和 ARF 都要支持最坏的情况，也就是在一个周期内执行的所有指令都需要读取 ROB( 或 ARF),这样导致 ROB 和 ARF 的读端口都会非常多，例如对于 4-way 的超标量处理器来说，如果一条指令的源寄存器有 2 个，那么 ARF 和 ROB 都需要支持 $2\times4=8$ 个读端口，这对芯片的面积和延迟造成了很大的负面影响。
总体来看，基于 ROB 的寄存器重命名方式虽然有缺点，但是这种方式容易实现，相应的设计复杂度也不高，因此可以获得不错的性能，Intel 在自己的很多处理器中采用了这种方法，基于 P6 架构的所有处理器都可以见到它的影子，例如 Pentium-Pro, Pentium Ⅲ、Pentium M 等处理器。
7.2.2 将 ARF 扩展进行寄存器重命名
这种方法是基于 ROB 进行重命名方法的延伸，由于在指令的执行过程当中，很多指令并没有目的寄存器，例如 store 指令、分支指令和比较指令等，在一般的典型程序中，这些指令占据了大约 25% 的比例8 (不同的应用程序或者不同的 ISA, 这个比例可能会有不同 )。在使用 ROB 进行寄存器重命名的方法中，ROB 中的每个表项 (entry) 都会留出一个空间用来存储指令的结果，也就是说，在 ROB 中的这部分区域会有很大一部分的空间是没有被使用而浪费掉的。因此，可以使用一个独立的存储部件，用来存储流水线中所有指令的结果，只有那些存在目的寄存器的指令才会占据这个存储部件当中的存储空间，这个存储部件称为 PRF(Physical Register File), 它可以看作是 ARF(Architecture Register File) 的扩展。这个 PRF 的地位和上面方法中的 ROB 是一样的。每次指令被解码之后，那些存在目的寄存器的指令会占据 PRF 的一个表项，这个表项的编号就是对应的物理寄存器的编号了；每次当指令退休 (retire) 的时候，由于指令的结果会被写到 ARF 中，所以在 PRF 中，这条指令所占据的空间也就没有用处了，可以进行释放，因此，PRF 本质上也可以用 FIFO 来实现，这和 ROB 是一样的。
指令在进行寄存器重命名的时候，如果它存在目的寄存器，则这条指令会占据 PRF 的一个空间，指令在得到结果之后，会首先将这个结果存储到 PRF 中，等到这条指令退休 (retire) 的时候，才会将它的结果搬移到 ARF 中，这个过程和基于 ROB 进行重命名的方式是一样的。如果 PRF 中已经没有空间了，那么流水线中，寄存器重命名阶段之前的所有流水线都需要暂停，直到流水线中有指令离开而释放 PRF 的空间时，寄存器重命名阶段之前的流水线才可以继续执行。
这种寄存器重命名的方式也需要一个重命名映射表，在其中记录了每个逻辑寄存器的值是位于 PRF 中还是 ARF 中，一条指令在 PRF 中对应的地址需要存储到这个表格中，如图 7.6 所示。
一个逻辑寄存器的值在其生命周期内，仍然可能存在于 PRF 和 ARF 两个地方，因此仍然会对后面的指令使用这个寄存器作为源操作数的过程产生影响，事实上，只要逻辑寄存器的值发生了存储地方的变化，这种影响就是存在的。
图 7.6 将 ARF 扩展进行寄存器重命名
7.2.3 使用统一的 PRF 进行寄存器重命名
在这种方法中，将上一种方法使用的 ARF 和 PRF 进行了合并，合并之后的部件称为统一的 PRF(Physical Register File),在其中存储了所有推测的 (speculative) 和正确的 (retire) 的寄存器值。很显然，这个统一的 PRF 中，物理寄存器的个数肯定要多于指令集中定义的逻辑寄存器的个数，需要注意的是，这个统一的 PRF 和上一节中的 PRF 是不同的，在这个 PRF 中，没有和指令产生映射关系的寄存器都是处于空闲 (free) 状态，使用一个空闲列表 (free list) 来记录这个 PRF 中哪些寄存器处于空闲状态；当一条指令被寄存器重命名，并且它存在目的寄存器的时候，它就会占据 PRF 当中的一个寄存器，这个寄存器就处于被占用的状态，处于这个状态的寄存器会经历值没有被计算出来、 值被计算出来但是没有退休 (retire)、退休这三个过程，在此过程中，并不需要将寄存器的内容进行搬移，这样便于后续的指令读取操作数。这种寄存器重命名的方法也需要一个重命名映射表，用来存储每个逻辑寄存器和物理寄存器的对应关系，如图 7.7 所示。
图 7.7 使用统一的 PRF 进行寄存器重命名
图 7.7 中，用来记录空闲物理寄存器的空闲列表 (Free List) 可以使用 FIFO 来实现，所有空闲状态的物理寄存器的编号都存储在其中，对于一个 4-way 的超标量处理器来说，由于每周期需要对四条指令进行寄存器重命名，需要这个 FIFO 每周期最多可以提供四个物理寄存器的编号，也就是每周期可以读取四个值。如果在流水线中，每周期可以退休 (retire)
的指令个数最多也是四条，那么每周期最多有四个空闲的物理寄存器的编号会写到这个 FIFO 中，也就是说，这个 FIFO 每周期最多可以写入四个值。这种多端口的 FIFO 需要使用交叠 (inter1eaving) 的方式来实现，具体的设计过程在前文已经有介绍，此处不再赘述。
一条指令在寄存器重命名的时候，需要对源寄存器和目的寄存器都进行处理，对于源寄存器来说，它会去查找重命名的映射表 (mapping table, Intel 将其称为 RAT, 本书在后文采用这种称呼 ), 找出它对应的物理寄存器的编号。同时，如果这条指令存在目的寄存器的话，需要为这个目的寄存器指定一个空闲状态的物理寄存器，这需要从空闲列表 (Free List) 中进行读取。如果此时空闲列表已经空了，那么就表明此时的物理寄存器已经全部被占用，则流水线的重命名阶段及其之前的流水线就要被暂停，直到有指令退休 (retire) 而释放掉物理寄存器为止 (后面会介绍一个物理寄存器何时会变为空闲状态 )。指令的目的寄存器会被重命名为空闲列表所提供的物理寄存器，同时这个新的对应关系会更新到 RAT 当中。
当需要从外部查看处理器的状态时，很多的物理寄存器由于处在推测 (speculative) 的状态，是不能够被外部看到的，一条指令只有退休 (retire) 的时候，它的结果才会被外部看到。要实现这样的功能，只使用上面所说的 RAT 就不能够满足要求了，此时还需要使用另外一个 RAT, 用来存储所有 “退休”状态的指令和物理寄存器的对应关系。每当指令退休的时候，它对应的映射关系就会写到这个 RAT 中，外界通过查询这个 RAT, 就可以找到逻辑寄存器此时对应的物理寄存器，这样避免了将内部一些可能错误的状态暴露给程序员，因此使用这种基于统一的 PRF 进行寄存器重命名的方法，在处理器中需要使用两个 RAT 来配合进行工作。
一个物理寄存器被占用之后，何时可以再次变为空闲状态呢？很显然，当一个物理寄存器不再被它后面的指令使用时，这个物理寄存器就可以变为空闲状态了，从理论上来讲，只要最后一条使用这个物理寄存器的指令由于退休而顺利地离开了流水线，这个物理寄存器就可以变为空闲状态。但是，对于一个物理寄存器来说，要识别出最后一次使用它的指令，并不是一件很直接的事情，虽然编译器可以很容易地获得这个信息，但是当今所有的指令集中，都没有地方能够装载这个信息来通知处理器的硬件，所以处理器可以采用一种很简单也很保守的方法，如图 7.8 所示。
图 7.8 当一条指令退休的时候，可以将它对应的旧映射关系进行释放
(a) ADD r1, r2, r3 → (a) ADD p1, p7, p9
⋮ ⋮
(b) MUL r1, r4, r5 → (b) MUL p6, p8, p2
当一条指令和后面的某条指令都写到同一个目的寄存器时，则后面的指令退休的时候，前面指令对应的物理寄存器就已经没有用处了，例如在图 7.8 中，指令 (a) 和指令 (b) 都使用了同一个目的寄存器 r1,如果一条指令使用了指令 (a) 的目的寄存器 p1 作为源寄存器，那么这条指令必然是位于指令 (a) 和指令 (b) 之间的，当指令 (b) 退休的时候，肯定就可以保证以后再也没有指令使用物理寄存器 p1 作为源寄存器了，所以物理寄存器 p1 可以变为空闲状态，指令 (b) 后面的指令使用逻辑寄存器 r1 作为源寄存器的时候，肯定就会使用物理寄存器 p6 了。也就是说，当指令 (b) 退休的时候，可以将物理寄存器 p1 变为空闲状态，本来对于指令 (b) 来说，物理寄存器 p6 才是它的目的寄存器，p1 和它并没有关系，为了实现上述的功能，在 ROB 中，除了记录逻辑寄存器当前对应的物理寄存器之外，还需要存储它之前对应的物理寄存器，以便于在指令退休的时候 ( 例如指令 (b)),将它对应的旧映射关系进行释放。
到目前为止，对三种寄存器重命名的方式进行了逐一的介绍，从寄存器重命名的过程来看，基于 ROB 的重命名方式是很简单的，它不需要管理哪些物理寄存器是可以使用的，在指令被写到 ROB 的时候，也就完成了寄存器重命名的过程，因此这个过程不需要复杂的控制逻辑，也就不会增加太多的硬件资源。而对于将 ARF 进行扩展的寄存器重命名方法来说，由于其中的 PRF 也是按照 FIFO 的方式进行管理，所以这个过程和基于 ROB 的方法是类似的，也相对比较简单；而使用统一的 PRF 进行寄存器重命名的方法，则需要更复杂的控制逻辑来管理重命名的过程，它需要使用一个表格 (free list) 来存储所有空闲的物理寄存器的编号，同时还需要两个重命名映射表 (RAT) 配合才可以正常进行工作，因此这种方法的设计难度是比较大的，但是，为什么还会有处理器采用这种方式呢？因为这种寄存器重命名的方式有两个优势。
第一，寄存器的值只需要被写入一次，不需要再进行移动，而在另外两种方法中，一个寄存器的值在它的生命周期内有两个地方要存放。第一次写到 ROB 或 PRF 中，第二次写到 ARF 中，很显然两次写入需要消耗更多的能量，因此这种方法在功耗上会占据优势，尤其是对于应用在嵌入式领域的 RISC 处理器来说，这更有吸引力。
第二，在这种方法中，一条指令的源寄存器的值只能存储于一个地方，即 PRF 中，而在其他两种方法中，有两个地方都有可能存储源寄存器的值，即 ARF 和 ROB( 或 PRF)。在前面说过，如果有两个地方都可以存储寄存器的值，那么当一条指令的目的寄存器的值从 ROB( 或者 PRF) 中搬移到 ARF 中的时候 ( 即这条指令退休的时候 ), 需要将这个信息通知给流水线中所有将这个寄存器作为操作数的指令，这样肯定增加了连线的数量，也会使功耗有所增大，并且增加了设计的复杂度。
正因为基于统一的 PRF 进行重命名的方式有上述的优势，现代的很多处理器，例如 MIPS R10000、Alpha 21264 和 Pentium 4 等处理器，都采用了这种方法进行寄存器重命名。
7.3 重命名映射表
在上面讲述的三种寄存器重命名方式中，都使用了重命名映射表 (mapping table, 在后文中简称为 RAT),用它来记录逻辑寄存器和物理寄存器之间的映射关系，指令在进行寄存器重命名的时候，它的源寄存器会通过查找 RAT 而得到其对应的物理寄存器的编号，而指令的目的寄存器也会对应到一个新的物理寄存器，这个映射关系会被写到 RAT 中，供以后的指令使用。顾名思义，RAT 是一个表格，使用逻辑寄存器作为地址来进行寻址，对于指令的源寄存器来说，可以从这个表格得到对应的物理寄存器的编号；对指令的目的寄存器来说，会将物理寄存器的编号写到这个表格中。这个表格在具体的物理实现层面上，主要有两种方式，一是基于 SRAM(SRAM-Based RAT,sRAT),二是基于 CAM(CAM-Based RAT，cRAT),这两种方式如图 7.9 所示。
在图 7.9 中，逻辑寄存器有 32 个 (R0~R31),需要使用 5 位来表示；物理寄存器有 64 个 (P0～P63),需要使用 6 位来表示。基于 SRAM 的重命名映射表 ( 在后文简称为 SRAT)
使用 SRAM( 或者直接使用寄存器 ) 作为表格的载体，考虑到每条指令的多个源寄存器和目的寄存器都可以在一个周期内寻址它，因此需要使用多端口的 SRAM( 或者寄存器 )。这个表格使用逻辑寄存器的编号对其进行寻址，因此在这个表格中，表项 (entry) 的个数等于逻辑寄存器的个数，即 32 个，每个表项中存放着对应的物理寄存器的编号，因此这个 SRAT 占据的存储空间是 $32\times6\mathrm{bits}=192\mathrm{bits}$, 如图 7.9(a) 所示为这种设计的示意图。
图 7.9 RAT 的两种物理实现方法
基于 CAM 的重命名映射表 ( 在后文简称为 cRAT) 虽然也是使用逻辑寄存器的编号进行寻址，但是这个表格的载体使用了内容寻址的存储器 ( 即 CAM),其大小等于物理寄存器的个数，在每个表项中都存放了逻辑寄存器的编号。在对这个表格进行寻址时，虽然也是使用逻辑寄存器的编号，但是它会和每个表项中存放的逻辑寄存器的编号进行比较，如果一个表项中存在有效的映射 (v 有效 ),并且比较结果也相等，则这个表项在 cRAT 中的地址就是对应的物理寄存器的编号了，这种方式使用了 CAM 作为表格的载体，占用的存储空间是 $64\times5\mathrm{bits}=320\mathrm{bits}$, 如图 7.9(b) 所示为这种设计的示意图。
由于 SRAM 的访问速度要快于 CAM, 而且基于 SRAM 的重命名映射表更节省存储器资源，毕竟这个表格的容量等于逻辑寄存器的个数，这个数量一般不大 (32 位的处理器一般有 16~32 个逻辑寄存器 ),也不会随着处理器性能的提高而显著变大，所以，上述两种方法相比较之下，基于 SRAM 的重命名映射表由于占用面积小、速度快且功耗低，这种优势随着硬件复杂度的上升变得更加明显，因为在提升处理器性能的同时，需要随之增加物理寄存器的个数，当物理寄存器的个数比较多时，sRAT 和 cRAT 这两种方法的区别就很明显了。例如，对于 4-way 的超标量处理器来说，当它的物理寄存器的个数为 128 个时，和访问 cRAT 相比，访问 sRAT 会节省 33% 的功耗，速度也会快 12.1%;而当物理寄存器的个数增长为 512 个时，差距就变成了节省 416%的功耗，速度快 34.6%26。
但是在现实世界的处理器中，仍然存在一些处理器在使用基于 CAM 的重命名映射表，这是为什么呢？在这种方式中，对 cRAT 进行 Checkpoint 只需要保存状态位 ( 即图 7.9 中的 V, 实际当中还有其他的一些状态位 ),而不需要将整个 cRAT 进行保存，这样就大大减少了 Checkpoint 电路的面积，因此较之 sRAT,cRAT 并不会随着 Checkpoint 个数的增加而引起复杂度和面积的显著增加。当 Checkpoint 的个数超过一定的值时，cRAT 就有优势了，而对于现代的处理器来说，更深的流水线和更高的执行并行度都会导致需要更多的 Checkpoint, 所以 cRAT 在此种情况下是一个很好的选择，例如 IBM 的 POWER 系列处理器均采用了基于 CAM 的重命名映射表，POWER 系列处理被用于 IBM 的服务器当中。
本节对这两种重命名映射表的实现方式进行说明，这两种方式在现代的处理器中都有使用，在具体的设计中采用哪种方式，需要根据处理器的功耗、面积和性能方面的要求，综合考虑之后才可以决定。
7.3.1 基于 SRAM 的重命名映射表
在基于 SRAM 的重命名映射表 (sRAT) 中，表项 (entry) 的个数等于处理器中逻辑寄存器的个数，使用逻辑寄存器的编号作为地址对 SRAT 进行寻址，对于每个逻辑寄存器来说，在 SRAT 中只有一个表项与之对应。也就是在任意时刻，每个逻辑寄存器都只有一个物理寄存器与之对应，这个对应关系不需要任何的标志位。当需要对分支指令的状态进行 Checkpoint 保存时，需要将整个 SRAT 都保存起来，因此这种方法的每个 Checkpoint 会占用大量的面积，正是由于这种限制，不可能将 Checkpoint 的个数做得很多，例如 MIPS R10000 处理器中27、28，就使用了这种基于 SRAM 的重命名映射表，只对分支指令使用了四个 Checkpoint, 也就是最多允许四条分支指令存在于流水线中，图 7.10 所示为 SRAT 的示意图。
图 7.10 基于 SRAM 的重命名映射表的示意图
对于 4-way 的超标量处理器来说，每周期最多需要对四条指令进行寄存器重命名，也就是 SRAT 需要支持 8 个读端口和 4 个写端口 ( 假设每条指令包括 2 个源寄存器和 1 个目的寄存器 ),每条指令的源寄存器都需要查找这个表格，得到对应的物理寄存器的编号，这需要使用 8 个读端口；每条指令的目的寄存器都需要找到一个空闲的物理寄存器，将它的编号写到表格中，这样就需要使用 4 个写端口；为了指示哪些物理寄存器是空闲状态的，还需要使用一个表格 (free list) 来进行记录；新写入到 sRAT 的值会覆盖掉原来旧的对应关系，如果不将这个旧的对应关系记录下来，那么这个信息就永远地丢失了，这样当然是不可以的，原因有二。
(1) 在之前说过，一条指令在退休 (retire) 的时候，会将它之前对应的物理寄存器变为空闲状态，因此在一个物理寄存器的编号写入到 SRAT 之前，需要将被覆盖的信息保存起来，什么地方可以保存这个信息？其实在 ROB 中就可以，在其中记录了逻辑寄存器对应的新旧物理寄存器，关于 ROB 在后文会详细介绍。
(2) 当一条指令之前存在异常 (exception) 或者分支预测失败 (mis-prediction) 的指令时，这条指令需要从流水线中被抹掉，同时这条指令对 RAT 的修改也需要被恢复过来，通过将一条指令旧的映射关系保存起来，可以协助完成 RAT 修复的过程。
从概念上来讲，基于 SRAM 的重命名映射表 (sRAT) 是最容易被理解的，较之基于 CAM 的重命名映射表 (cRAT), 读写速度会快一些，设计复杂度也不会随着物理寄存器个数的增加而变大，但是这种方式有一个最大的缺点，那就是无法对 RAT 使用个数比较多的 Checkpoint,因为每个 Checkpoint 都需要将 SRAT 复制一份，随着处理器并行度的提高，会有更多的指令存在于流水线中，也就是流水线中分支指令的个数也随之增多，这就需要对分支指令使用个数更多的 Checkpoint,于是矛盾就产生了：基于 SRAT 的寄存器重命名方法中，不能使用个数太多的 Checkpoint,而处理器性能的提高要求更多的分支指令存在于流水线中，这个矛盾如何解决？
在超标量处理器中，大量地使用了预测算法，例如分支预测、load/store 相关性预测、数值预测等，只要预测的准确度很高，它对于提高处理器的性能就可以起到很大的作用，上面所说的矛盾就可以使用预测方法来解决，因为分支指令一旦预测正确，那么它对应的 Checkpoint 其实是没有作用的，因此可以对分支指令预测的正确度也进行预测，对于那些预测正确率很高的分支指令，就不需要对它们使用 Checkpoint 了，而那些经常预测错误的分支指令 (很多分支指令本身就是没有规律，或者规律很难被发现，导致了这种分支指令预测的正确率很低 ),对它们就要使用 Checkpoint, 由于经常预测错误的分支指令只是一小部分，因此这种方法可以大大减少 Checkpoint 的个数。
但是，那些没有使用 Checkpoint 的分支指令，一旦被发现预测错误了，那么就需要使用速度比较慢的方法对 RAT 进行恢复，在后文会对这些恢复方法进行介绍，由于这种情况发生的频率很低，所以不会对性能造成太大的负面影响。
7.3.2 基于 CAM 的重命名映射表
从功能上来看，这种重命名映射表的功能和上面讲述的 SRAT 是一样的，都是用来记录逻辑寄存器和物理寄存器的对应关系的，但是它们在实现上却大不相同，虽然也是使用逻辑寄存器的编号对其进行寻址，但是它是一个内容寻址的存储器 (CAM), 它不会对地址直接进行解码，而是将这个地址和存储器中每个表项 (entry) 的内容进行比较，比较结果是相等的那个表项的地址，就是最终需要的结果，这种寻址方式和全相连结构 (fully-associative) 的 Cache 是一样的。在基于 CAM 的重命名映射表中 (cRAT),由于要找到逻辑寄存器和物理寄存器的对应关系，因此逻辑寄存器的编号就是每个表项中保存的内容，而物理寄存器的编号则是最后的结果。在 cRAT 中，表项的个数等于物理寄存器的个数，使用逻辑寄存器的编号对 cRAT 进行 CAM 方式的寻址，每个逻辑寄存器在 cRAT 中只有一个有效的表项与之对应，也就是在任意时刻，每个逻辑寄存器都只有一个物理寄存器与之对应，这可以使用一个有效位 (V) 来表示。每次对 cRAT 进行 Checkpoint, 只需要保存这个有效位即可。如图 7.11 所示为一个支持四个 Checkpoint 的 cRAT, 这种方式的 Checkpoint 由于占用的资源很少，所以可以将 Checkpoint 的个数做得很大，例如 Alpha 21264 处理器就使用 cRAT 进行寄存器重命名，包括了 80 个 Checkpoint,也就是最大允许 80 条分支指令存在于流水线中。事实上，这个处理器为流水线中的每条指令都使用了一个 Checkpoint, 这样任何指令发生异常 (exception) 时，都可以快速地进行状态恢复，这也是使用 cRAT 最大的优势了。
图 7.11 基于 CAM 的重命名映射表的结构图
在如图 7.11 所示的 cRAT 中，共有四个 Checkpoint(GC0～GC3),用来对有效位 (V) 进行保存，对于一个 4-way 的超标量处理器来说，每周期最多需要对四条指令进行寄存器重命名，也就是 cRAT 需要支持 8 个读端口和 4 个写端口 ( 假设每条指令包括 2 个源寄存器和 1 个目的寄存器 )。对于写 cRAT 来说，并不需要使用 CAM 的方式进行寻址，只需要将其作为一个普通的存储器，使用物理寄存器的编号作为地址就可以了。其实 cRAT 是由 CAM＋SRAM 组成的，如图 7.12 所示，SRAM 部分用来存储每个物理寄存器对应的逻辑寄存器的编号，而 CAM 部分用来进行内容的比较，每个表项的比较结果都会送到一个编码器 (Encoder) 中，编码器会结合每个表项是否有效 (V) 的信息，将最终匹配的那个物理寄存器的编号进行输出，这就是读取 cRAT 的过程了。
图 7.12 使用 CAM＋SRAM 的方式组成的 cRAT
而对于写入 cRAT 来说，就是直接使用物理寄存器的编号作为地址，写入到图 7.12 中的 SRAM 部分，因此在写入时和普通的 SRAM 是一样的。
基于 cRAT 进行寄存器重命名的方式，仍需要使用空闲列表 (free list) 来记录哪些物理寄存器是空闲的，对于一个物理寄存器何时可以变为空闲的状态，这和前文讲述的是一样的，需要等到后面写入到同一个逻辑寄存器的指令退休 (retire) 的时候，才可以将这个逻辑寄存器之前对应的物理寄存器变为空闲状态。正因为如此，在 cRAT 中，并不是一个物理寄存器对应的有效位 (V) 是 0, 就表示这个物理寄存器是空闲状态，有可能是这个映射关系刚刚被覆盖而已；但是一个物理寄存器变为空闲状态时，这个物理寄存器在 cRAT 中对应的有效位 (V) 肯定是 0, 这是毋庸置疑的。对物理寄存器何时变为空闲状态进行管理，需要使用 ROB 和空闲列表 (free list) 配合来实现，并不需要 cRAT 的参与。
这种重命名映射表最大的优势就是 Checkpoint 所占用的资源很少，每当对 cRAT 进行 Checkpoint 的时候，只需要保存这个表格的有效位 (V) 就可以了。举例来说，在一条分支指令进行寄存器重命名之前，将此时 cRAT 中的有效位 (V) 保存起来，就完成了 Checkpoint 的过程；当在流水线的后续阶段，发现这条分支指令预测失败的时候，将这条分支指令对应的 Checkpoint 写回到 cRAT 的有效位 (V),就可以完成对 cRAT 的恢复，这个过程其实和基于 sRAT 进行寄存器重命名的方法是相同的，只不过对 RAT 保存的内容只有有效位 (V) 而已。
还需要注意的是，一个物理寄存器对应的有效位 (V) 即使是 0, 也并不能表示它已经变为了空闲状态，有可能是它的映射关系刚刚被覆盖而已，当此时进行 Checkpoint 保存的时候，保存的就是这个状态；而经过一段时间之后，当需要使用这个 Checkpoint 对 cRAT 进行状态恢复时，这个物理寄存器可能已经变为了空闲状态，当然，此时 Checkpoint 仍旧会将它的有效位 (V) 恢复成 0, 这样不会引起任何错误，因为一个物理寄存器的有效位 (V) 是 0 也可以表示这个物理寄存器处于空闲状态，也就是说，此时状态恢复的内容，和状态保存之时已经不一样了。在状态保存的时候，很多不是空闲状态的物理寄存器，此时都已经变为了空闲状态，当然，这没有问题，因为在一条指令进行 Checkpoint 状态保存的时候，在它之前进入到流水线的指令，只要不发生异常 (exception) 和分支预测失败 (mis-prediction),都是允许离开流水线而退休 (retire) 的，因此这些指令可以将对应的物理寄存器变为空闲状态。
但是对 cRAT 中的一个物理寄存器的有效位 (V) 来说，在进行 Checkpoint 保存的时候为 0, 到了状态恢复的时候，就有可能已经变为 1 了。一个典型的情况就是这个物理寄存器在变为空闲之后又被新的指令所使用，但是既然要进行状态恢复，就表示这些新的指令肯定是处于异常 (exception) 或者分支预测失败 (mis-prediction) 的路径上，在状态恢复时，这些物理寄存器对应的有效位 (V) 就应该都被恢复成 0, 这样就消除了这些错误路径上的指令对 cRAT 的影响了，使用 Checkpoint 就可以达到这样的效果。
为了便于理解 cRAT 的状态保存和恢复的过程，下面使用一个例子进行讲解，考虑下面的汇编代码。
指令 A: addi r5, r0, 1
指令 B: addi r7, r0, 2
指令 C: addi r6, r7, 3
指令 D: addi r7, r7, r1
指令 E: addi r7, r7, r2
指令 F: beq r7, r3, TARGET1
指令 G: add r9, r5, r6
指令 H: add r7, r9, r9
上面的汇编程序在基于 cRAT 进行寄存器重命名的方法中，是如何执行的呢？下面给出这个执行过程。
(1) 在分支指令 F 进行寄存器重命名的时候，需要对 cRAT 进行 Checkpoint 保存，此时cRAT 的内容如表 7.1 所示 ( 假设在这个程序执行之前，cRAT 是空的 )。
表 7.1 分支指令 F 进行寄存器重命名之前，cRAT 的内容
| 指令 | Phy. Reg | Arch. Reg | V | GC0 | GC1 | GC2 | GC3 |
|---|---|---|---|---|---|---|---|
| P0 | |||||||
| ⋮ | ⋮ | ⋮ | ⋮ | ||||
| A | P10 | r5 | 1 | 1 | |||
| B | P11 | r7 | 1→0 | 0 | |||
| C | P12 | r6 | 1 | 1 | |||
| D | P13 | r7 | 1→0 | 0 | |||
| E | P14 | r7 | 1 | 1 | |||
| P15 | 0 | 0 | |||||
| P16 | 0 | 0 | |||||
| P17 | 0 | 0 | |||||
| ⋮ | ⋮ | ⋮ | ⋮ | ||||
| P63 | 0 | 0 |
由于指令 F 是分支指令，不包括目的寄存器，因此也就不需要占用 cRAT 的空间了，而指令 B、D、E 都写同一个逻辑寄存器 r7, 因此当指令 E 被寄存器重命名之后，物理寄存器 P14 和逻辑寄存器 r7 就是最新的对应关系，其他两条指令 B 和 D 对应的映射关系应该变为无效。也就是说，它们在 cRAT 中占用的空间都应该变为无效的状态，这在表 7.1 中用 (1→0) 来表示，在此时对 cRAT 进行状态保存的时候，指令 A～E对应的有效位 10101 就会被写到 GC0 中。
(2) 在指令 G、H 被寄存器重命名之后，分支指令 F被发现了分支预测失败，在对 cRAT 进行状态恢复之前，cRAT 的状态如表 7.2 所示。
表 7.2 指令 A～H 都被寄存器重命名之后，cRAT 的内容
| 指令 | Phy. Reg | Arch. Reg | V | GC0 | GC1 | GC2 | GC3 |
|---|---|---|---|---|---|---|---|
| P0 | |||||||
| ⋮ | ⋮ | … | ⋮ | ||||
| A | P10 | r5 | 1 | 1 | |||
| B | P11 | r7 | 1→0 | 0 | |||
| C | P12 | r6 | 1 | 1 | |||
| D | P13 | r7 | 1→0 | 0 | |||
| E | P14 | r7 | 1→0 | 1 | |||
| G | P15 | r9 | 1 | 0 | |||
| H | P16 | r7 | 1 | 0 | |||
| P17 | 0 | 0 | |||||
| ⋮ | ⋮ | … | ⋮ | ||||
| P63 | 0 | 0 |
分支指令 F在预测失败时进行的状态恢复，会使 GC0 的内容被写回到 cRAT 的有效位 (V) 区域，此时就可以将 cRAT 恢复到分支指令 F进行寄存器重命名之前的状态了。尽管在表 7.2 中，指令 B 占据的表项 (entry) 有可能已经变为空闲状态，甚至有可能已经被写入了新的指令，这都没有关系，在使用 GC0 进行状态恢复之后，指令 B 所在表项的有效位 (V) 就被恢复成了 0, 至于这个表项对应的物理寄存器是否是空闲的状态，需要查看空闲列表 (free list) 才可以知道。
如果在 cRAT 中，一个表项的有效位 (V) 一直为 1, 就表示该表项对应的逻辑寄存器没有被其他指令替换过，该表项就会一直被占据，它对应的物理寄存器也不会变为空闲状态，直到出现一条目的寄存器和它相等的新指令时，该表项的有效位 (V) 才会变为 0。
到此为止，就完成了对 cRAT 进行状态保存和恢复的过程，当然，这个例子比较简单，在其中只包括了一条分支指令，当流水线中同时存在多条分支指令时，也就需要使用多个 Checkpoint。一般情况下，流水线中最大允许存在的分支指令的个数，和处理器最大可以支持的 Checkpoint 个数是一样的 (假设只对分支指令使用 Checkpoint)。每个 Checkpoint 都有一个编号，例如它的个数是 80 个时，就使用 7 位进行编码，每次在流水线的寄存器重命名阶段遇到分支指令时，都会从表 7.2 中找出一个空闲的 GC 来存储此时的有效位 (V),并将这个 GC 的编号放到该分支指令的信息中，这样当这条分支指令在流水线的后续阶段，得到分支预测的结果之后，就可以根据这个编号来找到与之对应的 GC 了。如果分支预测正确，则将对应的 GC 释放，变为空闲状态，使后续的分支指令可以继续使用它；如果分支预测失败，则需要将对应 GC 中的内容写回到 cRAT 的有效位 (V) 当中，然后将这个 GC 释放，变为空闲的状态，使后续的分支指令可以继续它。
下面的汇编程序中，包括了两条分支指令，此时它的执行过程是怎样的呢？
指令 A: addi r7, r0, 3
指令 B: add r6, r7, r1
指令 C: add r7, r7, r2
指令 D: beq r7, r3, TARGET1
指令 E: add r9, r5, r6
指令 F: add r9, r9, r8
指令 G: beq r9, r3, TARGET2
指令 H: addi r7, r0, 1
指令 I: addi r6, r0, 2
指令 J: sub r9, r1, r0
下面给出几个时间节点上，cRAT 中的内容。
(1) 当第一条分支指令 D 进行寄存器重命名的时候，需要对此时的状态位 (V) 进行保存，假设将其保存到 GC0 中，则此时 cRAT 的内容如表 7.3 所示。
表 7.3 第一条分支指令 D 进行寄存器重命名之前，cRAT 中的内容
| 指令 | Phy. Reg | Arch. Reg | V | GC0 | GC1 | GC2 | GC3 |
|---|---|---|---|---|---|---|---|
| P0 | |||||||
| ⋮ | ⋮ | ⋮ | ⋮ | ||||
| A | P10 | r7 | 1→0 | 0 | |||
| B | P11 | r6 | 1 | 1 | |||
| C | P12 | r7 | 1 | 1 | |||
| P13 | 0 | 0 | |||||
| P14 | 0 | 0 | |||||
| P15 | 0 | 0 | |||||
| P16 | 0 | 0 | |||||
| P17 | 0 | 0 | |||||
| ⋮ | ⋮ | ⋮ | ⋮ | ||||
| P63 | 0 | 0 |
(2) 当第二条分支指令 G 进行寄存器重命名的时候，假设此时它之前的分支指令 D 还没有得到结果，则此时需要对状态位 (V) 进行保存，假设保存到 GC1 中，则此时 cRAT 的内容如表 7.4 所示。
表 7.4 第二条分支指令 G 进行寄存器重命名之前，cRAT 中的内容
| 指令 | Phy. Reg | Arch. Reg | V | GC0 | GC1 | GC2 | GC3 |
|---|---|---|---|---|---|---|---|
| P0 | |||||||
| ⋮ | ⋮ | ⋮ | ⋮ | ⋮ | |||
| A | P10 | r7 | 1→0 | 0 | 0 | ||
| B | P11 | r6 | 1 | 1 | 1 | ||
| C | P12 | r7 | 1 | 1 | 1 | ||
| E | P13 | r9 | 1→0 | 0 | 0 | ||
| F | P14 | r9 | 1 | 0 | 1 | ||
| P15 | 0 | 0 | 0 | ||||
| P16 | 0 | 0 | 0 | ||||
| P17 | 0 | 0 | 0 | ||||
| ⋮ | ⋮ | ⋮ | ⋮ | ⋮ | |||
| P63 | 0 | 0 | 0 |
(3) 当所有的指令都完成了寄存器重命名的时候，cRAT 的内容如表 7.5 所示。
表 7.5 指令 A～J 都完成了寄存器重命名之后，cRAT 的内容
| 指令 | Phy. Reg | Arch. Reg | V | GC0 | GC1 | GC2 | GC3 |
|---|---|---|---|---|---|---|---|
| P0 | |||||||
| ⋮ | ⋮ | ⋮ | ⋮ | ⋮ | |||
| A | P10 | r7 | 1→0 | 0 | 0 | ||
| B | P11 | r6 | 1→0 | 1 | 1 | ||
| C | P12 | r7 | 1→0 | 1 | 1 | ||
| E | P13 | r9 | 1→0 | 0 | 0 | ||
| F | P14 | r9 | 1→0 | 0 | 1 | ||
| H | P15 | r7 | 1 | 0 | 0 | ||
| I | P16 | r6 | 1 | 0 | 0 | ||
| J | P17 | r9 | 1 | 0 | 0 | ||
| ⋮ | ⋮ | ⋮ | ⋮ | ⋮ | |||
| P63 | 0 | 0 | 0 |
如果此时发现分支指令 D 预测错误了，那么就需要使用 GC0 对 cRAT 进行状态恢复，分支指令 D 后面的所有指令对 cRAT 的修改都将变为无效，它们对应的有效位 (V) 都会变为 0。当然，为了保持正确性，还需要对空闲列表 (free list) 也进行状态恢复，那些被占用的物理寄存器都将重新变为空闲的状态 (这是通过恢复 free list 的读指针来实现的 )。而且，如果采用了顺序执行 (in-order) 分支指令的架构，则当前在执行阶段解决的分支指令必然是流水线中最旧的分支指令，当发现该分支指令预测失败时，此时其他所有的 GC 中包含的值都已经是无效的了，因为这些 GC 所对应的分支指令都是处于分支预测失败 (mis-prediction) 的路径上，因此，对于顺序执行分支指令的架构来说，一旦发现分支预测失败，所有的 GC 都会被释放掉。
如果发现分支指令 D 预测正确，而分支指令 G 预测错误的话，那么就释放 GC0,并使用 GC1 对 cRAT 进行状态恢复，当然，恢复完成后，GC1 也需要被释放掉。
从上面的描述可以看出，对 cRAT 进行状态恢复，就是要还原出逻辑寄存器真正对应的物理寄存器，因为后续分支预测失败 (mis-prediction) 路径上的指令可能会修改这个对应关系，需要将其纠正过来。但是 cRAT 并不负责管理哪些物理寄存器是空闲状态的，这个功能是通过 ROB 和空闲列表 (free list) 来实现的。
基于 CAM 方式来实现的重命名映射表，一个最大的弊端就是其面积会随着处理器中物理寄存器个数的增加而变大，因为这种映射表中，表项 (entry) 的个数等于物理寄存器的个数，而可以预见的是，随着处理器并行度的增加 (或许还伴随着流水线的加深 ),需要更多的物理寄存器来适应这样的趋势，此时 cRAT 中就需要更多的比较电路来配合，这会严重拖累处理器的速度；但是从另一个方面来说，在对 cRAT 进行状态保存的时候，只需要保存它的有效位 (V) 就可以了，这样大大降低了对硬件的需求，尤其是现代处理器中，会有更多的分支指令存在于流水线当中，这就需要更多的 Checkpoint 与之配合，这时候 cRAT 的优势就体现出来了，因此基于 CAM 方式的重命名映射表是一把双刃剑，需要在设计中仔细进行权衡。
7.4 超标量处理器的寄存器重命名
在之前的介绍中，已经对寄存器重命名阶段使用的关键部件重命名映射表 (RAT) 和空闲列表 (free list) 进行了说明，下面对一条指令的寄存器重命名过程进行一个梳理。
对于 Dest = Src1 op Src2 这样的指令来说，寄存器重命名的过程如下。
(1) 从重命名映射表 (RAT)? 中找到 Src1 和 Src2 对应的物理寄存器 Psrc1 和 Psrc2, 如图 7.13 所示。
图 7.13 找到两个源寄存器对应的物理寄存器
(2) 从空闲列表 (free list) 中找到一个空闲的物理寄存器 Pdest, 将其作为指令的目的寄存器 Dest 对应的物理寄存器，如图 7.14 所示。
图 7.14 为指令的目的寄存器指定一个物理寄存器
(3) 将逻辑寄存器 Dest 和物理寄存器 Pdest 的映射关系写到重命名映射表 (RAT) 中，这样在之后使用 Dest 作为源寄存器的指令就可以查找到这个映射关系了，如图 7.15 所示。
图 7.15 将新的映射关系写到 RAT 中
经过上面的三步之后，就完成了对一条指令的寄存器重命名的过程 ( 假设采用统一的 PRF 进行寄存器重命名 ),每条指令都会重复上述的过程。
由上面的过程可以知道，对一条指令进行寄存器重命名时，RAT 需要支持两个读端口，用来读取两个源寄存器对应物理寄存器的编号；同时 RAT 需要支持一个写端口，用来将一条指令的目的寄存器对应的新映射关系写到 RAT 中。为了能够将一个物理寄存器释放为空闲状态，还需要将每条指令之前对应的映射关系也保存到 ROB 中，因此 RAT 还需要一个额外的读端口，使用指令的目的寄存器作为地址，用来读出它之前对应的映射关系。也就是说，对于一条指令来说，RAT 需要三个读端口 (使用 Src1、Src2 和 Dest 作为地址 ) 和一个写端口 (使用 dest 作为地址，将空闲列表送出的值作为数据 )。
对于一条指令进行寄存器重命名的过程是比较简单的，但是对于每周期执行多条指令的超标量处理器来说，例如 4-way 的超标量处理器，每周期需要对四条指令进行寄存器重命名。刚才说过，每条指令需要使用 RAT 的 3 个读端口，因此四条指令需要 12 个读端口，寻址的这些端口地址是 src0_L、src0_R、src1_L、src1_R、src2_L、src2_R、src3_L、src3_R、dst0、dst1、dst2 和 dst3。每条指令需要使用 RAT 的 1 个写端口，因此四条指令需要的写端口的个数是 4, 它们用来更新 RAT, 需要使用的地址是 dst0、dst1、dst2 和 dst3,对应的写入数据来自于空闲列表 (Free List) 输出的物理寄存器的编号。因此，对于 4-way 的超标量处理器来说，RAT 总共需要 12 个读端口和 4 个写端口，如图 7.16 所示。
图 7.16 一个 4-way 的超标量处理器中的 RAT
但是，多端口的 RAT 只是超标量处理器的寄存器重命名过程中复杂性的一个方面，还需要考虑到每个周期同时进行重命名的多条指令之间还存在各种相关性，这对于重命名的过程有很大的影响，例如，对于 4-way 的超标量处理器来说，每个周期会对四条指令进行重命名，如图 7.17 所示。
图 7.17 每周期进行重命名的四条指令之间存在的各种相关性
add r0, r1, r2 → add P30, P11, P12 ← 指令A
add r0, r3, r0 → add P31, P13, P30 ← 指令B
sub r5, r4, r6 → sub P32, P14, P16 ← 指令C
sub r0, r8, r9 → sub P33, P18, P19 ← 指令D
在图 7.17 所示的例子中同时存在着先写后写 (WAW)、先写后读 (RAW) 和先读后写 (WAR) 三种相关性，具体如下。
(1) 指令 A 和指令 B 之间存在先写后读 (RAW) 的相关性，指令 B 的源寄存器 r0 来自于指令 A 产生的结果，因此在进行寄存器重命名的时候，指令 B 的 r0 对应的物理寄存器应该直接来自于指令 A 所对应的 P30, 而不应该来自于从 RAT 读取的值。
(2) 指令 A,B,D 之间存在先写后写 (WAW) 的相关性，虽然从字面上看，通过寄存器重命名可以消除这种相关性 (如图 7.17 所示中重命名之后的指令 ), 但是在实际当中，仍然无法忽视它的存在，这是为什么呢？原因有如下两个。
① 因为在写入 RAT 时，只需要将一个逻辑寄存器最新的映射关系写入到 RAT 中就可以了，如果在一个周期内进行重命名的多条指令之间都有着同一个目的寄存器 ( 即存在 WAW 相关性 ),那么只需要将最新的那条指令的映射关系写到 RAT 中即可。
② 在将每条指令的旧映射关系 ( 也就是图 7.17 中的 Ppreg) 写到 ROB 的时候，如果发现在一个周期内有多条指令都使用同一个目的寄存器，则此时写入到 ROB 中的旧映射关系不再是来自于 RAT 读取的值，而是直接来自于和它存在 WAW 相关性的指令。例如在图 7.17 所示的例子中，指令 B 的目的寄存器 r0 经过重命名之后对应的物理寄存器是 P31，而 r0 在上一次对应的物理寄存器是指令 A 当中的 P30, 而不是来自于 RAT 读出的结果；同理，指令 D 的目的寄存器 r0 对应的旧的映射关系是来自于指令 B 的 P31, 也不是来自于 RAT 读出的结果。
正因为有这两个原因，需要超标量处理器在寄存器重命名阶段，对指令间存在的 WAW 相关性进行检查。
(3) 指令 B 和指令 D 之间存在先读后写 (WAR) 的相关性，指令 B 读取寄存器 r0, 而指令 D 写入到寄存器 r0,通过寄存器重命名可以消除这种关系，并且对于实际的重命名过程来说，这种相关性也是没有影响的。
所以，需要在超标量处理器的寄存器重命名过程中考虑先写后读 (RAW) 和先写后写 (WAW) 这两种相关性，这样就增加了重命名过程的复杂度，在超标量处理器中，重命名阶段的延迟主要来自于两个方面，一个是多端口 SRAM 本身的延迟，另一个就是 RAW 和 WAW 相关性检查和处理电路引起的延迟。由于重命名映射表 (RAT) 需要多个端口，而 RAT 是由 SRAM 组成 (cRAT 本质上也是由 SRAM 和比较电路组成的 ),所以此处需要使用多端口的 SRAM。而对于 SRAM 来说，端口数量的增加直接影响了其面积和速度，此处需要对 SRAM 电路进行专门的设计，以降低对处理器周期时间的负面影响；而 RAW 和 WAW 这两种相关性的检查和处理电路也需要占用一定的时间来完成，因此综合看起来，寄存器重命名阶段对于处理器的周期时间的影响是很大的，已经有人提出了采用流水线的方式，使用两周期完成这个过程，这样可以在一定程度上减少对周期时间的影响，但是却增加了 RAW 和 WAW 相关性检查电路的复杂度，因为此时不但需要对当前周期进行寄存器重命名的指令进行相关性检查 ( 称为组内检查 ),还需要对上个周期进行寄存器重命名的指令进行相关性的检查 ( 称为组间检查 )。本书不再对流水线的重命名过程进行介绍，要想详细了解这方面的内容，可以参见参考文献29。
7.4.1 解决 RAW 相关性
对于 4-way 的超标量处理器来说，每周期最多可以对四条指令进行寄存器重命名，如果这四条指令之间不存在 RAW 相关性，那么这个过程是比较简单的，如图 7.18 所示。
图 7.18 对四条指令同时进行寄存器重命名 (假设不存在 RAW 相关性 )
R1 = R1 + R2
R3 = R3 + R4
R5 = R6 × R7
R8 = Ld 9[R9]
如图 7.18 所示的四条指令之间不存在 RAW 相关性，这是一种最简单的情况，四条指令的源寄存器都会从重命名映射表 (RAT) 中找到对应的物理寄存器，目的寄存器也会从 RAT 中找到之前映射的物理寄存器的编号，同时本周期还会从空闲列表 (free list) 中找出四个空闲的物理寄存器的编号，将它们和四条指令的目的寄存器产生新的映射关系，并将这个关系也写到 RAT 中。
空闲列表 (free list) 中保存着所有空闲的物理寄存器的编号，这些物理寄存器没有被映射到任何逻辑寄存器，每次当指令被重命名时，就会从空闲列表中找到空闲的物理寄存器；而每次当一个物理寄存器不会再被使用时，就会将它的编号写回到空闲列表中。如果一个周期内进行重命名的多条指令之间不存在 RAW 相关性，那么只需要简单地将一条指令的寄存器重命名过程扩展到四条指令就可以了。
但是，事情并不总是那么简单，当一个周期内进行寄存器重命名的多条指令之间存在 RAW 的相关性时，图 7.18 所示的方法就会出现问题，如图 7.19 所示。
图 7.19 当四条指令之间存在 RAW 相关性时，遇到的问题
R1 = R1 + R2
R3 = R3 + R4
R5 = R6 × R1
R8 = Ld 9[R9]
如图 7.19 所示中，对于 “R5 = R6×R1” 这条指令来说，源寄存器 R1 对应的物理寄存器应该来自于同时在本周期的指令 “R1 = R2 + R3”, 即图 7.19 中从空闲列表 (free list) 输出的 P31,而不应该来自于 RAT 输出的 P25, 如果不加以处理，就会使处理器的运行产生错误。
上述问题要求处理器中有一种检查机制，对一个周期内进行重命名的所有指令进行 RAW 相关性的检查，它被称为组内相关性检查。在寄存器重命名阶段，指令之间还保持着程序中指定的顺序 (in-order),因此只需要将每条指令的源寄存器编号和它前面所有指令的目的寄存器编号进行比较，如果存在一个相等的项，那么这个源寄存器对应的物理寄存器就不是来自于 RAT 的输出，而是来自于当前周期从空闲列表 (free list) 输出的对应值；如果存在多个相等的项，那么就使用最新的那条指令所对应的物理寄存器，如图 7.20 所示为在超标量处理器中对 RAW 相关性进行检查和处理的电路示意图。
图 7.20 对 RAW 相关性进行检查的电路图
在一个周期内进行寄存器重命名的四条指令中，第一条指令 (inst0) 的源寄存器对应的物理寄存器 (Psrc0_L 或 Psrc0_R ) 只能来自于 RAT 的输出；第二条指令 (inst1) 的源寄存器对应的物理寄存器 (Psrc1_L 或 Psrc1_R) 可能来自于 RAT 的输出，也可能来自于第一条指令的目的寄存器对应的物理寄存器 (FL0, 来自于空闲列表 ),因此需要根据组内相关性检查的结果，选择一个合适的值；第三条和第四条指令的处理情况也是类似的，源寄存器对应的物理寄存器除了可能来自于 RAT 的输出，还有可能来自于它前面指令的目的寄存器对应的物理寄存器，因此需要根据组内相关性检查的结果，选择合适的值。在寄存器重命名的这个周期内，一条指令的目的寄存器对应的物理寄存器来自于空闲列表 (free list),但是很显然，最后一条指令 (inst3) 的目的寄存器是不可能作为其他指令的源寄存器的，因此空闲列表输出的最后一个值并不会被其他指令使用。
从图 7.20 还可以看出，组内相关性检查电路和访问 RAT 是并行工作的，因此不会对处理器的周期时间产生负面的影响，在组内相关性检查电路中，需要将每条指令的源寄存器和它之前的所有指令的目的寄存器进行比较，根据比较的结果来控制这个源寄存器的来源，这个电路的实现方法如图 7.21 所示。
在一个周期内进行寄存器重命名的所有指令中，对第一条指令来说，由于它的前面已经没有指令，也就不需要进行先写后读 (RAW) 相关性的检查；其他的指令按照图 7.21 给出的方式进行 RAW 相关性的检查，如果发现一条指令的源寄存器和它之前的某些条指令的目的寄存器相等，那么就会使用最新的那条指令的映射关系。举例来说，如果第三条指令 (inst2) 的源寄存器 src2_L 和第一条指令 (inst0) 的目的寄存器 (dst0)、第二条指令 (inst1) 的目的寄存器 (dst1) 都相等，那么会使用第二条指令对应的物理寄存器 (FL1, 来自于空闲列表 ) 作为它的源寄存器。
图 7.21 组内相关性检查电路
7.4.2 解决 WAW 相关性
在前文说过，寄存器重命名虽然可以解决指令之间存在的先写后写 (WAW) 的相关性，但是这种相关性仍然无法被忽视，它影响着对重命名映射表 (RAT) 和 ROB 的写入过程，因此也需要在重命名阶段对其进行检查，但是对 RAT 和 ROB 这两个部件来说，虽然都是检查 WAW 相关性，但是它们的处理过程是不一样的，需要区别进行对待。
1. 对写 RAT 进行检查
在进行寄存器重命名的这个周期内，如果存在多条指令的目的寄存器都相等的情况，那么只有最新的那条指令的映射关系才允许写入到 RAT 当中，举例来说，有如下的四条指令。
指令 A: add r0, r1, r2
指令 B: add r0, r3, r0
指令 C: sub r5, r4, r6
指令 D: sub r0, r8, r9
在上面的指令中，有三条指令 (指令 A、指令 B、指令 D) 都使用了同一个目的寄存器 r0，但是只有最新的那条指令 (指令 D) 才允许将它的映射关系写到 RAT 中，这需要对一个周期内进行寄存器重命名的所有指令进行先写后写 (WAW) 相关性的检查。对于每条指令来说，都要将它的目的寄存器和后面所有指令的目的寄存器进行比较，如果发现存在相等的情况，则说明本条指令不应该更新 RAT, 通过这种方法就可以完成 WAW 相关性的检查。假设在当前周期进行寄存器重命名的四条指令，目的寄存器分别是 dst0、dst1、dst2 和 dst3, 则详细的检查过程如下。
(1) dst0 只要和 dst1、dst2 和 dst3 中的任意一个的任意一个存在相同的情况，就不需要将 dst0 对应的映射关系写到 RAT 当中了，因为后续的指令会覆盖这个映射关系；
(2) dst1 只要和 dst2 和 dst3 中的任意一个的任意一个存在相同的情况，就不需要将 dst1 对应的映射关系写到 RAT 当中了，因为后续的指令会覆盖这个映射关系；
(3) dst2 只要和 dst3 相同，就不需要将 dst2 对应的映射关系写到 RAT 当中了，因为后续的指令会覆盖这个映射关系；
(4) dst3 因为属于当前周期的最后一条指令，因此在本周期不会被覆盖，它的映射关系肯定会被写入到 RAT 中。
总结起来，对于写 RAT 来说，实现这种先写后写 (WAW) 相关性检查的电路如图 7.22 所示。
在寄存器重命名阶段的四条指令，应该对应着 RAT 的四个写端口，但是，并不是所有的指令都需要写 RAT, 当两条指令的目的寄存器相同时，只需要比较新的那条指令写 RAT 就可以了，其他的指令不需要写 RAT, 因此要将其对应的 RAT 写端口的使能信号置为无效，通过图 7.22 中的这种 WAW 相关性的检查，可以保证始终将最新的映射关系写到 RAT 中。
图 7.22 对于写 RAT 来说，实现 WAW 相关性检查的电路结构图
2. 对写 ROB 进行检查
在前文说过，为了能够释放掉那些不再使用的物理寄存器，同时又可以对处理器的状态进行恢复，每条指令都需要从 RAT 中读出它以前对应的物理寄存器，并将其写到 ROB 当中，如果在一个周期内进行寄存器重命名的几条指令中，有两条指令的目的寄存器相等 (也就是它们存在 WAW 相关性 ),那么比较新的这条指令对应的旧的物理寄存器就直接来自于比较旧的那条指令，而不是来自于 RAT。例如图 7.23 所示的例子中，指令 D 的目的寄存器 r0 之前对应的物理寄存器应该来自于指令 B 的 P31,而不是来自于 RAT 读出的值。
图 7.23 存在 WAW 相关性的四条指令
add r0, r1, r2 → add P30, P11, P12 ← 指令 A
add r0, r3, r0 → add P31, P13, P30 ← 指令 B
sub r5, r4, r6 → sub P32, P14, P16 ← 指令 C
sub r0, r8, r9 → sub P33, P18, P19 ← 指令 D
为了实现图 7.23 中的功能，需要对当前周期进行寄存器重命名的所有指令进行 WAW 相关性的检查，每条指令都需要和比它旧的所有指令进行目的寄存器的比较，如图 7.24 所示。
图 7.24 对于写 ROB 来说，进行 WAW 相关性的检查
在图 7.24 中，一个周期内进行寄存器重命名的四条指令中，每条指令的检查情况如下。
(1) 第一条指令 (inst0) 之前已经没有指令，所以这条指令对应的旧的映射关系只能是来自于 RAT；
(2) 第二条指令 (inst1) 的目的寄存器 (dst1) 需要和它之前的目的寄存器 (dst0) 进行比较，如果相等，则这个目的寄存器对应的旧的物理寄存器不是来自于 RAT 输出的值，而是来自于它之前的指令中的目的寄存器 (FL0)；
(3) 第三条指令 (inst2) 的目的寄存器 (dst2) 需要和它之前的目的寄存器 (dst0、dst1) 进行比较，如果存在相等的情况，则这个目的寄存器对应的旧的物理寄存器不是来自于 RAT 输出的值，而是来自于它之前的指令中的某个目的寄存器 (FL0 或 FL1)；
(4) 最后一条指令 (inst3) 的目的寄存器 (dst3) 需要和它之前的所有目的寄存器 (dst0、dst1、dst2) 进行比较，如果存在相等的情况，则这个目的寄存器对应的旧的物理寄存器不是来自于 RAT 输出的值，而是来自于它之前的指令中的某个目的寄存器 (FL0、FL1 或 FL2)。
图 7.24 表示了如何将重命名阶段的指令在写入到 ROB 之前进行 WAW 相关性的检查，因为在一个周期内，可能存在多条指令写入到同一个目的寄存器的情况，则此时一条指令所对应的旧映射关系不是来自于 RAT, 而是来自于本周期空闲列表 (free list) 输出的对应值。需要注意这种 WAW 相关性的检查和上一节的区别，在上一节中，WAW 相关性检查的结果用来控制对 RAT 的写入，而本节中 WAW 相关性的检查是用来控制对 ROB 的写入，虽然都是 WAW 相关性的检查，但是很明显它们的目的是不一样的。
从前面的过程可以知道，在寄存器重命名阶段，需要使用源寄存器和目的寄存器读取 RAT, 同时也需要使用目的寄存器将空闲列表 (free list) 送出的内容写到 RAT 中，由于 RAT 本质上是一个多端口的 SRAM, 或者是一个多端口的寄存器堆 (register file),它们的操作方式都是一样的，这里就必然需要考虑到一个问题，即当多端口 SRAM 的读地址和写地址一样时，如何进行处理？
对于寄存器重命名的过程来说，由于 RAT 的读地址和写地址都使用了指令的目的寄存器，因此这个问题是必须解决的，也就是说，在一个周期内，既要对 RAT 的某个地址进行读取，又要对这个地址进行写入，根据前文的讲述已经知道，应该保证使用目的寄存器读取 RAT 的过程先完成 ( 先要将之前的映射关系读取出来，然后才能更改它 ), 然后才能够向 RAT 的这些地址中写入新的内容 ( 写入新的映射关系 )。当然，在寄存器重命名的这个周期，读取 RAT 的源寄存器也可能和写 RAT 的目的寄存器存在相等的情况，这样也会遇到上述的问题，那么，这个问题如何解决呢？在实际使用的多端口 SRAM 中，都有成熟的方法解决这种在一个周期内读取和写入同一个地址所引起的问题。例如，在 Xilinx 的 FPGA 中，双端口的 SRAM 可以配置成如图 7.25 所示的两种情况 [30]。
图 7.25
在写优先 (Write First) 的模式中，写入到 SRAM 中某个地址的内容在写入完成后，可以马上在读端口被获得，也就是在当前周期就可以读取到刚才写入的内容；而在读优先 (Read First) 的模式，写入到 SRAM 中某个地址的内容只有在下个周期才可以被读取，在当前周期读取这个地址的内容，只能读取到在本周期这个地址被写入之前的内容。由图 7.25 所示的两种模式可以看出，对于 RAT 来说，要选择读优先 (Read First) 的模式，这样即使在一个周期内对一个地址同时发生了读和写的操作，读操作仍能够得到写之前的内容，这对于指令的目的寄存器读取 RAT 来说是必需的，因为目的寄存器读取 RAT 的真正原因，就是为了获得这个目的寄存器之前对应的物理寄存器；然而，对于源寄存器读取 RAT 来说，并不希望读取到旧的映射关系，而是希望得到最新的，因此，如果读取 RAT 的源寄存器和写入 RAT 的目的寄存器之间存在相等的情况，也就是存在先写后读 (RAW) 的相关性，那么源寄存器对应的物理寄存器应该是此时正在被写入到 RAT 当中的物理寄存器，这个需求在读优先 (Read First) 模式的 SRAM 中是无法满足的，需要使用之前讲述过的 RAW 相关性的检查和处理电路才可以得到上述的效果。
以上讲述的寄存器重命名过程有一个前提，那就是假设每周期正好可以对四条指令进行重命名，而且每条指令都包含两个源寄存器和一个目的寄存器，而实际上，有些指令并没有目的寄存器，例如分支指令或 store 类型的指令，而有些指令的源操作数是立即数，它并不需要进行重命名等，这些特殊的情况都需要在指令解码之后加以标记，做法如下。
(1) 根据当前周期中需要重命名的目的寄存器的个数，决定当前周期需要从空闲列表 (free list) 中读取的数值的个数；
(2) 使用目的寄存器读取 RAT 时，根据标记的信息，目的寄存器不存在的那些指令将不会读取 RAT, 也不会写入 RAT；
(3) 使用源寄存器读取 RAT 时，根据标记的信息，源寄存器不存在 (例如是立即数 ) 的那些指令将不会读取 RAT, 或者忽略从 RAT 中读出的结果；
(4) 在重命名阶段进行先写后读 (RAW) 和先写后写 (WAW) 相关性的检查时，如果一条指令的源寄存器或者目的寄存器不存在，那么忽略掉和它相关的所有比较结果。
7.5 寄存器重命名过程的恢复
由于分支预测失败 (mis-prediction) 或者异常 (exception) 等原因，所有处于流水线中的指令都处于推测 (speculative) 状态，这些指令在顺利地离开流水线之前 (也就是退休之前 ) 都有可能从流水线中被抹掉，但是，如果被抹掉的指令已经经过了寄存器重命名阶段，那么这条指令已经占据了重命名映射表 (RAT)、重排序缓存 (ROB) 和发射队列 (Issue Queue) 等资源，当指令从流水线中被抹掉时，被这条指令占用的资源需要进行恢复，这样才能够保证后续的指令可以在一个正确的流水线中开始执行，这个过程就是对寄存器重命名的恢复。在前文中，已经对重排序缓存 (ROB) 和发射队列 (Issue Queue) 这两个部件如何进行状态恢复进行了介绍，本节介绍如何对重命名映射表 (RAT) 进行恢复。其实有多种方法可以完成这个过程，本节只介绍三种典型的方法，它们对于三种寄存器重命名的方式 (基于统一的 PRF、基于扩展的 ARF 以及基于 ROB) 都是适用的。
(1) 使用 Checkpoint 对 RAT 进行恢复；
(2) 使用 WALK 对 RAT 进行恢复；
(3) 使用 Architecture State 对 RAT 进行恢复。
7.5.1 使用 Checkpoint
在处理器当中，Checkpoint 是指在某个时间点，将处理器中某些部件的内容 “原封不动”地保存起来，举例来说，对于一个有 32 个通用寄存器的处理器来说，如果将它的 32 个寄存器逐个保存到另一个存储器中，需要 32 个周期才能保存完毕，在以后进行状态恢复时，也需要 32 个周期才可以将这个通用寄存器恢复完毕，这就不能称为 Checkpoint; 如果这 32 个寄存器可以在一个周期内全部搬移到另一个存储器中 (例如另外一个寄存器堆 ),在恢复的时候也可以在一个周期内完成，这个就可以称为 Checkpoint, 如图 7.26 所示为它的原理图。
图 7.26 Checkpoint 的原理图
在图 7.26 中，将 Checkpoint 简称为 GC (Global Checkpoint),对于一个正在工作的部件来说，它可以将整个内容放到任意一个 GC 中，在它进行状态恢复的时候，也可以从任意一个 GC 中读取数据，那么就称这种方式为随机访问的 GC (Random Access GC, RAGC); 如果在进行状态保存的时候，需要经过逐个地移位才能够放到指定的 GC 中，这种方式就称为串行访问的 GC (Sequential Access GC, SAGC),这两种方式的工作原理如图 7.27 所示 [26]。
图 7.27 SAGC 和 RAGC 的工作原理
对于串行访问的 GC 来说，只有一个 GC 和主存储部件 ( 也就是正在工作的部件 ) 相连，当需要访问其他 GC 时，需要通过移位操作才可以完成，这种方法的好处是主存储部件不需要很大的驱动能力，但是当要访问的 GC 离得比较远时，需要经过很多次移位才可以实现。例如要使用 GC6 进行状态恢复，则需要移位经过 GC1～GC5 才可以实现，这样造成了过长的状态恢复时间，而 Checkpoint 设计的本意就是快速地进行状态恢复。对于随机访问的 GC 来说，每个 GC 都会和主存储部件相连，这样 GC 的访问就可以在一个周期内完成，并不需要进行移位的动作，但是这样造成了主存储部件的负载过大，需要很多的缓冲 (buffer) 才可以保证主存储部件的驱动能力，对面积和延迟都有负面的影响，但是考虑到使用 Checkpoint 的目的就是快速地对处理器中的某些部件进行保存和恢复，因此随机访问的 GC 才是更合适的实现方式。
对于 RAT 来说，当不考虑对它实现 Checkpoint 功能时，它本质上就是一个多端口的 SRAM( 或多端口的寄存器堆 ), 但是对于一个实现了 Checkpoint 功能的 RAT 来说，在 SRAM 的每个最小的存储单元 (Main Bit Cell, MBC) 周围都加入同样的存储单元 (Checkpoint Bit Cell, CBC),这些存储单元就实现了 Checkpoint 功能。当需要对 RAT 进行状态保存时，将 MBC 的内容复制到指定的 CBC 中 (这个过程也称为 Allocation); 当对 RAT 进行状态恢复时，将对应 CBC 中的内容复制到 MBC 中 (这个过程称为 Restore)。这样就可以快速地完成对 RAT 的状态保存和恢复，这种带有 Checkpoint 功能的 MBC 如图 7.28 所示 [31]。
图 7.28 带有 Checkpoint 功能的 Main Bit Cell
图 7.28 中，左边的 MBC 支持多个读端口和写端口，因为在超标量处理器中，RAT 是需要多个端口的；右边的 CBC 有一个读端口和一个写端口，它和 MBC 通过传输门直接相连，同时需要两个控制信号 (图 7.28 中的 Allocation 和 Restore),用来控制将数据从 MBC 转移到 CBC,或者反之。这种带 Checkpoint 功能的 RAT 需要在电路层面进行设计，当使用基于 CAM 结构 RAT 时 ( 即 cRAT),只需要对状态位 (V) 进行保存，因此 Checkpoint 所需要的电路面积并不是很大，对处理器的面积和速度的影响也比较小；而使用基于 SRAM 结构的 RAT 时 ( 即 sRAT),需要对整个 SRAM 进行保存，Checkpoint 所需要的电路面积很大，对处理器的速度和面积都会造成不小的负面影响，在设计时需要仔细进行权衡。
7.5.2 使用 WALK
使用 7.5.1 节中的 Checkpoint 电路会增加硬件的开销，而且由于硬件的限制，它的个数也没有办法很多，其实在超标量处理器中，还有一种更 “廉价”的方法来进行 RAT 状态的保存和恢复，那就是使用 ROB。对每一条指令来说，在 ROB 中都存储了这条指令之前对应的物理寄存器，利用这个信息，可以将 RAT 的状态逐步地 “倒回去”, 使那些处在错误路径上的指令，例如处在分支预测失败 (mis-prediction) 或者异常 (exception) 路径上的指令，对 RAT 的修改都进行恢复。举例来说，当发现一条分支指令预测失败时，使用这条分支指令的编号，将流水线中所有相关的指令都抹掉，同时将流水线暂停，从 ROB 的底端开始 (ROB 的最底端对应着最新被放入 ROB 的指令 ), 逐条地将每条指令之前对应的映射关系写到 RAT 中，这个过程被形象地称为 WALK, 通过这种方式，可以把所有更改 RAT 的指令按照相反的顺序，将 RAT 进行恢复。由于需要将之前的物理寄存器写回到 RAT 中，在一个 4-way 的超标量处理器中，考虑到 RAT 支持四个写端口，所以采用每周期从 ROB 中 WALK 四条指令的方法，可以最大限度地利用这四个写端口，这样经过一段时间之后 (具体的时间根据需要恢复的指令个数来决定 ),RAT 就可以恢复到需要的状态，此时就可以继续从正确的地址开始取指令了。
很显然，使用 WALK 的方法对 RAT 进行恢复是比较慢的，它首先需要对流水线中的指令有选择地进行抹掉，同时还需要逐个指令地进行恢复，需要消耗很多的时间。对于分支指令来说，这会增大分支预测失败时的惩罚 (penalty),但是对于异常 (exception) 发生时处理器的状态恢复，则不需要对流水线有选择地进行抹掉这个过程，因为在超标量处理器中，异常的处理需要等到这条指令变为流水线中最旧的指令时才进行，此时流水线中全部的指令都需要被抹掉了。
总体来看，虽然这种 WALK 的方法在速度上会慢一些，但是它的优点是消耗的硬件资源比较少，因此在一些处理器中，例如 MIPS R10000,使用这种方法来对异常发生时的处理器进行状态恢复，因为异常发生的频率相对于分支预测失败 (mis-prediction) 是比较低的，因此使用这种相对比较慢的方法也是可以接受的，而用比较快的 Checkpoint 方法对分支预测失败时的处理器进行状态恢复。
7.5.3 使用 Architecture State
在基于统一的 PRF 进行寄存器重命名的方法中，在指令集中定义的所有逻辑寄存器都混在处理器内部的物理寄存器当中了。当需要从处理器外部访问一个逻辑寄存器时，直接使用寄存器重命名阶段的 RAT 是很难做到的，因为它处在推测 (speculative) 状态，因此一般都会在流水线的提交 (Commit) 阶段也使用一个 RAT, 所有正确离开流水线的指令都会更新这个 RAT, 因此这个 RAT 中记录的状态肯定是正确的，称它为 aRAT(architecture RAT)。因为外界访问 CPU 时，只能看到指令集中定义的逻辑寄存器，而不能看到物理寄存器，因此，只有从 aRAT 中才可以找到逻辑寄存器对应的正确状态的物理寄存器。如果直接查找寄存器重命名阶段的 RAT, 则得到的只是处于推测 (speculative) 状态的物理寄存器，例如图 7.29 所示的例子。
图 7.29 寄存器重命名的一个例子
指令 A: r1 = r2 + r3 → P31 = P22 + P23
指令 B: r1 = r1 + r4 → P32 = P31 + P24
指令 C: r1 = r1 + r5 → P33 = P32 + P25
指令 D: r1 = r1 + r6 → P34 = P33 + P26
当指令 A 已经成功地离开了流水线，而其他指令仍旧还在流水线当中时，逻辑寄存器 r1 对应的正确的值此时存储在物理寄存器 P31 中，如果在指令 D 完成寄存器重命名的那个时刻，从处理器外部访问逻辑寄存器 r1, 如果直接使用重命名阶段的 RAT 的话，只能得到 r1 对应的物理寄存器是 P34 这个结果，而此时指令 D 处于推测 (speculative) 状态，有可能会由于它前面的指令存在分支预测失败 (mis-prediction) 或者异常 (exception) 的原因而使它从流水线中被抹掉，因此外界不应该看到 r1 和 P34 的映射关系，所以，需要在流水线的提交 (Commit) 阶段设置另外一个 RAT, 即 aRAT。这个 RAT 的结构和寄存器重命名阶段使用的 RAT 是一样的，所有顺利离开流水线的指令都会将它对应的物理寄存器的编号写到这个 RAT 中，外界在访问处理器时，通过访问 aRAT, 在任何一个时刻，总能够得到所有逻辑寄存器对应的正确状态，这个状态称做 Architecture State, 如图 7.30 所示。
图 7.30 通过访问 aRAT 来访问 Architecture 寄存器
利用这个总是正确的 aRAT, 也可以对寄存器重命名阶段使用的 RAT 进行恢复，这是如何进行的呢？举例来说，当在流水线的执行阶段发现分支指令预测失败 (mis-prediction) 时，并不马上进行 RAT 状态的恢复，而是让处理器继续执行，当这条分支预测失败的分支指令变成流水线中最旧的指令时，此时的 aRAT 即表示了分支指令所对应的正确状态的 RAT。因为此时，在分支指令之前进入到流水线中的所有指令都已经顺利地离开了流水线，并且更新了处理器的状态，而该分支指令后面所有的指令都没有在 aRAT 中留下痕迹，此时，可以将 aRAT 的内容复制到重命名阶段的 RAT 中，这样就完成了分支预测失败时对 RAT 的恢复。因为重命名阶段使用的 RAT 和 aRAT 的结构是一模一样的，那么这样的复制工作是相对简单的，只需要在物理层面上将两个 RAT 的位单元 (Bit cell) 之间架起一个直连的通道，通过相应的信号进行控制，就可以将 aRAT 的内容在一个周期之内复制到重命名阶段的 RAT 当中，这和前文中讲述的 Checkpoint 的方法是一样的。其实，这种方法对其他两种寄存器重命名的方式也是适用的，等到分支指令退休 (retire) 的时候，此时的 ARF 就处在正确的状态，可以将 RAT 中所有的逻辑寄存器都指向 ARF,就完成了对 RAT 的状态恢复。
但是，当在流水线的执行阶段发现了分支预测失败时，可能在流水线中还存在很多指令先于这条分支指令进入流水线，如果这些指令中存在 D-Cache 缺失的 load 指令，那么这条分支指令可能需要等待一段时间才可以等到这些指令全部顺利地离开流水线，这会导致分支预测失败时的惩罚 (penalty) 变大，一定程度上影响了处理器执行的效率。
在超标量处理器的流水线中，那些先于分支指令进入到流水线的指令中，如果有指令发生了异常 (exception),例如 TLB 缺失、Page Fault 等，那么处理器需要对这些异常进行处理，此时需要等到这条发生异常的指令变为流水线中最旧的指令时，将流水线中全部的指令进行抹掉，并跳转到对应的异常处理程序中，这样，那条预测失败的分支指令并不会被处理，因为它从流水线中被抹掉了，不可能退休 (retire)。这也是等到分支指令变为流水线中最旧的指令的时候，才对 RAT 进行状态恢复的一个好处，如果在一条分支指令之前存在异常或者另一个分支预测失败，那么即使这条分支指令发生了分支预测失败，它也不会被处理，而是会从流水线中被抹掉，这样就避免了做无用功，在一定程度上可以节约处理器的功耗。
7.6 分发
到现在为止，前文讲述的超标量处理器的所有流水线阶段，都是按照程序指定的顺序 (in-order) 对指令进行处理，而对于超标量处理器来说，乱序执行 (out-of-order) 才是最关键的地方，流水线的分发 (Dispatch) 阶段就是顺序执行和乱序执行的分界点，指令经过寄存器重命名之后，就会进入流水线的分发阶段。在这个阶段，经过寄存器重命名之后的指令会被写到流水线的很多缓存中，这样就为乱序执行做好了准备，具体来说，可以分为三大类的缓存。
(1) 发射队列 (Issue Queue) (out-of-order),大部分的功能单元 (FU) 都可以按照乱序的方式来执行指令，指令在送到 FU 中被执行之前，先被放到一个缓存中，这个缓存就是发射队列，每个 FU 都对应着一个发射队列 ( 先假设如此 ), 当指令被放到这个缓存中的时候，它的操作数可能还没有完全准备好，那么它就在这个缓存中等待，只要一条指令的所有源操作数都准备好了，就可以将其送到 FU 中执行，而不用理会这条指令在程序中原始的顺序，超标量处理器正是依靠这种方式来获得比较高的性能，这需要发射队列可以支持这种乱序发射指令的特性。不仅如此，在一个 4-way 的超标量处理器中，每周期最多可以有四条指令被写到这个缓存中，这需要从其中找出四个空闲的表项 (entry),由于乱序执行的特性，缓存中空闲表项的分布是没有规律的，从其中找出四个空闲的表项并不是一件容易的事情，需要在设计中进行权衡，这部分内容将在后文介绍。
(2) 发射队列 (Issue Queue) (in-order), 即使在乱序执行的超标量处理器中，仍旧有部分指令是按照程序中指定的顺序来执行的，例如分支指令和 store 指令，这些指令如果按照乱序的方式执行，会带来不菲的硬件消耗，而且在性能上也不会带来本质的提高，因此对这些指令一般采取顺序的方式来执行，容纳这些指令的发射队列本质上就是 FIFO, 通过调整写指针就可以从中找到空闲的空间，将重命名之后的指令放到其中，因此完全可以用之前讲过的交叠 (interleaving) 方式来实现这种 FIFO。
(3) 重排序缓存 (ROB),这个部件可以将乱序执行的指令拉回程序中指定的原始顺序，指令经过寄存器重命名之后，按照程序中指定的顺序写到重排序缓存中，同时在重排序缓存中还会记录下指令在执行过程中的一些状态，例如是否产生异常等信息，即使有些指令很早就计算完成了，但是它必须等到重排序缓存中在它前面 (也就是比它更旧 ) 的所有指令都离开了 (也就是退休 ), 才会允许这条指令改变处理器的状态 (这称为 Architecture State)。重排序缓存本质上也是 FIFO,通过调整写指针就可以找到空闲的空间，将指令写到其中。
总结来说，流水线的分发 (Dispatch) 阶段就是将寄存器重命名之后的指令写到发射队列 (Issue Queue) 和重排序缓存 (ROB) 的过程，指令到达发射队列之后，就可以按照乱序的方式执行了，通过重排序缓存将这些指令再变回到程序中指定的顺序。分发阶段可以和寄存器重命名阶段放在一个周期内完成，但是当发射队列和重排序缓存的容量比较大时，向它们当中写入东西会变得很慢，这样会严重影响处理器的周期时间，因此很多处理器都会为分发阶段单独使用一个流水段，从功能上来看，分发阶段可以称得上是超标量处理器的流水线中最轻松的一级了。
本站所有文章转发 CSDN 将按侵权追究法律责任，其它情况随意。