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

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

开发ILP的途径有两种

• 资源重复，重复设置多个处理部件，让它们同时执行相邻或相近的多条指令；

• 采用流水线技术，使指令重叠并行执行。

指令级并行的概念

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

• 主要基于硬件的动态开发方法

• 基于软件的静态开发方法

流水线处理机的实际CPI

• 理想流水线的CPI加上各类停顿的时钟周期数： $CPI_{流水线}=CPI_{理想}+停顿_{结构冲突}+停顿_{数据冲突}+停顿_{控制冲突}$

• 理想CPI是衡量流水线最高性能的一个指标。

• IPC：Instructions Per Cycle（每个时钟周期完成的指令条数）

基本程序块

• 基本程序块：一串连续的代码除了入口和出口以外，没有其他的分支指令和转入点 。

• 程序平均每4～7条指令就会有一个分支。

循环级并行：使一个循环中的不同循环体并行执行。

• 开发循环的不同叠代之间存在的并行性 最常见、最基本

• 是指令级并行研究的重点之一

最基本的开发循环级并行的技术

• 循环展开（loop unrolling）技术

• 采用向量指令和向量数据表示

相关与指令级并行

相关与流水线冲突

• 相关有三种类型： 数据相关、名相关、控制相关

• 流水线冲突是指对于具体的流水线来说，由于相关的存在，使得指令流中的下一条指令不能在指定的时钟周期执行。 流水线冲突有三种类型：结构冲突、数据冲突、控制冲突

• 相关是程序固有的一种属性，它反映了程序中指令之间的相互依赖关系。

• 具体的一次相关是否会导致实际冲突的发生以及该冲突会带来多长的停顿，则是流水线的属性。

可以从两个方面来解决相关问题：

• 保持相关，但避免发生冲突。 指令调度

• 通过代码变换，消除相关。

程序顺序：由原来程序确定的在完全串行方式下指令的执行顺序。 只有在可能会导致错误的情况下，才保持程序顺序。

控制相关并不是一个必须严格保持的关键属性。

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

• 保持异常行为是指：无论怎么改变指令的执行顺序，都不能改变程序中异常的发生情况。

  • 即原来程序中是怎么发生的，改变执行顺序后还是怎么发生。

  • 弱化为：指令执行顺序的改变不能导致程序中发生新的异常。

• 数据流：指数据值从其产生者指令到其消费者指令的实际流动。

  • 分支指令使得数据流具有动态性，因为一条指令有可能数据相关于多条先前的指令。

  • 分支指令的执行结果决定了哪条指令真正是所需数据的产生者。

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

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

指令的动态调度

静态调度

• 依靠编译器对代码进行静态调度，以减少相关和冲突。

• 它不是在程序执行的过程中、而是在编译期间进行代码调度和优化。

• 通过把相关的指令拉开距离来减少可能产生的停顿。

动态调度

• 在程序的执行过程中，依靠专门硬件对代码进行调度，减少数据相关导致的停顿。

• 优点：

  • 能够处理一些在编译时情况不明的相关（比如涉及到存储器访问的相关），并简化了编译器；

  • 能够使本来是面向某一流水线优化编译的代码在其它的流水线（动态调度）上也能高效地执行。

• 以硬件复杂性的显著增加为代价

动态调度的基本思想

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

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

• 为了使上述指令序列中的SUB.D指令能继续执行下去，必须把指令流出的工作拆分为两步：

  • 检测结构冲突

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

乱序执行

• 指令的执行顺序与程序顺序不相同

• 指令的完成也是乱序完成的 即指令的完成顺序与程序顺序不相同。

为了支持乱序执行，我们将5段流水线的译码阶段再分为两个阶段：

• 流出（Issue，IS）：指令译码，检查是否存在结构冲突。（in-order issue)

• 读操作数（Read Operands，RO）：等待数据冲突消失，然后读操作数

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

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

• 我们假设具有多个功能部件。

指令乱序完成带来的最大问题：异常处理比较复杂（精确异常处理、不精确异常处理）

• 动态调度的处理机要保持正确的异常行为 对于一条会产生异常的指令来说，只有当处理机确切地知道该指令将被执行时，才允许它产生异常。

• 即使保持了正确的异常行为，动态调度处理机仍可能发生不精确异常。

• 不精确异常：当执行指令i导致发生异常时，处理机的现场（状态）与严格按程序顺序执行时指令i的现场不同。

  • 发生不精确异常的原因：因为当发生异常（设为指令i）时： 流水线可能已经执行完按程序顺序是位于指令i之后的指令； 流水线可能还没完成按程序顺序是指令i之前的指令。

  • 不精确异常使得在异常处理后难以接着继续执行程序。

• 精确异常：如果发生异常时，处理机的现场跟严格按程序顺序执行时指令i的现场相同。

记分牌算法和Tomasulo算法是两种比较典型的动态调度算法。

记分牌动态调度算法

基本思想

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

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

• 采用了记分牌的MIPS处理器的基本结构

  • 每条指令都要经过记分牌。

  • 记分牌负责相关检测并控制指令的流出和执行。

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

  • 流出 如果当前流出指令所需的功能部件空闲，并且所有其他正在执行的指令的目的寄存器与该指令的不同，记分牌就向功能部件流出该指令，并修改记分牌内部的记录表。 解决了WAW冲突

  • 读操作数 记分牌监测源操作数的可用性，如果数据可用，它就通知功能部件从寄存器中读出源操作数并开始执行。 动态地解决了RAW冲突，并导致指令可能乱序开始执行。

  • 执行 取到操作数后，功能部件开始执行。当产生出结果后，就通知记分牌它已经完成执行。 在浮点流水线中，这一段可能要占用多个时钟周期。

  • 写结果 记分牌一旦知道执行部件完成了执行，就检测是否存在WAR冲突。如果不存在，或者原有的WAR冲突已消失，记分牌就通知功能部件把结果写入目的寄存器，并释放该指令使用的所有资源。

• 如果检测到WAR冲突，就不允许该指令将结果写到目的寄存器。这发生在以下情况：

  • 前面的某条指令（按顺序流出）还没有读取操作数；而且：其中某个源操作数寄存器与本指令的目的寄存器相同。

  • 在这种情况下，记分牌必须等待，直到该冲突消失。

• 记分牌中记录的信息由3部分构成

  • 指令状态表：记录正在执行的各条指令已经进入到了哪一段。

  • 功能部件状态表：记录各个功能部件的状态。每个功能部件有一项，每一项由以下9个字段组成： Busy：忙标志，指出功能部件是否忙。初值为“no”； Op：该功能部件正在执行或将要执行的操作； Fi：目的寄存器编号； Fj，Fk：源寄存器编号； Qj，Qk：指出向源寄存器Fj、Fk写数据的功能部件 ； Rj，Rk：标志位，为“yes”表示Fj，Fk中的操作数就绪且还未被取走。否则就被置为“no”。

  • 结果寄存器状态表Result：每个寄存器在该表中有一项，用于指出哪个功能部件（编号）将把结果写入该寄存器。 如果当前正在运行的指令都不以它为目的寄存器，则其相应项置为“no”。 Result各项的初值为“no”（全0）。

具体算法

约定：

• FU：表示当前指令所要用的功能部件；

• D：目的寄存器的名称；

• S1、S2：源操作数寄存器的名称；

• Op：要进行的操作；

• Fj[FU]：功能部件FU的Fj字段（其他字段依此类推）；

• Result[D]：结果寄存器状态表中与寄存器D相对应的内容。其中存放的是将把结果写入寄存器D的功能部件的名称。

（1）指令流出 进入条件： 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]； // 记录将产生第二个源操作数的部件。 Rj[FU]←not Qj[FU]； // 置第一个源操作数是否可用的标志。如果Qj[FU]为“no”，就表示没有操作部件要写S1，数据可用。置Rj[FU]为“yes”。否则置Rj[FU]为“no”。 Rk[FU]←not Qk[FU]；// 置第二个源操作数是否可用的标志。 Result[D]←FU； // D是当前指令的目的寄存器。功能部件FU将把结果写入D。 （2）读操作数 进入条件： Rj[FU] & Rk[FU]；// 两个源操作数都已就绪。 计分牌内容修改： Rj[FU]←no； // 已经读走了就绪的第一个源操作数。 Rk[FU]←no； // 已经读走了就绪的第二个源操作数。 Qj[FU]←0； // 不再等待其他FU的计算结果。 Qk[FU]←0； （3）执行 结束条件： 功能部件操作结束。 （4）写结果 进入条件： $\forall f((Fj[f]\neq Fi[FU] or Rj[f]=no)$or$(Fk[f]\neq Fi[FU] or Rk[f]=no))$; // 不存在WAR冲突。 计分牌内容修改： $\forall f(if Qj[f]=FU then Rj[f]\leftarrow yes)$; // 如果有指令在等待该结果（作为第一源操作数），则将其Rj置为“yes”，表示数据可用。 $\forall f(if Qk[f]=FU then Rk[f]\leftarrow yes)$; // 如果有指令在等待该结果（作为第二源操作数），则将其Rk置为“yes”，表示数据可用。 Result(Fi[FU])←0； // 释放目的寄存器Fi[FU]。 Busy[FU]=no； // 释放功能部件FU。

记分牌的性能受限于以下几个方面：

• 程序代码中可开发的并行性，即是否存在可以并行执行的不相关的指令。

• 分牌的容量。 记分牌的容量决定了流水线能在多大范围内寻找不相关指令。流水线中可以同时容纳的指令数量称为指令窗口。

• 功能部件的数目和种类。 功能部件的总数决定了结构冲突的严重程度。

• 反相关和输出相关。 它们引起计分牌中WAR和WAW冲突 。

Tomasulo算法

基本思想

核心思想

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

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

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

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

  • 浮点加法器有3个保留站：ADD1，ADD2，ADD3

  • 浮点乘法器有两个保留站：MULT1，MULT2

  • 每个保留站都有一个标识字段，唯一地标识了该保留站。

• 公共数据总线CDB （一条重要的数据通路）

  • 所有功能部件的计算结果都是送到CDB上，由它把这些结果直接送到（播送到）各个需要该结果的地方。

  • 在具有多个执行部件且采用多流出（即每个时钟周期流出多条指令）的流水线中，需要采用多条CDB。

• load缓冲器和store缓冲器

  • 存放读/写存储器的数据或地址

  • load缓冲器的作用有3个： 存放用于计算有效地址的分量； 记录正在进行的load访存，等待存储器的响应； 保存已经完成了的load的结果（即从存储器取来的数据），等待CDB传输。

  • store缓冲器的作用有3个： 存放用于计算有效地址的分量； 保存正在进行的store访存的目标地址，该store正在等待存储数据的到达； 保存该store的地址和数据，直到存储部件接收。

• 浮点寄存器FP

  • 共有16个浮点寄存器：F0，F2，F4，…，F30。

  • 它们通过一对总线连接到功能部件，并通过CDB连接到store缓冲器。

• 指令队列

  • 指令部件送来的指令放入指令队列

  • 指令队列中的指令按先进先出的顺序流出

• 运算部件

  • 浮点加法器完成加法和减法操作

  • 浮点乘法器完成乘法和除法操作

在Tomasulo算法中，寄存器换名是通过保留站和流出逻辑来共同完成的。

• 当指令流出时，如果其操作数还没有计算出来，则将该指令中相应的寄存器号换名为将产生这个操作数的保留站的标识。

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

Tomasulo算法具有以下两个特点：

• 冲突检测和指令执行控制是分布的。 每个功能部件的保留站中的信息决定了什么时候指令可以在该功能部件开始执行。

• 计算结果通过CDB直接从产生它的保留站传送到所有需要它的功能部件，而不用经过寄存器。

指令执行的步骤 使用Tomasulo算法的流水线需3段：

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

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

  • 完成对目标寄存器的预约工作 （消除了WAW冲突）

  • 如果没有空闲的保留站，指令就不能流出。 （发生了结构冲突）

• 执行

  • 当两个操作数都就绪后，本保留站就用相应的功能部件开始执行指令规定的操作。

  • load和store指令的执行需要两个步骤： 计算有效地址（要等到基地址寄存器就绪） 把有效地址放入load或store缓冲器

• 写结果

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

每个保留站有以下7个字段：

• Op：要对源操作数进行的操作

• Qj，Qk：将产生源操作数的保留站号

  • 等于0表示操作数已经就绪且在Vj或Vk中，或者不需要操作数。

• Vj，Vk：源操作数的值

  • 对于每一个操作数来说，V或Q字段只有一个有效。

  • 对于load来说，Vk字段用于保存偏移量。

• Busy：为“yes”表示本保留站或缓冲单元“忙”

• A：仅load和store缓冲器有该字段。开始是存放指令中的立即数字段，地址计算后存放有效地址。

• Qi：寄存器状态表

  • 每个寄存器在该表中有对应的一项，用于存放将把结果写入该寄存器的保留站的站号。

  • 为0表示当前没有正在执行的指令要写入该寄存器，也即该寄存器中的内容就绪。

Tomasulo算法具有两个主要的优点：

• 冲突检测逻辑是分布的（通过保留站和CDB实现） 如果有多条指令已经获得了一个操作数，并同时在等待同一运算结果，那么这个结果一产生，就可以通过CDB同时播送给所有这些指令，使它们可以同时执行。

• 消除了WAW冲突和WAR冲突导致的停顿 使用保留站进行寄存器换名，并且在操作数一旦就绪就将之放入保留站。

具体算法

各符号的意义

• 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） // 检测第一操作数是否就绪 {RS[r].Qj←Qi[rs]} //第一操作数没有就绪，进行寄存器换名，即把将产生该操作数的保留站的编号放入当前保留站的Qj。该编号是一个大于0的整数。 else{RS[r].Vj←Regs[rs]; //第一操作数就绪。把寄存器rs中的操作数取到当前保留站的Vj。 RS[r].Qj←0};  //置Qj为0，表示当前保留站的Vj中的操作数就绪 。 if（Qi[rt] ≠ 0） // 检测第二操作数是否就绪  {RS[r].Qk←Qi[rt]} //第二操作数没有就绪，进行寄存器换名，即把将产生该操作数的保留站的编号放入当前保留站的Qk。该编号是一个大于0的整数。 else{RS[r].Vk←Regs[rt]; //第二操作数就绪。把寄存器rt中的操作数取到当前保留站的Vk。 RS[r].Qk←0};  // 置Qk为0，表示当前保留站的Vk中的操作数就绪。 RS[r].Busy←yes; //置当前保留站为“忙” RS[r].Op←Op; //设置操作码 Qi[rd]←r; // 把当前保留站的编号r放入rd所对应的寄存器状态表项，以便rd将来接收结果。

• load和store指令 进入条件：缓冲器有空闲单元（设为r） 操作和状态表内容修改： if （Qi[rs] ≠ 0） // 检测第一操作数是否就绪 {RS[r].Qj←Qi[rs]}  //第一操作数没有就绪，进行寄存器换名，即把将产生该操作数的保留站的编号存入当前缓冲器单元的Qj。 else  {RS[r].Vj←Regs[rs]; // 第一操作数就绪，把寄存器rs中的操作数取到当前缓冲器单元的Vj RS[r].Qj←0}; // 置Qj为0，表示当前缓冲器单元的Vj中的操作数就绪。 RS[r].Busy←yes; // 置当前缓冲器单元为“忙” RS[r].A←Imm; // 把符号位扩展后的偏移量放入当前缓冲器单元的A 对于load指令： Qi[rt]←r; // 把当前缓冲器单元的编号r放入load指令的目标寄存器rt所对应的寄存器状态表项，以便rt将来接收所取的数据。 对于store指令： if（Qi[rt] ≠ 0） // 检测要存储的数据是否就绪  {RS[r].Qk←Qi[rt]}  //该数据尚未就绪，进行寄存器换名，即把将产生该数据的保留站的编号放入当前缓冲器单元的Qk。 else  {RS[r].Vk←Regs[rt]; // 该数据就绪，把它从寄存器rt取到store缓冲器单元的Vk RS[r].Qk←0}; // 置Qk为0，表示当前缓冲器单元的Vk中的数据就绪。

1. 执行

• 浮点操作指令

  • 进入条件：（RS[r].Qj = 0）且（RS[r].Qk= 0）； // 两个源操作数就绪

  • 操作和状态表内容修改：进行计算，产生结果 。

• load/store指令

  • 进入条件：（RS[r].Qj = 0）且r成为load/store 缓冲队列的头部

  • 操作和状态表内容修改： RS[r].A←RS[r].Vj + RS[r].A； //计算有效地址 对于load指令，在完成有效地址计算后，还要进行： 从Mem[RS[r].A]读取数据； //从存储器中读取数据

1. 写结果

• 浮点运算指令和load指令 进入条件：保留站r执行结束，且CDB就绪。 操作和状态表内容修改：  $\forall$x（if（Qi[x] = r） // 对于任何一个正在等该结果的浮点寄存器x {Regs[x]←result; // 向该寄存器写入结果 Qi[x]←0}; // 把该寄存器的状态置为数据就绪  $\forall$x（if（RS[x].Qj = r） // 对于任何一个正在等该结果作为第一操作数的保留站x {RS[x].Vj←result； // 向该保留站的Vj写入结果 RS[x].Qj←0; // 置Qj为0，表示该保留站的Vj中的操作数就绪  $\forall$x（if（RS[x].Qk = r） // 对于任何一个正在等该结果作为第二操作数的保留站x {RS[x].Vk←result; // 向该保留站的Vk写入结果 RS[x].Qk←0}; // 置Qk为0，表示该保留站的Vk中的操作数就绪。 RS[r].Busy←no; // 释放当前保留站，将之置为空闲状态。

• store指令 进入条件：保留站r执行结束，且RS[r].Qk = 0 // 要存储的数据已经就绪 操作和状态表内容修改： Mem[RS[r].A]←RS[r].Vk // 数据写入存储器，地址由store缓冲器单元的A字段给出。 RS[r].Busy←no; //释放当前缓冲器单元，将之置为空闲状态。

《计算机系统结构教程（第2版）》张晨曦 王志英 等 著