Lec2 流水线

阅读信息

1888 字 8 分钟本页总访问量加载中...

流水线概念

流水线的定义：将一个过程划分为m个子过程（阶段），不同指令在不同阶段并行执行。

流水线的特点：每阶段时间尽量相等，每段必须有寄存器，任务必须连续输入（否则流水线空转，效率低）

流水线的分类：

按流水线功能，分为单功能流水线和多功能流水线。多功能流水线的切换分为静态（某个功能的指令完成后才能切换）和动态（某个功能的指令部分未完成，只要其他功能的指令准备好，即可进入）。
按调度过程中是否有回路，分为线性（无回路）和非线性（有回路）。
按指令的执行是否有顺序，分为顺序和乱序。
按计算类型，分为标量和向量（向量机，并行运算且相互无关联）。

静态流水线 vs 动态流水线

按照是否允许同一时间执行不同功能分类：

静态流水线：同一时间，流水线的各阶段只能执行同一种功能；切换功能时，必须等待上一功能的阶段全部流出。
- 优点：控制简单，实现成本低，稳定
- 缺点：资源利用率低，并行能力弱
动态流水线：同一时间，流水线的各阶段可以执行不同功能；切换功能时，直接交叉使用两种功能。
- 优点：资源利用率高，并行能力强，吞吐率高
- 缺点：控制复杂，冲突多，硬件开销大

静态流水线用于基本CPU流水线（如riscv五级流水线）和简单嵌入式，动态流水线用于现代高性能CPU等。

线性流水线 vs 非线性流水线

按调度过程中是否有回路分类：

线性流水线：各阶段串行连接，每个任务最多经过一次每个阶段。单向流动、无回环、每段只用一次。
非线性流水线：流水线中存在反馈路径（loop），任务可能多次经过某些阶段。同一阶段被重复访问，用于处理浮点运算、向量运算等需要迭代或中间结果反馈的计算。

三段流水线

三段流水线中，将指令执行分为IF, ID和EX三个阶段。

有以下三种执行方式：

顺序执行：\(T=3n \Delta t\)，时间与指令数成正比
单重叠执行（一级重叠）：\(T=(2n+1)\Delta t\)
双重叠执行（二级重叠）：\(T=(n+2)\Delta t\)。如果用buffer提高读取速度，则IF段时间可忽略不计，二级重叠变为一级重叠，硬件复杂度降低。

重叠的阶段数越多，加速比越大，但硬件实现越复杂。当指令数很大时，加速比约等于阶段数。

ID和EX时间不同的问题：在其中加读数的buffer，能重叠到buffer开始，减少时间不同的影响。

流水线性能计算

优化流水线：

细分：将慢段拆分为多个小段
复制：增加多个并行单元

时间

记 \(\Delta t\) 为时钟周期，由最慢段决定。有两类时间指标：

通过时间（pass time）：第一条指令从进入流水线，到完全执行结束所需的时间。记m为阶段数，则 \(T_{pass} = m \Delta t\)。
排空时间（empty time）：最后一条指令进入流水线后，到它完全执行结束所需时间。也为 \(T_{pass} = m \Delta t\)。

总时间 \(T_{total} = (m + n - 1) \Delta t\)。

吞吐率

吞吐率（throughput，PT）：单位时间执行的指令数，即指令总数除以总时间。

\[ TP = \frac{n}{T} = \frac{n}{(m+n-1) \Delta t} \]

当指令数远大于阶段数时，TP趋向最大极限 \(TP_{max} = \frac{1}{\Delta t}\)。

加速比

加速比（speedup，Sp）：顺序执行的时间和流水线执行时间之比。

\[ Sp = \frac{nm \Delta t}{(m+n-1) \Delta t} = \frac{nm}{m+n-1} \]

当指令数远大于阶段数时，Sp趋向最大极限m，即理想加速比=流水线段数。

效率

效率（efficiency，\(\eta\)）：实际加速比与理想加速比的比值。

\[ \eta = \frac{Sp}{m} = \frac{n}{m+n-1} \]

当指令数远大于阶段数时，\(\eta\) 趋向最大极限1。

线性流水线的冲突

结构冲突

结构冲突（structural hazard）：多个阶段同时需要通过一个硬件资源（如memory）。

解决方法：

硬件分离：如使用平行的cache
增加硬件资源

数据冲突

数据冲突（data hazard）：后续指令依赖前面指令的结果，但结果还未写回。

类型：

RAW（read after write）：上一条指令计算、下一条指令使用。又分为以下几种情况：
上一条写后，直接读：EX-MEM寄存器直接forwarding到下一条指令EX阶段。
上一条写后，隔一条再读：读指令ID时写指令已到MEM，将MEM-WB寄存器forwarding到读指令EX阶段。
前两条都写，下一条读：EX/MEM和MEM/WB同时匹配，优先用户EX/MEM。
上一条load后，直接读写入的寄存器：load的数据在MEM后才产生，需要stall一个周期，再forwarding到读指令的EX阶段。
WAR（write after read）：只在乱序中存在
WAW（write after write）：写顺序问题，只在乱序中存在

解决方法：

stall：等待前一条指令完成
forwarding：直接将EX/MEM或MEM/WB的结果送到下一条
编译器优化

控制冲突

控制冲突（control hazard）：分支指令导致不知道下一条执行什么。

解决方法：

stall：等待branch指令判断完成。
分支预测：使用BHT（branch history table）和BTB（branch prediction buffer）预测。
提前计算：将计算提前到EX阶段。
延迟槽（delay slot）（基本不使用）：假设branch后的那条指令一定执行。

预测错误时需要flush，具体操作为将控制信号置零。按branch结果在哪个阶段得到分为以下情况：

EX阶段得到：此时先取的两条指令错误，需flush掉IF和ID阶段。
ID阶段得到（提前计算下）：只需flush掉IF阶段。
MEM阶段得到（另外的流水线设计下）：需flush掉IF、ID、EX阶段。

非线性流水线的调度

非线性流水线中，同一个阶段在不同时间被重复使用，可能导致冲突。

Q：预约表是什么？怎么检查两个任务是否冲突？

预约表（reservation table）：用于表示一个任务在每个时刻使用了哪些阶段。横轴表示拍数，纵轴表示阶段，对应拍数下用到阶段则打勾。表结构为：

时间	1	2	3	...
阶段1	√
阶段2		√		√
...			√

有多个任务（如流水线）时，每个任务为第一个任务的勾平移对应拍数。如果所有任务打勾后，存在一个格中有多个勾，则表示有冲突。

Q：Prohibited set和conflict vector是什么？怎么更新？

禁止间隔（prohibited set）表示会产生冲突的间隔拍数的集合。即考察单个任务的预约表中，每个阶段相邻两次使用的间隔拍数，取其集合。在调度中始终不变。

冲突向量（conflict vector）表示对于选定的阶段，在哪些间隔拍数下会与其他阶段冲突。第i位表示是否允许间隔拍数为i，1表示禁止（会冲突）、0表示允许（不会冲突）。初始conflict vector只在prohibited set的对应位为1。

CCV（current conflict vector）表示当前所有conflict vector的按位或，用于考察所有阶段的整体冲突情况。

更新方式：每选择一个间隔拍数i（必须在CCV中为0），原阶段的conflict vector为原来的向量左移i位，新阶段的conflict vector为初始值。更新CCV为所有向量的按位或。

Q：怎么用状态图表示调度？

状态图（state transition graph）的组成及含义：

节点：CCV
边：间隔拍数
路径：一个调度方案
环：可重复的调度策略

使用方法：对所有CCV中为0的间隔拍数，计算选择该拍数后的CCV，将所有可能情况画在状态图中。最终图中的环表示可行的循环调度方案（interval的循环组合）。

调度策略的目标为：减小interval的平均值。