Skip to main content

流水线技术与指令级并行

warning

相当复杂，瞎记一下。

并行处理技术​

同时性：同一时刻

并发性：同一时刻间隔

并行处理技术有三种形式：

  1. 时间并行：时间重叠
  2. 空间并行：资源重复
  3. 时间空间并行：超标量流水线

通过将某一 重复 的工作分解为若干子过程，每个子过程可以在专用设备构成的流水线功能段上实现，达到与其他子过程同时执行的效果，这种技术就被成为流水技术。

流水线的一般结构

  1. 每个子过程被称为流水线的级或段，级的个数被称为流水线的而深度；
  2. 流水线有一定 通过时间，即在此之后才能进入稳定的工作状态；
  3. 流水线不能单个任务的响应时间，但是可以提高吞吐率；
  4. 流水线速度受限于最慢流水线段的速度。

分类

系统级流水线/轰流水线：多机系统中由多个处理机串行构成的流水线；

处理器级流水线：指令间流水执行，如执行指令时可以先取下一个指令；

部件级流水线：如微程序控制单元中取微指令和执行微指令流水执行。

流水线功能的强弱

单功能流水线：每条流水线只能完成单一的功能；

多功能流水线：还可以细分为静态和动态流水线，可以在一条流水线上实现不同的功能；静态流水线只有在某个功能的任务执行完毕之后才能切换为其他任务，动态流水线则不然，但是其复杂度很高。

反馈回路

没有反馈回路的流水线被称为 线性流水线，而 非线性流水线 可以选择数据流向，需要使用流水线连接图和流水线预约表共同表示。

顺序流水线

按照流水线输出端任务流出顺序和输入端流入顺序是否相同划分，相同则为顺序流动流水线，不同则为异步流动流水线，具体分为无序流水线、错序流水线和乱序流水线。

指令流水线策略​

增加指令深度

将子过程进一步细分，可以使得单条指令流水线并行执行指令的能力变强，每一级处理时间更短，提高处理器的工作频率；但是分支预测失败的开销太大。

时空图​

横轴为时钟周期，纵轴为段的图，方格中写所执行的指令（子过程）有几个段就可同时流水处理几个指令，其通过时间为 (流水线级数 −1-1) ×\times 时钟周期，即从第一个段执行第一个子过程到最后一段开始执行第一个子过程的时间。

另一种时空图横轴不变，纵轴为所执行指令，方格中写所执行的段号

吞吐率：单位时间内流水线过完成的任务数或输出结果的数量

最大吞吐率：达到稳定状态后的吞吐率

实际吞吐率：从开始运行到结束的实际吞吐率，若每段执行时间相同，对于 mm 个段和 nn 个任务，则其实际吞吐率为

TP=nmT+(n−1)TTP=\frac{n}{mT+(n-1)T}

每段执行时间不同，计算公式为

TP=n∑i=1mτi+(n−1)⋅max{τi}TP=\frac{n}{\sum_{i=1}^m\tau_{i}+(n-1)\cdot max\{\tau_{i}\}}

其中 τi\tau_{i} 表示相应段的执行周期。

单流水线计算机的理想 CPI=1CPI=1，最大吞吐率就是主频 fCLKf_{CLK}

加速比：采用流水之后和不采用流水线的比值。

效率：数格子，执行指令的格子和所有格子之比，其实际上是实际加速比和最大加速比的比值，当 τ\tau 不变时，效率与吞吐率呈正比；当 τ\tau 和段数都不变时，加速比和吞吐率呈正比。

流水线的基本性能问题​

info

流水线的深度受限于流水线的延迟、时间不均衡和流水线的额外开销，指令执行时可能存在的 相关 或 冒险 问题。

相关 是指相邻或相近的两条指令因为存在某种关联，后一条指令不能在原定时钟周期开始执行，相关或冒险有 33 类：

  1. 结构相关：如资源冲突等。
  2. 数据相关：某条指令需要用到前面某条指令的结果。
  3. 控制相关，与前两种不同，控制相关是全局性的，开销很大。

结构相关​

结构相关的资源冲突问题，是因为两个以上的流水线段需要使用同一个硬件资源，解决办法有：

  1. 存储器冲突可以使用哈佛结构
  2. 计算冲突：添加两个加法器

数据相关​

数据相关有三种类型：先写后读、先读后写和写 - 写相关，后两种是异步流水带来的问题：

  1. 先写后读：指令依赖于前面指令的计算结果，需要等待其写出结果才行；
  2. 先读后写：某些指令执行流程可能相较于前面的指令更快，这时需要将结果写入一个寄存器，而前面的指令还在执行中，其在最后才会使用到（读取）相同寄存其的内容，因此后面的指令应该等待前面的指令将寄存器内容读出使用，再将结果存入寄存器；
  3. 写 - 写：与上面的情况类似，会导致乱序。

先写后读相关存在于所有的流水线当中，其解决方式有：

  1. 添加流水线互锁硬件控制；
  2. 采用直通技术，后面的指令直接使用前面指令的输出，而不是从硬件中读取，前面的指令将结果直通的同时写入对应的硬件；
  3. 使用编译程序来解决，重排指令或者插入空操作；
  4. 使用乱序的方式，先执行后续无相关的指令。

乱序流水线受到先读后写和写 - 写相关的干扰，因此需要额外解决方式——数据重定向技术，对于先写后读相关，就是上述的直通技术；对于写 - 写相关，只需要后一条指令写寄存器即可；先读后写相关一般发生在多功能流水线或有多条流水线的超标量处理机中，在只有一个写功能段的单条流水线中不会发生，可以设置缓冲寄存器，把发生相关的原存储单元的内容复制过去即可。

寄存器重命名

控制相关​

控制相关的解决方式：

  1. 冻结流水线：指令移码段检测到分支指令，则在转移目标地址确定之前保存或删除素有紧随分支指令之后的指令，确定后才重新填充流水线，但是会严重影响流水线性能；
  2. 预取分支目标：预取跳转的分支目标，当跳转发生时，目标指令可立刻执行；
  3. 多流：条件分支的两路上同时启动取指令操作，属于对预取分支目标的发展；
  4. 循环缓冲器：将段循环程序整个装入指令缓冲器，并暂停指令的预取，减少不必要的访存，同时让流水的循环出口恒选循环分支；
  5. 分支预测：可以分为静态和动态分支预测，动态分支预测需要维护一个分支历史表；
  6. 延迟分支：延迟转移技术：只用在 RSICRSIC 机器上，通过编译器实现，必须将跳转指令后延时槽中的指令执行完毕后才能跳转；指令取消技术：将循环中的第一条指令拿出来放在循环体上面以及跳转指令的延时槽中，对于循环程序，大部分情况都是转移成功的，只有最后一次出循环时，转移不成功。

超标量处理器​

tip

为了充分利用 度 为 mm 的超标量处理器，mm 条指令必须是可以并行执行的，否则流水线停顿；芯片中含有多个独立的执行单元，每个单元采用流水结构；采用了乱序发射、重命名技术，CPICPI 实际低于 11，通常 IPC∈[2,6]IPC\in [2,6].

超长指令字处理器 VLIW​

最初来源于水平微程序，一条指令中包含有多个能同时执行的操作，如 TRACE28/300TRACE_{2}8/300 处理机一条指令中最多含有 2828 条可以同时执行的操作。

CPUCPU 内部有多少个执行单元，指令字就有多少个字段与其对应，可以使用表调度法将串行的指令划分为更短的并行指令，通常采用指令窗方法，把一段指令（长度为窗口的大小，如 88）取到窗口中，判断这段指令能否并行执行。

VLIWVLIW 的主要特点有：

  1. 采用显式并行指令计算的方式，处理机中所运行的程序是一个 二维 的指令矩阵，每一行上的所有操作组成一条超长指令，他们之间没有数据相关、控制相关和结构相关的冲突，因此可以同时执行，而上述的超标量处理机和超流水线处理机采用的是隐式并行指令方式，程序是 一维 线性的指令序列，每条指令中一般只包含一个操作；
  2. 指令级并行度更高，上述的处理机并行度只有 2∼62\sim 6，而 VLIW 可以达到几十；
  3. VLIW 中使用并行编译器来寻找程序中指令级并行，同时可以采用软件流水、循环展开等指令级并行度很高的方法提高并行性；
  4. 硬件结构规整、简单、功耗低，不需要很复杂的指令并行调度窗口及多发射机制等；
  5. 编译器实现难度大，由上，并行编译器依靠指令级并行算法、数据相关性分析算法、寄存器分配算法及并行编译技术等来显式提升并行性，因此开发难度很大；

目标代码兼容问题

使用虚拟机模拟 x86x86 等机器，依次达到兼容，但是性能很差。

VLIWVLIW 的一些问题：

  1. 定位尴尬：价格高于、性能低于同档次 x86x86 处理机；
  2. 生态问题：没有公司愿意继续开发软件；
  3. 维保费用昂贵。