流水线、向量处理与并行处理

本节导读

这一节对应大纲系统结构部分的第 6 到第 9 条：流水线的原理、性能分析和调度，数据相关与控制相关；超标量处理机；向量处理机；互连网络；并行处理机与多处理机。大纲特别写了「重点掌握流水线数据相关和控制相关的概念和相关的基本解决方法」。

流水线要会的计算很多：吞吐率、加速比、效率、瓶颈段的处理、非线性流水线的调度，都有固定的公式和步骤；互连网络要会算互连函数、记住静态网络的参数；多处理机以概念为主。学完你应该能画出或想象出时空图、写出完整的流水线计算过程，并能判断一段指令序列里有哪几种相关。

流水线的分类与性能

流水线把一个任务分成若干段，各段由独立的部件依次处理，多个任务重叠执行。按级别分为部件级、处理机级和处理机间流水线；按功能分为单功能和多功能流水线，多功能的又分静态（同一时间只按一种功能连接）和动态（不同功能可以同时进行）；按连接方式分为线性和非线性流水线。

设流水线有 k 段，各段时间都是 $\Delta t$Δt，连续处理 n 个任务：

指标	公式	n 很大时
总时间	$T = (k + n - 1) \Delta t$T=(k+n−1)Δt	—
吞吐率	$TP = \frac{n}{(k + n - 1) \Delta t}$TP=(k+n−1)Δtn​	趋于 $\frac{1}{\Delta t}$Δt1​
加速比	$S = \frac{nk}{k + n - 1}$S=k+n−1nk​	趋于 k
效率	$E = \frac{n}{k + n - 1}$E=k+n−1n​	趋于 1

例如 4 段、每段 10 ns、处理 20 个任务：T = 230 ns，吞吐率约 $8.7 \times 10^7$8.7×107 个/秒，加速比 $\frac{80}{23} \approx 3.48$2380​≈3.48，效率约 0.87。各段时间不等时，最慢的一段是瓶颈：$T = \sum \Delta t_i + (n - 1) \Delta t_{\max}$T=∑Δti​+(n−1)Δtmax​，最大吞吐率是 $\frac{1}{\Delta t_{\max}}$Δtmax​1​。消除瓶颈有两种办法：把瓶颈段再细分成几段，或者重复设置几个瓶颈段轮流使用。

非线性流水线的调度

非线性流水线有反馈，一个任务会多次使用同一段，相邻两个任务的启动间隔（延迟）选不好就会冲突。调度的步骤：一，写出预约表（每段在哪些时刻被使用）；二，求禁止表 F——同一行里任意两个使用时刻之差的集合；三，写出初始冲突向量 C，第 i 位（从右往左数）为 1 表示延迟 i 被禁止；四，从初始状态出发画状态图：用允许的延迟 j 启动下一个任务后，新状态是「当前状态右移 j 位，再与初始冲突向量按位或」；五，在状态图里找平均延迟最小的循环，就是最小平均延迟（MAL）。

数据相关与控制相关

流水线中的相关分三类。结构相关：两条指令同时要用同一个部件，用重复设置部件或暂停解决。数据相关有三种：

名称	含义	举例（先 i 后 j）
写后读（RAW，真相关）	j 要读 i 写的结果	i 写 R1，j 读 R1
读后写（WAR，反相关）	j 要写 i 还没读的寄存器	i 读 R1，j 写 R1
写后写（WAW，输出相关）	i、j 写同一个寄存器	i 写 R1，j 也写 R1

顺序发射、顺序写回的简单流水线里只有写后读会造成冲突，解决办法是定向（旁路，把结果直接送到要用的地方）、暂停（插入气泡）和编译器的指令调度；读后写和写后写在乱序执行时才会出问题，用寄存器换名解决。控制相关来自转移指令，解决办法有冻结流水线、预测转移不成功、延迟转移（转移后面的延迟槽放一条总要执行的指令），以及静态和动态的转移预测（转移历史表、转移目标缓冲）。

超标量与超流水线

超标量处理机有多条流水线，每个时钟周期同时发射 m 条指令；超流水线处理机把每段再细分成 n 个小段，每 $\frac{\Delta t}{n}$nΔt​ 发射一条指令。k 段流水线执行 N 条指令，理想情况下所需时间：

处理机	时间
普通标量流水线	$(k + N - 1) \Delta t$(k+N−1)Δt
超标量（度 m）	$(k + \frac{N - m}{m}) \Delta t$(k+mN−m​)Δt
超流水线（度 n）	$(k + \frac{N - 1}{n}) \Delta t$(k+nN−1​)Δt
超标量超流水线（m、n）	$(k + \frac{N - m}{mn}) \Delta t$(k+mnN−m​)Δt

多发射时还要处理多条流水线之间的资源冲突和相关，调度方式有顺序发射顺序完成、顺序发射乱序完成、乱序发射乱序完成。

向量处理机

向量运算有三种处理方式：横向（逐个元素算完整个表达式，相关太多，不适合流水线）、纵向（整个向量算完一步再算下一步，适合存储器—存储器结构）、纵横（分组，每组长度等于向量寄存器长度，适合寄存器—寄存器结构）。

提高向量处理机性能的主要方法是链接技术：前一条向量指令的结果直接送进后一条指令所用的功能部件，两条流水线串成一条。链接的条件是没有向量寄存器使用冲突、没有功能部件冲突，而且时间要对准。此外还有向量循环开采（把长向量分段处理）和向量递归技术。