当前位置: article > 正文

计算机体系结构第5章指令级并行及其开发—硬件方法（1）_计算机体系结构量化研究方法线程级并行

作者：花生_TL007 | 2024-03-21 12:22:55

踩

计算机体系结构量化研究方法线程级并行

文章目录

第5章指令级并行及其开发—硬件方法

第5章指令级并行及其开发—硬件方法

5.1 指令级并行的概念

指令级并行（Instruction-Level Parallelism，ILP）：指指令之间存在的一种并行性，利用它，计算机可以并行执行两条或两条以上的指令。

5.1.1 相关概念介绍

开发ILP的两种途径：

资源重复：重复设置多个处理部件，让它们同时执行相邻或相近的多条指令;
采用流水线技术：使指令重叠并行执行。

开发ILP的方法可以分为两大类：

主要基于硬件的动态开发方法（本章内容）
基于软件的静态开发方法

流水线处理机的实际CPI

理想流水线的CPI加上各类停顿的时钟周期数：
$CPI_\text{流水线} = CPI_\text{理想} + \text{停顿}_\text{结构冲突} + \text{停顿}_\text{数据冲突} + \text{停顿}_\text{控制冲突}$
理想CPI是衡量流水线最高性能的一个指标
IPC：Instructions Per Cycle：每个时钟周期完成的指令条数

基本程序块

基本程序块：一串连续的代码除了入口和出口以外，没有其他的分支指令和转入点 。
实际上程序平均每4～7条指令就会有一个分支。

循环级并行

使一个循环中的不同循环体并行执行。
开发循环的不同叠代之间存在的并行性（最常见、最基本）
是指令级并行研究的重点之一
一种开发循环级并行性的重要方法是采用向量指令和向量数据表示

5.2 相关与指令级并行

5.2.1相关与流水线冲突

5.2.2 程序顺序

程序顺序：由原来程序确定的在完全串行方式下指令的执行顺序。

只有在可能会导致错误的情况下，才保持程序顺序。

程序顺序与属性

控制相关：并不是一个必须严格保持的关键属性（不是提高性能的主要限制）。

对于正确地执行程序来说，必须保持的最关键的两个属性是：数据流和异常行为。

保持异常行为是指：无论怎么改变指令的执行顺序，都不能改变程序中异常的发生情况。
- 即原来程序中是怎么发生的，改变执行顺序后还是怎么发生。
- 弱化为：指令执行顺序的改变不能导致程序中发生新的异常。
数据流：指数据值从其产生者指令到其消费者指令的实际流动。
- 分支指令使得数据流具有动态性，因为一条指令有可能数据相关于多条先前的指令。
- 分支指令的执行结果决定了哪条指令真正是所需数据的产生者。

有时，不遵守控制相关既不影响异常行为，也不改变数据流。

可以大胆地进行指令调度，把失败分支中的指令调度到分支指令之前。

例如：对于以下程序

          DADDU     	R1，R2，R3
          BEQZ	R12，Skipnext
          DSUBU	R4，R5，R6
          DADDU	R5，R4，R9
Skipnext：OR	R7，R8，R9
1
2
3
4
5

假设我们知道R4在Skipnext之后不再被使用，而且DSUBU不会产生异常，那么就可以把DSUBU移到分支指令之前。这是因为这个移动不会改变数据流。
如果分支成功，尽管按原程序DSUBU指令是不该执行的,但现在执行了也没关系,因为它不会影响程序的执行结果。

5.3 指令的动态调度

静态调度与动态调度的对比

	静态调度	动态调度
调度发生时间	在编译期间进行代码调度和优化	在程序的执行过程中
依靠	依靠编译器对代码进行静态调度，以减少相关和冲突	依靠专门硬件对代码进行调度
调度方式	通过把相关的指令拉开距离来减少可能产生的停顿	减少数据相关导致的停顿

动态调度的优缺点

优点	缺点
能够处理一些在编译时情况不明的相关（比如涉及到存储器访问的相关），并简化了编译器	硬件复杂性的显著增加为代价
能够使本来是面向某一流水线优化编译的代码在其它的流水线（动态调度）上也能高效地执行

静态与动态流水线的时空图

静态和动态流水线的时空图

5.3.1 动态调度的基本思想

5段流水线的最大局限性

到目前为止我们所使用流水线（5段流水线）的最大的局限性:

指令是按序流出和按序执行的

例：考虑下面一段代码：

DIV		F4，F0，F2
ADD		F10，F4，F6 
SUB		F12，F6，F14
1
2
3

ADD指令与DIV指令关于F4相关，导致流水线停顿。
SUB指令与流水线中的任何指令都没有关系，但也因此受阻。
这是按序流出和按序执行带来的局限性。如果可以不按程序顺序执行指令,就能进一步提高性能。

在5段流水线中,结构冲突和数据冲突都是在译码(ID)段进行检测的。只有当既没有结构冲突也没有数据冲突时，指令才能够流出。为了使上述指令序列中的SUB指令能继续执行下去,必须把指令流出的工作拆分为两步

检测结构冲突;
等待数据冲突消失。

只要检测到没有结构冲突，就可以让指令流出。并且流出后的指令一旦其操作数就绪就可以立即执行。

⚠️修改后的流水线是乱序执行

即指令的执行顺序与程序顺序不相同。
同样，指令的完成也是乱序完成的，即指令的完成顺序与程序顺序不相同。
为了支持乱序执行，将前述5段流水线的译码(ID)段细分为两个段。
1. 流出（Issue，IS）：指令译码,并检查是否存在结构冲突。如果不存在结构冲突，就将指令流出。
2. 读操作数（Read Operands，RO）：等待数据冲突消失(如果有)，然后读操作数。
指令的流出仍然是按序流出(In-order Issue)的。

但是,它们在读操作数段可能停顿和互相跨越，因而进入执行段时就可能已经是乱序的了。

修改前后的时空图

按序发射按序执行

DIV F4,F0,F2	IF	ID	EX	MEM	WB
ADD F10, F4, F6		stall	stall	stall	IF	ID	EX	MEM	WB
SUB F12, F6, F14						IF	ID	EX	MEM	WB

无序发射无序执行

DIV F4,F0,F2	IF	ID	EX	MEM	WB
ADD F10, F4, F6		stall	stall	stall	IF	ID	EX	MEM	WB
SUB F12, F6, F14		IF	ID	EX	MEM	WB

在前述5段流水线中，是不会发生WAR冲突和WAW冲突的。但乱序执行就使得它们可能发生了。

考虑以下代码：

DIV	  F10, F0, F2
ADD	  F10, F4, F6
SUB	  F6, F8, F14
1
2
3

DIV指令与ADD指令存在输出相关
ADD指令和SUB指令存在反相关
可以通过使用寄存器重命名（换名）来消除。

动态调度的流水线支持多条指令同时处于执行当中。

要求：具有多个功能部件、或者功能部件流水化、或者兼而有之。
我们假设具有多个功能部件。

指令乱序完成带来的最大问题:

异常处理（中断）比较复杂
- 分为：精确异常处理、不精确异常处理
- 不精确异常：当执行指令i导致发生异常时，处理机的现场（状态）与严格按程序顺序执行时指令i的现场不同。
- 精确异常：当执行指令i导致发生异常时，处理机的现场（状态）与严格按程序顺序执行时指令i的现场相同。要设置一定数量的后援寄存器，把流水线中所有指令的执行结果和现场保存下来。成本高，现在都这样实现。
动态调度的处理机保持正确的异常行为的方式：
- 对于一条会产生异常的指令来说，只有当处理机确切地知道该指令将被执行时，才允许它产生异常。
即使保持了正确的异常行为，动态调度处理机仍可能发生不精确异常。
- 发生不精确异常的原因：因为当发生异常（设为指令i）时：
  - 流水线可能已经执行完按程序顺序是位于指令i之后的指令；
  - 流水线可能还没完成按程序顺序是指令i之前的指令。
- 不精确异常使得在异常处理后难以接着继续执行程序。

精确断点法与不精确断点法

精确断点法
- 要设置一定数量的后援寄存器，把流水线中所有指令的执行结果和现场保存下来。
不精确断点法：
- 流水线可以不“断流”；
- 所需要的硬件比较少，控制逻辑相对比较简单
- 中断响应时间稍长，要增加一条流水线的时间长度
采用不精确断点法可能会发生如下两个问题：
- 程序执行的结果可能出错
- 程序的调试困难

5.3.2 记分牌动态调度算法

CDC 6600计算机最早采用此功能

记分牌算法的基本思想

该机器用一个称为记分牌的硬件实现了对指令的动态调度。
该硬件中维护着3张表，分别用于记录指令的执行状态、功能部件状态、寄存器状态以及数据相关关系等。
它把前述5段流水线中的译码段ID分解成了两个段：流出段和读操作数段，以避免当某条指令在ID段被停顿时挡住后面无关指令的流动。

记分牌的目标

在没有结构冲突时，尽可能早地执行没有数据冲突的指令，实现每个时钟周期执行一条指令。

要发挥指令乱序执行的好处，必须有多条指令同时处于执行阶段。

CDC 6600具有16个独立的功能部件
- 4个浮点部件
- 5个访存部件
- 7个整数操作部件

为了讨论的简单，假设所考虑的处理器有2个乘法器、1个加法器、1个除法部件和1个整数部件。

整数部件用来处理所有的存储器访问、分支处理和整数操作。

记分牌的MIPS处理器的基本结构

记分牌算法的执行

每条指令的执行过程（EX段）分为4段 （主要考虑浮点操作）

流出
- 如果当前流出指令所需的功能部件空闲，并且所有其他正在执行的指令的目的寄存器与该指令的不同（其他指令不写该指令的目的寄存器），记分牌就向功能部件流出该指令，并修改记分牌内部的记录表。
- 解决了WAW冲突
读操作数
- 记分牌监测源操作数的可用性，如果数据可用，它就通知功能部件从寄存器中读出源操作数并开始执行。
- 动态地解决了RAW冲突，并导致指令可能乱序开始执行。
执行
- 取到操作数后，功能部件开始执行。当产生出结果后，就通知记分牌它已经完成执行。
- 在浮点流水线中，这一段可能要占用多个时钟周期。
写结果
- 记分牌一旦知道执行部件完成了执行，就检测是否存在WAR冲突。如果不存在，或者原有的WAR冲突已消失，记分牌就通知功能部件把结果写入目的寄存器，并释放该指令使用的所有资源。

检测到WAR冲突的情况以及解决

如果检测到WAR冲突，就不允许该指令将结果写到目的寄存器。这发生在以下情况：
- 前面的某条指令（按顺序流出）还没有读取操作数；而且：其中某个源操作数寄存器与本指令的目的寄存器相同。
- 在这种情况下，记分牌必须等待，直到该冲突消失。

记分牌的信息

由三部分构成

指令状态表：记录正在执行的各条指令已经进入到了哪一段。
功能部件状态表：记录各个功能部件的状态。每个功能部件有一项，每一项由以下9个字段组成：
- $B u s y$ ：忙标志，指出功能部件是否忙。初值为“no”；
- $O p$ ：该功能部件正在执行或将要执行的操作；
- $F_{i}$ ：目的寄存器编号；
- $F_{j}，F_{k}$ ：源寄存器编号；
- $Q_{j}，Q_{k}$ ：指出向源寄存器 $F_{j}、F_{k}$ 写数据的功能部件；
- $R_{i}，R_{j}$ ：标志位，为“yes”表示 $F_{j}$ ， $F_{k}$ 中的操作数就绪且还未被取走。否则就被置为“no”。
结果寄存器状态表Result：每个寄存器在该表中有一项，用于指出哪个功能部件（编号）将把结果写入该寄存器。
- 如果当前正在运行的指令都不以它为目的寄存器，则其相应项置为“no”。
- Result各项的初值为“no”（全0）。

记分牌算法举例

分析下列代码运行过程中记分牌保存的信息

L.D	    	F6, 34(R2)
L.D	    	F2, 45(R3)
MULT.D      F0, F2, F4
SUB.D	    F8, F6, F2
DIV.D	    F10, F0, F6
ADD.D	    F6, F8, F2
1
2
3
4
5
6

情况一：第一条指令L.D执行完毕；第二条指令L.D执行完毕，但没有写入目的寄存器F2，记分牌状态表如下：

MIPS记分牌中的信息1

在上图的指令状态表中：
- 第一条L.D指令已经完全执行完，其结果已经写人了F6;
- 第二条L.D指令也已经执行完，但是结果还没有写人目的寄存器F2;
- 由于第二条L.D指令与MULT.D和SUB.D指令之间存在关于寄存器F2的先写后读(RAW)相关，因此MULT.D和SUB. D在流出段等待，不能进入流水线的读操作数段。
- 同样，MULT.D与DIV.D之间存在关于寄存器F0的RAW相关，因此DIV.D也只能在流出段等待。
- 指令ADD.D与指令SUB.D之间存在关于加法器的结构相关，因此后面的ADD.D连流出都不能做，必须等到前面SUB.D指令全部执行完毕、释放加法器后才能够流出。
在上图的**功能部件状态表**中：
- 整数(Integer)部件
  - Busy字段为yes,表示部件正忙
  - 其Op表示它在执行L.D指令
  - 目的寄存器字段 $F_{i}$ 中记录的是F2。相应地，在结果寄存器状态表的F2字段中记录的是Integer部件。
  - 对于存储器访问类指令来说,第一源操作数寄存器字段 $F_{j}$ 中记录的是访存地址寄存器。在本例中就是R3。它的 $R_{j}$ 字段为no,表示R3的数据已经被读取过了。
- 在乘法1(Mult1)部件
  - Busy字段是yes,表示正忙
  - Op字段记录的是MULT.D指令
  - 其目的寄存器字段 $F_{i}$ 的内容为F0。相应地,在结果寄存器状态表的F0字段中记录的是Mult1,表示F0将存放Mult1部件的运算结果。
  - 在第一源操作数寄存器字段 $F_{j}$ 中记录的是F2,它的 $Q_{j}$ 字段为Integer,表示F2的数据将来自Integer部件的操作结果，它的 $R_{j}$ 字段为no,表示F2的数据还没有就绪,这个过程可以用来判断并解决数据的写后读(RAW)相关
  - 第二源操作数寄存器字段 $F_{k}$ 中记录的是F4， $Q_{k}$ 字段为空,表示F4不依赖于当前工作的任何部件, $R_{k}$ 字段为yes,表示F4的数0据已经就绪。
- 乘法2(Mult2)部件
  - Busy字段是no,表示该功能部件当前空闲。
- 其余部件的分析类似
在上图的结果寄存器状态表中：
- 表中的字段与每个寄存器一一对应，它记录了当前机器状态下将把结果写人该寄存器的功能部件的名称
- 当前写F0的为Mult1部件,写F2的为Integer部件,写F8的为Add部件,写F10的为Divide部件。
- 字段为空表示空闲，即对应的寄存器没有被任何当前正在工作的功能部件作为目的寄存器使用。

为更进一步分析，假设复电流水线各部件的延迟如下：

加法需2个时钟周期
乘法需10个时钟周期
除法需40个时钟周期

情况二：给出MULT.D和DIV.D准备写结果之前的记分牌状态。

程序执行到MULT.D将要写结果时记分牌的状态

MIPS记分牌中的信息2

从上图中可以知道，在MULT. D准备写结果之前，由于DIV.D指令与MULT.D指
令之间存在关于寄存器F0的RAW相关，因此在MULT. D指令完成写结果之前,DIV.D
指令被阻塞在流出段而无法进人读操作数段。

同时由于ADD.D指令与DIV.D指令之间存在关于寄存器F6的WAR相关，因此在DIV.D指令从F6中读出操作数之前，ADD. D指令被阻塞在执行段,无法进入写结果段。

程序段执行到DIV.D将要写结果时记分牌的状态

在上图中

由于DIV.D指令执行需要40个时钟周期，其后的ADD.D指令只需要两个时钟周期
DIV.D准备写结果之前，这条指令前面的指令已经全部执行完毕
而且DIV.D和ADD. D之间存在的WAR相关在DIV.D读走源操作数后就已经消失了
因此ADD.D有足够的时间完成所有操作,所以就只剩下DIV.D指令没有完成写结果操作。

记分牌算法伪代码

为了表述算法的方便，约定：

FU：表示当前指令所要用的功能部件；
D：目的寄存器的名称；
S1、S2：源操作数寄存器的名称；
Op：要进行的操作；
$F_{j}[FU]$ ：功能部件FU的 $F_{j}$ 字段（其他字段依此类推）；
Result[D]：结果寄存器状态表中与寄存器D相对应的内容。其中存放的是将把结果写入寄存器D的功能部件的名称。

指令流出

//进入条件：
not Busy[FU] & not Result[D]; // 功能部件空闲且没有写后写（WAW）冲突。

//计分牌内容修改:
Busy[FU] ← yes; // 把当前指令的相关信息填入功能部件状态表。
Op[FU] ← Op;    // 记录操作码。
Fi[FU] ← D;     // 记录目的寄存器编号。
Fj[FU] ← S1;    // 记录第一个源寄存器编号。
Fk[FU] ← S2;    // 记录第二个源寄存器编号。

Qj[FU] ← Result[S1];	// 记录将产生第一个源操作数的部件。
Qk[FU] ← Result[S2];	// 记录将产生第二个源操作数的部件。

//如果Qj[FU]为“no”，就表示没有操作部件要写S1，数据可用。
//置Rj[FU]为“yes”。否则置Rj[FU]为“no”。
Rj[FU] ← not Qj[FU];	// 置第一个源操作数是否可用的标志。
Rk[FU] ← not Qk[FU];	// 置第二个源操作数是否可用的标志。
Result[D] ← FU;			// D是当前指令的目的寄存器。功能部件FU将把结果写入D。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

指令流出

//进入条件：
Rj[FU] & Rk[FU];	// 两个源操作数都已就绪。

//计分牌内容修改:
Rj[FU] ← no;	// 已经读走了就绪的第一个源操作数。
Rk[FU] ← no;	// 已经读走了就绪的第二个源操作数。
Qj[FU] ← 0;		// 不再等待其他FU的计算结果。
Qk[FU] ← 0; 
1
2
3
4
5
6
7
8

执行

//结束条件
//功能部件操作结束。
1
2

写结果

//进入条件:不存在WAR冲突。
∀f((Fj[f] ≠ Fi[FU] or Rj[f] = no)
&  (Fk[f] ≠ Fi[FU] or Rk[f]=no))
//计分牌内容修改:
// 如果有指令在等待该结果（作为第一源操作数），则将其Rj置为“yes”，表示数据可用。
∀f(if Qj[f] = FU then Rj[f] ← yes);
// 如果有指令在等待该结果（作为第二源操作数），则将其Rk置为“yes”，表示数据可用。
∀f(if Qk[f]=FU then Rk[f]←yes);	

Result(Fi[FU]) ← 0;	// 释放目的寄存器Fi[FU]。
Busy[FU] = no;		// 释放功能部件FU。
1
2
3
4
5
6
7
8
9
10
11

记分牌的性能限制（四个方面）

程序代码中可开发的并行性，即是否存在可以并行执行的不相关的指令。
记分牌的容量。
- 记分牌的容量决定了流水线能在多大范围内寻找不相关指令。
- 流水线中可以同时容纳的指令数量称为指令窗口。
功能部件的数目和种类。
- 功能部件的总数决定了结构冲突的严重程度。
反相关和输出相关。
- 它们引起计分牌中WAR和WAW冲突。
问题(2)和(3)可通过增加记分牌的容量和功能部件的数量来解决,但这会导致处理器成本增加，并可能影响系统时钟周期时间。
在采用动态调度的处理器中，WAW和WAR冲突会增多，因为乱序流出的指令在流水线中会引起更多的名相关。
如果在动态调度中采用分支预测技术，就会出现循环的多个迭代同时执行，名相关将更加严重。

5.3.3 Tomasulo算法

IBM 360/91首先采用了Tomasulo算法。

核心思想

记录和检测指令相关，操作数一旦就绪就立即执行，把发生RAW冲突的可能性减少到最小（引入延迟）；
通过寄存器换名来消除WAR冲突和WAW冲突。

IBM 360/91 采用Tomasulo算法的原因

IBM 360/91的设计目标是基于整个360系列的统一指令系统和编译器来实现高性能，而不是设计和利用专用的编译器来提高性能。与此同时， 需要更多地依赖于硬件。
IBM 360体系结构只有4个双精度浮点寄存器，限制了编译器调度的有效性。
360/91的访存时间和浮点计算时间都很长。

基于Tomasulo算法的MIPS处理器浮点部件的基本结构

其中各个功能部件介绍如下：

1.保留站（reservation station）

每个保留站中保存一条已经流出并等待到本功能部件执行的指令（相关信息）。
存储内容包括：操作码、操作数以及用于检测和解决冲突的信息。
对源操作数的处理
- 在一条指令流出到保留站的时候，如果该指令源操作数已经在寄存器中就绪，则将之取到该保留站中。
- 如果操作数还没有计算出来，则在该保留站中记录将产生这个操作数的保留站的标识。
每个保留站都有一个标识字段，唯一地标识了该保留站。
保留站的类型
- 浮点加法器有3个保留站：ADD1，ADD2，ADD3
- 浮点乘法器有两个保留站：MULT1，MULT2

2.公共数据总线CDB

是该结构中的一条重要的数据通路
所有功能部件的计算结果都是送到CDB上，由它把这些结果直接送到（播送到）各个需要该结果的地方。
在具有多个执行部件且采用多流出（即每个时钟周期流出多条指令）的流水线中，需要采用多条CDB。

3.load缓冲器和store缓冲器

存放读/写存储器的数据或地址
load缓冲器的作用有3个：
- 存放用于计算有效地址的分量；
- 记录正在进行的load访存，等待存储器的响应；
- 保存已经完成了的load的结果（即从存储器取来的数据），等待CDB传输。
store缓冲器的作用有3个：
- 存放用于计算有效地址的分量；
- 保存正在进行的store访存的目标地址，该store正在等待存储数据的到达；
- 保存该store的地址和数据，直到存储部件接收。

4.浮点寄存器FP

共有16个浮点寄存器：F0，F2，F4，…，F30。
它们通过一对总线连接到功能部件，并通过CDB连接到store缓冲器。

5.指令队列

指令部件送来的指令放入指令队列
指令队列中的指令按先进先出的顺序流出

6.运算部件

浮点加法器完成加法和减法操作
浮点乘法器完成乘法和除法操作

Tomasulo算法的寄存器换名

实现：

寄存器换名是通过保留站和流出逻辑来共同完成的。
当指令流出时，如果其操作数还没有计算出来，则将该指令中相应的寄存器号换名为将产生这个操作数的保留站的标识。

结论：

指令流出到保留站后，其操作数寄存器号或者换成了数据本身（如果该数据已经就绪），或者换成了保留站的标识，不再与寄存器有关系。

Tomasulo算法的两个特点

由于Tomasulo算法采用分布的保留站，因此具有以下特点：

冲突检测和指令执行控制是分开的。
- 每个功能部件的保留站中的信息决定了什么时候指令可以在该功能部件开始执行。
计算结果通过CDB直接从产生它的保留站传送到所有需要它的功能部件，而不用经过寄存器。

Tomasulo算法指令执行的步骤

使用Tomasulo算法的流水线需3段（均在EX段）：

1.流出：从指令队列的头部取一条指令。

如果该指令的操作所要求的保留站有空闲的，就把该指令送到该保留站（设为r）。
如果其操作数在寄存器中已经就绪，就将这些操作数送入保留站r。
如果其操作数还没有就绪，就把将产生该操作数的保留站的标识送入保留站r。
一旦被记录的保留站完成计算，它将直接把数据送给保留站r。

消除WAR以及WAW冲突

在这一阶段，通过对寄存器换名（换成保留站的标识）和对操作数进行缓冲（就绪的操作数直接存入保留站），消除了WAR冲突。
此外，这一阶段还完成了对目的寄存器的预约工作，将其设置为接收保留站r的结果，这实际上相当于完成了写操作（预约）。由于指令是按照顺序流出的，当出现多条指令写同一个结果寄存器时，最后留下的结果一定是最后一条指令的，即消除了WAW冲突。

如果没有空闲的保留站，指令就不能流出。

发生了结构冲突

2.执行

当两个操作数都就绪后，本保留站就用相应的功能部件开始执行指令规定的操作。
load和store指令的执行需要两个步骤：
- 计算有效地址（要等到基地址寄存器就绪）
- 把有效地址放入load或store缓冲器

消除RAW冲突

此处要等到所有操作数都准备就绪才开始执行指令，即通过推迟执行的方式解决RAW冲突。

3.写结果

功能部件计算完毕后，就将计算结果放到CDB上，所有等待该计算结果的寄存器和保留站（包括store缓冲器）都同时从CDB上获得所需要的数据。

保留站的7个字段

$O p$ ：要对源操作数进行的操作
$Q_{j}，Q_{k}$ ：将产生源操作数的保留站号
- 等于0表示操作数已经就绪且在 $V_{j}$ 或 $V_{k}$ 中，或者不需要操作数。
$V_{j}，V_{k}$ ：源操作数的值
- 对于每一个操作数来说， $V$ 或 $Q$ 字段只有一个有效。
- 对于load来说， $V_{k}$ 字段用于保存偏移量。
$B u s y$ ：为“yes”表示本保留站或缓冲单元“忙”
$A$ ：仅load和store缓冲器有该字段。开始是存放指令中的立即数字段，地址计算后存放有效地址。
$Q_{j}$ ：寄存器状态表
- 每个寄存器在该表中有对应的一项，用于存放将把结果写入该寄存器的保留站的站号。
- 为0表示当前没有正在执行的指令要写入该寄存器，也即该寄存器中的内容就绪。

Tomasulo算法举例

对下列指令序列给出当第一条指令完成并写入结果时，Tomasulo算法所用的各信息表中的内容

L.D	F6,34（R2）
L.D	F2,45（R3）
MUL.D	F0,F2,F4
SUB.D	F8,F2,F6
DIV.D	F10,F0,F6
ADD.D	F6,F8,F2 
1
2
3
4
5
6

Tomasulo示例

图中所有的指令均已流出，但只有第一条load指令执行完毕并将结果写到CDB上。
第二条load指令已经完成有效地址计算，正在等待存储器的响应。
用Regs[]表示寄存器组,用Mem[]表示存储器。
这里,刚刚流出的ADD.D指令与前一条指令DIV.D有一个WAR冲突,但它可以先于DIV. D完成而不会导致错误。

Tomasulo算法伪代码

各符号的意义

r：分配给当前指令的保留站或者缓冲器单元编号；
rd：目标寄存器编号；
rs、rt：操作数寄存器编号；
imm：符号扩展后的立即数；
RS：保留站；
result：浮点部件或load缓冲器返回的结果；
Qi：寄存器状态表；
Regs[ ]：寄存器组；
与rs对应的保留站字段：Vj，Qj
与rt对应的保留站字段：Vk，Qk
Qi、Qj、Qk的内容或者为0，或者是一个大于0的整数。
- Qi为0表示相应寄存器中的数据就绪。
- Qj、Qk为0表示保留站或缓冲器单元中的Vj或Vk字段中的数据就绪。
- 当它们为正整数时，表示相应的寄存器、保留站或缓冲器单元正在等待结果。

1. 指令流出

浮点运算指令

// 进入条件：有空闲保留站（设为r）
// 操作和状态表内容修改：
if （Qi[rs] ≠ 0）	// 检测第一操作数是否就绪
{
    //第一操作数没有就绪，进行寄存器换名，即把将产生该操作数的保留站的编号放入当前保留站的Qj。
    //该编号是一个大于0的整数。
    RS[r].Qj ← Qi[rs]; 
}
else
{
    RS[r].Vj ← Regs[rs]; //第一操作数就绪。把寄存器rs中的操作数取到当前保留站的Vj。 
    RS[r].Qj ← 0		//置Qj为0，表示当前保留站的Vj中的操作数就绪 。
}

if （Qi[rt] ≠ 0）	// 检测第二操作数是否就绪
{
    //第二操作数没有就绪，进行寄存器换名，即把将产生该操作数的保留站的编号放入当前保留站的Qk。
    //该编号是一个大于0的整数。
    RS[r].Qk ← Qi[rt]; 
}
else
{
    RS[r].Vk ← Regs[rt]; //第二操作数就绪。把寄存器rt中的操作数取到当前保留站的Vk。 
    RS[r].Qj ← 0;		//置Qk为0，表示当前保留站的Vk中的操作数就绪 。
}

RS[r].Busy ← yes;	//置当前保留站为“忙”
RS[r].Op ← Op;  	//设置操作码
Qi[rd] ← r;	// 把当前保留站的编号r放入rd所对应的寄存器状态表项，以便rd将来接收结果。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

load和store指令

// 进入条件：缓冲器有空闲单元（设为r） 
// 操作和状态表内容修改：
if （Qi[rs] ≠ 0）	// 检测第一操作数是否就绪
{
    //第一操作数没有就绪，进行寄存器换名，即把将产生该操作数的保留站的编号存入当前缓冲器单元Qj。
    //该编号是一个大于0的整数。
    RS[r].Qj ← Qi[rs]; 
}
else
{
    RS[r].Vj ← Regs[rs]; //第一操作数就绪。把寄存器rs中的操作数取到当前缓冲器单元的Vj。 
    RS[r].Qj ← 0		//置Qj为0，表示当前缓冲器单元的Vj中的操作数就绪 。
}
RS[r].Busy ← yes；	// 置当前缓冲器单元为“忙”
RS[r].A ← Imm；		// 把符号位扩展后的偏移量放入当前缓冲器单元的A                               
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

对于load指令

// 把当前缓冲器单元的编号r放入load指令的目标寄存器rt所对应的寄存器状态表项，以便rt将来接收所取的数据。
Qi[rt] ← r；	
1
2

对于store指令

if (Qi[rt]  ≠ 0)	// 检测要存储的数据是否就绪
{
	// 该数据尚未就绪，进行寄存器换名，即把将产生该数据的保留站的编号放入当前缓冲器单元的Qk。
	RS[r].Qk ← Qi[rt];
}else
{
    RS[r].Vk ← Regs[rt]；	// 该数据就绪，把它从寄存器rt取到store缓冲器单元的Vk
    RS[r].Qk ← 0;			 // 置Qk为0，表示当前缓冲器单元的Vk中的数据就绪。
}
1
2
3
4
5
6
7
8
9