第三章 流水线技术

提高计算机性能

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

3.1 先行控制技术

指令重叠执行

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

先行控制技术

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

3.2 流水线的基本概念

概念

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

分类

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

性能指标

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

若干问题

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

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

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

3.3 流水操作中的相关

相关

• 概念：指令存在依赖关系
• 名相关：两条指令访问相同名称的寄存器/存储器单元，但没有数据流动
  • 反相关：j 写 = i 读
  • 输出相关：j 写 = i 写
  • 换名技术：修改操作数名，一改全改
• 数据相关：
  • 条件（满足其一即是数据相关）
    • j 使用 i 的结果
    • j 与 k 数据相关且 k 与 i 数据相关（传递性）
  • 存储器数据相关考虑其有效地址
• 控制相关：分支指令引起
  • 两个限制
    • 被分支指令控制的指令不能移动到分支指令之前
    • 不被分支指令控制的指令不能移动到分支指令之后

冲突

• 概念：由于相关使得下一条指令不能在指定时钟周期执行
• 结构冲突：同一时间争用同一功能部件
  • 解决方法：暂停一拍，气泡
• 数据冲突：指令重叠执行导致数据访存顺序改变
  • 解决方法：定向传送技术，旁路技术，相关专用通路技术
  • 类型
    • RAW 先读后写
      • 定向传送技术：顺序流动流水线，不一定管用
      • 互锁硬件：检测流水线冲突，插入暂停，直至冲突消失
      • 指令调度：乱序流动流水线，编译调整指令顺序
    • WAR 先写后读，覆盖了真正想读出的原来的内容，乱序流水
    • WAW 写后写，改变写入顺序，乱序流水
• 控制冲突：分支指令引起 PC 值变化
  • 解决办法
    • 尽早计算目标地址，尽早判断转移是否成功
      • 使得目标地址能在 ID 后可知
    • 预测分支失败
      • 失败：正常流动（不浪费周期）
      • 成功：后一条指令做空（浪费 1T）然后执行目标指令
    • 预测分支成功
      • 条件：先知道目标地址，后知道是否成功（同时知道，则没有作用）
    • 延迟分支：“延长”分支指令执行时间
      • 从前调度：不被依赖，总能提高流水线性能
      • 从目标处调度：失败必须保证被调度的指令对程序的执行没有影响，成功时可提高流水线性能
      • 从失败处调度：成功必须保证被调度的指令对程序的执行没有影响，失败时可提高流水线性能