流水线的相关与冲突

一段经典的5段流水线

  以一个经典的5段RISC(Reduced Instruction Set Computer,精简指令集计算机)流水线为例。
  一条指令的执行过程分为以下5个周期:
  1. 取指令周期(IF)
  根据PC指示的地址从存储器中取出指令并放入指令寄存器IR;同时PC值加4(假设每条指令占4个字节),指向顺序的下一条指令。
  2. 指令译码/读寄存器周期(ID)
  对指令进行译码,并用IR中的寄存器编号去访问通用寄存器组,读出所需的操作数。
  3. 执行/有效地址计算周期(EX)
  在这个周期,ALU对在上一个周期准备好的操作数进行运算或处理。不同指令所进行的操作不同:
  (1)存储器访问指令:ALU把所指定的寄存器的内容与偏移量相加,形成用于访存的有效地址。
  (2)寄存器-寄存器ALU指令:ALU按照操作码指定的操作对从通用寄存器组中读取的数据进行运算。
  (3)寄存器-立即数ALU指令:ALU按照操作码指定的操作对从通用寄存器组中读取的第一操作数和立即数进行运算。
  (4)分支指令:ALU把偏移量与PC值相加,形成转移目标地址。同时,对在前一个周期读出的操作数进行判断,确定分支是否成功。
  4. 存储器访问/分支完成周期(MEM)
  1)load和store指令
  如果是load指令,就用上一个周期计算出的有效地址从存储器中读取相应的数据;如果是store指令,就把指定的数据写入这个有效地址所指出的存储器单元。
  2)分支指令
  如果在前一个周期判定该分支“成功”,就把转移目标地址送入PC。分支指令完成。
  5. 写回周期(WB)
  ALU运算指令和load指令在这个周期把结果数据写入通用寄存器组。对于ALU运算指令来说,这个结果数据来自ALU,对于load指令,结果数据来自存储器系统。

相关

  相关是指两条指令之间存在某种依赖关系。有三中类型:数据相关(真数据相关),名相关,控制相关。

数据相关(data dependence)

  对于两条指令i和j(有先后关系),如下条件之一成立,则称有数据相关:
  (1)指令j使用指令i产生的结果。
  (2)指令j与指令k数据相关,指令k又与指令i数据相关。
  其中,第二个条件表明,数据相关具有传递性。

名相关(name dependence)

  这里的名是指指令所访问的寄存器或存储器单元的名称。如果两条指令使用相同的名,但是他们之间没有数据流动,则称这两条指令之间存在名相关。名相关有一下两种:
  (1)反相关。如果指令j写的名和指令i读的名相同,则称为反相关。
  (2)输出相关。如果指令i和j写的名相同,称为输出相关。
  名相关可以通过换名技术消除,即把其中一条指令所使用的名换成别的,并不影响另一条指令的正常执行

控制相关(control dependence)

  (此消除不能消除)控制相关是指由分支指令引起的相关。他需要根据分支指令的执行结果来确定后续指令是否执行。一般来说,为了保证程序应有的执行顺序,必须严格按控制相关确定的顺序执行。控制相关的一个简单例子是if语句中的then部分。

流水线冲突

  流水线冲突是指对于具体的流水线来说,由于相关的存在,使得指令流中的下一条指令不能在指定的时钟周期执行。
  流水线冲突有以下3中类型:
  (1)结构冲突:因硬件资源满足不了指令重叠执行的要求而发生的冲突。
  (2)数据冲突:当指令在流水线中重叠执行时,因需求用到指令的执行结果而发生的冲突。
  (3)控制冲突:流水线遇到分支指令和其他会改变PC值的指令所引起的冲突。

结构冲突

  当功能部件不是完全流水或资源不够时,往往发生冲突。
  解决方法是对功能部件进行流水或重复设置资源。

数据冲突

  数据冲突有三种:
  (1)写后读冲突:指令j用到指令i的计算结果,而且在i将结果写入寄存器之前就去读该寄存器,因而得到的是旧值。对应真数据相关。
  (2)写后写冲突:指令j和指令i的结果单元(寄存器或存储器单元)相同,而且j在i写入之前就先该单元进行了写入操作,从而导致了写入顺序错误。对应输出相关。
  前面介绍的5段流水线由于只发生在WB段写寄存器,不会发生写后写冲突。写后写冲突仅发生在这样的流水线中:①流水线中不止一个段可以进行写操作;②当先前某条指令停顿时,允许其后续指令继续前进。
  (3)读后写冲突:指令j的结果单元和指令i的源操作上述单元相同,而且j在i读取该单元之前就先对之进行了写入操作,导致i读取到的值是错误的。对应反相关。
  读后写冲突不会发生在前述5段流水线中,因为这种流水线中的所有读操作(在ID段)都在写结果前发生。此冲突发生在:①有些指令的写结果操作提前了,而且有些指令的读操作滞后了;或②指令被重写排序了。

通过定向技术减少数据冲突引起的冲突

  通过定向技术(旁路或短路技术)解决写后读冲突。
  关键思路是:在某条指令在产生计算结果前,其他指令并不真正立即需要该计算结果,如果能够将该计算结果从其产生的地方直接送到其他指令需要的地方,那么就可以避免停顿。实现方法:
  (1)EX段和MEM段之间的流水寄存器中保存的ALU运算结果总是送到ALU的入口。
  (2)当定向硬件检测到前一个ALU运算结果写入的寄存器就是当前ALU操作的源寄存器时,那么控制逻辑就选择定向的数据作为ALU的输入结果,而不采用从通用寄存器组读出的值。

需要停顿的数据冲突

  在某些不能通过定向技术等方法解决冲突时,需要设置一个“流水线互锁机制”的功能部件。来检测、发现数据冲突,并使得流水线停顿,直至冲突消失。在停顿处加入“气泡”。

依靠编译器解决数据冲突

  为减少冲突,对于无法用定向技术解决的数据冲突,可以通过在编译时让编译器重新组织指令顺序来消除冲突,称为“指令调度”或“流水线调度”。对于各种冲突,都有可能用指令调度来解决。

控制冲突

  控制冲突可能产生比数据冲突更多的性能损失。对于分支指令,有两种结果,一种是分支“成功”,PC改变为分支转移的目标地址。另一种是“不成功”或者“失败”,这是PC值保持正常递增,按原来顺序执行下一条指令。如果分支成功,在条件判定和转移地址计算都完成后,才改变PC值。对于前述5段流水线来说,改变PC值是在MEM段进行的。
  处理分支指令最简单的方法是“冻结”或“排空”流水线。即当出现分支指令时,立即停止以后的指令执行,知道分支指令结果确定。
  由分支指令引起的延迟称为分支延迟。
  为减少分支延迟,可采取以下措施:
  (1)在流水线中尽早判断出分支转移是否成功。
  (2)今草计算出分支目标地址。
  这两种措施缺一不可。只有两者都有时,才能进行转移。
  通过软件(编译器)减少分支延迟的方法主要有三种:预测分支成功,预测分支失败,延迟分支。

预测分支失败

  当分支指令出现时,沿失败的分支继续处理指令,当分支指令结果确定后,在按照结果,如果是分支失败,则辨明预测成功,继续执行;如果是分支成功,流水线就把分支指令之后取出的指令转化为空操作,并按照分支目标地址重新取指令执行。

预测分支成功

  与预测分支失败同理。

延迟分支

  这种方法主要是从逻辑上“延迟”分支指令的执行时间。把延迟分支看成是由原来的分支指令和若干延迟槽构成。在实际机器中,绝大多数情况下只有一个延迟槽。
  延迟分支的效率完全取决于编译器能否把有用的指令调度到延迟槽中。这也是一种指令调度技术。常用的调度方法有3种:从前调度,从目标出调度,从失败处调度。