计算机体系结构 第3章 流水线技术（3）_分支延迟

第3章 流水线技术

3.4 流水线的相关与冲突

3.4.1 一条经典的5段流水线

3.4.1.1 指令周期详解

一条指令的执行过程分为以下5个周期：

• 取指令周期（IF）
  • 以程序计数器PC中的内容作为地址，从存储器中取出指令并放入指令寄存器IR；
  • 同时PC值加4（假设每条指令占4个字节），指向顺序的下一条指令。
• 指令译码/读寄存器周期（ID）
  • 对指令进行译码，并用IR中的寄存器地址去访问通用寄存器组，读出所需的操作数。
• 执行/有效地址计算周期（EX）
  • 不同指令所进行的操作不同：
  • load和store指令：ALU把指令中所指定的寄存器的内容与偏移量相加，形成访存有效地址。
  • 寄存器－寄存器ALU指令：ALU按照操作码指定的操作对从通用寄存器组中读出的数据进行运算。
  • 寄存器－立即数ALU指令：ALU按照操作码指定的操作对从通用寄存器组中读出的操作数和指令中给出的立即数进行运算。
    分支指令：ALU把指令中给出的偏移量与PC值相加，形成转移目标的地址。同时，对在前一个周期读出的操作数进行判断，确定分支是否成功。
• 存储器访问／分支完成周期（MEM）
  • 该周期处理的指令只有load、store和分支指令。
  • 其它类型的指令在此周期不做任何操作。
  • load指令：用上一个周期计算出的有效地址从存储器中读出相应的数据；
  • store指令：把指定的数据写入这个有效地址所指出的存储器单元。
  • 分支指令：分支“成功”，就把转移目标地址送入PC。分支指令执行完成。
• 写回周期（WB）
  • ALU运算指令和load指令在这个周期把结果数据写入通用寄存器组。
  • ALU运算指令：结果数据来自ALU。
  • load指令：结果数据来自存储器。

在这个实现方案中：

• 分支指令需要4个时钟周期（如果把分支指令的执行提前到ID周期，则只需要2个周期）；
• store指令需要4个周期；
• 其它指令需要5个周期才能完成。

将上述实现方案修改为流水线实现：

• 每一个周期作为一个流水段；
• 在各段之间加上锁存器（流水寄存器）。

经典5段流水线

3.4.1.2 采用流水线方式实现时，应解决的问题

• 要保证不会在同一时钟周期要求同一个功能段做两件不同的工作。
  • 例如：不能要求ALU同时做有效地址计算和算术运算。
• 避免IF段的访存（取指令）与MEM段的访存（读/写数据）发生冲突。
  • 可以采用分离的指令存储器和数据存储器；
  • 一般采用分离的指令Cache和数据Cache。
• ID段和WB段都要访问同一寄存器文件。
  • ID段：读、WB段：写
  • 解决对同一寄存器的访问冲突：把写操作安排在时钟周期的前半拍完成，把读操作安排在后半拍完成。
• 对PC的处理
  • 流水线为了能够每个时钟周期启动一条新的指令，就必须在每个时钟周期进行PC值的加4操作（默认一条指令长度为4字节），并保留新的PC值。这种操作必须在IF段完成（需设置一个专门的加法器），以便为取下一条指令做好准备。
  • 但分支指令也可能改变PC的值，而且是在MEM段进行，这会导致冲突。

3.4.1.3 5段流水线的两种描述方式

• 第一种描述（类似于时空图）

• 第二种描述（按时间错开的数据通路序列）

3.4.2 相关与流水线冲突

3.4.2.1 相关

• 相关：两条指令之间存在某种依赖关系。
  • 如果两条指令相关，则它们就有可能不能在流水线中重叠执行或者只能部分重叠执行。
• 相关有3种类型
  • 数据相关（也称真数据相关）
  • 名相关
  • 控制相关

1. 数据相关

• 对于两条指令i（在前，下同）和j（在后，下同），如果下述条件之一成立，则称指令j与指令i数据相关。
  • 指令j使用指令i产生的结果，指令j与指令i数据相关；
  • 指令j与指令k数据相关，而指令k又与指令i数据相关。
• 数据相关具有传递性。
• 数据相关反映了数据的流动关系
• 当数据的流动是经过寄存器时，相关的检测比较直观和容易。
• 当数据的流动是经过存储器时，检测比较复杂。
  • 相同形式的地址其有效地址未必相同；
  • 形式不同的地址其有效地址却可能相同。

例：下面这一段代码存在数据相关。

Loop:  L.D     F0，0（R1）		// F0为数组元素
       ADD.D   F4，F0，F2		 // 加上F2中的值
       S.D     F4，0（R1）		// 保存结果
       DADDIU  R1，R1，－8		// 数组指针递减8个字节
       BNE     R1，R2，Loop	 // 如果R1≠R2，则分支 
1
2
3
4
5

2. 名相关

• 名：指令所访问的寄存器或存储器单元的名称。

• 如果两条指令使用相同的名，但是它们之间并没有数据流动，则称这两条指令存在名相关。

• 指令j与指令i之间的名相关又分为两种（j后进入）：

  • 反相关：如果指令j写的名与指令i读的名相同，则称指令i和j发生了反相关。

    指令j写的名＝指令i读的名
    1

  • 输出相关：如果指令j和指令i写相同的名，则称指令i和j发生了输出相关。

     指令j写的名＝指令i写的名
    1

• 名相关的两条指令之间并没有数据的传送。因此，如果一条指令中的名改变了，并不影响另外一条指令的执行。

换名技术

• 通过改变指令中操作数的名来消除名相关。
• 对于寄存器操作数进行换名称为寄存器换名。
• 既可以用编译器静态实现，也可以用硬件动态完成。

例：DIV.D和ADD.D存在反相关。

DIV.D	F2，F8，F4
ADD.D	F8，F0，F12
SUB.D	F10，F8，F14
1
2
3

进行寄存器换名（F8换成S）后，变成

DIV.D	F2，F8，F4
ADD.D	S，F0，F12
SUB.D	F10，S，F14 
1
2
3

3. 控制相关

• 控制相关是指由分支指令引起的相关它需要根据分支指令的执行结果来确定后面该执行哪个分支上的指令。
  • 为了保证程序应有的执行顺序，必须严格按控制相关确定的顺序执行。
• JMP 跳转可以引起全局相关

示例：典型的“if-then”结构

• if p1 与S1控制相关、if p2 与S2控制相关
• S与p1和p2均无关

if p1 {
	S1;
};
S;
if p2 {
	S2；
};
1
2
3
4
5
6
7

控制相关带来了以下两个限制：

• 与一条分支指令控制相关的指令不能被移到该分支之前。否则这些指令就不受该分支控制了。

  • 对于上述的例子，then 部分中的指令（如S1）不能移到if语句之前。

• 如果一条指令与某分支指令不存在控制相关，就不能把该指令移到该分支之后。

  • 对于上述的例子，不能把S移到if语句的then 部分中。

3.4.2.2 流水线冲突

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

流水线冲突有3种类型：

• 结构冲突：因硬件资源满足不了指令重叠执行的要求而发生的冲突。
• 数据冲突：当指令在流水线中重叠执行时，因需要用到前面指令的执行结果而发生的冲突。
• 控制冲突：流水线遇到分支指令和其它会改变PC值的指令所引起的冲突。

流水线冲突带来的问题：

• 导致错误的执行结果。
• 流水线可能会出现停顿，从而降低流水线的效率和实际的加速比。
• 我们约定：当一条指令被暂停时，在该暂停指令之后流出的所有指令都要被暂停，而在该暂停指令之前流出的指令则继续进行（否则就永远无法消除冲突）。

1. 结构冲突

• 在流水线处理机中，为了能够使各种组合的指令都能顺利地重叠执行，需要对功能部件进行流水或重复设置资源。
• 如果某种指令组合因为资源冲突而不能正常执行，则称该处理机有结构冲突。
• 常见的导致结构冲突的原因：
  • 功能部件不是完全流水
  • 资源份数不够

举例：访存冲突

有些流水线处理机只有一个存储器，将数据和指令放在一起，访存指令会导致访存冲突。

如上图中：由于流水的设置，指令i+3与load指令需要同时访问存储器

• 解决办法Ⅰ：插入暂停周期（“流水线气泡”或“气泡”）

引入暂停后的时空图

• 解决方法Ⅱ： 设置相互独立的指令存储器和数据存储器、或设置相互独立的指令Cache和数据Cache。

有时流水线设计者允许结构冲突的存在

• 主要原因：减少硬件成本
• 如果把流水线中的所有功能单元完全流水化，或者重复设置足够份数，那么所花费的成本将相当高。

2. 数据冲突

当相关的指令靠得足够近时，它们在流水线中的重叠执行或者重新排序会改变指令读/写操作数的顺序，使之不同于它们串行执行时的顺序，则发生了数据冲突。

根据指令读访问和写访问的顺序，可以将数据冲突分为3种类型。

• 考虑两条指令i和j ，且i在j之前进入流水线，可能发生的数据冲突有：
  1. 写后读冲突（RAW）
     • 在 i 写入之前，j 先去读。 j 读出的内容是错误的。
     • 这是最常见的一种数据冲突，它对应于真数据相关。
  2. 写后写冲突（WAW）

     • 在 i 写入之前，j 先写。最后写入的结果是i写入 的。错误！

     • 这种冲突对应于输出相关。

     • 写后写冲突仅发生在这样的流水线中：

       • 流水线中不只一个段可以进行写操作；
       • 指令被重新排序了。

     • 前面介绍的5段流水线不会发生写后写冲突。原因：只在WB段写寄存器

  3. 读后写冲突（WAR）
     • 在 i 读之前，j 先写。i 读出的内容是错误的！
     • 由反相关引起。
     • 发生的情况
       • 有些指令的写结果操作提前了，而且有些指令的读操作滞后了；
       • 指令被重新排序了。

⚠️（这几种冲突的名字实际上是正确执行的顺序，冲突的含义是这一顺序被颠倒了）

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

• 定向技术也称为旁路或短路

关键思想：

• 在计算结果尚未出来之前，后面等待使用该结果的指令并不真正立即需要该计算结果，如果能够将该计算结果从其产生的地方直接送到其它指令需要它的地方，那么就可以避免停顿。

解释如下：

采用定向技术后的流水线数据通路如下图所示：

定向的实现：

• EX段和MEM段之间的流水寄存器中保存的ALU运算结果总是回送到ALU的入口。
• 当定向硬件检测到前一个ALU运算结果写入的寄存器就是当前ALU操作的源寄存器时，那么控制逻辑就选择定向的数据作为ALU的输入，而不采用从通用寄存器组读出的数据。
• 结果数据不仅可以从某一功能部件的输出定向到其自身的输入，而且还可以定向到其它功能部件的输入。

⚠️并不是所有的数据冲突都可以用定向技术来解决

例如：无法将LD指令的结果定向到DADD指令

LD    R1，0（R2）
DADD  R4，R1，R5
AND   R6，R1，R7
XOR   R8，R1，R9
1
2
3
4

解决方法：

• 增加流水线互锁机制，插入“暂停”。
• 作用：检测发现数据冲突，并使流水线停顿，直至冲突消失。

依靠编译器解决数据冲突

• 让编译器重新组织指令顺序来消除冲突，这种技术称为指令调度或流水线调度。

例：为下列表达式生成没有暂停的指令序列:

A＝B＋C;
D＝E－F;
1
2

假设载入延迟为1个时钟周期。

题解：

• 调度前的代码

LD     Rb，B
LD     Rc，C
DADD   Ra，Rb，Rc 	#注意到此处存在冲突
SD     Ra，A
LD     Re，E
LD     Rf，F
DSUB   Rd，Re，Rf
SD     Rd，D
1
2
3
4
5
6
7
8

解释：如图所示，LD指令以及DADD指令存在数据冲突，LD指令在MEM段取出的数据在DADD指令的EX段就需要使用，因此若两条指令相邻只想，则会产生，冲突，若是在这两条指令直接插入一条“指令”，即可解决这一问题，更进一步的是，若由编译器调度一条独立的指令在LD指令以及DADD指令之间，则完全不会影响流水线的运行。

一种调度方式如下所示：

LD     Rb，B
LD     Rc，C
LD     Re，E     
DADD   Ra，Rb，Rc
LD     Rf，F
SD     Ra，A     
DSUB   Rd，Re，Rf
SD     Rd，D
1
2
3
4
5
6
7
8

3. 控制冲突

执行分支指令的结果有两种

• 分支成功：PC值改变为分支转移的目标地址。在条件判定和转移地址计算都完成后，才改变PC值。
• 不成功或者失败：PC的值保持正常递增，指向顺序的下一条指令。

处理分支指令最简单的方法：“冻结”或者“排空”流水线

• 优点：简单

  简单处理分支指令：分支成功的情况

• 把由分支指令引起的延迟称为分支延迟。
• 分支指令在目标代码中出现的频度
  • 每3～4条指令就有一条是分支指令。
    假设：分支指令出现的频度是30％，流水线理想 CPI＝1
    那么：流水线的实际 CPI ＝ 1.9（一条指令延迟了3个时钟周期）
• 可采取两种措施来减少分支延迟。
  • 在流水线中尽早判断出分支转移是否成功；
  • 尽早计算出分支目标地址。
  • 假设：这两步工作被提前到ID段完成，即分支指令是在ID段的末尾执行完成，所带来的分支延迟为一个时钟周期。

3种通过软件（编译器）来减少分支延迟的方法

共同点：

• 对分支的处理方法在程序的执行过程中始终是不变的，是静态的。
• 要么总是预测分支成功，要么总是预测分支失败。

1. 预测分支失败

• 允许分支指令后的指令继续在流水线中流动，就好象什么都没发生似的；
• 若确定分支失败，将分支指令看作是一条普通指令，流水线正常流动；
• 若确定分支成功，流水线就把在分支指令之后取出的所有指令转化为空操作，并按分支目地重新取指令执行。
• 要保证：分支结果出来之前不能改变处理机的状态，以便一旦猜错时，处理机能够回退到原先的状态。

2. 预测分支成功

• 假设分支转移成功，并从分支目标地址处取指令执行。
• 起作用执行的前题：先知道分支目标地址，后知道分支是否成功。
• 前述5段流水线中，这种方法没有任何好处（判断分支是否成功与分支目标地址计算是在同一段流水段完成的）。

3. 延迟分支的方法

• 主要思想：
  • 从逻辑上“延长”分支指令的执行时间。把延迟分支看成是由原来的分支指令和若干个延迟槽构成，不管分支是否成功，都要按顺序执行延迟槽中的指令。
  • 分支延迟槽中的指令“掩盖”了流水线原来必需插入的暂停周期。

分支失败的情况：

分支成功的情况：

分支延迟指令的调度

• 任务：在延迟槽中放入有用的指令
• 由编译器完成。能否带来好处取决于编译器能否把有用的指令调度到延迟槽中。
• 三种调度方法：
  • 从前调度：把位于分支指令之前的一条独立指令移到延迟槽
  • 从目标处调度：把目标处的指令复制到延迟槽，同时修改分支指令的目标地址（预测成功）
  • 从失败处调度

• 分支延迟受到两个方面的限制：
  • 可以被放入延迟槽中的指令要满足一定的条件；
  • 编译器预测分支转移方向的能力。
• 进一步改进：分支取消机制（取消分支）
  • 当分支的实际执行方向和事先所预测的一样时，执行分支延迟槽中的指令，否则就将分支延迟槽中的
    指令转化成一个空操作。

预测分支失败的情况下，分支取消机制的执行情况

预测分支成功的情况下，分支取消机制的执行情况：