流水线技术与指令级并行
流水线举例
洗衣店
并行处理技术
并行性的两种含义：
- 同时性：同一时刻
- 并发性：同一时间间隔
并行处理技术的三种形式：
- 时间并行：时间重叠，流水
- 空间并行：资源重复
- 时间并行+空间并行：超标量流水
将一重复的处理过程分解为若干子过程，每个子过程都可在专用设备构成的流水线功能段上实现，并可与其他子过程同时执行，这种技术成为流水技术。
流水线的一般结构
结论：
- 流水过程中由多个相联系的子过程组成，每个子过程由专用的功能设备实现，每个子过程成为流水线的“级”或“段”。“级”数成为流水线的“深度”；
- 流水线需要有“通过时间”，在此之后的流水过程才进入稳定工作状态，每一个时钟周期流出一个结果；
- 流水线不能缩短单个任务的响应时间，但可以提高吞吐率；
- 流水线速度受限于最慢流水线段的运行速度，所以，各个功能段所需要时间应尽量相等；
- 流水技术适合于大量重复的处理过程，只有流水线的输入能连续地提供任务，流水线的效率才能充分发挥；
- 流水线中多个任务是并行处理的。
流水线的分类
按流水线位于计算机系统的层级划分：
- 系统及流水线/宏流水线：在多计算机系统中由多个处理机串行构成的流水线。
- 处理器级流水线
- 部件级流水线
按流水线功能的强弱划分：
- 单功能流水线
- 多功能流水线
按流水线是否有反馈回路划分：
- 线性流水线
- 非线性流水线——流水线调度
按流水线流出顺序与输入端任务流入顺序是否相同划分：
- 顺序流动流水线
- 异步流动流水线
指令流水线
基本的指令流水线
指令流水线策略
1.增加指令流水线的深度
2.增加指令流水线的条数
7.4流水线的性能度量
7.4.1时-空图
通过时间 = （流水线级数 - 1）* 时钟周期
7.4.2吞吐率
吞吐率：单位时间内流水线所完成的任务数或输出结果的数量。
最大吞吐率TPmax：流水线在达到稳定状态后所得到的吞吐率。（流水线时钟周期的倒数）
提高方法：细分、重复设置
实际吞吐率：若流水线由m段组成，完成n个任务的吞吐率成为实际吞吐率，记作TP。
假设流水线各段运行时间相等，为一个时钟周期TCLK，在不出现流水线断流的情况下
7.4.3加速比
若流水线为m段，加速比S定义为等功能的非流水线执行时间T(l)与流水线执行时间T(m)之比。
增大指令流水线的级数和送入流水线的指令数均可以加速流水线的运行速度。
7.4.4效率
7.5指令流水线的性能提高
7.5.1流水线的基本性能问题
限制指令流水线性能提高的因素：
- 流水线的深度受限于流水线的延迟、流水线段的时间不均衡和流水线的额外开销。
- 指令执行时可能存在的相关或“冒险”问题。
相关：相邻或相近的两条指令因存在某种关联，后一条指令不能在原指令的时钟周期开始执行。
相关或冒险有三类：
- 结构冒险：资源冲突（局部性相关）
- 数据冒险：一条指令需要用到前面某条指令的结果（局部性相关）
- 控制冒险：分支等转移类指令/其他能够改变PC值的指令（全局性相关）
7.5.2结构冒险
有两种情形会导致结构冒险：
- 部分功能单元没有充分流水。
解决方法：将流水线设计的更合理。
- 资源冲突：当两个以上流水线段需要同时使用同一个硬件资源时，会发生冲突。
解决方法：
- 增加资源副本：
- 存储器冲突：哈佛结构
- 两个ALU：取指令—地址加法器
- 改变资源以便它们能并发的使用
- 不相关的数据尽量使用不同的寄存器
- 寄存器重命名
- 通过延迟（或暂停）流水线的冲突段或在冲突段插入流水线气泡（气泡在流水线中只占资源不做实际操作），使各段“轮流”使用资源。
7.5.2数据冒险
相关类型：
- 先写后读
- 先读后写
- 写一写
解决方法：
- 采用直通技术（相关直接通路），将运算结果经相关直接通路直接送入所需部件。
- 增加专用硬件（推后法），增加流水线互锁硬件。互锁硬件先要检测流水线中指令的数据相关性，当互锁硬件发现数据相关时，使流水线工作停顿下来，直到相关消失为止。
- 采用编译器 流水线调度/指令调度：编译器可以对指令重新排序或插入空操作指令，使得加载任何冲突数据的操作被延迟，但对程序逻辑或输出不受影响。
7.5.4控制相关
对条件分支指令的处理方法
方法1：冻结流水线
- 一旦在指令译码段检测到分支指令，就在转移目标地址确定之前保存或删除所有紧随分支指令之后的指令，当分支指令从执行段流出、确定出新的PC值时，流水线才继续依据新PC值填充流水线。
- 会严重地影响流水线的性能。
- 早期的CPU。
方法2：预取分支目标
- 当条件分支指令被识别时，除了紧随其后的指令外，分支目标也被预取，并保存到分支指令被执行。
- 如果分支跳转发生，已预取到的目标指令可立刻执行。
方法3：多流
方法4：循环缓冲器
方法5：分支预测
1.静态分支预测
可以采用的预测方法：
- 预测分支不会发生 “出错检测处理”
- 预测分支总是发生 “循环”
- 由编译器预测
- 测试法 实际运行该程序（一般是在模拟器上），然后将有关信息送给编译器
2.动态分支预测
- 通过记录分支指令的近期运行历史，并以此作为预测的依据，来提高分支预测的准确度。
- 分支历史表，也称分支预测缓存。
方法6：延迟分支
延迟转移技术 无条件转移指令的延迟执行：
采用延迟转移技术的两个限制条件：
- 被移动指令在移动过程中与所经过的指令之间没有数据相关。
- 被移动指令不破坏条件码，至少不影响后面的指令使用条件码。
如果找不到符合上述条件的指令，必须在条件转移指令后面插入空操作。
如果指令的执行过程分为多个流水段，则要插入多条指令。
