第三章流水线技术

提高计算机性能

缩短 CPI：RISC技术
提高指令并行度：流水线技术

3.1 先行控制技术

指令重叠执行

指令执行时间： $T_i = t_取指令+t_分析+t_执行$
执行方式（假设三个阶段的 t 相等，一共 N 条指令）
- 顺序执行： $T = 3 Nt$
- 重叠执行
  - 一次重叠： $T = (1 + 2 N) t$
  - 两次重叠： $T = (2 + N) t$

先行控制技术

关键：缓冲技术、预处理技术
目的：指令流和数据流的预处理和缓冲，使指令分析器和指令执行独立工作，始终忙碌
问题
- 部件独立
  - 独立取指、分析、执行部件，设置对应存储、指令、运算控制器
- 主存访问冲突
  - 拆分程序和数据总线和存储器/cache（哈佛结构）
    - 结构复杂，数据线多，对汇编、机器程序员不透明
  - 多体交叉存储结构
  - 先行控制技术
- 分析和执行指令时间不同
  - 先行控制技术
先行控制处理机
- 缓冲栈深度： $D 取指栈 \geq D 操作栈 \geq D 读栈 \geq D 写栈$

在这里插入图片描述

3.2 流水线的基本概念

概念

流水线技术：重复过程 -> 若干子过程，子过程由专门部件实现
流水线级或段：子过程及其功能部件
流水线深度：流水线段数
标量流水：取指、译码、执行、访存、写回
流水线结构：功能部件+缓冲寄存器
时空图： $k$ 段流水线， $n$ 条指令，每段用时 $△t\triangle t$
- 填入时间： $\cdot \triangle t$
- 填满+排空时间： $\cdot \triangle t$
- 功能部件延时 $△ts\triangle ts$ ，锁定时间 $△tl\triangle tl$
  - 最高工作频率 $TPMAX=1△ts+△tlTP_{MAX} = \frac{1}{\triangle ts+\triangle tl}$
  - 延时时间不等，则最高工作频率 $TPMAX=1max(△ts+△tl)TP_{MAX} = \frac{1}{max(\triangle ts+\triangle tl)}$
特点
- 每段用时 $△t\triangle t$ 应尽量相等，否则成为瓶颈，影响吞吐率，造成阻塞或断流
  - 分割瓶颈部件工作
  - 重复设置瓶颈部件
- 满载时每隔 $△t\triangle t$ 将有一个结果输出

分类

按处理机
- 操作部件级：处理机算术逻辑运算部件分段，如浮点运算，超流水线处理机，子部件+缓冲
- 处理机级：指令流水线，拆分指令解释执行过程，部件+缓冲
- 处理机间级：多处理机系统任务调度策略，处理机+缓冲
按功能
- 单功能：一条流水线完成单一任务
- 多功能：改变部件连接，从而改变流水线功能，标量运算
按工作方式
- 静态流水线：某功能指令全部流出后，才允许改变部件连接，单/多功能
- 动态流水线：可在任何时候改变连接，多功能
按连接方式
- 线性流水线：没有反馈连接，常用
- 非线性流水线：通过反馈线使部件重复使用
按流入流出顺序
- 顺序流水线：输出结果与输入次序相同，早期
- 乱序流水线：打乱次序利于执行，结果恢复原次序，现代、
按数据表示方式：标量流水线、向量流水线
按控制方法：同步、异步
- 处理机内：同步
- 处理机间：异步

性能指标

吞吐率：单位时间内完成任务量
- $\frac{n}{T_k} = \frac{n}{(m+n-1) \triangle t}$
- $n$ 完成指令条数
- $T_k$ 完成任务所用时间 $Tk=(m+n−1)△tT_k = (m+n-1) \triangle t$ （各级执行时间相等且无气泡时才可用，否则看图说话）
- 当 $\to \infty$ 时 $TPmax=lim⁡n→∞n(m+n−1)△t=1△tTP_{max} = \lim_{n \to \infty} \frac{n}{(m+n-1) \triangle t} = \frac{1}{\triangle t}$
- m 级流水线，n 条指令，各级执行时间不等
  - $\frac{n}{\sum_{i=1}^{m} \triangle t_i+(n-1)\max(\triangle t_1,\dots,\triangle t_m)}$
  - 当 $\to \infty$ 时 $TPmax=1max⁡(△t1,…,△tm)TP_{max} = \frac{1}{\max(\triangle t_1,\dots,\triangle t_m)}$
加速比：同一批任务，不用和采用流水线所用时间之比
- $\frac{T_0}{T_k} = \frac{nm \triangle t}{(m+n-1) \triangle t} = \frac{nm}{m+n-1}$
- $T_0$ 不用流水线所用时间 $T0=nm△tT_0 = nm \triangle t$ （各级执行时间相等可用，否则看条件说话）
- $T_k$ 采用流水线所用时间
- 当 $\to \infty$ 时 $Smax=lim⁡n→∞nmm+n−1=mS_{max} = \lim_{n \to \infty} \frac{nm}{m+n-1} = m$
- m 级流水线，n 条指令，各级执行时间不等
  - $\frac{n \cdot \sum_{i=1}^{m} \triangle t_i}{\sum_{i=1}^{m} \triangle t_i+(n-1)\max(\triangle t_1,\dots,\triangle t_m)}$
效率： n 个任务占用的时空区与 m 个功能段总的时空区之比
- $\frac{T_0}{m \cdot T_k} = \frac{nm \triangle t}{m(m+n-1) \triangle t} = \frac{n}{m+n-1}$
- 当 $\to \infty$ 时 $Emax=lim⁡n→∞nm+n−1=1E_{max} = \lim_{n \to \infty} \frac{n}{m+n-1} = 1$
- m 级流水线，n 条指令，各级执行时间不等
  - $\frac{n \cdot \sum_{i=1}^{m} \triangle t_i}{m \cdot [\sum_{i=1}^{m} \triangle t_i+(n-1)\max(\triangle t_1,\dots,\triangle t_m)]}$
- 效率不高的原因
  - 数据相关
  - 任务较少时，填入和排空所占比例较大
  - 静态流水线导致排空拉长
关系（各级执行时间相等）： $\cdot E = m \cdot \triangle t \cdot TP$
性能价格比
- $\frac{TP_{max}}{C} = \frac{1}{\frac{t}{k}+d} \cdot \frac{1}{a+bk}$
- $TPmax=1△t=1tk+dTP_{max} = \frac{1}{\triangle t} = \frac{1}{\frac{t}{k}+d}$
  - $t$ 串行执行一个任务所用时间（取指分析执行一条指令所用时间）
  - $tk+d\frac{t}{k}+d$ 同等速度在 k 段流水机执行一个任务所用时间
  - $d$ 锁存器延迟时间
- $C = a + bk$ 流水线总价格
  - $a$ 流水段本身价格总和
  - $b$ 单个锁存器价格
- 对 k 求导得，PCR 极值时 $K0=tadbK_0 = \sqrt{\frac{ta}{db}}$
- k >= 8 超流水线，超流水线处理机

若干问题

瓶颈问题：流水线各段不均匀，时钟周期取决于瓶颈段延迟时间
额外开销：寄存器延迟，时钟偏移开销
冲突问题：重要问题

非线性流水线的竞争与调度

冲突
- 启动距离：前一条指令输入开始到下一条指令输入为止的时间差
  - 禁止启动距离：会引起冲突的启动距离
  - 启动循环：任何时间都不会发生冲突的启动距离
最优调度方法
- 根据预约表写出第一条指令的禁止向量 F
  - 对每个部件计算任意两次复用时间差
  - 求所有部件的时间差的集合为禁止向量 F
  - 向量元素为禁止距离
- 根据禁止向量计算初始冲突向量
  - 为一串二进制串，F 中存在 i 时该位为 0 否则为 1，串长度 $len = \max(F_i)$ （len <= 流水段数 m）
  - 第 i 位表示启动距离为 $\triangle t$ 时的冲突情况，0 不会冲突，1 冲突
- 根据初始冲突向量推算出全部冲突向量
  - 初始向量右移，高位补零，地位溢出 1 时不做处理，溢出 0 时与初始向量相或，结果加入冲突向量集合
  - 再从向量集合中选中一个未操作向量，重复上述步骤，直至冲突向量集合不再扩展
- 画出表示冲突向量迁移的有向图
  - 将冲突向量高位隐式补充到 n-1 位，n 为预约表最大周期数
  - 冲突向量第 i 位为 0，右移 i 位后与初始向量相或，得到结果向量，用有向边连接冲突向量节点与结果向量节点，边权为 i
  - 保证节点出度 = 冲突向量中 0 的个数
- 根据冲突向量迁移图写出启动循环
  - 简单循环：有向图中的闭合回路，（1，7）表示第二条在 1 个周期后进入，第三条在 7 个周期后进入，第四条循环为 1 个周期后进入…
  - 平均启动距离（平均间隔时钟周期数）：闭合回路的平均边权，
  - 最小启动循环（最优调度方案）：平均启动距离最小的，且同时考虑奇、偶条指令的情况
  - 最小恒定循环：只有一条边的闭合回路
- 计算最大吞吐率
- 画出功能部件连接图
  - 最后一个到达的功能部件连接输出