深入理解CPU乱序执行：从流水线停滞到指令级并行优化

如果你写性能敏感代码多半经历过这种迷惑循环明明按顺序一行一行写逻辑依赖也清清楚楚可一上perf看统计后端停顿backend stall高得吓人。你说这段代码到底卡在哪答案有时很反直觉——CPU 根本没有老老实实按你的指令顺序干活它内部在乱序执行Out-of-Order Execution。如果 CPU 真的严格按程序顺序执行那么任何一次缓存未命中几百个周期、一条长延迟的除法几十个周期、一次分支猜错十多个周期都会让整条流水线干瞪眼。于是从上世纪 60 年代的 CDC 6600、IBM 360/91 开始处理器设计者就想明白了一件事与其傻等不如先把不依赖当前结果的后续指令捞上来算掉最后再按原始顺序对外交差。这也是为什么现代 CPU 能倒着干活还又快又对。这篇文章把乱序执行的完整链路拆开指令之间的依赖关系怎么识别、寄存器重命名为什么是消除假相关的关键、保留站和公共数据总线如何调度、重排序缓冲区怎么保证精确异常。对做性能优化、编译器后端或者底层系统开发的人这几块内容属于必须啃下的硬骨头。1. 流水线空泡背后的无奈顺序执行的 CPU 究竟浪费了什么1.1 五级流水线与每周期一条指令的理想乡教科书上最经典的流水线是五级取指IF、译码ID、执行EX、访存MEM、写回WB。理想情况下每周期完成一条指令CPIcycles per instruction每指令周期数等于 1。再往后超标量设计让 CPU 每周期可以发射多条指令到不同执行单元IPC 还能大于 1。这也是为什么主频相同新处理器更快——它不只靠频率还靠每周期能塞进更多有效指令。但理想乡的前提是所有指令都稳定执行、互不干扰。现实是任何一条慢指令都会在顺序执行的流水线里砸出一串空泡pipeline bubble。打个比方一条流水线上有人卡住了后面所有人只能站着等哪怕他们手里的活其实互不相干。1.2 延迟的贫富差距慢指令怎么把整条流水线按住不同操作的延迟差异可以用贫富差距来形容而且差距是数量级的。下面这张表是我经常拿来跟同事对标的典型延迟数据操作典型延迟生活类比L1 缓存命中4-5 周期手边的东西一伸手就够到L2 缓存命中12-15 周期起身去抽屉里翻找L3 缓存命中30-60 周期下楼取个快递主存储器 DRAM100-400 周期网购等快递送到整数加减1 周期眨一下眼整数乘法3-4 周期心算两位数乘法整数/浮点除法20-40 周期手工做长除法分支预测猜错惩罚15-30 周期路走错了掉头重来看这三行汇编ld r1, [r0] ; 访存指令假设 L2 未命中要等 200 周期 add r2, r1, 1 ; 依赖 r1必须等 sub r3, r4, r5 ; 完全无关却排在后面在严格的顺序执行核心上sub只能眼巴巴看着前两条走完。load等了 200 周期sub实际花了 200 多周期才轮到。如果这段代码在一个长循环里反复执行白等的时间会累积成巨大的性能黑洞。乱序执行想解决的核心矛盾就一句话等待等于浪费与其站着等不如去找不需要等的活先干。2. 指令间的三类相关哪些能乱序哪些必须排队要乱序第一步是搞清楚哪些指令能乱、哪些指令绝对不能乱。这就要说到指令之间的相关dependency一共三大类数据相关、名字相关、控制相关。2.1 RAW真正的依赖锁链绕不过去RAWRead After Write写后读是最硬的真相关。指令 I2 要读的寄存器恰好是 I1 要写的那 I2 就必须等 I1 算完拿到值。比如add r1, r2, r3 ; I1r1 r2 r3 sub r4, r1, r5 ; I2需要 I1 算出来的 r1这就像煮面必须等水烧开电磁炉再智能也变不出开水来。RAW 是程序数据流的本质任何硬件手段都无法消除只能等。它是制约指令级并行ILPInstruction-Level Parallelism的根本上限。2.2 WAR 与 WAW看似冲突实则是名字打架再看这两对指令mul r1, r2, r3 ; I1r1 r2 * r3 add r2, r4, r5 ; I2r2 r4 r5I1 要读 r2I2 要写 r2。按程序顺序I1 必须先读到旧 r2 的值。如果 I2 抢跑先把新值写进 r2I1 就读错数据了。这种写后读冲突叫 WARWrite After Read也叫反相关anti-dependency。再比如mul r1, r2, r3 ; I1写 r1 xor r1, r8, r9 ; I4也写 r1两条指令都写 r1程序最终要的是 I4 的结果。如果它们乱序执行I1 后完成就可能把 I4 的结果覆盖掉这种写后写冲突叫 WAWWrite After Write也叫输出相关output dependency。关键点来了WAR 和 WAW 本质上只是名字打架。它们冲突的根源在于架构寄存器太少——x86-64 对程序员只暴露 16 个通用寄存器ARM64 也只有 31 个。寄存器名 r2 只是个名字而已硬件完全可以在内部再造出几百个幕后寄存器让每条要写值的指令各用各的互不抢名字。这就是寄存器重命名的意义。2.3 寄存器重命名给每个新值发一把新笔重命名的具体做法是架构寄存器程序员看到的那 16/31 个只作为门牌号真正存数据的是物理寄存器physical register file现代核心里通常有两三百个多的能到五百个。硬件里有一张寄存器别名表RATRegister Alias Table记录当前架构寄存器 → 哪个物理寄存器。当一条指令要写 r1 时重命名阶段会从空闲物理寄存器列表里取一个新的物理寄存器 P_new把 RAT 里 r1 的映射更新为 P_new。而之前读过 r1 的旧指令在重命名时已经拿到了旧映射也就是它们会读那个被 P_new 替换下来的旧物理寄存器。于是 WAR 冲突凭空消失——大家各读各的谁也不用等。用前面四行例子推演一遍重命名后的效果指令实际写入的物理寄存器效果I1: mul r1, r2, r3写入 P10RAT[r1] P10正常执行I2: add r2, r4, r5写入 P11RAT[r2] P11和 I1 读到的旧 r2 不冲突可以立刻执行I4: xor r1, r8, r9写入 P12RAT[r1] P12和 I1 的 WAW 消失也可以立刻执行最终提交时按程序顺序走I4 的 P12 被转正为架构 r1I1 的结果则被回收覆盖。整个流程对外部完全透明程序看到的 r1永远等于最后一条写 r1 的指令的值。2.4 控制相关分支是最大的变数条件分支、跳转、函数调用都属于控制相关。顺序执行处理器遇到分支要么死等条件算出来要么提前猜。现代处理器选择猜——用分支预测器猜方向然后沿着猜出来的路径继续取指和执行。猜对了等于免费猜错了就要把后面所有推测性执行的结果全部作废重新走正确路径。乱序执行和分支预测是一对搭档预测器负责提供可以继续往下走的信心乱序引擎负责在信心之上并行执行。这个搭配后面第 4 节还会详细讲。3. 乱序的工厂车间重命名、保留站与广播总线的工作方式理解了依赖关系再看乱序执行的硬件流水线就顺理成章了。现代乱序核心的指令流大致是取指IF→ 译码Decode→ 重命名/分配Rename/Allocate→ 分发Dispatch→ 调度器/保留站Scheduler/RS→ 执行Execute→ 写回Writeback→ 提交Commit/Retire真正乱的部分发生在调度器到执行这一段前面和后面都是规规矩矩的。3.1 重命名/分配阶段给每条指令上户口指令经过译码后会进入重命名与分配阶段。这个阶段干四件事为写目的寄存器的指令分配一个新的物理寄存器更新 RAT 映射在重排序缓冲区ROB里分配一个条目条目序号就是这条指令的程序顺序提交时靠它来排队如果是访存指令还要在 load/store 队列里占一个位置。这一步把程序顺序和物理存储位置彻底解耦是后面所有乱序操作的户籍簿。3.2 保留站操作数不齐就原地待命重命名之后的指令会被分发到保留站Reservation StationRS也常叫调度器scheduler。保留站的每个条目类似一个储物格存放指令的操作码、源操作数要么已经拿到值要么还挂着等待某个物理寄存器的结果的标签、目的寄存器等信息。调度器的规则很简单也很反直觉不是谁先来谁先走而是谁的操作数先齐谁先走。只要某条指令的全部源操作数都就绪并且有空闲的执行端口调度器就把它发射出去执行。这就是倒着干活的核心——后面的sub和前面的load没有依赖关系它就可以在 load 等待内存的几百个周期里抢先跑到执行单元上算完。选择发射哪条就绪指令也有讲究现代核心普遍采用最老优先oldest-first策略防止年轻指令反复插队把老指令饿死同时还能兼顾公平性和时序收敛。3.3 公共数据总线结果一出来全车间都听得见保留站里等待的源操作数靠什么方式被通知到了这是 Tomasulo 算法1967 年 IBM 360/91 引入的精华——公共数据总线Common Data BusCDB。任何执行单元算完一个结果都会把结果值 对应的物理寄存器标签广播到总线上。所有保留站条目在同一时刻监听总线当广播标签与自己等待的标签匹配时就在同一个周期内把数据锁存下来。这个机制就像小区大喇叭喊3 栋的快递到了请下来拿——所有等这个包裹的人同时听见不需要物业挨家挨户敲门。现代核心里的总线早就不是一根共享线了电气上广播延迟太大取而代之的是分布式的 operand collector、点对点环形网络这类结构但核心思想依然是标签匹配 广播唤醒。3.4 四行汇编的乱序实验手把手推演时间线理论说了一堆不如动手推演一个完整例子。这四条指令假设内存地址[r2]不在 L1/L2 缓存里访问主存需要约 200 个周期ld r1, [r2] ; I1从内存读数据到 r1长延迟 mul r3, r1, r5 ; I2r3 r1 × r5依赖 I1RAW add r4, r8, 1 ; I3r4 r8 1完全没有依赖 sub r6, r2, r7 ; I4r6 r2 - r7完全没有依赖顺序执行的局面是I1 卡 200 周期 → I2 再等 4 周期 → I3、I4 在后面排队总耗时 200 周期起步。乱序执行的时间线则完全不同周期发生了什么0-1四条指令完成译码、重命名分配好各自的 ROB 条目进入保留站2I1 被发射到访存单元开始向内存要数据I2 因为缺 r1 的结果在保留站待命3I3 源操作数已齐r8 和立即数发射到 ALU1 个周期后算完4I4 源操作数已齐发射到另一个 ALU算完5-201I1 在内存子系统里排队等数据I2 继续在保留站等 r1202I1 数据返回并广播结果I2 在同一个周期捕获 r1203-206I2 发射到乘法器4 个周期后算完广播结果207四条指令按 ROB 里的原始顺序依次提交程序状态与顺序执行完全一致看懂这张表你就抓住了乱序执行的精髓I3、I4 早早算完却不会抢先交差它们的结果被暂存在一边等 I1、I2 这些老指令先提交。执行阶段尽管乱提交阶段绝对不乱。这也回答了标题里又快又对的一半——快是因为把等待时间用阴影里的独立指令填满了对是因为有顺序提交兜底。4. 怎么保证又快又对顺序提交、精确异常与分支推测回滚4.1 重排序缓冲区乱序干完活排队交差重排序缓冲区Reorder BufferROB是乱序执行安全绳的关键结构。它在重命名阶段按程序顺序为每条指令分配一个条目条目里保存这条指令的状态执行完没有、结果值、目的物理寄存器。执行单元算完结果后指令进入已完成但未提交状态待在 ROB 里排队。提交commit/retire永远从 ROB 的头部开始只有 ROB 头部那条指令才能转正。转正意味着把物理寄存器的值正式变成架构状态、回收旧物理寄存器、对于 store 指令把数据真正写入缓存或内存。所以乱序执行的设计可以概括成一句话执行可以乱提交必须按序。你从程序员视角看到的 CPU永远是一台严格执行程序顺序的机器。4.2 精确异常程序计数器必须准确指到肇事现场为什么 ROB 的顺序提交这么重要除了语义正确性还因为操作系统和调试器需要一个能力精确异常precise exception。假设 I1 是一条从非法地址读数据的 load它引发缺页异常但 I3 这条年轻指令早就执行完、结果都广播过了。如果此时中断进来CPU 必须告诉操作系统异常发生在 I1 这条指令上而且 I3 执行的副作用一点都不能残留。做不到这一点的 CPU操作系统和编译器根本没法写。ROB 让这件事变得干净利落I3 虽然执行完了但结果还留在物理寄存器或 ROB 里没有提交。一旦检测到 I1 异常处理器就把 ROB 里 I1 之后的所有年轻指令全部清空把 RAT、物理寄存器映射回滚到 I1 之前保存的检查点然后跳转到异常处理程序。整个过程对软件完全透明。4.3 分支预测错误投机执行需要后悔药乱序执行通常会配合投机执行speculative executionCPU 预测分支方向后把预测路径上的指令也丢进执行流水线。这些指令都是推测性的它们的执行结果同样被 RO B 扣着没有提交。当分支条件真正算出来时如果发现预测错了ROB 会把该分支之后的所有指令统统丢弃重新从正确目标地址取指。一次猜错的代价是流水线清空加重新填充大约 15-30 个周期。这也是现代分支预测器TAGE、感知机预测器、BTB、RAS把准确率堆到 95%-99% 的原因——猜错的次数越少这个后悔药的副作用就越小。有个反直觉的规律要注意乱序窗口越大投机失败时被丢弃的指令越多浪费也越狠所以窗口不是越大越好。4.4 内存访问的插队规则Load/Store 也不能随便乱来寄存器运算可以靠重命名和 ROB 完美屏蔽乱序但访存指令天生有个麻烦——CPU 不能随便把 store 提前写进内存。假如一条 load 越过前面的 store 执行而两边的地址恰好指向同一个位置load 就会读到旧值程序语义就崩了。反过来等所有 store 都提交再执行 load又会拖慢性能。现代核心的做法是搞一个 store buffer存储缓冲区store 先提交到这个缓冲区真正写缓存/内存要等到它成为 ROB 头部提交之后。年轻一点的 load 可以提前执行但必须跟前面未提交的 store 做地址比对如果地址不冲突load 随便跑如果地址疑似冲突load 可以从 store buffer 里直接转发数据store-to-load forwarding相当于走个小后门如果地址还无法确定就得靠内存消歧预测器猜猜错了整个流水线又要推倒重来。注意乱序执行保证的是单线程看起来按顺序执行的正确性。多线程场景下CPU 和编译器仍然会做内存重排不同架构的内存序模型也不同x86 偏强ARM/RISC-V 偏弱。跨线程同步必须靠原子操作和内存屏障不能依赖代码里写的指令先后顺序。5. 现代乱序核心的家底硬件规模、参数对比与性能代价5.1 一个乱序核心都藏着哪些重资产每次看到大核架构图我都会感叹乱序执行真的是拿晶体管堆出来的。一个典型的现代乱序核心至少包含这些关键结构寄存器别名表RAT几十项映射每个周期要支持多条指令同步读写物理寄存器堆PRF200-500 个 64 位物理寄存器每个寄存器有多个读端口和写端口这是面积和功耗的大户重排序缓冲区ROB200-600 条指令的容量决定乱序窗口能在飞多少条指令调度器/保留站80-140 个条目每个条目都要能监听广播总线并做标签比对Load/Store 队列几十到上百条负责访存顺序的追踪和转发执行端口8-16 个ALU、分支、访存、浮点、SIMD 各占若干分支预测器BTB、TAGE 多级表、RAS 返回栈几千到几万条预测记录。这些结构还都得是多端口设计因为每个周期要同时服务多条指令。端口一多面积和功耗指数级上涨。可以说乱序执行是现代处理器单核性能最强也是最贵的奢侈品。5.2 各家乱序窗口有多大一份公开数据对照表不同微架构的乱序能力差异很大最直观的指标就是 ROB 大小。我整理了近几代知名核心的公开数据供参考数据来自各家白皮书、WikiChip 和第三方 die-shot 逆向统计口径不完全一致看量级即可微架构发布年份ROB 容量物理寄存器堆调度器条目前端宽度Intel Skylake2015224180974-wideAMD Zen 32020256192964-wideAMD Zen 42022320224886-wideIntel Golden Cove2021512280976-wideARM Cortex-X22021288224约 1005-wideApple Firestorm2020630约 354待确认8-wide这些数字背后能看出一个清晰趋势Apple 的 Firestorm 核心把乱序窗口堆到了 600 多条物理寄存器堆也相当庞大这正是 M1 系列单核性能一骑绝尘的重要硬件基础。而 ARM 的 Cortex-X2、AMD 的 Zen 4 走的是相对克制的路线用更小的窗口换取功耗和面积的平衡。5.3 乱序窗口越大越好吗现实没这么简单既然乱序窗口越大越能发现并行指令那堆到几千条行不行工程上不行原因有四个复杂度非线性增长ROB、物理寄存器、调度器都是多端口结构容量翻倍仲裁逻辑和布线的复杂度远不止翻倍投机失败代价变高分支猜错一次窗口越大被丢弃的年轻指令越多浪费的周期越多物理实现拖慢主频大容量多端口寄存器堆和调度器的访问延迟会变长反而压低了时钟频率一加一减可能不划算ILP 有天花板乱序执行只能挖掘程序里本来就存在的指令级并行。如果一段热循环里全是串行依赖链比如链表逐节点累加窗口再大也只能坐等。这最后一点也解释了为什么现在处理器厂商都搞混合架构大核用超大乱序窗口榨性能小核用很小的乱序窗口甚至顺序执行换能效。Apple 的 Icestorm 效率核、Intel 的 E-core 走的都是这条路。5.4 软件层面能薅到的羊毛围绕乱序思维做优化懂了乱序执行很多性能优化动作就有了理论依据不再是玄学。我总结几条实战中直接可用的主动给硬件制造并行循环展开、把sum sum a[i]改成两个独立累加器最后再合并都是在拆短 RAW 依赖链让乱序引擎有更多独立的活可干找到程序的关键路径把热路径上的串行指针追链、层层解引用去掉或者用并行的哈希/索引替代等于直接缩短了乱序核心必须等待的最长依赖链提高内存级并行一次循环里多发几个独立的 load让多个缓存未命中同时在进行中MLP乱序窗口才能把几百个周期的内存延迟藏起来会用 perf 定位停顿用perf stat -e stalled-cycles-frontend,stalled-cycles-backend这类计数器如果后端停顿backend stall偏高多半就是依赖链太长或者 ILP 不足乱序引擎没活可干而不是缓存不够大别把指令顺序当语义单线程里 CPU 帮你兜底顺序多线程里没有这套兜底正确性必须靠屏障和原子操作。最后分享一个我真实踩过的优化经历。之前调一条图像处理的热路径发现后端停顿占比极高代码看着很简洁就是acc acc * k bias[i]这种串行累加。乱序窗口命令保留站把不相干的指令往前塞但这个循环里几乎所有指令都被这条长依赖链拴着根本找不到并行。我把单累加改成两个独立累加器交替计算最后再合并后端停顿直接降了一个数量级。乱序窗口再大也架不住你硬生生写出一条串行的长锁链。理解 CPU 为什么倒着干活说到底是为了让你写的代码恰好落在它最擅长发挥的地方。