流水线技术

1. 流水线基本概念

1.1 定义与工业类比

• 核心思想：将重复过程分解为子过程（功能段），各段并行处理不同任务。
• 关键术语：
  • 通过时间：首个任务从进入流水线到流出的时间。
  • 排空时间：末个任务从进入流水线到流出的时间。
  • 时空图（页10）：纵轴为功能段，横轴为时间，直观展示任务重叠执行过程。

1.2 流水线分类

分类依据	类型	特点与示例
应用等级	部件级流水线	浮点加法分解为求阶差、对阶、尾数相加、规格化
	处理器级流水线	指令分解为取指(IF)、译码(ID)、执行(EX)、访存(MEM)、写回(WB)
	系统级流水线	多处理机串行处理数据流
功能灵活性	单功能流水线	仅固定功能
	多功能流水线	各段可重构，如ASC流水线支持浮点加/定乘
段间连接	静态流水线	同一时间仅一种功能连接，效率低
	动态流水线	同一时间支持多种功能连接，控制复杂
拓扑结构	线性流水线	无反馈回路，如SI→S2→S3→S4
	非线性流水线	含反馈回路，需预约表调度（页25）
任务顺序	顺序流水线	输入/输出顺序一致
	乱序流水线	允许后进先出，如Tomasulo算法
数据类型	标量流水线	处理标量数据
	向量流水线	处理向量数据，如SIMD架构

2. 流水线性能指标

2.1 吞吐率（TP）

• 定义：单位时间完成的任务数 $TP = \frac{n}{T}$。
• 计算：
  • 各段时间相等（均为 $\Delta t$）：
    $$ T = (m + n - 1) \Delta t, \quad TP = \frac{n}{(m + n - 1) \Delta t}, \quad TP_{\text{max}} = \frac{1}{\Delta t} $$
  • 各段时间不等（$\Delta t_i$为第i段时间）：
    $$ T = \sum_{i=1}^m \Delta t_i + (n-1) \cdot \max(\Delta t_i), \quad TP_{\text{max}} = \frac{1}{\max(\Delta t_i)} $$
• 瓶颈段处理：
  • 细分瓶颈段：如 $S_4$（耗时 $3\Delta t$）拆分为 $S_{4-1}, S_{4-2}, S_{4-3}$（各 $\Delta t$）。
  • 重复设置瓶颈段：如 $S_{4a}, S_{4b}, S_{4c}$ 并行，需复杂控制逻辑。

2.2 加速比（S）

• 定义：顺序执行时间 $T_s$ 与流水执行时间 $T_m$ 之比 $S = \frac{T_s}{T_m}$。
• 计算：
  • 各段时间相等：
    $$ T_s = n \cdot m \cdot \Delta t, \quad T_m = (m + n - 1) \Delta t, \quad S = \frac{n \cdot m}{m + n - 1}, \quad S_{\text{max}} = m $$
  • 各段时间不等：
    $$ S = \frac{n \sum_{i=1}^m \Delta t_i}{\sum_{i=1}^m \Delta t_i + (n-1) \max(\Delta t_i)} $$
• 段数选择：段数 $m$ 增加需更多任务才接近 $S_{\text{max}}$，过多段数可能因寄存器延迟降低效率。

2.3 效率（E）

• 定义：设备利用率 = 任务占用时空区 / 总时空区。
• 计算：
  $$ E = \frac{n \cdot \sum_{i=1}^m \Delta t_i}{m \cdot \left[ \sum_{i=1}^m \Delta t_i + (n-1) \max(\Delta t_i) \right]} $$
  • 加权版本（页48）：考虑功能段权值 $\alpha_i$（如 $S_4$ 权值=3）。

3. 非线性流水线调度

3.1 单功能非线性流水线调度

• 预约表：矩阵表示任务占用功能段的时间点。
• 步骤：
  1. 禁止集合 $F$：计算预约表中同行任意两个"×"的距离。
  2. 冲突向量 $C$：$m$ 位二进制（$m = \max(F)$)，$C_i = 1$ 当 $i \in F \。
  3. 状态转移图：初始冲突向量逻辑右移，若移出0则与初始向量"或"运算。
  4. 最优调度：找平均启动距离最小的启动循环（如 (1,7)）或恒定循环（如 (5)）。
• 示例：
  • 预约表：

    时间	1	2	3	4	5	6	7
    S1	×						×
    S2		×				×
    S3			×		×
    S4				×

  • 转移图

  graph LR
    A(101010) -->|1| B(111111)
    A -->|3| C(101111)
    A -->|5| D(101011)
    A -->|7*| A
    B -->|7*| A
    C -->|7*| A
    C -->|5| D
    D -->|3| C
    D -->|5| D
    D -->|7*| A
  

  • 禁止集合 $F = \{2, 4, 6\}$ → 冲突向量 $C = (101010)$。
  • 最优循环：(1,7) 平均距离=4。

3.2 多功能非线性流水线调度

• 冲突矩阵：
  $$ M_A^{(0)} = \begin{bmatrix} C_{AA} \\ C_{AB} \end{bmatrix}, \quad M_B^{(0)} = \begin{bmatrix} C_{BA} \\ C_{BB} \end{bmatrix} $$
  • $C_{pq}$：p类任务后流入q类任务的冲突向量。
• 动态调度：
  • 根据任务类型选择初始矩阵。
  • 状态转移公式：$\text{SHR}^{(i)}(M_k) \lor M_r^{(0)}$。

4. 相关与冲突

4.1 指令相关

类型	定义与示例	解决方法
数据相关（RAW）	指令j依赖指令i的结果： DADD R1,R2,R3 → DSUB R4,R1,R5	定向技术、暂停
名相关	反相关（WAR）：写后读冲突 输出相关（WAW）：写后写冲突	寄存器换名
控制相关	分支指令改变执行流	分支预测、延迟槽

4.2 流水线冲突

冲突类型	原因与示例	解决方案
结构冲突	资源争用，如单端口存储器同时取指与访存	分离指令/数据Cache
数据冲突	RAW/WAR/WAW	定向技术、编译器调度
控制冲突	分支指令改变PC	分支预测

• 定向技术（旁路）：
  • 原理：将结果直接从产生段（如EX）送至依赖段（如EX），避免写回等待。
  • 局限性：Load结果需MEM段结束，无法定向到下一指令EX段，需插入暂停。
• 延迟槽调度：
  • 方法：分支指令后插入1个延迟槽，填充独立指令（从前调度）、目标处指令（从目标调度）或失败处指令（从失败调度）。
  • 示例：

    DADD R1,R2,R3    ; 从前调度（独立指令）
    if R1=0 then     ; 分支指令
    DSUB R4,R5,R6   ; 延迟槽指令（始终执行）

5. 流水线实现细节

5.1 RISC-V 5段流水线

阶段	功能	关键操作
IF	取指	PC = PC+4, IR = Mem[PC]
ID	译码	读寄存器、立即数扩展、分支目标计算
EX	执行	ALU计算、分支条件判断
MEM	访存	Load/Store数据访问
WB	写回	结果写寄存器

• 定向路径设计：EX段结果直连ALU输入，MEM段结果直连MEM输入。

5.2 流水线最佳段数选择

• 总时间模型：$T_k = \frac{t}{k} + d$（$t$：顺序时间，$d$：锁存器延迟）。
• 价格模型：$C = a + b \cdot k$（$a$：功能段总价，$b$：锁存器单价）。
• 性价比最大化：
  $$ \text{PCR} = \frac{1}{(t/k + d)(a + b k)} \implies k_{\text{opt}} = \sqrt{\frac{a t}{b d}} $$

6. 关键问题说明

1. 非线性流水线调度难点：

   • 预约表与冲突向量关系：预约表中"×"最多的行是瓶颈，理想最小启动距离等于该行"×"数。
   • 预留算法：插入非计算延迟段修改预约表（如延迟 $S_4$ 输出），使启动循环最小化。

2. 控制冲突处理：

   • 分支取消机制：预测失败时将延迟槽指令转为空操作（nop）。
   • 动态预测：课件未详述，实际常用两位预测器、BTB等。

3. 多功能流水线冲突矩阵：

   • 示例中 $C_{BA} = (1011)$ 计算过程需结合预约表分析（页89），未完全展开，需补充：
     • 避免S1冲突：时间差1,4（因B任务在周期1,2,5占用S1）。
     • 避免S2冲突：时间差2（B任务周期2占用S2）。
     • 综合得 $F = \{1,2,4\} \rightarrow C_{BA} = (1011)$（二进制从低位到高位对应1,2,3,4）。