辩经到了第六篇得先承认一件事这个系列的话题一个比一个容易被教材带了节奏。超标量处理器听了不少静态排流水这个词估计很多人第一次听到时脑子里的第一反应是排流水不是硬件在排吗怎么还有静态的这里面藏着一个理解偏差。绝大多数人接触超标量处理器都是从乱序执行out-of-order execution入门的——Tomasulo算法、保留站、重排序缓冲这些概念都属于动态调度的范畴。于是很容易形成一种印象超标量要挖掘指令级并行必须靠硬件在运行时动态地重排指令顺序。但静态排流水说的恰恰是另一条路让编译器在生成指令流的时候就把指令顺序排好保证硬件用最简单的顺序发射逻辑也能在每个周期尽量填满功能单元。排流水这个词其实对应的是英文里的instruction scheduling翻译过来叫指令调度也有人叫指令排程。它要解决的问题很具体哪条指令什么时候进入流水线、什么时候占用哪个功能单元、什么时候把结果写回以及最重要的是在存在数据依赖的时候拿什么指令去填补等待延迟造成的空缺。说到静态就要追问一句静态是谁的静态答案是编译器的静态。编译器看到了整段代码的指令流它可以在程序运行之前就把每条指令的发射顺序定下来。硬件拿到手的指令流已经是被排过序的。反过来说动态调度里的动态指的是硬件在运行时根据实际的操作数就绪情况临时决定让哪条指令进入执行阶段。这两者没有谁一定更高级。静态调度的好处是硬件简单、功耗低、时序容易收敛代价是编译器得扛下所有而且碰上分支预测失败、Cache缺失这种运行期才发生的事件静态安排好的顺序照样会被打乱。动态调度则正好相反硬件聪明了编译器可以相对笨一点写编译器的人可以少操很多心。所以静态排流水并不是一个过时的古董概念它是一类设计哲学的代名词。理解它你就理解了为什么IA-64安腾要把指令打包成组为什么DSP处理器到今天还在用静态调度也理解了姚永斌《超标量处理器设计》为什么要把这一章放在乱序执行前面。1. 先把排流水这三个字掰扯清楚排流水这个词我第一次在姚永斌的书里看到时其实愣了一下。因为中文教材里讲超标量处理器讲指令调度的不少但用排流水这种说法的确实不多。后来想明白了这个词反而更直白——它的意思就是把指令一条一条地排进流水线。但排这个动作藏着两个关键问题谁来排怎么排谁来排是硬件还是编译器怎么排是按照什么规则决定指令的发射周期和功能单元分配。搞清楚这两个问题静态和动态的界限其实就清楚了。静态调度里负责排的是编译器。编译器在对源代码做完优化、生成目标指令之后还会额外做一道工序把指令的发射顺序重新洗牌。洗牌的依据是目标处理器的时序信息包括每条指令的执行延迟、功能单元的种类和数量、发射宽度等。编译器洗好牌之后硬件只需要保证按顺序发射、按顺序执行就行了。它不需要在运行期做任何判断——哪条指令现在能发射不需要判断编译器已经替我判断完了。动态调度里负责排的是硬件。硬件拿到手的指令流顺序只是大致的真正决定哪条指令占用哪个功能单元、什么时候开始执行的是运行期的调度逻辑。Tomasulo算法的保留站就是一个经典的调度器指令发射到保留站后需要等到操作数就绪才能进入执行阶段。这个等待操作数就绪的判断是硬件在运行期完成的。那么问题来了既然动态调度看起来更聪明为什么还有人走静态这条路答案还是成本。硬件做判断是要付出代价的——面积、功耗、时序收敛的难度。编译器做判断的代价是什么编译时间变长以及需要精确模拟目标机的行为。对于一个性能敏感、但代码模式又相对稳定的场景比如信号处理、通信基带、数字滤波编译时的精确调度往往能换来接近理论峰值的硬件利用率这个性价比是很划算的。还有一点容易被忽略静态调度不是只有一种形式。它可以细分成静态发射 静态执行和静态发射 动态执行的混合形态。经典的六段RISC流水线里很多处理器是静态发射、静态执行指令顺序在进入流水线那一刻就锁死了。再往上看VLIW超长指令字把静态调度做到了最极端——一个指令包里塞进多个操作每个操作固定对应一个功能单元。而不少现代DSP处理器采用的则是编译器调度 硬件部分乱序的混合策略。所以看一个处理器是不是静态排流水不能只看它叫不叫超标量要看指令发射权到底掌握在谁手里。2. 静态调度和动态调度的分水岭到底在哪个环节要比较这两种思路最好的办法不是背定义而是拿一小段指令看两种方案分别怎么对待它。假设我们有这么四条指令R3 R1 R2R5 R3 R4R6 R1 * R4R7 R6 R1第2条指令依赖第1条的结果R3第4条指令依赖第3条的结果R6。这是一个非常典型的依赖图两条链并行。如果处理器每周期只能发射一条指令硬件只能老老实实按顺序执行。但超标量意味着每周期可以发射多条比如2发射。这时候问题就来了如果第1和第2条指令放在同一拍发射第2条会在第1条还没算完的时候就尝试读R3读到的是旧值或者直接触发stall。怎么办动态调度的硬件回答是我没关系我先把第1条和第3条发出去第2条和第4条进保留站等着等第1条的结果通过公共数据总线广播出来保留站里的第2条检测到操作数就绪再自己进入执行。硬件在做的事本质上是等到万事俱备再动手。静态调度的编译器的回答则是我在生成指令流时就不要把第1条和第2条排进同一个发射周期。我给第2条多留几个周期的距离中间穿插第3条、第4条或者别的无关指令。这样一来硬件那套发射逻辑压根不需要判断R3就绪了没有它只需要按顺序把指令送进流水线即可。注意这个差异的实质动态调度把检测依赖、等待操作数的责任放在了硬件里硬件要多花面积做保留站、做寄存器重命名、做乱序提交静态调度把这个责任上移到了编译器硬件只保留最朴素的顺序发射逻辑。责任归属不同导致后面的整个设计取舍都不一样。为什么动态调度在今天的通用处理器里占据主流因为通用程序里的分支行为、访存延迟都是运行期数据编译器在编译时的预测再准也有限。一旦某个分支跳转得跟编译器预期不一样静态排好的指令流就瞬间出现气泡。硬件动态调度的价值恰恰在于它能容忍编译期看不准的信息。但静态调度在特定领域一直活得很好。典型的例子是信号处理、网络处理器、GPGPU的某些调度环节。这些场景的代码循环密集、控制流相对规整编译器可以把指令流调度到接近理想的水平。硬件省下来的面积和功耗可以直接换成更多的计算单元或更长的电池寿命。这里我想插一句做芯片设计的同行在评估面积和功耗时静态调度方案通常比同性能的动态调度方案省20%以上的逻辑资源这个数字来自我自己做过的一个教学级RISC处理器的综合结果虽然是教学级趋势是有参考意义的。这是静态方案最硬核的竞争力。维度动态调度静态调度指令发射顺序硬件在运行时动态决定编译器在编译时静态决定依赖检测保留站/记分牌等硬件机制编译器数据流分析硬件复杂度高面积、功耗、时序压力大低发射逻辑简单编译器复杂度低硬件兜底高依赖精确时序模型对分支预测的依赖需要推测执行配合分支前的调度受限分支后需重新排对访存延迟的容忍度高非阻塞继续发射无关指令低按假定的延迟值调度典型代表Intel Core、ARM Cortex-AVLIW、低功耗RISC核心、多数DSP这个表格做完我想再补充一个容易被误解的点静态调度不等于不超标量。静态调度的超标量处理器依然可以有多个功能单元、每个周期发射多条指令只是这个周期发射哪几条是编译器定好的。硬件只是照着发射而已。所以在术语上静态超标量和VLIW是有区别的静态超标量是一条指令一个槽位的顺序发射VLIW是显式地把多条指令打包到一个超长指令字里。3. 编译器这头怎么排从依赖图到列表调度这一章我们进编译器后端看看静态排流水在软件侧究竟是怎么干活的。3.1 先把数据依赖理干净编译器做指令调度的前提是把指令之间的依赖关系画出来。经典的三类依赖RAWRead After Write第2条读第1条刚写的结果这是真正的数据依赖无法绕过WARWrite After Read第2条写一个寄存器而第1条还要读它如果乱序执行会出错WAWWrite After Write两条指令写同一个寄存器顺序反了会导致最终结果错误WAR和WAW都是名字冲突不是真正的数据依赖。编译器可以通过寄存器重命名来消除——把其中一个操作数换一个不冲突的新寄存器。这一点和硬件里的寄存器重命名思想是一样的只是发生的时间点不同。编译器在DAG图上就能完成这个变换不需要运行期硬件参与。这里有一个初学者容易混淆的点静态调度里消除WAR/WAW的方式通常叫变量重命名或寄存器重命名但它是逻辑寄存器层面的硬件动态调度里也有寄存器重命名但那是物理寄存器层面的。两者解决的问题相同实现层次不同。理解这个层次差异你就能明白为什么有些依赖不用硬件兜底、编译器自己就能消掉。3.2 列表调度最经典的静态排流水算法把所有依赖画成一张有向无环图DAG后编译器会用一种叫列表调度list scheduling的贪心算法来为每条指令分配发射周期。算法的核心步骤很简单根据依赖图标出每个节点的最早可发射周期每一拍从就绪指令集合中挑选优先级最高的一条或多条发射更新依赖图一条指令被发射后它下游的依赖节点的就绪状态可能改变重复直到所有指令发射完毕优先级怎么定最常用的是关键路径优先。依赖图里从当前节点到终点的最长路径长度叫做该节点的深度。深度越大的节点越应该优先发射不然它会在关键路径上拖累整体执行时间。这个策略可以保证整体执行周期数尽量贴近关键路径长度。我放一个简化版的调度前后对比感受会比较直观。假设是单发射机器Load延迟2个周期、ADD延迟1个周期、MUL延迟2个周期。调度前的指令序列LD R1, [x] LD R2, [y] ADD R3, R1, R2 ST R3, [z] LD R4, [a] LD R5, [b] MUL R6, R4, R5 ST R6, [c]如果编译器不做调度第一条ADD要等两次LD的结果至少空转2拍后面的MUL其实跟ADD并没有数据依赖但它排在ADD后面也被迫等着。经过列表调度后编译器会把最后两条LD提前来填Load延迟的槽LD R1, [x] LD R4, [a] LD R2, [y] ; 前两条LD的结果还没到先发射另一条LD LD R5, [b] ADD R3, R1, R2 MUL R6, R4, R5 ST R3, [z] ST R6, [c]这样填完气泡之后流水线的利用率从大约60%提到了接近100%精确数值取决于功能单元数量和发射宽度。这个过程就是排流水三个字最像素级的解释。你甚至可以把编译器干的事理解为为每个时钟周期找一条闲着也是闲着的指令放进去。3.3 软件流水应对循环的静态排流水列表调度处理的是一个基本块一段没有分支的指令序列。但真实程序里有大量循环循环每一次迭代执行同样的指令序列如果每次迭代都单独调度跨迭代的指令重叠会被浪费。软件流水software pipelining解决这个问题。它的思路是把多个迭代的指令层层重叠让第i次迭代的指令和第i1次迭代的指令在同一时刻执行不同阶段就像硬件流水线重叠不同指令一样。循环体的每一次迭代相当于流水线的一级编译器负责把各级的指令排进同一个发射周期里。一个经典的例子是modulo scheduling按迭代间隔IIiteration interval把循环体分成几个阶段每次发射时是多个迭代的不同阶段的指令按序放进发射槽。II越小循环整体吞吐越高。这个问题在编译器领域有大量研究从Rau的modulo scheduling到Huff的HRMS算法都是圈内耳熟能详的名字。循环展开loop unrolling是另一个配合手段把多个迭代拷贝成一段无分支的指令块让列表调度有更大的调度窗口。展开因子不是越大越好太大指令缓存放不下反而得不偿失。我记得有个开源项目里做过测试展开因子从4提到8性能反而掉了就是因为指令缓存I-Cache压力过大。软件流水对循环的加速效果在DSP场景里经常能达到2到4倍。因为循环体里往往有一堆乘加运算互相之间依赖链很长不重叠迭代的话功能单元大部分时间在空等操作数。软件流水一旦把迭代重叠起来乘法器和加法器就能几乎每个周期都忙碌。3.4 目标机描述不到位调度就成了玄学这里必须提一个工程上的坑。编译器做静态调度必须精确知道目标处理器的每类指令的执行延迟、功能单元数量、发射端口限制。这些信息通常以机器描述文件的形式提供给编译器比如LLVM里就是ScheduleModel和机器指令的SchedRW。我写过一个很小的教学模拟器想用LLVM做静态调度提升性能结果发现默认的机器模型把每条指令都当成1周期延迟。优化几乎无效。后来改了机器描述把Load延迟设为3、MUL延迟设为2调度的效果立刻出来了。所以做静态排流水的编译器后端的同学最先要确认的不是算法有多高级而是你手上的目标机描述是不是反映了芯片真实的情况。芯片勘误表没更新、流水线级数改版了、功能单元加了一个这些都会让编译器排出一份纸面完美但实际低效的指令流。这个坑静态方案逃不掉。动态调度因为硬件自己承担检测责任对描述文件的误差容忍度反而高得多。4. 静态排流水躲不开的几个死穴任何方案都有软肋静态排流水的软肋在运行期的不可预测性。这一章把几个典型的死穴摊开来看。4.1 分支编译期看不穿的分叉口编译器在调度一个基本块时做的事情是精确的指令固定依赖图固定延迟固定。但一旦遇到分支编译器只能在两个分支路径上分别调度。真正的运行时会走哪条路、分支预测器猜得准不准编译器统统不知道。更麻烦的是静态调度设计下如果分支跳转成功预取好并排好序的下一个基本块指令直接作废流水线要重新填充。这与动态调度里分支预测失败后需要清空ROB和保留站本质上是同一个问题但静态方案缺少一个运行期重新调度的最后防线。所以静态排流水常见的配套设计是什么延迟槽。MIPS指令集就是典型在分支指令后面固定留出1个槽位编译器必须填一条无论跳不跳都要执行的指令进去。这是把分支指令之后那个周期的调度硬编码进架构层面的设计。编译器填得好的话这一个周期本来是空的填了就是白赚填不了就只能放一条空操作。延迟槽在RISC-V里被舍弃了一个重要原因就是它对静态调度要求太高反而束缚了编译器的优化空间。但MIPS在相当长一段时间内靠着延迟槽和编译器配合把分支开销降得非常低。这是静态调度和架构设计互相咬合的一个历史案例。4.2 访存延迟编译器只能按猜的来Cache命中与否是个运行期事件。编译器不知道某条Load指令是命中L1还是掉到L2甚至主存它只能按某个假定的延迟值来安排后续的依赖指令的位置。假设编译器按L1命中、3周期延迟来调度结果实际执行时Load没命中访问L2需要14个周期。排好的指令流里等待操作数的指令还是会空转。动态调度怎么办同样的场景保留站里等着的那条指令继续等但其它不依赖这条Load的指令还能继续发射流水线不会完全空着。这一点的差距是静态方案与生俱来的只能靠一些运行时机制来弥补比如非阻塞Cache、访存指令提前预取等。所以在实际工程里给静态调度的处理器做编译时通常会用假定L1命中的乐观模型同时尽量把Load指令往前提。因为即便偶尔不命中把Load提前也能让等待期与其他指令重叠。这是一种概率思维赌大部分命中把赌输的损失摊到其它指令的并行执行上。4.3 乱序执行能力为零停顿就是停顿静态排流水让硬件省掉了乱序执行的逻辑代价是硬件不会灵机一动去执行后面的指令。一旦某条指令因为操作数没到、功能单元忙、访存阻塞等原因停在流水线里它后面的指令全都得停下来。我做一个比喻动态调度像是一个餐厅里有个特别会统筹的大堂经理哪桌客人菜没上齐他会先去安抚别的桌静态调度像是把所有人的上菜顺序在早晨就打印成了流程图只要有一盘菜晚了后面全等着。这个比喻有点夸张但很能说明为什么通用处理器最终选了动态调度。这个死穴也解释了为什么静态调度通常和简单的顺序流水线绑定在一起。一旦进入多发射、多功能单元的领域顺序执行的停顿代价会被放大很多倍。因为停顿的不是一个功能单元而是整条流水线的发射带宽全部浪费。4.4 指令集复杂性带来的调度困难还有一层障碍来自指令集本身。一个指令格式不规则、寻址方式繁多、寄存器编码花哨的指令集会让编译器在解码、计算依赖、估算延迟时都变得更困难。静态调度的猪队友就是CISC风格的高熵指令集。这也是为什么VLIW和很多静态调度处理器通常搭配精简、规整的指令集设计。另外提一句x86虽然指令集很复杂但现代x86处理器内部普遍使用微码翻译成类似RISC的微操作再做动态调度。这不是静态调度恰恰是以动态调度的方式去消化复杂指令集。从编译器视角看x86的后端调度经历了一个从硬件微码调度到指令窗口调度再到现代乱序调度的演变。5. 静态排流水没有消失它在这些地方活着聊完了死穴聊聊静态排流水在当代芯片中实实在在的栖息地。它不是博物馆文物而是好几条产业线的主力。5.1 VLIW/DSP静态调度的主战场超长指令字VLIW架构把编译器负责排流水推到了极致。一条指令字里打包多个操作每个操作对应一个功能单元发射槽与功能单元一一对应。编译器必须在编译时精确决定每个槽位放什么操作放不进去就放空操作。TI的C6000系列DSP、Qualcomm的Hexagon DSP、早期的一些网络处理器都是这个路数。它们的应用场景大多是循环密集、控制流简单的信号处理代码静态调度能发挥出极高效率。而且因为没有复杂的调度硬件芯片面积小、功耗低对嵌入式场景非常友好。我在做无线基带算法加速时曾经为了把一个FFT的软件流水II压到最小连续调了好几天编译器编译选项和循环体结构——那种手工跟编译器一起排流水线的体验和写动态调度模拟器完全不一样但你确实能精确地控制每一个槽位。5.2 GPU大规模并行中的静态调度影子NVIDIA的GPU指令调度器虽然是硬件动态的但编译器的作用极为关键。NVVM后端会做大量的指令调度尽量让每个线程的指令流在运行时少产生分支、少产生访存冲突。这种编译器排好 硬件有限度动态的混合模式处处能看到静态排流水思想的影子。有意思的是GPU里单条指令流其实是高度规整的一大波线程在同一时刻执行同一条指令SIMT模型如果编译器不把指令排整齐让硬件频繁等待操作数整个warp的执行效率都会拖垮。所以在GPU的编译流水线里指令调度器的优先级非常高。5.3 低功耗设计者的最爱静态调度最大的优势是硬件简单。复杂度低意味着面积小、漏电少、时序容易收敛。在可穿戴设备、IoT处理器、以及某些讲究每毫瓦性能比的专用加速器里设计团队往往宁可多花几个月调编译器也不愿在硅片上多堆一套乱序执行单元。我记得有一次跟一个做MCU的哥们聊他说他们产品线里卖得最好的那颗内核流水线就是静态调度的四发射编译器是自家魔改的一套工具链。前几年很多人觉得静态调度在通用CPU已经死了但他那颗内核一年出货还在千万级。原因就一条省功耗省面积就是省成本。5.4 编译器后端的通用做法还有一个很多人没察觉的地方即使是全乱序的CPU编译器后端的指令调度器也仍然在起作用。因为乱序窗口不是无限大的调度器的重排序能力受到ROB、保留站等资源容量的限制。如果编译器能把依赖距离拉开让指令在进入乱序窗口后不至于一眼看去全是依赖等待乱序执行的硬件效率会高不少。所以别把静态调度和动态调度理解成非此即彼。现代高性能处理器普遍是混合体底层以动态调度兜底上层用编译器把指令流排得更整齐。静态排流水作为一种编译器侧的优化技术地位从来没动摇过。6. 姚永斌教材的读法静态调度这章不是过渡章节最后聊聊大家都关心的姚永斌《超标量处理器设计》该怎么读。这本书在中文体系结构圈子里地位很高很多人手里都有实体书或电子版。我自己那本纸质版已经翻得有点脱胶了书架上是常驻书位。这本书的结构是先讲超标量处理器的基本概念、流水线基础、相关性分析然后是静态调度然后进入动态调度Tomasulo、寄存器重命名、ROB再往后是分支预测、存储系统、多核一致性等等。很多读者到静态调度这一章时会觉得这不是编译器的事吗跟处理器设计有什么关系于是草草翻过去直接奔乱序执行去了。但我建议稍微停留一下至少弄清三件事。第一为什么静态调度章节会被放在动态调度之前因为动态调度解决的核心问题恰恰是静态调度解决不了的问题。你不先理解编译器排出来的指令流在运行期会出哪些问题你就理解不了硬件为什么要花大代价做保留站和重排序。这个顺序不是随意的是顺着问题链条走的。第二书上列举的静态调度对硬件的要求——多发射、多功能单元、发射控制逻辑——是理解后续乱序执行硬件复杂度的一个基准线。你可以在脑内给静态方案打个得分然后看动态方案为了补齐哪些短板额外支付了多少硬件成本。看完动态调度那章再回头看静态调度往往会有一种原来如此的顿悟。第三静态调度章节的练习题值得动手做。画依赖图、填列表调度、算每拍发射了哪几条指令这个过程是训练流水线直觉最好的方式。我见过不少同学上来就啃Tomasulo结果连RAW和WAR都分不清楚回头补静态调度顿时觉得天都亮了。还有一个私人的建议读这本书时手里最好备一块白板把每一章的处理器结构图画一遍特别是静态调度那章的发射逻辑图。画一遍你就会发现所谓的静态其实只是把动态检测的电路换成了对指令流的顺序信任而已。一旦建立了这个模型再看后面动态调度那一堆硬件结构就会觉得条理清晰很多。如果让我用一句话总结这章的读后感那就是静态排流水逼迫你用最朴素的方式思考指令应该在哪个周期发射这种思考练出来的肌肉记忆在你看动态调度那章时会成倍偿还。