指令级并行概念

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

开发ILP的方法主要分为基于硬件的动态开发方法和基于软件的静态开发方法。

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

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

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

  • 开发循环的不同迭代之间存在的并行性(最常见、最基本)
  • 是指令级并行研究的重点之一

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

  • 循环展开技术
  • 采用向量指令和向量数据表示

相关与指令级并行

相关有三种类型:数据相关,名相关,控制相关。

流水线冲突:对于具体的流水线,由于相关的存在,使得指令流中的下一条指令不能在指定的时钟周期执行

  • 结构冲突:多个指令的执行向同一硬件资源提出请求(硬件资源无法满足程序并行运行)
  • 数据冲突:由数据相关产生的冲突,后一条指令需要使用前一条指令执行结果而产生的冲突
    • 写后读冲突RAW:真数据相关,下一条指令依赖于上一条指令的执行结果
    • 写后写冲突WAW:名相关的输出相关,两条指令写同一个名
    • 读后写冲突WAR:名相关的反相关,后条指令写的名与前条指令读的名相同

可从两方面解决相关问题:

  • 保持相关,但避免发生冲突
    • 指令调度
  • 通过代码变换,消除相关

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

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

  • 保持异常行为:无论怎么改变指令的执行顺序都不能改变程序中的异常发生情况
  • 数据流:数据值从其产生着指令到其消费者指令的实际流动

分支指令使得数据流具有动态性。

有时,不遵守控制相关既不影响异常行为也不改变数据流,可以大胆地进行指令调度,把失败分支的指令调度到分支指令之前。

指令动态调度

静态调度

  • 依靠编译器对代码进行静态调度以减少相关和冲突
  • 通过把相关的指令拉开距离来减少可能的停顿

动态调度

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

优点:

  • 能够处理一些在编译时情况不明的相关(涉及存储器访问的相关),并简化了编译器
  • 能够使本来是面向某一流水线优化编译的代码在其他的流水线上也能高效运行

缺点:

  • 以硬件的复杂性显著提升为代价

动态调度基本思想

流水线的最大局限性:指令是按序流出和按序执行的

按序发射按序执行
DIV.D F4,F0,F2 IF ID EX MEM WB
ADD.D F10,F4,F6 STALL STALL STALL IF ID EX MEM WB
SUB.D F12,F6,F14 IF ID EX MEM WB
无序发射无序执行
DIV.D F4,F0,F2 IF ID EX MEM WB
ADD.D F10,F4,F6 STALL STALL STALL IF ID EX MEM WB
SUB.D F12,F6,F14 IF ID EX MEM WB

在流水线的ID模块,需要检测结构冲突和数据冲突。

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

乱序执行:

  • 指令的执行顺序与程序顺序不同
  • 指令的完成也是乱序完成的

为了支持乱序执行,译码阶段再分为两个阶段

  • 流出(IS):指令译码,检查是否存在结构冲突
  • 读操作数(RO):等待数据冲突消失然后读操作数

正常五级流水不会发生WAR和WAW冲突,但乱序执行使得它们可能发生

例如:

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

1,2存在输出相关,2,3存在反相关

可以通过寄存器重命名来消除相关

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

指令乱序完成带来的最大问题就是异常处理(中断)比较复杂

  • 动态调度的处理机要保持正确的异常行为
  • 即使保持了正确的异常行为,动态调度处理机仍可能发生不精确异常
  • 不精确异常:当指令i导致发生异常时,处理机的现场与严格按程序执行时指令i的现场不同
    • 原因1:发生异常时流水线可能已经执行完按程序顺序是位于指令i之后的指令
    • 原因2:流水线可能还没完成按程序顺序是指令i之前的指令
  • 精确异常:当指令i导致发生异常时,处理机的现场与严格按照程序执行时指令i的现场相同
    • 需要设置一定数量的后院寄存器,把流水线中所有指令的执行结果和现场保存下来。成本较高

记分牌动态调度算法

基本思想

  • 目标:在没有结构冲突时,尽可能早地执行没有数据冲突的指令,实现每个时钟周期执行一条指令
  • 要发挥指令乱序执行的好处,必须有多条指令同时处于执行阶段
  • 指令执行过程分为四段
    • 流出:如果当前流出指令所需的功能部件空闲,并且所有其他正在执行的指令的目的寄存器与该指令的不同,记分牌就向功能部件流出该指令,并修改记分牌内部的记录表。解决了WAW冲突。
    • 读操作数:记分牌监测源操作数的可用性,如果数据可用,它就通知功能部件从寄存器中读出源操作数并开始执行。动态地解决了RAW冲突,并导致指令可能乱序开始执行。
    • 执行:取到操作数后,功能部件开始执行。当产生出结果后,就通知记分牌它已经完成执行。在浮点流水线中,这一段可能要占用多个时钟周期。
    • 写结果:记分牌一旦知道执行部件完成了执行,就检测是否存在WAR冲突。
      • 如果不存在,或者原有的WAR冲突已消失,记分牌就通知功能部件把结果写入目的寄存器,并释放该指令使用的所有资源。
      • 若检测到WAR冲突,就不能写结果,这时前面某条指令(按顺序流出)还没有读操作数,某个源操作数寄存器与本指令的目的寄存器相同,这种情况下记分牌必须等待,直到冲突消失。

记分牌中的信息

  • 指令状态表:记录正在执行的各条指令进入到了哪一段
  • 功能部件状态表:记录各个功能部件的状态。每个功能部件有一项,包含九个字段
    • Busy:忙标志,初始为no
    • Op:该功能部件正在执行或将要执行的操作
    • Fi:目的寄存器编号
    • Fj,Fk:源寄存器编号
    • Qj,Qk:指出向源寄存器Fj,Fk写数据的功能部件
    • Rj,Rk:标志位,yes表示Fj,Fk中的操作数就绪且未被取走。否则置no
  • 结果寄存器状态表Result:每个寄存器在该表中有一项,指出哪个功能部件把结果写入该寄存器
    • 若正在运行的指令都不以它为目的寄存器,其相应项置no
    • 初值全为no

例子:

起始记分牌信息:

其中.D表示双精度浮点数,.S表示单精度浮点数。

  • L.D: 从存储器中读取双精度浮点数到寄存器中
  • S.D:把双精度数据从存储器存储到存储器中
  • ADD.D:一个双精度浮点数加上一个单精度浮点数,结果是双精度浮点数
  • SUB.D:一个双精度浮点数减去一个单精度浮点数,结果为双精度浮点数
  • MULT.D:一个双精度浮点数乘以一个单精度浮点数,结果为双精度浮点数
  • DIV.D:一个双精度浮点数除以一个单精度浮点数,结果为双精度浮点数

假设加法需要2时钟周期,乘法需要4时钟周期,除法需要40时钟周期

指令级并行1.png

写后读相关:

  • L.D指令到MULT.D和SUB.D之间,L.D先写F2,MULT.D和SUB.D后读F2
  • MULT.D到DIV.D之间,MULT.D先写F0,DIV.D后读F0
  • SUB.D到ADD.D之间,SUB.D先写F8,ADD.D后读F8

读后写相关:

  • DIV.D和ADD.D之间,DIV.D先读F6,ADD.D后写F6
  • SUB.D和ADD.D之间,SUB.D先读F6,ADD.D后写F6

结构相关:

  • ADD.D和SUB.D指令关于浮点加法部件

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

指令级并行2.png

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

指令级并行3.png

算法

约定:

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

(1)指令流出

  • 进入条件:
    • not Busy[FU] & not Result[D]:功能部件空闲且没有写后写冲突
  • 记分牌内容修改:
    • 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]:记录第一个源操作数是否可用,若没有部件要写S1,则可用
    • Rk[FU]←not Qk[FU]:记录产生第二个源操作数是否可用
    • Result[D]←FU:功能部件FU把结果写入D

(2)读操作数

  • 进入条件:
    • Rj[FU] & Rk[FU]:两个源操作数都可用
  • 记分牌内容修改:
    • Rj[FU]←no:第一个源操作数已读取
    • Rk[FU]←no:第二个源操作数已读取
    • Qj[FU]←0:第一个操作数不再使用部件FU
    • Qk[FU]←0:第二个操作数不再使用部件FU

(3)执行

  • 结束条件:
    • 功能部件操作结束

(4)写结果

  • 进入条件:
    • 对任意在忙的部件f应当有((Fj[f] != Fi[FU] or Rj[f] == no) & (Fk[f] != Fi[FU] or Rk[f] == no)):对任意在忙的部件f(对应一条指令),它的源操作数寄存器Fj[f]不是当前指令要写入的目的寄存器或者它的源操作数暂时不可用,即不存在读后写冲突。
  • 记分牌内容修改:
    • 对任意在忙的部件f有if Qj[f] == FU then Rj[f]←yes:对任意在忙的部件f(对应一条指令),若它的第一源操作数需要使用当前指令的运算结果,则将其Rj[f]置yes表示第一源操作数可用
    • 对任意在忙的部件f有if Qk[f] == FU then Rk[f]←yes:对任意在忙的部件f(对应一条指令),若它的第二源操作数需要使用当前指令的运算结果,则将其Rk[f]置yes表示第二源操作数可用
    • Result(Fi[FU])←0:释放当前指令目的寄存器
    • Busy[FU]←no:释放当前指令的功能部件

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

  • 程序代码中可开发的并行性,及是否存在可以并行执行的不相关的指令
  • 记分牌的容量,记分牌的容量决定了流水线能在多大范围内寻找不相关指令。流水线中可以同时容纳的指令数量称为指令窗口
  • 功能部件的种类和数目,功能部件的总数决定了结构冲突的严重程度
  • 反相关和输出相关,它们引起记分牌中的WAR和WAW冲突

Tomasulo算法

基本思想

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

寄存器换名可以消除WAR和WAW冲突,例:

  1. DIV.D F0,F2,F4
  2. ADD.D F6,F0,F8
  3. S.D F6,0(R1)
  4. SUB.D F8,F10,F14
  5. MUL.D F6,F10,F8

其中2和5之间存在反相关可能导致WAR冲突,2和5之间存在输出相关可能导致WAR冲突,通过寄存器换名:

  1. DIV.D F0,F2,F4
  2. ADD.D S,F0,F8
  3. S.D S,0(R1)
  4. SUB.D T,F10,F14
  5. MUL.D F6,F10,T

消除了名相关

指令级并行4.png

硬件说明

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

指令级并行5.png

  • 保留站:每个保留站存储一条已经流出并等待到本功能部件执行的指令(相关信息),包括操作码,操作数以及用于检测和解决冲突的信息
    • 在一条指令流出到保留站的时候,如果该指令的源操作数已经在寄存器中就绪,则将之取到该保留站中
    • 如果操作数还没有计算出来,则在该保留站中记录将产生这个操作数的保留站的标识
    • 每个保留站具有唯一的标识字段,例如浮点加法器有三个保留站ADD1,ADD2,ADD3
  • 公共数据总线CDB(一条重要的数据通路)
    • 所有功能部件的计算结果都是送到CDB上,由它把这些结果直接送到(播送到)各个需要该结果的地方
    • 在具有多个执行部件且采用多流出(即每个时钟周期流出多条指令)的流水线中,需要采用多条CDB
  • load缓冲器和store缓冲器
    • 存放读/写存储器的数据或地址
    • load缓冲器作用
      • 存放用于计算有效地址的分量
      • 记录正在进行的load访存,等待存储器的响应
      • 保存已经完成了的load的结果(即从存储器取来的数据),等待CDB传输
    • store缓冲器作用
      • 存放用于计算有效地址的分量
      • 保存正在进行的store访存的目标地址,该store正在等待存储数据的到达
      • 保存该store的地址和数据,直到存储部件接收
  • 浮点寄存器FP
    • 共16个浮点寄存器:F0,F2,F4……F30
    • 它们通过一对总线连接到功能部件,并通过CDB连接到store缓冲器
  • 指令队列
    • 指令部件送来的指令放入指令队列
    • 指令队列中的指令按先进先出的顺序流出
  • 运算部件
    • 浮点加法器完成加法和减法操作
    • 浮点乘法器完成乘法和除法操作

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

  • 当指令流出时,如果其操作数还没有计算出来,则将该指令中相应的寄存器号换名为将产生这个操作数的保留站的标识
  • 指令流出到保留站后,其操作数寄存器号或者换成了数据本身(如果该数据已经就绪),或者换成了保留站的标识,不再与寄存器有关系

一个简单的流程:

Tomasulo算法有以下两个特点:

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

指令执行步骤:

  • 流出:从指令队列的头部取一条指令
    • 如果该指令的操作所要求的保留站有空闲的,就把该指令送到该保留站(设为r)
      • 如果其操作数在寄存器中已经就绪,就将这些操作数送入保留站r
      • 如果其操作数还没有就绪,就把将产生该操作数的保留站的标识送入保留站r
      • 一旦被记录的保留站完成计算,它将直接把数据送给保留站r
      • (寄存器换名和对操作数进行缓冲,消除WAR冲突)
    • 完成对目标寄存器的预约工作(消除了WAW冲突)
    • 如果没有空闲的保留站,指令就不能流出(发生了结构冲突)
  • 执行
    • 当两个操作数都就绪后,本保留站就用相应的功能部件开始执行指令规定的操作
    • load和store指令的执行需要两个步骤
      • 计算有效地址(要等到基地址寄存器就绪)
      • 把有效地址放入load或store缓冲器
  • 写结果
    • 功能部件计算完毕后,就将计算结果放到CDB上,所有等待该计算结果的寄存器和保留站(包括store缓冲器)都同时从CDB上获得所需要的数据

每个保留站有以下七个字段:

  • Op:对源操作数进行的操作
  • Qj,Qk:将产生源操作数的保留站号
    • 等于0表示操作数已经就绪且在Vj或Vk中,或者不需要操作数
  • Vj,Vk:源操作数的值
    • 对于每一个操作数来说,V或Q字段只有一个有效
    • 对于load来说,Vk字段用于保存偏移量
  • Busy:为yes表示本保留站或缓冲单元“忙”
  • A:仅load和store缓冲器有该字段。开始是存放指令中的立即数字段,地址计算后存放有效地址
  • Qi:寄存器状态表
    • 每个寄存器在该表中有对应的一项,用于存放将把结果写入该寄存器的保留站的站号
    • 为0表示当前没有正在执行的指令要写入该寄存器,也即该寄存器中的内容就绪

Tomasulo算法的两个主要优点:

  • 冲突检测逻辑是分布的(通过保留站和CDB实现)
    • 如果有多条指令已经获得了一个操作数,并同时在等待同一运算结果,那么这个结果一产生,就可以通过CDB同时播送给所有这些指令,使它们可以同时执行
  • 消除了WAW冲突和WAR冲突导致的停顿
    • 使用保留站进行寄存器换名,并且在操作数一旦就绪就将之放入保留站

例子:

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

当第一条指令执行完并写入结果时,Tomasulo算法所用的各信息表的内容:

指令级并行6.png

假设上例各操作延迟为:

  • load:1时钟周期
  • 加法:2时钟周期
  • 乘法:10时钟周期
  • 除法:40时钟周期

则MUL.D指令准备写结果时各状态表的内容为:

指令级并行7.png

具体算法

符号意义:

  • 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)指令流出

  • 浮点运算指令(MUL.D F4,F0,F2:[rd:F4],[rs:F0],[rt:F2])

    • 进入条件:有空闲保留站,设为r

    • 操作和状态表内容修改:

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      //检测第一个操作数是否就绪
      if (Qi[rs] != 0){
      //没有就绪,进行寄存器换名,即把将产生该操作数的保留站的编号存入当前缓冲器单元的Qj
      RS[r].Qj = Qi[rs];
      }else{
      //第一操作数就绪,把寄存器rs中的操作数取到当前缓冲器单元的Vj
      RS[r].Vj = Regs[rs];
      //置Qj为0,表示当前缓冲器单元的Vj中的操作数就绪
      RS[r].Qj = 0;
      }
      //检测第二个操作数是否就绪,同第一
      if (Qi[rt] != 0){
      RS[r].Qk = Qi[rt];
      }else{
      RS[r].Vk = Regs[rt];
      RS[r].Qk = 0;
      }
      //设置当前保留站为忙
      RS[r].Busy = yes;
      //设置操作码
      RS[r].Op = Op;
      //把当前保留站的编号r放入rd所对应的寄存器状态表项,以便rd将来接收结果
      Qi[rd] = r;
  • load和store指令(L.D F2,45(R3):[rt:F2],[imm:45],[rs:R3])

    • 进入条件:缓冲器有空闲单元,设为r

    • 操作和状态表内容修改:

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      //检测第一个操作数是否就绪
      if (Qi[rs] != 0){
      //没有就绪,进行寄存器换名,即把将产生该操作数的保留站的编号存入当前缓冲器单元的Qj
      RS[r].Qj = Qi[rs];
      }else{
      //第一操作数就绪,把寄存器rs中的操作数取到当前缓冲器单元的Vj
      RS[r].Vj = Regs[rs];
      //置Qj为0,表示当前缓冲器单元的Vj中的操作数就绪
      RS[r].Qj = 0;
      }
      //设置当前保留站为忙
      RS[r].Busy = yes;
      //把符号位扩展后的偏移量放入当前缓冲器单元的A
      RS[r].A = imm;

      对于load指令:

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

      对于store指令:

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

(2)执行

  • 浮点操作指令

    • 进入条件: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]

(3)写结果

  • 浮点运算和load指令

    • 进入条件:保留站r执行结束且CDB就绪

    • 操作和状态表内容修改:

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      对任意正在等该结果的浮点寄存器x
      if(Qi[x] == r){
      //向该寄存器写入结果
      Regs[x] = result;
      //把该寄存器的状态置为数据就绪
      Qi[x] = 0;
      }
      对任意正在等该结果作为第一操作数的保留站x
      if(RS[x].Qj == r){
      //向该保留站的Vj写入结果
      RS[x].Vj = result;
      //置Qj为0,表示该保留站的Vj中的操作数就绪
      RS[x].Qj = 0;
      }
      对任意正在等该结果作为第二操作数的保留站x
      if(RS[x].Qk == r){
      //向该保留站的Vj写入结果
      RS[x].Vk = result;
      //置Qj为0,表示该保留站的Vj中的操作数就绪
      RS[x].Qk = 0;
      }
      //释放当前保留站,将之置为空闲状态
      RS[r].Busy = 0;
  • store指令

    • 进入条件:保留站r执行结束且RS[r].Qk == 0 //要存储的数据已经就绪

    • 操作和状态表内容修改:

      1
      2
      3
      4
      //数据写入存储器,地址由store缓冲器单元的A字段给出
      Mem[RS[r].A] = RS[r].Vk;
      //释放当前缓冲器单元,将之置为空闲状态
      RS[r].Busy = no;

说明:

  • 当浮点运算指令流出到一个保留站r时,把该指令的目的寄存器rd的状态表项设置为r,方便将来接收运算结果
  • load和store指令的处理与浮点运算指令不同。只要load缓冲器有空闲单元,就可以流出。STORE指令在写结果段执行