指令级并行性
指令级并行性
指令级并行性(Instruction-Level Parallelism, ILP)指的是:在同一段程序里,多条指令其实并没有先后依赖,可以同时在 CPU 里执行。现代处理器几乎都靠 ILP 提速,而编译器的一项核心工作,就是把源代码里潜在的并行性"挖"出来,用硬件能吃得下的方式喂进去。
通俗理解:想象食堂打饭窗口。传统单指令执行像一个人从头做到尾——刷卡、打菜、结账、离开,下一个才开始;流水线像四个窗口分工,前一个人在结账时,后一个人已经在打菜。而 ILP 更进一步:如果打菜和刷卡互不相关,就同时进行,让每个窗口一刻不停。
一条指令在 CPU 内部通常要走五个阶段:取指(IF)、译码(ID)、执行(EX)、访存(MEM)、写回(WB)。五段流水线的理想吞吐是每周期完成一条指令。但只要相邻指令之间有依赖或资源冲突,流水线就会"气泡"(stall),实际吞吐远低于理论值。
流水线的三种冒险
冒险(hazard)是流水线停顿的根因,分三类:
- 数据冒险:后一条指令要用前一条的结果。又分 RAW(读后写,真依赖)、WAR(写后读,反依赖)、WAW(写后写,输出依赖)。RAW 是真实的信息流,必须等;WAR/WAW 只是"名字冲突",可以通过寄存器重命名消除。
- 控制冒险:分支指令要等到执行阶段才知道该跳哪里,之前取进流水线的指令可能全白取。
- 结构冒险:两条指令想同时用同一个功能单元(比如同一个乘法器、同一个内存端口),只能排队。
编译器主要能缓解数据冒险和控制冒险,结构冒险更多由硬件调度器处理。
编译器视角的数据依赖
编译器在做指令调度前,会先建立数据依赖图:节点是指令,边是依赖关系。
i1: R1 = R2 + R3 ; 生成 R1
i2: R4 = R1 * 2 ; RAW,依赖 i1 的 R1
i3: R1 = R5 + R6 ; WAW(对 i1)+ WAR(对 i2)
RAW(i1 到 i2)是真依赖,无法移除;WAW 和 WAR 只是因为复用了寄存器 R1 才产生的假依赖——只要把 i3 的目标改成 R7,两条假依赖立刻消失,i3 就能提到 i2 之前甚至和 i1 并行执行。这就是寄存器重命名的价值:编译器在 SSA 形式下天然回避了假依赖,硬件在乱序执行时也会做重命名。
循环级并行:展开与软件流水
循环是并行性最丰厚的矿区,两把常用工具是循环展开和软件流水。
循环展开把连续几次迭代合并成一次,减少分支开销、暴露更多可调度指令:
// 原始
for (int i = 0; i < n; i++) a[i] = b[i] + c[i];
// 展开 4 遍
for (int i = 0; i < n; i += 4) {
a[i] = b[i] + c[i];
a[i+1] = b[i+1] + c[i+1];
a[i+2] = b[i+2] + c[i+2];
a[i+3] = b[i+3] + c[i+3];
}
展开后,4 组加法互不依赖,可以塞进不同的功能单元同时执行。
软件流水更进一步:把一次迭代拆成 load、add、store 三段,让不同迭代的这三段在时间轴上交错重叠。稳态阶段每个周期都有一条 load、一条 add、一条 store 在跑:
时钟: 1 2 3 4 5
迭代 i: load add store
迭代 i+1: load add store
迭代 i+2: load add store
流水启动(prologue)和排空(epilogue)需要少量补偿代码,但稳态吞吐从"3 周期/迭代"降到"1 周期/迭代"。
跨基本块调度
局部调度只在一个基本块内重排指令,遇到分支就止步。但很多热点程序的基本块只有几条指令,可挖的并行度有限。Trace 调度先根据 profile 找出一条最常执行的路径(trace),把它当作一个大基本块整体调度;对分支的另一条冷路径,用补偿代码恢复正确语义。Superblock 调度通过尾复制让 trace 只有一个入口,简化了补偿逻辑。跨块调度能显著提高 VLIW 处理器的利用率。