跳转至

理论复习

1. 标量处理机与流水线技术

标量数据表示和标量指令系统的处理机被称为标量处理机。它是最通用也是使用最普遍的一种处理机。而为了提高标量处理机的性能，也就是提高指令执行的速度，通常会采取以下几种途径:

  1. 提高处理机的主频，事实上在科技发展和商业竞争的驱动下，处理机的主频每隔 2~3 年 (现在甚至更短) 就要提高一个数量级了。

  2. 采用更好的算法和设计更好的功能部件，例如采用精简指令系统计算机 (Reduction Instruction Set Computer, 简称 RISC) 技术来减少执行指令的平均周期数，用多位的乘除法缩短乘除法的执行时间，设计新型的 ROM 运算部件等等。

  3. 采用指令并行技术，就是多条指令并行地执行。

其中指令并行可以由以下三种方法来实现:

  • 一是采用流水线技术 (Pipeline)，这种处理机称为流水线处理机或超流水线处理机;

  • 二是采用独立的功能部件来分担不同的操作和运算，诸如浮点加、乘除法、分支操作等等;

  • 三是超长指令字技术 (Very Long Instruction Word, 简称 VLIW)。

而在这个实验里面，我们关心的是指令并行技术中的流水线技术的实现和改进。

2. 流水线冲突

流水线技术的一大问题就是冲突 (Hazards)，是指对于具体的流水线来说，由于指令相关的存在，使得指令流中的下一条指令不能在指定的时钟周期开始执行的情况。冲突有以下三种类型：

  1. 结构冲突：因硬件资源满足不了指令重叠执行的要求而发生的冲突。

  2. 数据冲突：当指令在流水线中重叠执行时，因需要用到前面指令的执行结果而发生的冲突。

  3. 控制冲突：流水线遇到分支指令或其他会改变PC值的指令所引起的冲突。

其中数据冲突又可以具体分为写后读冲突 (Read After Write, RAW)、读后写冲突 (Write After Read, WAR)、写后写冲突 (Write After Write, WAW)三种。在这个实验中，我们关心的是数据冲突和控制冲突，以及如何使用经典 Tomasulo 算法结合再定序缓冲器（ReOrder Buffer，ROB）和分支目标缓冲器（Branch Target Buffer，BTB）来解决这些问题。

3. Tomasulo算法

Tomasulo 算法是由 Robert Tomasulo 发明的，因而以他的名字命名。IBM360/91 机器中的浮点部件首先采用了这种方法。尽管许多现代处理机采用了这种方法的各种变形，但其核心思想都是：

  1. 记录和检测指令相关，操作数一旦就绪就立即执行，把发生RAW冲突的可能性减少到最少。

  2. 通过寄存器换名来消除WAR冲突和WAW冲突。

Tomasulo 算法的 主要功能部件 如下：

  • 保留站
    保留站设置在运算部件的入口，每个保留站中保存一条已经流出并等待到本功能部 件执行的指令(相关信息)，包括操作码、操作数以及用于检测和解决冲突的信息。在一条指令流出到保留站的时候，如果该指令的源操作数已经在寄存器中就绪, 则将之取到该保 留站中。如果操作数还没有计算出来，则在该保留站中记录将产生这个操作数的保留站的标识。每个保留站都有一个标识字段,唯一地标识了该保留站。

  • 公共数据总线 CDB
    公共数据总线 CDB 是该结构中的一条重要的数据通路，所有功能部件的计算结果都是送到 CDB 上，由它把这些结果直接送到（播送到）各个需要该结果的地方。从存储器读 取的数据也是送到 CDB 上。CDB 连到除了 load 缓冲器以外的所有部件的入口。浮点寄存器通过一对总线连接到功能部件，并通过 CDB 连接到 store 缓冲器的入口。

  • load 缓冲器和 store 缓冲器
    load 缓冲器和 store 缓冲器中存放的是读/写存储器的数据或地址。它们的行为和保留站类似，所以也把它们当作保留站来看待。只有必须区别它们时，才加以区分。

Tomasulo 算法中指令的执行过程如下：

  • 流出

从指令队列的头部取一条指令。如果该指令的操作所要求的保留站有空闲的，就把该指令送到该保留站（设为 r）。并且，如果其操作数在寄存器中已经就绪，就将这些操作数送入保留站 r。如果其操作数还没有就绪，就把将产生该操作数的保留站的标识送入保留站r。这样一旦被记录的保留站完成计算，它就直接把数据送给保留站 r。这一步实际上是进行了寄存器换名（换成保留站的标识）和对操作数进行了缓冲，消除了 WAR 冲突。

另外，还要完成对目的寄存器的预约工作，将之设置为接收保留站 r 的结果。这实际上相当于提前完成了写操作（预约）。由于指令是按程序顺序流出的，当出现多条指令写同一个结果寄存器时，最后留下的预约结果肯定是最后一条指令的，就是说消除了 WAW 冲突。当然，如果没有空闲的保留站，指令就不能流出，这是发生了结构冲突。

  • 执行

如果某个操作数还没有计算出来，本保留站将监视 CDB，等待所需的计算结果。一旦那个结果产生，它就被放到 CDB上，本保留站将立即获得该数据。当两个操作数都就绪后，本保留站就用相应的功能部件开始执行指令规定的操作。这里是等到所有操作数都备齐后才开始执行指令，也就是说是靠推迟执行的方法解决 RAW 冲突的。由于结果数据是从其产生的部件（保留站）直接送到需要它的地方，所以这已经是最大限度地减少了 RAW 冲突的影晌。

显然，保留站有可能会出现多条指令在同一时钟周期变成就绪的情况。不同的功能部件可以并行执行，但在一个功能部件内部，就绪的多条指令就得逐条地处理。可以采用随机 的方法选择要执行的指令。

load 和 store 指令的执行需要两个步骤：计算有效地址（要等到基地址寄存器就绪）和把有效地址放入 load 或 store 缓冲器。load 缓冲器中的 load 指令的执行条件是存储器部件就绪。而 store 缓冲器中的 store 指令在执行前必须等到要存入存储器的数据到达。通过按顺序进行有效地址计算来保证程序顺序，这有助于避免访问存储器的冲突。

  • 写结果

功能部件计算完毕后，就将计算结果放到 CDB 上，所有等待该计算结果的寄存器和保留站（包括 store 缓冲器）都同时从 CDB 上获得所需要的数据。store 指令在这一步完成对存储器的写入：当写入地址和数据都备齐时，将它们送给存储器部件，store 指令完成。

4. ROB

对于多流出的处理机来说，只准确地预测分支已经不能满足要求了，因为有可能每个时钟周期都要执行一条分支指令。控制相关已经成了开发更多指令级并行的一个主要障碍。

前瞻执行 能很好地解决控制相关的问题，它对分支指令的结果进行猜测，并假设这个猜测总是对的，然后按这个猜测结果继续取、流出和执行后续的指令。只是执行指令的结果不是写回到寄存器或存储器，而是放到一个称为 ROB 的缓冲器中。等到相应的指令得到“确认”（即确实是应该执行的）后，才将结果写人寄存器或存储器。之所以要这样，是为了在猜测错误的情况下能够恢复原来的现场(即没有进行不可恢复的写操作)。基于硬件的前膽执行是把三种思想结合在了一起：

  1. 动态分支预测，用来选择后续执行的指令。
  2. 在控制相关的结果尚未出来之前,前瞻地执行后续指令。
  3. 用动态调度对基本块的各种组合进行跨基本块的调度。

对 Tomasulo 算法加以扩充，就可以支持前膽执行，也是本次实验要求大家实现的。在经典 Tomasulo 算法中，写结果和指令完成是一起在“写结果”段完成的。现在我们要把写结果和指令完成加以区分，分成两个不同的段：“写结果”和“指令确认”。

  • “写结果”段是把前瞻执行的结果写到 ROB 中，并通过 CDB 在指令之间传送结果，供需要用到这些结果的指令使用。当然，这些指令的执行也是前膽执行的。
  • “指令确认”段是在分支指令的结果出来后，对相应指令的前膽执行给予确认，把在 ROB 中的结果写到寄存器或存储器（如果前面所做的猜测是对的）。如果发现前面对分支结果的猜测是错误的，那就不予以确认，并从该分支指令的另一条路径开始重新执行。

前瞻执行允许指令乱序执行，但要求按程序顺序确认。并且在指令被确认之前，不允许它进行不可恢复的操作，如更新机器状态或发生异常。

ROB 中的每一项由以下 4 个字段组成:

  1. 指令类型：指出该指令是分支指令、store 指令或寄存器操作指令。
  2. 目标地:给出指令执行结果应写人的目标寄存器号（如果是 load 和 ALU 指令）或存储器单元的地址（如果是 store 指令）。
  3. 数据值字段：用来保存指令前膽执行的结果，直到指令得到确认。
  4. 就绪字段：指出指令是否已经完成执行并且数据已就绪。

在前瞻执行机制中，Tomasulo 算法中保留站的换名功能是由 ROB 来完成的。这样保留站的作用就仅仅是在指令流出到指令开始执行期间，为指令保存运算操作码和操作数。由于每条指令在被确认前，在 ROB 中都有相应的一项，对执行结果是用 ROB 的项目编号作为标识，而不像 Tomasulo 算法那样是用保留站的编号，这就要求在保留站中记录分配给该指令的 ROB 项目编号。

5. BTB

对五段流水线来说，分支目标缓冲器 BTB 可以在 IF 段获取预测的分支目标地址。BTB 的结构如下图所示，可以把它看成用专门的硬件实现的一张表格。表格中的每一项至少有两个字段：

  1. 执行过的成功分支指令的地址。
  2. 预测的分支目标地址。

在每次取指令的同时，用该指令的地址与BTB中的所有项目的第一个字段进行比较。如果有匹配的，我们就知道该指令是分支指令且上一次执行是分支成功。据此可以预测这次执行也将分支成功，其分支目标地址由匹配项的第二个字段给出。如果没有匹配的，就把当前指令当作普通的指令（即不是分支指令）来执行。

BTB 的另一种形式是在分支目标缓冲器中增设一个至少两位的分支历史表（Branch History Table，BHT）字段。这样“分支指令地址”字段存放的就不仅仅是成功分支指令的地址，所有执行过的分支指令的地址都可以放在这里。BHT 用来预测转移方向。在本次实验中，我们就要求同学们实现一个这样的两位饱和计数器来预测是否跳转。如下图所示，这种方法实际上就是 BTB 与 BHT 的結合。

两位 BHT 的工作机制如下图所示：

最后更新: 2024年2月23日
作者：cuibst (49.14%), cpu (45.69%), hogura (5.17%)