Sherfiter's wiki for fun

第 6 章 · 指令流水线

先看一个我当年死活想不通的实验。对同一个数组求和,循环里带一个分支:

for (int i = 0; i < 262144; ++i) {
    if (data[i] >= 128) sum += data[i];
}

两份数据,内容一模一样,只是一份有序、一份乱序,同一台机器上测出来的典型结果:

排序后的数组:  0.32 秒
乱序的数组:    1.14 秒

差了三倍多。算法一样,数据规模一样,循环次数一样,比较运算也不挑数据的顺序,时间从哪多出来的?答案在 CPU 的流水线和它背后的「赌徒」:分支预测器。本章讲清楚流水线怎么把 CPU 变快、三种会打乱它的「冒险」,以及为什么一个 if 的数据分布能决定性能差几倍。这是全课第二个建议慢读的章节。

6.1 流水线:洗衣店的比喻成真

洗衣服有四个阶段:洗衣机洗、烘干机烘、叠、收。一个人洗四批衣服,可以一批做完再做下一批,也可以第一批进烘干机时就把第二批塞进洗衣机。后者不省任何单批的时间,但四批衣服的总时间砍到接近四分之一。CPU 执行指令同理:第 5 章把一条指令拆成五拍(取指 IF、译码 ID、执行 EX、访存 MEM、写回 WB),流水线给每拍配一套专属硬件,让五条指令同时在场、各占一拍:

周期:    1    2    3    4    5    6    7
指令1   IF   ID   EX   MEM  WB
指令2        IF   ID   EX   MEM  WB
指令3             IF   ID   EX   MEM  WB
指令4                  IF   ID   EX   MEM  WB

从第 5 拍起,每一拍都有一条指令完成,吞吐逼近 1 IPC(每周期一条指令)。n 条指令走 k 级流水线,总时间约 (k + n - 1) 拍,对比多周期的 n×k 拍,快了接近 k 倍。代价是硬件翻倍、时序更紧张,以及本章主角:指令之间开始互相干扰。

6.2 三种冒险:流水线打结的三种方式

流水线的理想是「每拍稳稳完成一条」,但指令是会互相使绊子的,教材称冒险(hazard),共三类。

结构冒险:两条指令要抢同一件硬件。经典案例是取指和访存都要走内存:第 4 条指令在 IF 取指令时,第 1 条正好在 MEM 读数据。解法干脆:拆两个存储口,指令 Cache 和数据 Cache 各一个(第 7 章的 L1 就是这么分的)。

数据冒险:后面的指令要用前面那条还没算完的结果。真依赖(RAW)是唯一在顺序流水线里真实存在的:

add a0, a1, a2     ; a0 在 EX 末尾才算出,WB 才写回
sub a3, a0, a4     ; 它在 ID 就想读 a0,晚了三拍

(WAR、WAW 在顺序流水线不会出事,那是乱序执行时代的课题,知道名字即可。)

控制冒险:分支指令要到 EX 甚至更晚才知道「跳不跳、跳到哪」,但流水线等不了,IF 每一拍都必须取出下一条指令。顺序执行时「下一条」当然就是 PC+4,可分支一出现,这个假设随时作废。

6.3 转发与停顿:数据冒险的两味药

转发(forwarding) 是主力药。意识到一个问题后它几乎是免费的:ALU 算出的 a0 其实已经躺在 EX 级的输出锁存器里了,何必等它绕道寄存器文件?直接拉一根线,把 EX/MEM 级间锁存器里的值旁路给下一条指令的 ALU 输入:

add a0,a1,a2:   IF  ID  EX  MEM  WB
                            │
sub a3,a0,a4:       ID  EX ◄┘ a0 直接从锁存器喂进来

大多数 RAW 一转发就没了,零停顿。

停顿(stall) 是兜底药,转发救不了的才轮到它。典型是 load-use:load 的数据要到 MEM 末尾才到手,紧接着的下一条指令 EX 就要用,转发线也追不上:

ld  a0, 0(a1)
add a3, a0, a4    ; 只能插一个气泡,空转一拍

编译器的对策是指令调度:把一条不相干的指令塞到 load 和它的使用者中间,把气泡填满。你在第 10 章读 gcc 输出的汇编时会发现指令顺序经常和源码不一样,不少就是这类调度。

6.4 分支预测:开头那个实验的真相

现在回到实验。那个 if 每轮循环都要「问一次方向」,流水线等不起真答案,于是赌:预测跳还是不跳。赌对了零代价;赌错了,已经进了流水线的后续指令全是废牌,得整体冲刷,损失等于流水线深度(现代 CPU 十几到二十拍)。

预测器是流水线时代的隐形发动机,两层结构值得认识:

  • 分支目标缓冲(BTB):记住每条分支指令「上次跳去了哪」,命中就直接朝那里取指,连目标地址的计算都省了。
  • 两位饱和计数器:每条分支配一个两比特状态机,预测对加一、错减一,连续错两次才翻转预测方向。这个「惯性」设计专为循环优化:循环体 100 次里 99 次跳、1 次不跳,一位计数器会在进出循环时各错一次,两位计数器把错误同样压到这两个边界,但中途一次偶然反向不会再多错。

现在解释实验:有序数组里,比较结果先是一长串「不跳」,再是一长串「跳」,两位计数器在两个边界各错一次,接近 100% 命中;乱序数组里跳与不跳五五开掷硬币,预测器命中率塌到 50%,等于每隔两条指令冲刷一次流水线。三倍的时间差,全部来自这两次「赌局胜率」的区别。

这个实验还有个后续值得知道:2018 年闹得沸沸扬扬的 Spectre 漏洞,攻击面正是预测执行的副作用。CPU 赌错后会冲刷指令,但冲刷前的访存已经在 Cache 里留下了痕迹,攻击者测 Cache 访问时间就能把「本不该读的数据」侧信道偷走。分支预测这条性能生命线,也是安全史的转折点。

常见错误

  • 在热循环里写「数据顺序不可控」的分支。若逻辑允许,先排序再处理、或把分支改成无分支写法(条件移动、查表),速度差不是百分之几,是几倍。
  • 以为循环里加个 if 无所谓。if 的「可预测性」比「有没有」更关键,稳定走向的 if 几乎免费,随机走向的 if 是性能刺客。
  • 把 load 的结果马上用。a[i] 刚取出来立刻参与运算,在深流水机器上可能吃一个停顿;适当拉开距离(或交给编译器 -O2)。

练习

  1. 手算:五级流水线执行 100 条指令,无冒险要多少拍?若第 50 条是 load-use 停 1 拍、第 80 条分支预测错误(冲刷 10 拍),总共多少拍?
  2. 手算:把上题分支的预测错误率从 50% 压到 5%(262144 次判断的实验场景),每错一次损 15 拍,总共能省多少拍?和 6.4 实验的三倍差距对上号了吗?
  3. 动手:把 6 章开头的实验代码跑一遍(记得 gcc -O1 或 -O2,数据 26 万规模),再给循环里加一句「把数组先排序」的版本,验证时间差;顺便用 std::sort/qsort 的时间,算算「排序 + 快求和」和「乱序慢求和」谁赢。
  4. 思考:流水线越深,主频越高,但冲刷代价越大。Pentium 4 搞 31 级深流水线翻车了,Apple M 系列用 10 来级照样快。深浅之间到底在权衡什么?(提示:每级的逻辑深度、分支误预测频率、功耗。)
豫ICP备2026027944号