指令级并行的概念

提高处理速度的两种途径:

  • 提高主频
  • 并行工作

并行可以在下面几个粒度进行

  • 指令级别
  • 线程级别
  • 处理器之间
  • 独立计算机之间

指令级粒度是最小的.

指令级并行英文缩写为ILP(Instruction-Level Parallelism)

在本章中,主要采用流水线以及相关优化技术,使得指令能够重叠并行执行.

  • 指令流水线技术
  • 每条指令的执行也可以分为多个环节
    • 取指
    • 译码
    • 执行
    • 写回

流水线处理机的实际CPI,理想情况下,有几级流水线,CPI就会降低几倍.

而实际情况下理想流水线的CPI加上各类停顿的时钟周期数,主要是以下三种停顿

  • 结构冲突
  • 数据冲突
  • 控制冲突

相关

  • 两条指令之间存在某种依赖关系
  • 两条指令相关,就不能在流水线中重叠执行或只能部分重叠执行
  • 分类
    • 数据相关
    • 名相关
    • 控制相关

数据相关

  • 两条指令存在生产-消费关系
  • 在前一条指令完成了执行环节,但结果还没写回寄存器之前,下一条指令就不能跟着上一条指令进入执行环节,否则就会读出一个错误的数据.

名相关

  • 反相关: 与数据相关相反,即先消费再生产,不会造成停顿
  • 输出相关

控制相关

  • 当某个变量不为零时继续执行后续的指令,为零时要跳转
  • 这个条件分支指令还没执行完时,后续的几条指令也会跟着进入流水线
  • 当这条指令执行完,若要跳转到新的地址去执行,这样指令流水线的效率也会降低

相关是程序的固有属性,反映了程序中指令之间的依赖关系

相关是引起冲突的主要原因,但并非唯一原因,例如结构冲突并没有对应的相关.

消除相关是减少冲突的一种有效方法.

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

流水线冲突

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

相关的两类解决方案

  • 保持相关,但避免发生冲突(指令调度)
  • 通过代码变换,消除相关(寄存器重命名技术)

开发ILP的方法

  • 基于硬件的动态开发方法
  • 基于软件的静态开发方法
  • 必要时,还能采用软硬件结合的方式,最大程度地挖掘程序中存在的指令级并行

指令的动态调度

静态调度

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

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

动态调度的优点:

  1. 能够处理一些在编译时情况不明的相关,并简化编译器
  2. 能够使面向某一类流水线优化编译的代码在其他的流水线上也能高效的执行

经典(顺序)流水线的局限性:由于指令是按序流出和按序执行的,考虑下面这段代码

DIV F4,F0,F2
ADD F10,F4,F6
SUB F12,F6,F14

ADD指令与DIV指令关于F4相关,导致流水线停顿
SUB指令与流水线的任何指令都没有关系,也因此受阻

SUB指令需要等待的原因:在ID段检测结构冲突和数据冲突,一旦一条指令受阻,其后的指令也都将停顿
解决方法:允许乱序执行

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

  • 流出:Issue,IS.此阶段执行指令译码,检查是否存在结构冲突
  • 读操作数: Read Operands,RO.此阶段等待数据冲突消失,然后读操作数
  • 引入指令缓冲区,直到冲突消除
  • 部署更多执行部件,使多条指令能同时执行或访存

乱序执行引起的新问题:可能会发生WAR冲突和WAW冲突

例如考虑下面的代码

DIV F10,F0,F2
ADD F10,F4,F6
SUB F6,F8,F14

上面DIV和ADD存在输出相关,ADD和SUB指令存在反相关.打乱后就会导致冲突

这两类冲突,可以使用寄存器重命名技术来消除

但由于寄存器数目有限,所以这不是一个通用的解决方案

寄存器分配算法实际上是一个NP Hard问题

乱序执行导致多条指令同时处于执行或访存当中

乱序执行引入的最大问题在于异常处理比较复杂,异常可以分为

  • 精确异常: 如果发生异常时,处理机的现场跟严格按照程序顺序执行时指令i的现场相同
  • 不精确异常: 当执行指令i发生异常时,处理机的现场(状态)与严格按程序顺序执行时指令i的现场不同

发生不精确异常的原因由两个:

  1. 流水线可能执行完按程序顺序时位于指令i之后的指令
  2. 流水线可能还没完成按程序顺序是指令i之前的指令

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

因此这里动态调度的处理机要保持正确的异常行为,对于一条会产生异常的指令来说,只有当处理机确切的直到该指令将被执行时,才允许它产生异常.

例如,指令i,j顺序流入流水线,j位于条件语句中,选择执行,会引起异常,但不会被执行.j被调度到i之前执行,执行过程中发生了异常,实际不会被执行,也不会引起异常.这里,j语句就不被允许产生异常

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

例如,指令i,j顺序流入流水线,指令i会导致异常,但被调度到指令j之后执行,假设j执行完后改变了上下文,那么i产生异常时,上下文与顺序执行的上下文已经是不同的了

动态分支预测技术

分支指令如果不作处理,在跳转时会带来流水线中指令的浪费和丢弃,造成流水线停顿

如果我们做分支指令做预测,就可以防止或减少分支时产生的副作用

我们所开发的ILP越多,控制相关的制约就越大,分支预测就要有更高的准确度

这里介绍的方法着重解决对于每个时钟周期流出多条指令(若为n条指令就称为n流出)的处理机来说非常重要,原因如下

  • 在n-流出的处理机中,遇到分支指令的可能性增加了n倍
  • 要给处理器连续提供指令,就需要准确预测分支

动态分支预测

  • 在程序运行时,根据分支指令过去的表现来预测其将来的行为
  • 如果分支行为发生了变化,预测结果也跟着改变
  • 相比静态预测,动态预测有着更好的预测准确度和适应性

分支预测的有效性取决于

  • 预测的准确性
  • 预测正确和不正确两种情况下的分支开销

决定分支开销的因素

  • 流水线的结构
  • 预测的方法
  • 预测错误时的恢复策略等

采用动态分支预测技术的目标有

  • 尽快预测分支是否成功
  • 尽快找到分支目标地址(或指令)

需要解决的关键问题有

  • 如何记录分支的历史信息,要记录哪些信息
  • 如何根据这些信息来预测分支的去向,甚至提前取出分支目标处的指令

在预测错误时,要作废已经预取和分析的指令,恢复现场,并从另一条分支路径重新取指令

分支历史表

最简单的动态预测方法:分支历史表BHT

用BHT来记录最近一次或几次的执行情况(成功还是失败),并据此进行预测

最简单的BHT:记录分支指令最近一次的历史,BHT中只需1位二进制
规则为:上次分支成功就认为下次分支成功,否则就失败

多位预测位的BHT:以2个预测位的做例子
规则为根据统计规律来进行预测
研究结果表明两位分支预测性能与n位分支预测的性能差不多

以两位BHT为例,阐述其操作步骤

  • 分支预测:当分支只能到达译码段时,根据从BHT读出的信息进行分支预测
    • 若预测正确,继续处理后续指令,流水线没有断流
    • 若预测失败,作废预取和分析的指令,恢复现场,并从另一条分支路径重新取指令
  • 状态修改:根据状态变迁图修改状态

BHT技术什么时候能够带来效益呢?

  • 判断分支是否成功所需的时间大于确定分支目标地址所需的时间?
    • 在前述5段经典流水线中,由于判定分支是否成功和计算目标地址都是在ID段完成,所以BHT不会给该流水线带来好处

研究结果表明

  • 对于SPEC89测试程序来说,具有4KB的BHT预测准确率为82%到99%
  • 一般来说,采用4KB的BHT就可以了

BHT的实现

  • BHT可以跟分支指令一起存放在指令Cache中
  • 也可以用一块专门的硬件来实现

分支目标缓冲器

分支目标缓冲器BTB的具体目标为将分支的开销降为0

分支目标缓冲器BTB的具体方法为将分支成功的分支指令的地址和它的分支目标地址都放在一个缓冲区种保存起来,缓冲区以分支指令的地址作为标识

表格至少有两个字段

  • 执行过的成功分支指令的地址
  • 预测的分支目标地址
指令在BTB中? 预测 实际情况 延迟周期
是 成功 成功 0
是 成功 不成功 2
不是 成功 2
不是 不成功 0

改进BTB的方法:在分支目标缓冲器中增设一个至少是两位的分支历史表字段以改善预测准确率

更进一步,在表中对每条分支指令都存放若干条分支目标处的指令,就形成了分支目标指令缓冲器(保护Icache?)

补充

课后作业

5.8 假设有一条长流水线,仅仅对条件转移指令使用分支目标缓冲。假设分支预测错误的开
销为4个时钟周期,缓冲不命中的开销为3个时钟周期.假设：命中率为90%,预测精度为90%,分支频率为15%,没有分支的基本CPI为1。
(1) 求程序执行的CPI
(2) 相对于采用固定的2个时钟周期延迟的分支处理,哪种方法程序执行速度更快？

解:
(1) 分支延迟 = 分支预测错误的延迟 + 缓冲不命中的延迟 = $4 \times 0.1 \times 0.9 + 3 \times 0.1 = 0.66$
$程序执行的CPI = CPI_{基本}+分支延迟$ = $1+15% \times 0.66 = 1.099$
(2) 采用固定的两个时钟周期延迟的分支处理,程序执行CPI = $1 + 15% \times 2 = 1.3$
因此显然采用分支目标缓冲器技术速度更快

5.9 假设分支目标缓冲的命中率为90%,程序中无条件转移指令的比例为5%,没有无条件转移指令的程序CPI值为1。假设分支目标缓冲中包含分支目标指令,允许无条件转移指令进入分支目标缓冲,则程序的CPI值为多少？假设无条件分支指令不进入分支目标缓冲时程序执行的CPI为1.1

解:
无条件分支指令不进入分支目标缓冲时有
$$
CPI = 1 + 0.05 \times 无条件分支延迟 = 1.1
$$
因此无条件分支延迟为2

无条件分支指令进入分支目标缓冲时有
$$
无条件分支指令造成的分支延迟 = 0.1 \times 2 = 0.2
$$
因此程序的CPI = $1 + 0.2 \times 0.05= 1.01$

5.11 设指令流水线由取指令、分析指令和执行指令3个部件构成,每个部件经过的时间为△t,连续流入12条指令。分别画出标量流水处理机以及ILP均为4的超标量处理机、超长指令字处理机、超流水处理机的时空图,并分别计算它们相对于标量流水处理机的加速比.

解:

标量流水处理机的时空图如下图所示,其用时为14△t

超标量处理机的时空图如下图所示,其用时为5△t,

超长指令字处理机的时空图如下图所示,其用时为5△t

超流水处理机的时空图如下图所示,其用时为5.75△t

它们相对标量流水处理机的加速比依次为
$$
S_{2} = \frac{14}{5} = 2.8
$$
$$
S_{3} = \frac{14}{5} = 2.8
$$
$$
S_{2} = \frac{14}{5.75} = 2.435
$$

赏

我很好奇