流水线性能分析这个题目看起来是一道公式题实际上是整个计算机体系结构里最容易以为自己懂了的一块。我见过太多人把 (TP\frac{n}{(kn-1)\Delta t}) 背得滚瓜烂熟一碰上带气泡、带转发、还问你效率和非线性调度的综合题就开始东拼西凑最后错在单位和口径上。这篇我想把这条推理链完整地捋一遍从时空图为什么必须画到吞吐率、加速比、效率三个指标各自的物理含义再到冒险怎么把理想公式吃掉最后落到非线性流水线的预约表和冲突向量。国内不少高校的体系结构课用的是胡伟武老师那套教材课后题的路子和这里讲的基本一致把这几块串通了习题册上的大部分流水线题都能自己推。1. 时空图把跑完要几拍变成一道几何题流水线性能分析的核心工具不是公式是时空图。我个人的习惯是只要题目问的是拍数、吞吐率、效率第一步永远是先把时空图画出来。图画对了公式只是把图上的面积点出来而已图画错了公式背得再熟也救不回来。1.1 为什么第一条指令就要占满 k 拍一条 k 段流水线里的第一条指令从进入 IF 到最后 WB需要完整地穿越 k 个流水段也就是占用 k 个流水周期。这段时间里除了它自己没有别的指令能走完是整个流水线的装入时间。从第二条指令开始每隔一个周期就有一条新指令进入 IF。所以第 n 条指令进入流水线的时刻是在第一条指令进入后的第 n-1 个周期。它本身还要再走 k 拍才完成于是整条流水线完成 n 条指令的总时间是[ T_k k \cdot \Delta t (n-1) \cdot \Delta t (k n - 1) \cdot \Delta t ]这里的 (\Delta t) 是流水线周期。很多人第一次接触会误以为 (\Delta t) 是每段耗时的平均值其实不是。(\Delta t) 必须取所有段里最慢的那一段假设段间有锁存器做缓冲理由很简单一条指令走完 IF 后必须等上一段腾出位置如果 EX 最慢那整条线的节拍就被 EX 卡住其他段即使很快也得跟着一起慢下来。提示如果各段耗时不完全相等先把每一段的时间列出来取最大值作为 (\Delta t)这一步错了后面全错。1.2 三种读图方式横着看、竖着看、算面积时空图是一张二维图横轴是时间拍纵轴是流水段或功能部件。同一张图有三种读法分别对应三类问题横着看按拍每一拍里有哪些段在忙、哪些在空闲。看空闲就能发现结构冒险和气泡。竖着看按段每一段在整个执行过程中被占用了多少时间。这段被占的比例就是该段的效率。算面积每个小方格代表一个部件被占用一个周期这就是有效时空区。三种读法里算面积是最容易被忽视但最有用的。它把效率这种抽象的百分比直接变成了一个几何问题有效面积除以总面积就是效率。这一点后面第 2 章还会展开。我一般画时空图时会在每个小方格右上角标上指令编号比如 I1、I2、I3这样一旦有气泡空拍一眼就能看出是哪两条指令之间产生了停顿、停顿了几拍。1.3 理想时空图隐含的四个假设大部分教材在推公式前会先画一张完美错位的时空图I1 在拍 1 到 5 走完I2 在拍 2 到 6依此类推所有方格严丝合缝地叠成一个平行四边形。这张图成立其实偷偷依赖了四个假设所有指令的每个段耗时都相同都等于 (\Delta t)。不存在结构冒险每条指令想访问哪个部件都能立刻访问到。不存在数据冒险后面指令要用的操作数前面已经准备好。不存在控制冒险取指永远取的是正确的下一条指令。现实中的 CPU 一个都满足不了。所以理想公式算出来的是一个理论上限考试题里如果提到理想流水线或者不考虑冒险你才能放心大胆用一旦题目里出现转发分支load-useCache 缺失这些词就要把停顿周期加进去这是下面第 3 章要处理的事。2. 吞吐率、加速比、效率三个指标的分母到底是什么这三个指标我经常看到有人混着用算完效果不好还找不到原因。它们的区别其实全在分母上吞吐率的分母是时间加速比的分母是顺序执行时间效率的分母是总时空区面积。分清楚这三个分母指标就不会串。2.1 吞吐率的两种写法实际值和上限值吞吐率Throughput记作 TP的定义非常直白单位时间内完成的任务数或指令数。[ TP \frac{n}{T_k} \frac{n}{(kn-1)\Delta t} ]这是实际吞吐率。分母里既包含了装入和排空的时间也包含所有停顿。当 (n \to \infty) 时((kn-1)) 里的 (k-1) 可以忽略得到[ TP_{max} \frac{1}{\Delta t} ]这是最大吞吐率物理意义是流水线满负荷运转时每拍能流出一条指令。注意它的单位是条每拍或者条每秒题目里如果 (\Delta t) 给的是纳秒你算出的 (1/\Delta t) 是 GHz 量级别写成 MHz。一个容易踩的坑有些题目会先问理想流水线的吞吐率是多少再问加入 xx 冒险后的吞吐率。这时候两个分母就不能用同一个 (T_k) 了后者要把停顿周期全加进去具体做法见第 3 章。2.2 加速比分子分母必须用同一套口径加速比Speedup记作 S是非流水线方式所花时间除以流水线方式所花时间。[ S \frac{T_s}{T_p} \frac{n \cdot k \cdot \Delta t}{(kn-1)\Delta t} \frac{n k}{kn-1} ]这里 (T_s nk\Delta t) 是假设每条指令串行地走完 k 段所需的时间。当 (n \to \infty) 时(S_{max} k)也就是流水线的段数。这个结论很漂亮也很有迷惑性——它暗示段数越多加速比越高但实际上段数越多单段的逻辑越复杂(\Delta t) 越大而且冒险带来的开销也越大。这才是现代处理器流水线深度在某个点之后不再增加的根本原因。我见过最多的一种错误是加速比的分子用了非流水线的时间分母却写成了流水线中某一段的时间。分子分母口径不对齐结果自然离谱。判断口径是否对齐就看两边是不是完成同样 n 条指令的全部时间。2.3 效率把抽象百分比还原成面积比效率Efficiency记作 E是最容易算错的一个因为它没有直接的时间含义而是资源利用率。定义是[ E \frac{\text{有效时空区面积}}{\text{总时空区面积}} \frac{n k \Delta t}{k (kn-1)\Delta t} \frac{n}{kn-1} ]分子 (nk\Delta t) 是 n 条指令真正在工作的方格数每条指令走 k 段每段一个方格。分母 (k(kn-1)\Delta t) 是把整个时空图看成一个 k 行、总时间为 (T_k) 的矩形。这个定义等价于每一段在整个执行过程中忙的比例。画图的时候你会发现前半段各流水段的利用率是逐渐爬升的后半段是逐渐下降的中间那段是满的只有 (n) 远大于 (k) 时这些爬升和下降阶段的面积才可以忽略效率趋近于 1。注意效率的分母里乘的是 k 而不是 n很多人在套公式时下意识地写成了 (n(kn-1)\Delta t)多算了一个量级结果效率大于 1。一旦算出的效率超过 100%立刻回头检查分母。2.4 三个指标之间的换算关系与互相验算这三个指标不是孤立的它们之间有一个简洁的关系链[ E TP \cdot \Delta t, \qquad S k \cdot E, \qquad S k \cdot TP \cdot \Delta t ]推导一下也不难把 (TP n/(kn-1)/\Delta t) 乘以 (\Delta t)正好得到 (n/(kn-1))就是效率而 (S nk/(kn-1) k \cdot E)。这个关系链的实用价值在于互相验算。比如一道题你先算了加速比得到 4.5段数 k5那么效率就应该是 (4.5/5 0.9)。如果你另外独立算出的效率是 0.45 或者 1.8其中至少有一个错了。我考试或者改作业时经常用这一招快速判断学生的中间结果靠不靠谱。下面这张表把三种指标的定义、理想上限、常见错误整理在一起做题时可以直接对照指标定义式理想上限常踩的坑吞吐率 TPn / T_k1/Δt把 Δt 当成平均段耗时加速比 ST_s / T_pk分子分母口径不对齐效率 E有效面积 / 总面积1分母误乘 n出现 E13. 让理想公式失效的三类冒险与它们的精确代价理想公式和实际工程之间的距离全部体现在冒险里。所谓冒险就是下一拍该做的事现在做不了。冒险带来的直接后果是停顿周期也叫气泡它会把 (T_k (kn-1)\Delta t) 里的总拍数直接撑大。这一章我想把三类冒险的停顿代价说清楚因为很多题就是在这里下的套。3.1 结构冒险两条指令抢同一个硬件结构冒险是资源竞争。最经典的一种如果指令存储器和数据存储器是同一个那么 IF 阶段取指和 MEM 阶段访存就可能在同一拍抢这块存储器其中一条必须等一拍。以 5 段流水线为例I1 在第 4 拍进入 MEMI4 在第 4 拍进入 IF如果 IF 和 MEM 共用一块存储器这拍就冲突了。解决办法有两种硬件加资源把指令 Cache 和数据 Cache 分开哈佛结构或者让存储器双端口。这样结构冒险根本不会出现。插入气泡如果资源不能加就得让后一条指令等I4 被推到第 5 拍 IF这一拍的空缺就是气泡。题目里如果没特别说明存储资源独立而你又正好算出一条指令在第 4 拍 IF 和另一条在 MEM 撞上那基本就是出题人埋的结构冒险。判断依据非常机械同一部件在同一拍被两条指令占用。3.2 数据冒险RAW 是主角转发能救回几拍数据冒险里真正需要担心的只有 RAW先写后读。WAR 和 WAW 在按序流水线里不会造成停顿在乱序流水线里才会属于另一个话题考试里也很少出现。5 段 MIPS 流水线IF、ID、EX、MEM、WB里RAW 的典型场景是后一条指令在 EX 阶段要用到前一条指令的结果而前一条的结果要到 WB 阶段才写回寄存器堆。这里有一个关键的工程优化转发Forwarding / Bypassing。有了转发前一条指令在 EX 阶段末算出的结果可以直接从 EX/MEM 流水线寄存器送回到下一条指令的 EX 输入不必等它写回寄存器。我把常见的几种 RAW 场景整理成一张表停顿拍数按最常见的 5 段流水线口径给出前一条指令后一条指令无转发停顿有转发停顿ALU 产生结果紧跟使用该结果的 ALU/Store2 拍0 拍Loadlw紧跟使用该数据的指令2 拍1 拍ALU 产生结果间隔一条指令后使用1 拍0 拍Load-Use 是唯一一种即使有转发也躲不掉的 1 拍停顿原因是数据要等到 MEM 阶段末才从存储器取出来而紧跟的指令在 EX 阶段就要用时间上差了一个阶段。这一拍的解决方案通常有两种编译器把一条无关指令调度到 load 和使用之间指令调度或者硬件插入 1 拍气泡。这两个方案在体系结构课上都会讲到。3.3 控制冒险分支预测失败要吞掉几拍控制冒险来自转移指令。处理器在取到分支指令的那一刻其实还不知道下一条到底该取哪个地址只能猜。猜对了没有代价猜错了就得把错误路径上已经取进来的指令全部作废冲刷重新从正确地址取指。损失几拍取决于在哪一段做出分支决策如果分支在ID 阶段就能算出目标地址和判定结果需要额外的比较器和加法器那么只损失 1 拍。经典做法是用一个延迟槽delay slot把这 1 拍填掉这就是 MIPS 里那个著名的分支延迟槽。如果分支要在EX 阶段才能判定那就损失 2 拍。现代深流水线如果分支判定在更靠后的阶段损失会更大所以才有各种分支预测器、BTB、返回地址栈。选题时最需要注意的是延迟槽是否填满。题目如果明确说没有延迟槽或者延迟槽为空那每次执行分支都要损失固定几拍如果说编译器完全填满延迟槽损失就可以按 0 算。3.4 把停顿周期塞进总拍数的计算方法有了上面这些代价实际总拍数的算法就非常机械了[ T_k^{real} (k n - 1)\Delta t N_{stall} \cdot \Delta t ]其中 (N_{stall}) 是所有冒险造成的停顿周期总和。工程上有一个更直观的口径是 CPICycles Per Instruction[ CPI 1 \frac{N_{stall}}{n} ]理想流水线 CPI 是 1每多一个停顿CPI 就往上抬。有了 CPI实际吞吐率就是[ TP_{real} \frac{1}{CPI \cdot \Delta t} ]这个口径比总拍数更有用因为它直接告诉你平均每条指令要花几拍方便和处理器性能公式 (CPU\ Time IC \cdot CPI \cdot Clock\ Cycle) 对接。提示算 (N_{stall}) 时很多人会漏掉分支占的比重。比如题目给分支指令占 20%每次分支损失 1 拍那么 (N_{stall} 0.2n \times 1 0.2n)而不是 (1)。频率和次数的混淆是这一块的高频错误。下面用一小段伪代码把上面这套算法串起来方便你按自己的题目改参数def pipeline_perf(n, k, dt_ns, stall_per_instr0.0): T_ideal (k n - 1) * dt_ns # 理想总时间单位 ns T_real T_ideal n * stall_per_instr * dt_ns TP_ideal n / T_ideal # 条/ns TP_real n / T_real S_ideal n * k * dt_ns / T_ideal # 加速比 S_real n * k * dt_ns / T_real E_ideal n / (k n - 1) # 效率 E_real n * k * dt_ns / (k * T_real) return TP_ideal, TP_real, S_ideal, S_real, E_ideal, E_real我把每一条公式都对应到时空图上的面积是为了强调所谓实际效率其实也是有效方格占实际总方格的比例只是总方格数被气泡撑大了。4. 非线性流水线的调度从预约表推导最小启动距离线性流水线是每个任务从第 1 段开始依次走到第 k 段非线性流水线则存在反馈回路比如乘法器、除法器会重复占用某些段。它的调度问题不是问跑 n 条指令要多久而是问每隔几拍启动一个新任务才能让所有任务互不冲突且平均间隔最小。这是体系结构题里最非典型的一块也是区分度最高的一块。4.1 预约表与冲突向量的构造规则一条非线性流水线只要给出每个任务占用各段的时刻就能画出一张预约表行是流水段列是时间拍X 表示该段在这一拍被占用。从预约表出发构造冲突向量的流程是固定的求禁止向量对每一段把它占用的所有时刻两两作差把所有差值收集起来去重得到禁止向量。含义是如果两个任务的启动时刻相差 d 拍而 d 出现在禁止向量里那么这两个任务会在同一段同一拍撞车。确定位宽冲突向量的位宽等于禁止向量里的最大值。如果禁止向量是空集纯线性流水线位宽取 1 即可。生成初始冲突向量第 j 位为 1 表示启动距离 j 禁止为 0 表示允许。举个具体例子方便你对照着做。假设一条 3 段线性结构但带反馈的流水线预约表如下段 \ 时间12345S1XXXS2XS3X先看 S1占用的时刻是 1、2、5两两差值2-115-145-23。S2 只有时刻 3没有差值。S3 只有时刻 4也没有差值。所以禁止向量是 ({1, 3, 4})。位宽取 4按位 1 到 位 4的顺序写出各位位 1 禁止1位 2 允许0位 3 禁止1位 4 禁止1初始冲突向量就是 (1011)。4.2 状态转移图与平均延迟的枚举有了初始冲突向量下一步是构造状态转移图。从当前状态 C 出发找出所有为 0 的位也就是允许的启动距离对每个允许的距离 j 做如下操作把 C 逻辑右移 j 位超出位宽的高位补 0记为 (C)。用 (C) 与初始冲突向量 C0 做按位或得到新状态。从 C 到新状态引一条边边上标注距离 j。以初始状态 (1011) 为例位 1 是 1禁止跳过。位 2 是 0允许。右移 2 位得到 (0010)(1011 \gg 2)或上 (1011) 得 (1011)正好回到状态 (1011) 自己边标注距离 2。位 3 是 1禁止。位 4 是 1禁止。所以整个状态图只有一个状态唯一允许的启动距离是 2平均延迟就是 2。物理意义是这条流水线每隔 2 拍才能启动一个新任务稳定的调度是启动、等 2 拍、启动、等 2 拍……。在更复杂的预约表里位为 0 的位置会更多状态图会有多条边、多个状态这时候要枚举所有简单循环从一个状态出发最后回到该状态的路径分别计算每条循环的平均延迟 循环上的距离之和 / 循环上的边数取最小的那个作为最小平均延迟。4.3 一个带多状态转移的完整推演再看一个稍复杂、能出现多个状态的例子段 \ 时间1234567S1XXXS2XXS3XS4XS1 占用时刻 1、3、5差值 (2, 4, 2)S2 占用 2、6差值 4其余段只有一个 X。禁止向量 ({2, 4})。位宽取 4位 1 允许、位 2 禁止、位 3 允许、位 4 禁止初始冲突向量 (1010)等等按 1、2、3、4 的顺序写应该是 0、1、0、1也就是 (0101)。从 (0101) 出发位 1 是 0允许。右移 1 位(0010)或上 (0101) 得 (0111)记作状态 D边标注 1。位 2 是 1跳过。位 3 是 0允许。右移 3 位(0000)或上 (0101) 得 (0101)回到自身边标注 3。位 4 是 1跳过。再看状态 D (0111)位 1 是 0允许。右移 1 位(0011)或上 (0101) 得 (0111)又回到 D边标注 1。其余位都是 1跳过。状态图整理如下C(0101) --1-- D(0111) C(0101) --3-- C(0101) D(0111) --1-- D(0111)枚举简单循环循环 ((3))平均延迟 3。循环 ((1))从 C 出发进 D然后在 D 上自环 1稳定之后平均延迟 1。循环 ((1,3))平均延迟 ((13)/2 2)。最小平均延迟取 1。也就是说只要先启动一个任务并等 1 拍进入状态 D之后这条流水线就能每隔 1 拍启动一个新任务稳定吞吐率反而比一开始的距离 3更高。这个例子很能说明一个反直觉的结论非线性流水线的最优调度不一定一开始就把间隔拉到最大有时候过渡一下反而能进到更宽松的状态。注意一定要区分稳定状态后的平均延迟和启动序列前半段的实际延迟。考试里如果问稳定状态下的平均延迟那就是循环上的平均如果问前 m 个任务的启动间隔之和就得按具体序列算。5. 做题和实战里最容易翻车的六个地方讲完了原理最后这一章我想把踩过或者见过的高频坑集中列一下。这些坑有的不出现在教材正文里只在习题和实际估算时暴露。5.1 单位、口径和入流出流没对齐最常见的翻车是没有统一单位。题目给的往往是纳秒问的却是 GHz给的是每条指令的字节数问的却是字节每秒的带宽。碰到这种情况我一般先在草稿纸右上角写一行换算表1 ns 1e-9 s频率和周期的关系是 (f 1/\Delta t)然后再动笔。学生时代有一次把 (\Delta t 2) ns 直接当成了 (2 \times 10^{-6}) s 代进去前面所有推导都对最后数字错到不可收拾。第二个口径问题是入流出流。题目里如果出现流水线已经充满从第 t 拍开始计数或者忽略装入和排空时间那 (T_k) 就不能用 (kn-1) 拍而要按 (n) 拍或者题目指定的区间来。这类题的陷阱在于出题人会先用一段描述让你误以为要考虑 k实际上它是想考你会不会只算稳定段。5.2 把理想公式直接套到带冒险的题上只要题目描述里出现了下列任何一个词你就要放弃 (T_k(kn-1)\Delta t) 这个理想公式转发、旁路Forwarding / Bypassingload-use 冒险分支指令占比、分支预测错误结构冲突Cache 缺失、访存延迟正确的做法是先算 (N_{stall})再用 (T_k^{real} (kn-1)\Delta t N_{stall} \cdot \Delta t)或者用 CPI 口径。这里特别提醒一点理想公式中 ((kn-1)) 已经包含了装入和排空不要重复计入。有人一看有停顿就把气泡加在总拍数上又另外加了一次 (k) 拍的排空结果多算了。5.3 加速比的分母写错加速比的分母 (T_p) 是流水线执行同样 n 条指令的总时间不是某一段的耗时也不是理想总时间除以段数。我见过一种典型的错法直接用 (1/\Delta t)也就是 (TP_{max})当分母得到的加速比正好是 (\Delta t) 倍看起来还挺整齐其实是量纲都不对。一个自检方法加速比一定是无量纲的纯数而且对于 (n) 条指令的流水线它应该落在 1 和 k 之间理想情况趋近于 k带冒险时低于 k。如果你算出的加速比是 1e9 这种量级基本可以确定分子或分母漏了单位。5.4 非线性流水线启动距离的边界非线性流水线的冲突向量有个隐蔽的边界位宽到底取多少。位宽必须足到覆盖禁止向量里的最大差值否则右移时会把有效位提前移出去。上面第 4 章那个禁止向量 ({1,3,4}) 的例子位宽必须是 4如果只写 3 位位 4 的信息就丢了状态图会算出一个错误的更小启动距离最后实际运行时就会撞车。另一个边界是距离大于位宽怎么办。当启动距离大于位宽时右移会把所有位都移出去结果全为 0也就是任何距离都被允许。这个现象是对的只要间隔足够远任务之间自然就不会撞车。5.5 分支预测失败率的相乘关系分支那一块还有一个高频错误是把分支指令占比和预测错误率简单地相加。正确的算法是链式的[ \text{每次预测失败的平均停顿拍数} \text{分支指令占比} \times \text{预测错误率} \times \text{失败时的停顿拍数} ]举个例子分支占 20%其中 30% 预测失败失败一次损失 2 拍那么平均到每条指令上的停顿就是 (0.2 \times 0.3 \times 2 0.12) 拍。有些人会直接写 (0.2 0.3 0.5) 或者 (0.2 \times 2 0.4)两个都是错的。前者把独立事件加起来了后者漏掉了错误率的条件概率。5.6 复习和上机时的自查清单前面这些坑集中起来就是一份很短的清单。做题前花十秒过一遍能挡掉八成以上的低级错误检查项判断依据Δt 取的是不是最慢段各段耗时列表里取最大值有没有冒险题目是否提到转发、分支、CacheN_stall 是按次数还是频率算词是占比就是频率条数就是次数加速比的分子分母口径是否一致两边都是完成 n 条指令的总时间效率有没有超过 1超过就查分母有没有误乘 n非线性流水线位宽是否足够是否覆盖了禁止向量的最大值5.7 从会算到会用我个人最大的体会是流水线性能分析的价值不在算出一个具体数字而在于它逼你把性能这个词拆成可量化的东西。同一个处理器换一套转发逻辑、换一个分支预测器、换一种调度顺序算出来的 CPI 和吞吐率完全不同。教材上的公式之所以看起来简陋是因为它们假设了太多理想条件一旦你把冒险、停顿、调度这些因素逐项加进去得到的就不再是背出来的结果而是一个能指导你设计取舍的模型。上机做流水线 CPU 的时候很多体系结构课程都会安排一个 5 段 MIPS 流水线实验你会发现仿真波形里那些多出来的气泡和你手算的 N_stall 是完全对得上的。那种纸上的公式和波形上的空拍严丝合缝的瞬间才是真正把这块内容吃透的标志。所以不要跳过时空图哪怕是在赶考试一张画对的图胜过十个记牢的公式。