6、指令并行.md

### 指令并行

#### 概念

ILP（Instruction-Level Parallelism）

* 指令之间的可并行性
* 运用流水线以及相关优化技术，使得指令能够重叠并行执行



并行的重要性

* 理想流水线的CPI加上各类停顿的时钟周期数：

  <img src="https://img-blog.csdnimg.cn/20201225154046883.png" width="50%"/>



* 理想CPI是衡量流水线最高性能的一个指标



具体问题

* 相关
  * 两条指令之间存在某种依赖关系
  * 分类：数据相关、名相关、控制相关
* 流水线冲突
  * 对于具体的流水线来说，由于相关等原因的存在，使得指令流中的下一条指令不能在指定的时钟周期执行。
  * 流水线冲突有三种类型：结构冲突、数据冲突、控制冲突
* 小结与比较
  * 相关是程序固有的一种属性，它反映了程序中指令之间的相互依赖关系。
  * 具体的一次相关是否会导致实际冲突的发生以及该冲突会带来多长的停顿，则是流水线的属性。



相关的两类解决方案

* 保持相关，但避免发生冲突
  * 指令调度
    * 基于硬件的动态开发方法
    * 基于软件的静态开发方法
* 通过代码变换，消除相关
  * 寄存器重命名







#### 指令调度

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

* 指令是按序流出和按序执行的，即使后面不依赖前面的指令也将等待

* 解决办法：乱序执行

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

  <img src="https://img-blog.csdnimg.cn/20201225154119996.png" width="30%" />





调度分类

* 静态调度

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

* 动态调度

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

  



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

* 动态调度的流水线支持多条指令同时处于执行当中
* 要求
  * 具有多个功能部件
  * 或者功能部件流水化
  * 或者兼而有之。



复杂的异常处理

*  精确异常
   * 如果发生异常时，处理机的现场跟严格按程序顺序执行时指令i的现场相同。
*  不精确异常
   * 当执行指令i导致发生异常时，处理机的现场（状态）与严格按程序顺序执行时指令i的现场不同。
   * 发生不精确异常的原因：因为当发生异常（设为指令i）时
     * 流水线可能已经执行完按程序顺序是位于指令i之后的指令；
     * 流水线可能还没完成按程序顺序是指令i之前的指令。 
   * 不精确异常使得在异常处理后难以接着继续执行程序。
*  动态调度的处理机要保持正确的异常行为
   * 对于一条会产生异常的指令来说，只有当处理机确切地知道该指令将被执行时，才允许它产生异常。
*  即使保持了正确的异常行为，动态调度处理机仍可能发生不精确异常。







#### 多指令流出技术

工作动机

* 实际CPI=理想CPI+各种冲突引入的停顿
  * 上面说的技术主要集中后者（消除/减少各种冲突引入的停顿）
  * 也可以考虑通过提升前者，改进实际CPI
* 前面讲的所有流水线都是单流出的，即一个时钟周期内至多流出一条指令，理想CPI=1
* 多指令流出技术：一个时钟周期内流出多条指令，理想CPI<1。





单流出与多流出对比

* 单流出时空图

  <img src="https://img-blog.csdnimg.cn/20201225154141560.png" width="30%"/>

* 多流出时空图

  <img src="https://img-blog.csdnimg.cn/20201225154208108.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw==,size_16,color_FFFFFF,t_70" width="30%" />





两种基本风格

* 超标量（Superscalar）
  * 即在同一个时间段充分使用多个不同的流水线
  * 在每个时钟周期流出的指令条数不固定，依代码的具体情况而定。（有个上限）
  * 设这个上限为n，就称该处理机为n-流出。
  * 可以通过编译器进行静态调度，也可以基于Tomasulo算法进行动态调度。
* 超长指令字VLIW（Very Long Instruction Word）
  * 在每个时钟周期流出的指令条数是固定的，这些指令构成一条长指令或者一个指令包。
  * 指令包中，指令之间的并行性是通过指令显式地表示出来的。
  * 指令调度是由编译器静态完成的。



超标量处理机

* 优势

  * 超标量结构对程序员是透明的，处理机能自己检测下一条指令能否流出，不需要由编译器或专门的变换程序对程序中的指令进行重新排列；
  * 即使是没有经过编译器针对超标量结构进行调度优化的代码或是旧的编译器生成的代码也可以运行，当然运行的效果不会很好。
  * 要想达到很好的效果，方法之一：使用动态超标量调度技术。

* 基于静态调度

  * 在典型的超标量处理器中，每个时钟周期可流出1到8条指令。
  * 指令按序流出，在流出时进行冲突检测。
  * 由硬件检测当前流出的指令之间是否存在冲突以及当前流出的指令与正在执行的指令是否有冲突。

  <img src="https://img-blog.csdnimg.cn/20201225154020756.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw==,size_16,color_FFFFFF,t_70" width="40%"/>

* 限制超标量流水线的性能发挥的障碍

  * Load指令
    * Load后续3条指令都不能使用其结果，否则就会引起停顿。
  * 分支延迟
    * 如果分支指令是流出包中的第一条指令，则其直接影响后续3条指令；
    * 否则就是流出包中的第二条指令，其直接影响后续2条指令。



超长指令字技术

* 概念

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

* VLIW存在的一些问题

  * 程序代码长度增加了

    * 提高并行性而进行的大量的循环展开；

    * 指令字中的操作槽并非总能填满。

      解决：采用指令共享立即数字段的方法，或者采用指令压缩存储、调入Cache或译码时展开的方法。

  * 采用了锁步机制

    * 任何一个操作部件出现停顿时，整个处理机都要停顿。

  * 机器代码的不兼容性



超流水线处理机

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

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

  * 实际上该超流水线计算机的流水线周期为1/n个时钟周期。

  <img src="https://img-blog.csdnimg.cn/20201225153949911.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw==,size_16,color_FFFFFF,t_70" width="40%" />