跳到主要内容

指令级并行性

指令级并行性​

指令级并行性(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 处理器的利用率。

硬件模型:从顺序到 VLIW​

三类主流的并行执行硬件对编译器的要求截然不同:

  • 顺序超标量(in-order superscalar):一个周期最多取多条指令,但必须按程序顺序发射。编译器负责调度,否则一遇冒险就停摆。
  • 乱序超标量(out-of-order):硬件维护指令窗口,动态发现独立指令并乱序执行,还会做寄存器重命名。编译器的调度重要性下降,但仍能通过好的指令布局减小重排缓冲区压力。
  • VLIW(Very Long Instruction Word):一条"长指令"里显式打包多个操作槽,每个槽送到一个功能单元。硬件极简,全部并行度都由编译器静态决定。DSP、TPU、部分 GPU 走这条路线。

投机执行​

有些并行机会藏在分支后面,需要"赌一把"。条件执行(predicated execution)把分支变成带条件位的普通指令,两侧代码都执行,但只有条件为真的一侧写回结果,从而消除短分支:

; 原代码:if (x > 0) y = a + b;
cmp p1, x, 0 ; 生成谓词 p1
(p1) add y, a, b ; p1 为真时才写回

编译器辅助的投机加载把内存加载提前到分支之前执行,用一条 check 指令验证;如果分支实际没走那条路,硬件默默丢弃加载结果和潜在异常。IA-64(Itanium)把这套机制做到了极致。

一个具体的调度例子​

假设一条 load 需要 2 个周期结果才可用,加法 1 周期,处理器每周期发射 2 条独立指令。原始循环每次迭代需要 4 个周期:

1: load  r1, b[i]
2: (等 load 结果)
3: add r2, r1, c[i]
4: store r2, a[i]

展开 4 遍并交错后(省略 store),可以变成:

1: load b[i]     | load b[i+1]
2: load b[i+2] | load b[i+3]
3: add r1,b[i] | add r2,b[i+1]
4: add r3,b[i+2]| add r4,b[i+3]

4 个周期完成 4 次迭代,平均 1 周期/迭代,理论加速 4 倍。这就是编译器能带给硬件的杠杆。

编译器与硬件的分工​

同一份并行性挖掘工作,可以在编译期做,也可以在运行期做。乱序超标量把大部分调度搬进硬件,编译器随便写点代码它也能跑得不错——代价是芯片面积和功耗巨大。VLIW 反过来:硬件只按编译器排好的时序执行,芯片小、功耗低,但编译器必须承担所有静态调度、依赖分析、投机决策,稍有失误性能就断崖式下跌。

因此嵌入式 DSP、AI 加速器往往搭配定制编译器一起交付;而通用 CPU 则倾向让编译器只做"友好的调度",剩下的交给硬件动态处理。理解 ILP,才理解现代高性能代码的性能到底来自何处。