rhb_blog

rao的博客

0%

计算机系统结构-指令级并行

发表于 更新于 分类于 ，

指令级并行的概念

提高处理速度：

  • 提高主频【高到一定程序，发热能耗都会升高】
  • 并行工作：多个部件同时工作

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

需要解决的具体问题

相关和流水线冲突：

相关是程序固有的一种属性，它反映了程序中指令之间的相互依赖关系。相关是引起冲突的主要原因（并非唯一？结构冲突无对应相关）。因此消除相关是减少冲突停顿的一种有效方法。

相关是引发冲突的主要原因，其中数据相关与名相关可能导致数据冲突，而控制相关可能导致控制冲突。

相关的两类解决方案

  • 保持相关，但避免发生冲突

    • 指令调度

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

    • 寄存器重命名

指令调度分类

  • 静态调度

    • 依靠编译器对代码进行静态调度，以减少相关和冲突。
    • 它不是在程序执行的过程中、而是在编译期间进行代码调度和优化。
    • 通过把相关的指令拉开距离来减少可能产生的停顿。

  • 动态调度

    • 在程序的执行过程中，依靠专门硬件对代码进行调度，减少数据相关导致的停顿。
    • 优点：
      • 能够处理一些在编译时情况不明的相关（比如涉及到存储器访问的相关），并简化了编译器；
      • 能够使本来是面向某一流水线优化编译的代码在其它的流水线（动态调度）上也能高效地执行。
      • 以硬件复杂性的显著增加为代价

经典（顺序）流水线的局限性

由于指令是按序流出和按序执行的。

例如：

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

假设DIV（除法）指令执行时间（EX）是10个时钟周期，ADD（加法）与SUB（减法）分别为1个，（由于除法与加法之间的数据相关）那么ADD必须等待9个时钟周期才能进入EX阶段。在我们学过的顺序流水线中，由于ID部件被ADD指令占据，SUB指令只有在ADD指令流入EX（执行）阶段后才能进入ID阶段，即其也需要等待9个时钟周期。然而，如果这些指令不用按顺序执行，则SUB（减法）无需等待。

SUB指令需要等待的原因：在ID阶段会检测结构冲突与数据冲突，当发现冲突后，导致冲突的指令中较晚进入流水线的那条（ADD指令），将冻结在流水寄存器中，不在向前流动。由于流水寄存器只能存放一条指令，一旦这条指令受阻，其后的指令（SUB指令）都将停顿。

解决方法：允许指令乱序执行

指令乱序执行

将ID段分为两个阶段：流出（IS）和读操作数(RO)。IS阶段执行指令译码，检查是否存在结构冲突；RO阶段等待数据冲突消失，再进行读操作数的操作。

两个方法：

  • 引入指令缓冲区：不能流出的指令就在缓冲区里排队等待，直到冲突消除
  • 部署更多的执行部件（这里的执行部件是广义的执行，包括：运算器、访存设备等），使得多条指令能都同时执行或访存

乱序执行的问题

WAR冲突和WAW冲突

乱序执行可能会导致WAR冲突和WAW冲突。

可以使用寄存器重命名来消除冲突。值得注意的是，寄存器的数量是有限的，更多的寄存器会导致编译器变慢。

多条指令同时处于执行或访存中

乱序执行将使得多条指令处于执行当中，因此要求，具有多个功能部件、或者功能部件流水化、或者兼而有之。

复杂的异常处理

乱序指令引入的最大问题在于，异常处理比较复杂。异常可以分为精确异常与不精确异常。

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

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

    • 发生不精确异常的原因：因为当发生异常（设为指令i）时

      • 流水线可能已经执行完按程序顺序是位于指令i之后的指令；
      • 流水线可能还没完成按程序顺序是指令i之前的指令。

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

显然，动态调度的处理机要保持正确的异常行为。具体而言，对于一条会产生异常的指令来说，只有当处理机确切地知道该指令将被执行时，才允许它产生异常。举个例子，指令i，j顺序流入流水线。j位于条件语句中（选择执行），会引起异常但不会被执行。j被调度到i之前执行，执行过程中发生了异常（实际不会被执行，所以也不会引起异常）。这样是不允许的。

然而，即使保持了正确的异常行为，动态调度处理机仍可能发生不精确异常。 举个例子：指令i，j顺序流入流水线，指令i会导致异常，但其被调度到j之后执行，假设j执行完后直接改变了上下文，那么i产生异常时，上下文与顺序执行的上下文已经不同了。

动态分支预测

ILP（指令级并行）越多，控制相关的制约就越大，分支预测就要有更高的准确度。解决方法就是：动态分支预测。

动态分支预测

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

分支预测的有效性取决于

  • 预测的准确性
  • 预测正确和不正确两种情况下的分支开销
  • 决定分支开销的因素：
    • 流水线的结构
    • 预测的方法
    • 预测错误时的恢复策略等

目标与关键问题

  • 采用动态分支预测技术的目标【只有尽快做到下面两点，才能避免控制相关造成流水线停顿】

    • 预测分支是否成功
    • 尽快找到分支目标地址（或指令）（避免控制相关造成流水线停顿）

  • 需要解决的关键问题

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

预测错误时的处理方法

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

分支历史表BHT

基本思想是使用一张表（BHT）来记录分支指令最近一次或几次的执行情况（成功还是失败），并据此进行预测。

最简单的分支历史表

只有1个预测位的分支预测表

仅记录分支指令最近一次的历史，只需要1位二进制位。其规则也很简单，一句话，上次是分支成功就认为下次分支成功，上次失败就认为下次失败。

两位预测位的分支历史表

两个位记录分支最近两次的执行情况（成功1或失败0）

研究结果表明：两位分支预测的性能与n位（n>2）分支预测的性能差不多。

操作步骤

  • 分支预测

    • 当分支指令到达译码段（ID）时，根据从BHT读出的信息进行分支预测 。
    • 若预测正确，就继续处理后续的指令，流水线没有断流。否则，就要作废已经预取和分析的指令，恢复现场，并从另一条分支路径重新取指令。

  • 状态修改。【根据状态变迁图修改状态】

BHT的作用范围

关键在于比较判定分支是否成功所需的时间和确定分支目标地址所需的时间哪个更大。

【在5段经典流水线中，判断分支是否成功和计算分支目标地址都是在ID段完成的，故BHT方法不会给该流水线带去什么好处。】

BHT技术只管了预测部份，没管预测后的处理部分。

BHT的实现

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

分支目标缓冲器BTB

BTB的目标是将分支的开销降为 0。具体方法是分支目标缓冲，即，将分支成功的分支指令的地址和它的分支目标地址都放到一个缓冲区中保存起来，缓冲区以分支指令的地址作为标识。

BTB可以看成是用专门的硬件实现的一张表格。表格中的每一项至少有两个字段。一是，执行过的成功分支指令的地址，用作该表的匹配标识。二是预测的分支目标地址。只有这两项的就是最简单的BTB。

注：在预测失败的情况下，会承受2个周期的延迟。

与BHT相比，BTB的优点在于IF周期就能找到分支地址，能够将分支成功且预测准确时的分支开销降到0。

改进BTB

1、在分支目标缓冲器中增设一个至少是两位的“分支历史表”字段

2、在表中对于每条分支指令都存放若干条分支目标处的指令，就形成了分支目标指令缓冲器。

这里，BTB中不在保存分支目标地址，而是保存分支目标指令。

为什么存指令，而非指令地址呢？因为IF是通过指令地址取指令，分支成功，程序的空间局部性spatial locality被破坏，取指令的时延很可能会增加

多指令流出技术

多指令流出技术通过降低理想CPI，以改善实际CPI。

多流出处理机的两种基本风格

超标量

  • 在每个时钟周期流出的指令条数不固定，依代码的具体情况而定。（有个上限）
  • 设这个上限为n，就称该处理机为n-流出。
  • 可以通过编译器进行静态调度，也可以基于Tomasulo算法进行动态调度。

超标量结构对程序员是透明的，处理机能自己检测下一条指令能否流出，不需要由编译器或专门的变换程序对程序中的指令进行重新排列

即使是没有经过编译器针对超标量结构进行调度优化的代码或是旧的编译器生成的代码也可以运行，当然运行的效果不会很好【若要想达到很好的效果，方法之一是：使用动态超标量调度技术。】

超长指令字VLIW

  • 在每个时钟周期流出的指令条数是固定的，这些指令构成一条长指令或者一个指令包。
  • 指令包中，指令之间的并行性是通过指令显式地表示出来的。
  • 指令调度是由编译器静态完成的。

基于静态调度的超标量流水线技术

指令按序流出，在流出时进行冲突检测。由硬件检测当前流出的指令之间是否存在冲突以及当前流出的指令与正在执行的指令是否有冲突。

超长指令字技术

超长指令字技术把能并行执行的多条指令组装成一条很长的指令，成为一个指令字。这条指令通常为100多位到几百位。为了支持多条指令的同时执行，需要设置多个功能部件。指令字被分割成一些字段，每个字段称为一个操作槽，直接独立地控制一个功能部件。在超长指令字处理机中，在指令流出时不需要进行复杂的冲突检测，而是依靠编译器全部安排好了。

问题

  • 程序代码长度增加了。原因在于，为提高并行性而进行的大量的循环展开；此外，指令字中的操作槽也并非总能填满。 对于这个问题，可以通过采用指令共享立即数字段的方法，或者采用指令压缩存储、调入Cache或译码时展开的方法予以解决。

  • 采用了锁步机制。任何一个操作部件出现停顿时，整个处理机都要停顿。

  • 机器代码的不兼容性，一旦体系结构发生了变化，代码就必须重新编译。

超流水线处理机

超流水线处理机的基本概念：将每个流水段进一步细分，这样在一个时钟周期内能够分时流出多条指令。这种处理机称为超流水线处理机。

对于一台每个时钟周期能流出n条指令的超流水线计算机来说，这n条指令不是同时流出的，而是每隔1/n个时钟周期流出一条指令。实际上该超流水线计算机的流水线周期为1/n个时钟周期。

指令调度和循环展开

指令调度的基本方法

指令调度一般由编译器完成。通过找出不相关的指令序列，让它们在流水线上重叠并行执行。

编译器做指令调度时，通常会收两个方面的制约。一是程序固有的指令级并行，二是流水线功能部件的延迟。

循环展开的基本概念和方法

循环展开是把循环体的代码复制多次并按顺序排放， 然后相应调整循环的结束条件。它是开发循环级并行的有效方法。

循环展开和指令调度的注意事项

（1）保证正确性

（2）注意有效性

（3）使用不同的寄存器

（4）删除多余的测试指令和分支指令，并对循环结束代码和新的循环体代码进行相应的修正。

（5）注意对存储器数据的相关性分析

（6）注意新的相关性