Lecture 2: Out-of-order Processor & Pipeline
Lecture 2: Out-of-order Processor & Pipeline
1. 章节标题与概述
Lecture 2: Out-of-order Processor & Pipeline
本讲核心问题：硬件如何在没有程序员显式说明的情况下，从一段顺序代码里自动挖掘并行性？既然”程序必须看起来是按程序序、一条一条执行的”，处理器又如何能在内部乱序、重叠、甚至猜测性地执行多条指令，从而让单个指令流的吞吐率远高于”一条指令走完四个阶段”的朴素模型？
- 涉及的主要硬件/软件机制：
- 流水线（pipelining）：把指令执行切成 Fetch / Decode / Execute / Commit 等阶段，让不同指令处于不同阶段，从而把一个阶段的时间变成整个处理器的吞吐周期。
- 冒险与消解（hazards）：数据冒险（data hazard）、控制冒险（control hazard）、结构冒险（structural hazard）分别用 旁路转发（forwarding）、停顿插泡（stall / bubble）、分支预测与推测（speculation）、流水线冲刷（flush）、以及增加执行端口来处理。
- 数据流（dataflow）与乱序执行（out-of-order, OoO）：用寄存器重命名把程序序翻译成”真依赖图”，在保留顺序幻觉的前提下按数据就绪顺序发射；前端取指/译码与后端提交保持顺序，中间的执行完全乱序。
- 超标量（superscalar）：加宽发射宽度 W，使 IPC 可以大于 1；代价是调度复杂度按 O(W²) 增长。
- 硬件多线程 / SIMD / 多核（CS149 补充视角）：当 ILP 在 8 宽左右”榨干”之后，工业界转向线程级、数据级并行，并用硬件多线程（SMT）隐藏内存延迟。
在并行计算知识体系中的角色：本讲是整门课的”硬件底座”。它解释了为什么”并行”不只是多线程和多核——单核内部本身就是一个复杂的并行机器（流水线并行 + 乱序并行 + 推测并行），也解释了为什么这套机制最终会撞墙（ILP 有限、调度复杂度 O(W²)、频率受功耗限制），从而把历史推向多核。同时它给出了两个贯穿全课程的性能分析工具：延迟界（latency bound，关键路径） 与 吞吐界（throughput bound，执行端口数量与发射率）——后面分析 SIMD、GPU、缓存、带宽时都会反复使用。
- 配套材料：
lectures/02_ilp.pdf（讲义正文标题页写作 “Lecture 2: Instruction-Level Parallelism”，共 112 页幻灯片抽取文本extracted/02_ilp.txt）：已公开，可在 https://www.cs.cmu.edu/~418/lectures/ 下直接下载（课程主页 https://www.cs.cmu.edu/~418/，日程表 https://www.cs.cmu.edu/~418/schedule.html，Fall 2026 日期 Aug 26）。讲义页脚沿用历史学期（如 Fall 2025）字样属于正常的讲义复用现象，不是错误。cs149_supp/multicore1.txt：Stanford CS149 Fall 2025 Lecture 2 “A Modern Multi-Core Processor (Part I)”（共 108 页）——公开的补充读物，用于补足”乱序之后怎么办”的部分（缓存层次、SIMD、多核、硬件多线程、GPU SM 结构）。- 讲课录像（Panopto / YouTube）：Fall 2026 日程表中被注释隐藏，属 未发布。
- Ed 讨论区、Autolab、Canvas：需登录，非公开。
- 历史学期 PDF（如 Performance Analysis/Profiling、Transactional Memory、AI in System Design 等 Fall 2026 尚未发布的讲义）位于
/afs/cs/academic/class/15418-*/public/之下，需要 CMU 登录，属未公开。 - 本讲 Fall 2026 授课教师为 Brian Railing 与 Dimitrios Skarlatos；课程由 Kayvon Fatahalian 创建。
2. 核心概念与硬件/软件架构图解
2.1 ISA 与微架构：接口与实现的分离
定义与目的：指令集架构（ISA, Instruction Set Architecture） 是硬件与软件之间的功能契约，它规定”每条指令做什么”，但不规定”怎么做”。微架构（microarchitecture） 是 ISA 的具体实现方式。讲义给出的关系式是：
Architecture : Microarchitecture :: Interface : Implementation这个分离是所有性能优化的前提：同一份二进制可以在完全不同的微架构上运行，因此“快”是实现的属性，不是 ISA 的属性。本讲讨论的流水线、乱序、推测全部属于微架构层面，对程序员”不可见”（不改变程序输出），但极大地改变性能。
直观解释（”它是什么？”）：把 ISA 想象成餐厅菜单，微架构想象成厨房。菜单上写着”A 套餐包含汤、主菜、甜点”（功能契约），但厨房可以是一个人从头做到尾（顺序执行、无流水线），也可以是一个流水线厨房：有人专管煮汤、有人专管煎牛排、有人专管摆盘（五级流水线）；甚至可以是一个”提前猜客人要点什么就先把牛排下锅”的厨房（推测执行）。客人（软件）看到的永远是同一份菜单。
架构/机制图解：
软件 / 编译器 （ISA: 接口层） ------------------------------------------------------------------ "ldr r5, [r3], #4" "mla r0, r4, r5, r0" "bne .L3" ^ 只规定语义：从 r3 取 4 字节，写 r5，r3+=4，等等 ------------------------------------------------------------------ 微架构实现层（对程序员不可见，可任意重排/重叠/猜测） Fetch -> Decode -> [ 乱序发射 ] -> Execute -> Commit 多宽？多深？哪些执行端口？ROB 多大？分支预测器多聪明？ ★ 这些选择只影响性能，不影响程序语义 ★关键操作与性能特征：ISA 固定了”每条指令的功能延迟”这一语义概念，但微架构决定了真实延迟与吞吐。例如同一条 FMA（乘加）指令，在不同实现上执行延迟可能是 4 或 5 个时钟周期，而吞吐可以是每周期 0.5 条或 2 条。本讲后半段的所有”延迟界/吞吐界”分析，都是在微架构层面对 ISA 指令流的定量刻画。
2.2 流水线（Pipelining）：用阶段并行换吞吐
定义与目的：把一条指令的执行过程切分成若干阶段（stage），让多条指令的不同阶段在时间上重叠。讲义给出的最简模型是四级：
1. Fetch – 从内存取指令 2. Decode – 确定要做什么并读取输入寄存器 3. Execute – 执行运算 4. Commit – 把结果写回寄存器/内存（真实处理器的流水线级数远多于此。）讲义用多项式求值循环体
.L3: ldr r5, [r3], #4 // r5 <- coef[j]; r3 <- r3 + 4 (两个操作) cmp r1, r3 // j < terms ? mla r0, r4, r5, r0 // value += r5 * power (乘 + 加) mul r4, r2, r4 // power *= x bne .L3 // 循环回边演示：非流水线时每条指令延迟 4 ns、吞吐 1 条/4 ns；四级流水线后延迟仍是 4 ns，但吞吐变成 1 条/ns，即 4× 加速。这就是”N 级流水线最多给出 N× 加速”的来源。
直观解释（”它是什么？”）：流水线就像洗衣房。洗一桶衣服要 30 分钟洗 + 30 分钟烘 + 30 分钟叠，一个人从头做到尾，每 90 分钟出一桶；但如果洗、烘、叠分别是三台机器/三个人，第 1 桶仍然要 90 分钟（延迟不变），但从第 2 桶开始每 30 分钟就出一桶（吞吐提高 3 倍）。你自己的衣服并没有变快，但洗衣房单位时间的产量变成了 3 倍。
架构/机制图解：
cycle: 1 2 3 4 5 6 7 8 9 +-----+-----+-----+-----+-----+-----+-----+-----+-----+ instr i F \| F \| D \| E \| C \| \| \| \| \| \| instr i+1 \| \| F \| D \| E \| C \| \| \| \| \| instr i+2 \| \| \| F \| D \| E \| C \| \| \| \| instr i+3 \| \| \| \| F \| D \| E \| C \| \| \| instr i+4 \| \| \| \| \| F \| D \| E \| C \| \| +-----+-----+-----+-----+-----+-----+-----+-----+-----+ 非流水线: 1 条 / 4 周期, 延迟 4 周期 流水线 : 1 条 / 周期 , 延迟仍为 4 周期 => 吞吐 4x 处理器同时在处理 4 条指令（4 份"在途"工作）关键操作与性能特征：设 stage 时间为 t、级数为 N，则
- 延迟（单条指令完成时间）= N·t，不被流水线改善；
- 吞吐 = 1/t（理想情况），改善 N 倍；
- 在途指令数 = N（在理想满流情况下）。
但理想情况要求每一级都始终有独立工作可做。只要相邻指令之间存在依赖（见 2.3），流水线就会出现气泡，实际吞吐下降到 1/(t + 停顿)。
2.3 冒险（Hazards）：三种让流水线停下来的原因
定义与目的：冒险是阻止下一条指令在下一个周期进入其应属阶段的条件。讲义把限制并行性的冒险分为三类：
冒险类型 触发条件 讲义中的例子 主要消解手段 数据冒险 (data hazard) 后续指令需要读取前面指令尚未写回的结果（RAW 读后写） ldr ra, [rb], #4写rb；紧邻的cmp rc, rd要读rb停顿插泡、旁路转发 (forwarding)、寄存器重命名 控制冒险 (control hazard) 分支尚未执行完，处理器不知道下一条该取谁 bne .L3之后仍顺序取到了pop/bx流水线冲刷 (flush)、推测执行 + 分支预测 结构冒险 (structural hazard) 数据已就绪，但没有空闲硬件端口可以发射 Mem / Int / Mult 三类端口分别只有 1 个，而循环体每轮需要 1 个 ldr、2 个整数 op、2 个乘法 op 增加执行端口数量、调整指令组合（编译器调度） - 直观解释（”它是什么？”）：
- 数据冒险像接力赛交接棒：第二棒选手必须在第一棒把棒子递到手上才能起跑。如果两人离得太近，第二棒就得原地等一下（stall）；旁路转发相当于第一棒选手在跑动中直接把棒子往前扔过去——不必等他把棒子放回存放区（Commit）再让第二棒去取。
- 控制冒险像开车到岔路口却看不清路牌。你要么减速停车看清（冲刷+重取，代价大），要么”凭经验猜左转”（分支预测），猜错了就得倒车重来（misprediction penalty）。
- 结构冒险像只有一台收银机的超市：顾客（指令）已经选好商品、钱也准备好了（数据就绪），但收银台被占着，只能排队。
架构/机制图解：下面是讲义中的数据冒险停顿与控制冒险冲刷两个时序图（
ldr写r3，因此紧随其后的cmp不能立刻发射）：(a) 数据冒险 -> 停顿插泡 (bubble) (b) 控制冒险 -> 冲刷 (flush) cycle: 1 2 3 4 5 6 cycle: 1 2 3 4 5 6 +----+----+----+----+----+----+ +----+----+----+----+----+----+ ldr \| F \| D \| E \| C \| \| \| mla \| F \| D \| E \| C \| \| \| cmp \| \| \| ?? \| ?? \| F \| D \| mul \| \| F \| D \| E \| C \| \| mla \| \| \| \| \| \| \| bne \| \| \| F \| D \| E \| C \| +----+----+----+----+----+----+ +----+----+----+----+----+----+ ldr 写 r3 -> cmp 读 r3 pop \| \| \| \| F \| D \| <- 错误取指! 中间插入 NOP 气泡, 吞吐下降 bx \| \| \| \| \| F \| <- 错误取指! ^^^ 分支跳转后必须丢弃, 从 .L3 重取 惩罚随流水线深度线性增长 (c) 旁路转发 (forwarding) 消除停顿 +----+----+----+----+----+ ldr \| F \| D \| E \| C \| \| Execute 阶段算出的 r3+4 cmp \| \| F \| D \| E \| C \| <- 直接从 E 的输出"抄近路"送到 D 的输入 +----+----+----+----+----+ 不必等 C 阶段写回寄存器堆 数据在 Execute 之后就已可用 => 大多数(不是全部)停顿可被消除关键操作与性能特征：
- 停顿（stall）：注入 NOP 气泡，代价 = 插入的周期数；但有些停顿不可避免——长延迟指令（除法、缓存缺失）无法靠转发解决。
- 转发（forwarding）：在 Execute 之后、Commit 之前就把结果前送。讲义明确指出：转发不是免费的——流水线越深越复杂，需要的转发通路数量急剧增长，所以”转发能消掉多少停顿”这件事本身随流水线加深而恶化。
- 冲刷（flush）：代价随流水线加深而线性增长（要丢弃的在途指令更多）。讲义因此总结：流水线深度在 N≈15 附近触顶，再深下去，转发成本与冲刷成本会吃掉所有收益。
2.4 推测执行与分支预测（Speculation）
定义与目的：程序必须”看起来按程序序执行”，因此所有指令看似都依赖前一条——但分支会跳转，处理器不能在等分支结果的同时空转。推测（speculation） 就是”猜一个方向，先把指令取进来执行，猜错就整体回滚（roll back）”。其目的是为流水线创造本不存在的独立工作，把控制冒险的代价从”串行等待分支解决”降为”猜错时的一次性惩罚”。
直观解释（”它是什么？”）：像考试时先做后面的题。你读到一道需要长时间计算的选择题，于是先”假设答案是 A”，然后按 A 往下推（推测执行）；如果后面发现 A 错了，就擦掉所有基于 A 写下的内容重做（回滚/冲刷），而不是从第一题一直卡在那里等。
架构/机制图解：
静态指令序列 (内存中的程序布局) +----------------------+ <-- .L3 循环体 \| ldr r5, [r3], #4 | | cmp r1, r3 | | mla r0, r4, r5, r0 | | mul r4, r2, r4 | | bne .L3 ----------+----(1) 预测"跳转" (taken) +----------------------+ \| \| pop {r4, r5} | <-- 顺序流(错误路径) | | bx lr | v +----------------------+ 继续投机执行 .L3 循环体 (2) 分支在 Execute 阶段出结果 ├─ 预测正确 (>95% 的情况): 零代价, 满载 └─ 预测错误: 冲刷错取指令, 从正确 PC 重取 惩罚 = 流水线深度（现代 CPU ~15-20 周期）关键操作与性能特征：
- 现代处理器会在 Fetch 阶段就做预测——甚至还没译码出”这是一条分支”就已经按预测的 PC 取指。
- 讲义给出的预测准确率量级是 >95%，但分支误预测仍然是主要性能问题：4 宽 × 20 级流水线的机器，每次误预测约损失 15–20 个周期，意味着可发射 60–80 条指令的窗口被浪费掉。
- 一个极端情形（讲义明确点名）：依据随机数据分支的代码——预测器无法学习规律，性能会被 fetch 停顿主导。这正是后面代码示例
branch_pred.cpp要量化的现象。
2.5 数据流（Dataflow）与真假依赖
定义与目的：程序序在寄存器层面引入了大量伪依赖（false dependency）。数据流（dataflow） 的思想是：只看指令之间真正的数据依赖关系（真依赖 = 读后写 RAW, read-after-write），忽略只由”复用了同一个寄存器名”造成的顺序约束，从而暴露出更多并行性。讲义的原话是：”Dataflow increases parallelism by eliminating unnecessary dependences.”
依赖类型速查（本章表格之一）： +-------+----------------------+----------------------------+------------------+ \| 类型 \| 含义 \| 反例（同一个寄存器名复用） \| 是否真依赖 \| +-------+----------------------+----------------------------+------------------+ \| RAW | 读后写 (read-after- | I1: r0 = a + b | 真依赖，必须保留 | | | write) | I2: c = r0 * 2 | | | WAR | 写后读 (write-after- | I1: c = r0 * 2 | 伪依赖，重命名消除| | | read) | I2: r0 = a + b | | | WAW | 写后写 (write-after- | I1: r0 = a + b | 伪依赖，重命名消除| | | write) | I2: r0 = c * d | | | 控制 | 分支决定后继 | bne .L3 之后的所有指令 | 推测+预测+冲刷处理| | 结构 | 端口/资源冲突 | 两条乘法指令争 1 个乘法端口 | 增加端口或用别类指令顶上 | +-------+----------------------+----------------------------+------------------+直观解释（”它是什么？”）：把寄存器想成白板上的编号格子。程序序规定”必须先擦掉 1 号格子的旧内容再写新的”，但这只是因为大家共用了那块白板。数据流说：再拿一块新白板写下新值就行了，需要旧值的人继续看旧白板，需要新值的人看新白板——两块白板互不干扰，于是原本必须排队的两步可以同时做。这就是寄存器重命名（register renaming） 的直觉。
架构/机制图解：以多项式循环体为例，讲义给出的数据流执行图（假设完美调度、无限执行单元）：
loop iteration j ================================================================== r3(j-1) ---> [ ldr ] --(2c)--> r5 ------------------------+ \| \| +------> r3(j) ---> [ cmp ] --(1c) | \| \| v v [ bne ] --(1c) [ mla ] --(3c)--> r0(j+1) ^ r4(j-1) ------+ ^ [ mul ] --(2c)-+--> r4(j+1) ================================================================== 指令延迟（讲义给定）: ldr = 2c, mul = 2c, cmp = 1c, bne = 1c, mla = 3c 跨迭代关键路径: r0 链 mla(j) 依赖 mla(j-1) : 3 周期/迭代 <== 瓶颈 r4 链 mul(j) 依赖 mul(j-1) : 2 周期/迭代 => 迭代下界 = max(3, 2) = 3 周期/迭代 每轮 5 条指令 => IPC = 5/3 ≈ 1.67 （对比: 完美流水线 IPC = 1）关键操作与性能特征：
- 关键路径（critical path） 的定义（讲义原文）：数据流图中跨迭代的最长路径。在上例中就是
mla链。 - 关键路径给出性能上限，且是”延迟界”（latency bound）：即使执行单元无限多、端口无限宽，也无法快过 3 周期/迭代，因为
mla必须等前一次mla的结果。这个程序是延迟受限的（latency-bound）。 - 讲义强调这只是一个心智模型与分析工具：真实 CPU 未必达到该界限，但用它来分析程序非常有用。
- 关键路径（critical path） 的定义（讲义原文）：数据流图中跨迭代的最长路径。在上例中就是
2.6 乱序执行（Out-of-Order, OoO）微架构
定义与目的：OoO 的核心思想是”按数据流顺序执行，但保持顺序执行的幻觉“。指令按程序序进入和离开一个指令缓冲/重排序缓冲（instruction buffer / reorder buffer, ROB），而在缓冲内部，发射顺序完全由操作数是否就绪决定。这样既拿到了数据流的并行性，又对软件保留了”顺序单发射机器”的语义。
直观解释（”它是什么？”）：像餐厅的出菜口。顾客（程序）按点单顺序排队（in-order frontend），厨房内部可以任意乱序地同时炒五道菜（out-of-order execute），但摆盘上菜必须按点单顺序（in-order commit）——1 号桌的菜没好，2 号桌的菜做好了也得先放在保温台上等着。顾客看到的永远是”按顺序上菜”，但厨房的吞吐被最大化了。
架构/机制图解：
+-------------------------------------------------------------------------+ | CPU core | | | | PC --> [ Fetch ] --> [ Decode ] --> +---------------------------+ | | in-order in-order | Instruction Buffer / ROB | | | | (W 条/周期进入, 乱序发射) | | | +-------------+-------------+ | | | | | +------------------------------+---------------+ | | | out-of-order issue (数据就绪即发射) | | | v v v v | | [ EXE: ALU ] [ EXE: FMA ] [ EXE: FMA ] [ EXE: LD/ST ] | | | | | | | | +--------------+------+-------+---------------+ | | v | | [ Commit / Retire ] <-- in-order | | | | +-------------------------------------------\|-----------------------------+ v 寄存器堆 / 内存状态 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 前端 in-order \| 执行 out-of-order \| 提交 in-order 讲义原话: "Instructions only enter & leave instruction buffer in program order; all bets are off in between!"关键操作与性能特征：
- 发射（issue）：一条指令只有在所有源操作数就绪且存在空闲执行端口时才会被发射。
- 写回/旁路：执行结果既可写寄存器堆，也可直接前送给等待它的指令（转发在 OoO 中依然重要）。
- 提交（commit）：按程序序退役，这是”顺序幻觉”的最后一道防线，也是精确异常（precise exception）和推测回滚的锚点。
- 设计目标（讲义原文）：OoO 设计的目标是”只受数据流执行限制“；Fetch 与 Commit 被超额配置（over-provisioned），使它们通常不成为瓶颈。因此程序员通常可以忽略取指与提交阶段。
- 重大例外：控制流本质上不可预测的程序（例如依据随机数据分支）会被取指停顿主导——这是唯一需要程序员重新关注前端的场景。
- 软件收益（讲义”Software Takeaway”）：OoO 对”好代码”的敏感度低得多，性能可移植性更好；编译器仍然重要，但远不如 in-order 机器上那么关键。
2.7 超标量（Superscalar）：让 IPC 突破 1
定义与目的：前面的 OoO 模型里每周期只能发射 1 条指令，因此即使数据流可以给出 1.67 的并行度，实际也会被”发射宽度 = 1”卡死在 IPC = 1。超标量（superscalar） 就是加宽流水线：每周期取指/译码/发射/提交多条指令，配合多个执行单元，使 IPC 可以大于 1。讲义的原话：”Must increase pipeline width to increase IPC > 1.”
直观解释（”它是什么？”）：单发射是单车道收费站，不管后面的车多想同时通过，一次只放一辆；超标量是把收费站扩成 4 条车道，并且装了一个”智能调度员”（乱序发射逻辑），实时判断哪几辆车可以同时放行（彼此独立、且各自的车道类型匹配：有的是 ETC（整数口）、有的是货车通道（乘法口）、有的要走称重（访存口））。
架构/机制图解（讲义把 OoO + 多执行单元纵向堆叠；下面是同一循环体在超标量 OoO 上的时序，见”结构冒险”一节）：
每周期可发射 2 条指令的"示例"超标量 OoO（讲义用 2 宽示意图）: cycle: 1 2 3 4 5 6 7 8 9 10 11 ------------------------------------------------------------------ Mem port: L0 L1 L2 L3 L4 Int port: C0 B0 C1 B1 C2 B2 C3 B3 C4 Mul port: M0 U0 M1 U1 M2 U2 M3 U3 M4 \____ j=0 ___/\____ j=1 ___/\____ j=2 ___/ ------------------------------------------------------------------ L = ldr C = cmp B = bne M = mla U = mul 乘法类端口每轮要处理 (1 个 mla + 1 个 mul)，若它们的发射占用 分别是 2 和 3 个周期 => 5 周期/迭代（结构冒险主导） 若配置了足够的乘法端口 => 回到延迟界 3 周期/迭代关键操作与性能特征：
- 代价（讲义重点）：判断”两条指令能否同时发射”需要比较它们的输入/输出寄存器对，复杂度是 O(W²)（W = 发射宽度）——”Not great!”
- 收益递减：讲义明确指出，即便调度完美，超过 8 宽也没有帮助（程序本身 ILP 有限）。
- 在途窗口：4 宽 × 20 级流水线 = 80 条指令在途；高性能 OoO 的缓冲可以容纳数百条指令。
- 结构冒险是真实的墙：执行单元是专用化的（浮点加/乘、整数加/乘/比较、访存），设计者必须选择包含哪些、各几个。数据就绪但没有空闲端口时只能等。
2.8 延迟界与吞吐界：讲义给出的两把尺子
定义与目的：讲义把 OoO 机器的性能分析归结为两个界，取二者较慢者即可很好地近似真实性能：
界 定义（讲义原文） 组成要素 典型瓶颈 延迟界 (latency bound) 数据流图中跨迭代的最长路径所决定的下界 真依赖链上各操作延迟之和 mla依赖链（3c/迭代）吞吐界 (throughput bound) ops / issue rate，即操作数除以执行端口发射率每类操作的数量 + 执行端口数量与发射率 乘法端口需 (1 mla + 1 mul) / (2 + 3 周期) = 5c/迭代 实际性能 ≈ max(延迟界, 吞吐界)。讲义强调真实 CPU 未必精确达到这些界，但作为分析工具非常有用。
- 直观解释（”它是什么？”）：
- 延迟界像一条只能单人通行的吊桥：桥上有多少人排队不重要，重要的是队首到队尾要走多久。加宽桥面（更多执行单元）毫无帮助，只能缩短链条（拆分依赖链）。
- 吞吐界像只有 3 条收银通道的超市：顾客之间毫无依赖（可以任意并行），但收银台数量决定了每秒最多结账多少单。这时增加顾客的独立性没用，只能加通道（加端口）或换更快的收银员（提高发射率）。
架构/机制图解：
(a) 延迟界: 一条长依赖链 —— 执行端口大量空闲, 加宽无用 t: 1 2 3 4 5 6 7 8 9 10 11 12 op1 [===== FMA (4c) =====] op2 [===== FMA (4c) =====] op3 [===== FMA (4c) =====] \|<-------- 关键路径 = 3 x 4 = 12 周期 -------->\| 端口空闲率极高, IPC 低; 想加速只能"拆链" (b) 吞吐界: 依赖链被拆成 8 条独立链 —— 端口成为瓶颈 t: 1 2 3 4 5 6 7 8 9 10 op1 [FMA] op2 [FMA] op3 [FMA] op4 [FMA] op5 [FMA] op6 [FMA] \|<-- 每周期都在发射, 端口 100% 占用 -->\| IPC 高, 想加速只能"加端口/加宽 SIMD" (c) 真实程序: 两个界同时存在, 取 max +--------------------------+ \| 实际性能 ≈ max(延迟界, 吞吐界) \| +--------------------------+ 多项式循环: 延迟界 3c/迭代, 吞吐界 5c/迭代 => 预期 5c/迭代关键操作与性能特征：这两个界是整个课程反复使用的分析框架。在后面的 SIMD/GPU 讲座中，”吞吐界”会变成”SIMD 通道数 × FMA 端口数”，”延迟界”会变成”寄存器依赖链长度”；在缓存/带宽讲座中，二者之上还会再加一个带宽界。
2.9 从 ILP 到 TLP：多核、SIMD 与硬件多线程（CS149 补充视角）
定义与目的：讲义最后给出了”为什么 ILP 会撞墙、为什么工业界转向多核”的完整论证链：
- 程序的 ILP 有限：即便完美调度，>8 宽也无收益；
- 流水线不能无限加深：分支误预测惩罚随深度增长；
- 频率受功耗限制：不能靠提频解决；
- 动态调度开销显著：OoO 硬件本身昂贵、O(W²) 复杂。 => 从硬件角度，多核效率高得多；但并行软件很难写。工业界”尽可能久地抵制多核”，最终多核到来时，CPU 微架构反而被简化以塞进更多核。
CS149 的补充讲义把”现代处理器上可用的并行形式”整理为三类，并额外增加硬件多线程用于隐藏内存延迟：
并行形式 粒度/来源 谁发现并行 硬件代价 对程序的要求 超标量 / ILP 指令级、隐式、细粒度（核内） 硬件运行时动态发现 昂贵复杂（O(W²) 调度、重命名、ROB） 顺序代码即可，性能可移植性好 SIMD 数据级（核内） 编译器静态向量化，或 GPU 硬件运行时（implicit SIMD） 中等（宽 ALU + 宽寄存器） 需要控制流一致（coherent execution），否则掩码浪费，最差降到 1/8（CPU 8 宽）或 1/32（GPU 32 宽） 多核 / 线程级 线程级、显式、粗粒度 软件显式创建线程 每核一套前端+执行资源 需要足够的并行工作与正确的同步 硬件多线程 (SMT/交错) 同一核上的多个上下文 软件给线程，硬件交错发射 额外的上下文存储 需要远多于 ALU 数量的独立工作来隐藏延迟 - 直观解释（”它是什么？”）：
- 多核像把一间大厨房隔成 4 间小厨房，每间自己买菜、自己炒（各自独立的指令流）；比”一间超级厨房里塞满自动炒菜机器人”（复杂 OoO 单核）更容易扩建。
- SIMD 像流水线上一个字模同时盖 8 个盒子：只有 8 个盒子都走同一步骤（同一条指令）时才高效；如果第 3 个盒子要求换个图案（控制流发散），字模得停下重来，其余通道只能空转（掩码丢弃）。
- 硬件多线程像一位厨师同时照看 4 口锅：第 1 口锅在炖（等内存，12 个周期），厨师立刻去翻第 2 口锅（发射另一个线程的算术指令）。锅并没有变快，但厨师不再闲着。
架构/机制图解（把四种并行叠在一张图上）：
+---------------------------------------------------------------------------+ | Chip —— 多核 (multi-core): M 个核, M 条并发指令流, 软件显式建线程 | | | | +---------------------------------+ +---------------------------------+ | | | Core 0 | | Core 1 | | | | +---------------------------+ | | +---------------------------+ | | | | | SMT: exec ctx 0 | ctx 1 | | | | SMT: exec ctx 0 | ctx 1 | | | | | | (每周期从多个线程选指令) | | | | | | | | | +---------------------------+ | | +---------------------------+ | | | | | OoO engine (ILP) | | | | OoO engine (ILP) | | | | | | issue width W, ROB 深 D | | | | issue width W, ROB 深 D | | | | | +---------------------------+ | | +---------------------------+ | | | | | 8-wide SIMD ALU x 3 | | | | 8-wide SIMD ALU x 3 | | | | | | (每周期 8 个 float 一条指令)| | | | (每周期 8 个 float 一条指令)| | | | | +---------------------------+ | | +---------------------------+ | | | +---------------------------------+ +---------------------------------+ | +---------------------------------------------------------------------------+ M=16 核 x 8 宽 SIMD x 2 (FMA) x 3.0 GHz = 768 GFLOPS 峰值(单精度)关键操作与性能特征（来自 CS149 补充讲义的关键数字）：
- Kaby Lake 系列核心：2 路 SMT；每核每周期最多 4 条独立标量指令、最多 3 条 8 宽向量指令（其中最多 2 条向量乘或 3 条向量加）。
- 4 核 × 8 宽 SIMD × 3 单元 × 4.2 GHz ≈ 400 GFLOP/s（讲义按”每条 SIMD 通道操作记 1 FLOP”计；若把 FMA 记作 2 FLOP 则约 800 GFLOP/s）。
- 数据访问延迟（Kaby Lake, 4 GHz）：L1 = 4 周期、L2 = 12 周期、L3 = 38 周期、DRAM 最好情况 ≈ 248 周期。带宽约 38 GB/s。
- 硬件多线程的必要线程数：若每线程执行”3 条算术指令 + 一次 12 周期延迟的 load”，单线程利用率仅 3/15 = 20%；两线程 40%；需要 5 个线程才能到 100%。若算术指令增至 6 条，则只需 3 个线程。→ “每次访存携带的算术越多，隐藏延迟所需线程越少”（这正是算术强度/计算访存比的直觉来源）。
- GPU 极端吞吐导向：以补充讲义给出的 V100 为例，一个 SM（Streaming Multiprocessor） 拥有 64 个 warp 执行上下文、4 个 sub-core、每个 sub-core 有 16 宽 fp32 SIMD 单元（每 2 个周期完成一次 32 宽操作）、256 KB 寄存器、128 KB 共享内存+L1；80 个 SM，HBM 带宽约 900 GB/s。
3. 代码示例与性能分析
3.1 示例一：多项式求值——从”延迟界”到 ILP 显式重构
讲义整场都在用多项式求值讲解流水线、数据流、乱序。下面把它写成一个可以真正跑出差异的基准测试：Horner 串行链（纯延迟界）对比偶/奇双链重构（把关键路径砍半）。
// ---------------------------------------------------------------
// poly_ilp.cpp
// 编译 (release):
// g++ -O3 -march=native -fno-tree-vectorize poly_ilp.cpp -o poly_ilp
// # -march=native 打开 FMA (vfmadd...), 使 mla 变成单条 FMA 指令
// # 注意: 不要加 -ffast-math, 否则编译器可自由重结合浮点, 实验失去意义
// 运行:
// ./poly_ilp 8192 2000 # 8192 个系数, 重复 2000 次
// 观察:
// two_chain 的耗时约为 horner 的一半 => 关键路径被砍半
// ---------------------------------------------------------------
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <chrono>
#include <cmath>
// (a) 朴素 Horner: value = ((c[n-1]*x + c[n-2])*x + ...)*x + c[0]
// 关键路径 = (n-1) 次 FMA 串行依赖 -> 纯 latency bound
static inline float poly_horner(const float* c, int n, float x) {
float value = c[n - 1];
for (int j = n - 2; j >= 0; --j)
value = value * x + c[j]; // 编译为 vfmadd213ss 等
return value;
}
// (b) 偶/奇双链: poly(x) = B(u) + x * A(u), u = x^2
// A(u) 收集所有奇数下标项, B(u) 收集所有偶数下标项 (要求 n 为偶数)
// 关键路径 ≈ 1 次 mul + (n/2) 次 FMA + 1 次 add -> 并行度 ~2
static inline float poly_two_chain(const float* c, int n, float x) {
const float u = x * x;
float A = 0.0f, B = 0.0f;
for (int j = n - 1; j >= 1; j -= 2) {
A = A * u + c[j]; // 奇数下标链 (与 B 链完全独立)
B = B * u + c[j - 1]; // 偶数下标链
}
return B + x * A;
}
int main(int argc, char** argv) {
const int n = (argc > 1) ? std::atoi(argv[1]) : 8192;
const int repeat = (argc > 2) ? std::atoi(argv[2]) : 2000;
if (n % 2) { std::fprintf(stderr, "n must be even\n"); return 1; }
std::vector<float> c(n);
for (int j = 0; j < n; ++j)
c[j] = std::sin(0.001f * (float)j); // 任意非平凡系数
auto bench = [&](const char* name, float (*fn)(const float*, int, float)) {
volatile float sink = 0.0f; // 防止整个循环被优化掉
float x = 1.0009765625f; // 略大于 1, 避免溢出
auto t0 = std::chrono::steady_clock::now();
for (int r = 0; r < repeat; ++r) {
sink = sink + fn(c.data(), n, x);
x += 1e-7f; // 让各次调用的 x 不同
}
auto t1 = std::chrono::steady_clock::now();
double sec = std::chrono::duration<double>(t1 - t0).count();
double perCall = sec / repeat;
// 用 3.0 GHz 估算关键路径周期数 (仅作量级参考)
std::printf("%-12s : %8.3f ms/call %8.2f cycles/FMA (@3.0GHz) sink=%.6f\n",
name, perCall * 1e3, perCall * 3.0e9 / (double)n, (double)sink);
};
bench("horner", poly_horner);
bench("two_chain", poly_two_chain);
return 0;
}
【代码做什么？】
- 构造
n个系数（n取偶数），保证两个版本计算的是同一个多项式。 poly_horner从最高次项开始向下迭代，每一步value = value*x + c[j]。这是一个严格的串行依赖链：第 j 步必须等第 j+1 步的value。poly_two_chain先把 偶数下标项 与 奇数下标项 分成两个独立的多项式（都关于u = x*x），各自做 Horner，最后B + x*A合并。两条链之间没有任何数据依赖，因此可以同时推进。- 两个函数都在
repeat次调用中被计时，用volatile sink阻止死代码消除，用x += 1e-7f阻止编译器把重复调用”折叠”成一次。 - 输出每次调用的毫秒数，并按 3.0 GHz 折算成”每个 FMA 的周期数”，便于对照讲义给出的 FMA 延迟 4 个周期。
【并行机制与性能解说】
- 硬件上如何并行：两个版本编译出的都是一串标量 FMA 指令，没有 SIMD、没有多线程。它们的唯一并行性来自 OoO 引擎发现的 ILP。
poly_horner的指令之间全部 RAW 依赖，OoO 窗口里根本没有可同时发射的指令；poly_two_chain则交替发射 A 链与 B 链的两条 FMA，每周期可发射 2 条（受 FMA 端口数限制，Skylake 级机器通常 2 个 FMA 端口）。 Work / Span / 并行度分析（设 n 个系数，一次调用）：
版本 Work（总操作数） Span（关键路径） 并行度 = Work/Span poly_horner(n−1) 次 FMA (n−1)·L_FMA ≈ 1 poly_two_chain2 mul + n 次 FMA + 1 add = n+3 L_mul + (n/2)·L_FMA + L_mul + L_add ≈ 2 取
n = 8192、L_FMA = L_mul = L_add = 4周期：- Horner: Span = 8191 × 4 ≈ 32 764 周期/次调用；
- two_chain: Span ≈ 4 + 4096×4 + 4 + 4 = 16 396 周期/次调用；
- 理论上限加速比 ≈ 2.0×，而 Work 增加了约 3 次操作（<0.04%）。
- 瓶颈诊断：这是教科书式的延迟界（latency bound）。执行端口几乎全程空闲，加宽机器、加更多 FMA 单元完全没有用；唯一有效的优化就是缩短关键路径。想继续加速就要继续拆链（Estrin 方案、4 链、8 链…），但每拆一层 Work 都会略微上涨，收益按 2^k 递减。
- 另一个真实世界的坑：如果加了
-ffast-math，编译器可能自己就把 Horner 重组成 Estrin，两个函数耗时相同——这不是实验失败，而是”编译器替你做了 ILP 重构”。反过来，不加-ffast-math时编译器不允许重结合浮点，所以它会老老实实保留串行链。这正是”什么时候必须手工暴露 ILP”的经典案例。
3.2 示例二：求和——延迟界 → 吞吐界 → 带宽界的连续迁移
同一个”求和”内核，用三种写法展示性能瓶颈的迁移：串行单累加器（延迟界）→ 串行多累加器（ILP 显式化）→ OpenMP 多线程多累加器（可能进入带宽界）。
// ---------------------------------------------------------------
// omp_sum.cpp
// 编译 (release):
// g++ -O3 -march=native -fopenmp omp_sum.cpp -o omp_sum
// 运行:
// OMP_NUM_THREADS=16 ./omp_sum 100000000 # 1 亿个 double = 800 MB
// ---------------------------------------------------------------
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <chrono>
#include <omp.h>
// (a) 串行, 单累加器: 关键路径 = N 次加法串行依赖 => 纯 latency bound
static double sum_serial(const double* a, size_t n) {
double s = 0.0;
for (size_t i = 0; i < n; ++i) s += a[i];
return s;
}
// (b) 串行, 4 个独立累加器: 关键路径 = N/4 次加法, 依赖链 4 条并行
// 编译器通常会把这样的写法直接向量化成 4 宽 SIMD (AVX2)
static double sum_serial_ilp(const double* a, size_t n) {
double s0 = 0, s1 = 0, s2 = 0, s3 = 0;
size_t i = 0;
for (; i + 4 <= n; i += 4) {
s0 += a[i]; s1 += a[i + 1]; s2 += a[i + 2]; s3 += a[i + 3];
}
double s = (s0 + s1) + (s2 + s3);
for (; i < n; ++i) s += a[i]; // 尾部
return s;
}
// (c) OpenMP + 每线程 4 个累加器: 线程级并行 x ILP 显式化
// 用 reduction(+:total) 让 OpenMP 负责最后合并, 避免手工加锁
static double sum_omp_ilp(const double* a, size_t n, int nthreads) {
double total = 0.0;
#pragma omp parallel num_threads(nthreads) reduction(+:total)
{
const int tid = omp_get_thread_num();
const int nth = omp_get_num_threads();
const size_t chunk = (n + (size_t)nth - 1) / (size_t)nth;
const size_t lo = (size_t)tid * chunk;
const size_t hi = (lo + chunk < n) ? (lo + chunk) : n;
double s0 = 0, s1 = 0, s2 = 0, s3 = 0;
size_t i = lo;
for (; i + 4 <= hi; i += 4) {
s0 += a[i]; s1 += a[i + 1]; s2 += a[i + 2]; s3 += a[i + 3];
}
double s = (s0 + s1) + (s2 + s3);
for (; i < hi; ++i) s += a[i];
total += s;
}
return total;
}
int main(int argc, char** argv) {
const size_t n = (argc > 1) ? std::strtoull(argv[1], nullptr, 10) : 100000000ULL;
std::vector<double> a(n);
for (size_t i = 0; i < n; ++i) a[i] = 1.0 + 1e-9 * (double)(i & 1023);
const double bytes = (double)n * sizeof(double);
auto run = [&](const char* name, double (*fn)(const double*, size_t)) {
auto t0 = std::chrono::steady_clock::now();
volatile double r = fn(a.data(), n);
auto t1 = std::chrono::steady_clock::now();
double sec = std::chrono::duration<double>(t1 - t0).count();
std::printf("%-16s : %8.2f ms %7.2f GB/s sum=%.1f\n",
name, sec * 1e3, bytes / sec / 1e9, (double)r);
};
run("serial", sum_serial);
run("serial_ilp", sum_serial_ilp);
{
auto t0 = std::chrono::steady_clock::now();
volatile double r = sum_omp_ilp(a.data(), n, omp_get_max_threads());
auto t1 = std::chrono::steady_clock::now();
double sec = std::chrono::duration<double>(t1 - t0).count();
std::printf("%-16s : %8.2f ms %7.2f GB/s sum=%.1f (threads=%d)\n",
"omp_ilp", sec * 1e3, bytes / sec / 1e9, (double)r,
omp_get_max_threads());
}
return 0;
}
【代码做什么？】
- 分配
n个double（默认 1 亿个 = 800 MB），填充成互不相同的数（防止编译器把”常量数组求和”折叠成乘法）。 sum_serial：一次遍历，单累加器s += a[i]，形成长度为 n 的加法依赖链。sum_serial_ilp：用 4 个累加器同时累加 4 个元素，最后两两合并；尾部剩余元素单独处理。sum_omp_ilp：#pragma omp parallel ... reduction(+:total)把区间按线程切分（块划分），每个线程内部再用 4 个累加器，最后由 OpenMP 的 reduction 把各线程的total合并（实现上等价于每线程私有副本 + 末尾层次化合并，不存在热点的原子操作）。- 三种写法都统计时间、实际带宽（GB/s）与校验和。
【并行机制与性能解说】
sum_serial在硬件上如何执行：只有 1 条依赖链，OoO 完全无指令可重叠。每次加法延迟约 4 个周期（Skylake 级），所以吞吐受延迟限制为 4 周期/元素。sum_serial_ilp如何加速：4 条独立链让 OoO 每周期都能发射 1 条加法，同时编译器大概率把它向量化为 256 位 SIMD（4 个 double 一条vaddpd）。于是瓶颈从”延迟界”转到”吞吐界“：每条 SIMD 加法只花 1 个周期，每周期消耗 32 字节。sum_omp_ilp如何并行：创建 T 个线程，每个线程拿到连续的一块区间（块划分 = 顺序访问，对预取器与 DRAM 行缓冲友好），线程之间没有共享可写数据（各自私有累加器），只在末尾做一次 reduction。无数据竞争、无伪共享。Work / Span / 并行度分析（N 个元素、T 个线程、每线程 4 个累加器）：
版本 Work Span 并行度 sum_serialN 次加法 N·L_add 1 sum_serial_ilpN 次加法（+3 次合并） (N/4)·L_add + 2·L_add ≈ 4 sum_omp_ilpN 次加法 (N/(4T))·L_add + log₂(T)·L_add ≈ 4T 取 N = 10⁸、T = 16、L_add = 4 周期、f = 3.0 GHz：
sum_serial: Span = 4×10⁸ 周期 = 133 mssum_serial_ilp: Span = 10⁸ 周期 = 33 ms（理想 4× 加速）sum_omp_ilp: Span = 10⁸/(4×16) ≈ 1.56×10⁶ 周期 ≈ 0.52 ms（理想 256× 加速）- 但物理下限是：800 MB ÷ 38 GB/s ≈ 21 ms（用讲义给出的 Kaby Lake 38 GB/s）。即便用 20 GB/s 的保守带宽，也要 40 ms。
- 瓶颈诊断（本示例最重要的结论）：当 T = 16 时，
Work/Span的并行度是 256，但实测只会落在 21–40 ms 区间，而非 0.52 ms。此时程序已经彻底从延迟界迁移到带宽界：再增加线程、再拆累加器、再宽 SIMD 都毫无收益（甚至因为超过内存控制器并发能力而变慢）。这就是”算术强度”概念要解决的问题——见第 4 节 Roofline 分析。 - 附带陷阱提示：如果为了让”每线程 4 个累加器”更细而把切分改成
a[i] += ...的跨步访问（stride = T），虽然累加器线程私有、没有伪共享，但访存变成非连续，会破坏预取与 DRAM 行局部性，带宽可能掉一半以上。这是”为了并行而牺牲局部性”的典型错误。
3.3 示例三：分支预测——控制冒险的量化实验
讲义在”控制冒险/推测”一节点名了最坏情况：基于随机数据的分支。下面的实验用同一份代码、同一份数据，仅改变数据的排列顺序，就能观察到数量级的差异。
// ---------------------------------------------------------------
// branch_pred.cpp
// 编译 (release):
// g++ -O2 -march=native branch_pred.cpp -o branch_pred
// 建议同时检查反汇编, 确认 if 没有被改写成无分支代码:
// objdump -d branch_pred | grep -A30 '<_Z12sum_branchy'
// 运行:
// ./branch_pred 40000000
// ---------------------------------------------------------------
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <chrono>
#include <cstdint>
// 数据相关的 if: 分支方向由数据决定
// 两个副作用 (s 与 hits 同时更新) 可降低编译器 if-conversion 成 cmov 的概率
static long long sum_branchy(const uint8_t* d, size_t n) {
long long s = 0, hits = 0;
for (size_t i = 0; i < n; ++i) {
if (d[i] >= 128) { // <-- 数据相关分支
s += d[i];
++hits;
}
}
return s + hits;
}
// 等价的无分支写法: 用条件表达式, 期望被编译成 cmov / 掩码运算
static long long sum_branchless(const uint8_t* d, size_t n) {
long long s = 0;
for (size_t i = 0; i < n; ++i) {
const uint8_t v = d[i];
s += (v >= 128) ? (long long)v : 0LL;
}
return s;
}
int main(int argc, char** argv) {
const size_t n = (argc > 1) ? std::strtoull(argv[1], nullptr, 10) : 40000000ULL;
std::vector<uint8_t> data(n);
unsigned seed = 12345u;
for (size_t i = 0; i < n; ++i) { // 简单 xorshift 伪随机
seed ^= seed << 13; seed ^= seed >> 17; seed ^= seed << 5;
data[i] = (uint8_t)(seed >> 24); // 均匀分布 0..255
}
auto time_it = [&](const char* tag, long long (*fn)(const uint8_t*, size_t)) {
auto t0 = std::chrono::steady_clock::now();
volatile long long r = fn(data.data(), n);
auto t1 = std::chrono::steady_clock::now();
double sec = std::chrono::duration<double>(t1 - t0).count();
std::printf("%-26s : %8.2f ms %6.3f ns/elem %5.2f cyc/elem(@3.5GHz) r=%lld\n",
tag, sec * 1e3, sec / (double)n * 1e9,
sec / (double)n * 3.5e9, (long long)r);
};
std::printf("--- 未排序 (分支方向随机, 预测器几乎无法学习) ---\n");
time_it("branchy / unsorted", sum_branchy);
time_it("branchless / unsorted", sum_branchless);
std::sort(data.begin(), data.end());
std::printf("--- 已排序 (前一半全不跳, 后一半全跳, 预测几乎全中) ---\n");
time_it("branchy / sorted", sum_branchy);
time_it("branchless / sorted", sum_branchless);
return 0;
}
【代码做什么？】
- 用 xorshift 生成 4×10⁷ 个均匀分布于 0..255 的字节，保证
d[i] >= 128大约一半为真、且彼此独立——这正是分支预测器最讨厌的模式（没有可学习的规律）。 - 先对未排序数据跑
sum_branchy与sum_branchless，再std::sort后跑同样的两个函数（排序后分支行为变成”长段全不跳 + 长段全跳”，预测器能学得很好）。 - 由于结果与顺序无关（加法可交换），排序不改变正确性，只改变分支的动态行为——这正是讲义所说”依据随机数据分支”的可控实验版本。
【并行机制与性能解说】
- 硬件上发生了什么：
sum_branchy的循环体里有一条数据相关分支。当数据未排序时，处理器每两次迭代就会误预测一次；每次误预测要冲刷流水线并从正确路径重取指，代价约 15–20 个周期。排序之后，同样的分支几乎全中，误预测惩罚消失。 branchless版本：条件表达式被编译成cmov（或 SIMD 掩码），没有任何控制冒险。它在未排序数据上应当明显快于branchy，而在排序数据上两者接近——这个”排序后差距消失”的现象，是判断”瓶颈到底是分支还是数据依赖”的关键证据。Work / Span / 并行度分析（N 次迭代）：
版本 Work Span 并行度 sum_branchy（预测正确）N 次比较 + N 次加法（+ 若干） N·L_add + N·L_branch_ok ≈ 1 sum_branchy（未排序）同上 N·L_add + (N/2)·P_mispredict ≈ 1，且 Span 被放大 sum_branchlessN 次比较 + N 次条件选择 + N 次加法 N·L_add ≈ 1 取 N = 4×10⁷、f = 3.5 GHz、
L_add = 1周期（累加是短延迟）、P_mispredict ≈ 17周期、误预测率 = 50%：- 理想（无分支代价）：4×10⁷ 周期 ≈ 11 ms
- 加上误预测：4×10⁷ + 2×10⁷×17 = 3.8×10⁸ 周期 ≈ 109 ms
- → 仅一个数据相关分支就能让这个内核慢 ~10 倍，而它的并行度始终是 1（
s的依赖链），所以即使有 16 个核可以帮忙，也不会有任何加速——除非改变算法（例如分块并行 + 树形归约）。
- 瓶颈诊断：这是控制冒险主导的场景。讲义给出的”分支预测准确率 >95%”是针对典型整数程序的平均值；对随机数据分支则接近 50%——预测器失效。此时 OoO 无能为力，因为乱序执行也无法越过一条它不知道目的地何时才确定的分支（分支解析前，后端根本不知道该执行哪些指令）。
- 工程结论：对这类内核，正确做法是去分支（branchless）或数据重排，而不是加核、加 SIMD 宽度或调 OoO 参数。
4. 性能模型与复杂度分析
本节用讲义与补充讲义给出的数字，把第 2、3 节的定性结论算成具体数字。
4.1 机器参数假设（全部取自讲义/补充讲义）
| 参数 | 取值 | 来源 |
|---|---|---|
| 时钟频率 f | 3.0–4.2 GHz | 讲义中 Kaby Lake 系列示例 |
| 发射宽度 W | 4 条标量指令/周期 | 补充讲义 Skylake/Kaby Lake 核心 |
| SIMD 宽度 | 8 × 32-bit（AVX2），每核 3 个向量单元 | 补充讲义 |
| FMA 延迟 L_FMA | 4 周期 | Skylake 级机器，与讲义”mla = 3 周期”同量级 |
| 内存延迟 | L1 = 4c，L2 = 12c，L3 = 38c，DRAM ≈ 248c（@4 GHz） | 补充讲义 |
| DRAM 带宽 | 38 GB/s（讲义示例机器）；保守取 20 GB/s | 补充讲义 |
| 分支误预测惩罚 | 15–20 周期 | 讲义”惩罚随流水线深度增长” |
| ROB 深度 | 数百条指令 | 讲义”high-performance OoO buffers hundreds of instructions” |
4.2 算例 A：多项式循环的延迟界 vs 吞吐界（讲义的完整推理）
循环体 5 条指令：ldr(2c)、cmp(1c)、mla(3c)、mul(2c)、bne(1c)。
- 延迟界：跨迭代关键路径是
mla链（每次mla依赖上一次的r0）：3 周期/迭代。此时 IPC = 5/3 ≈ 1.67（完美流水线是 1）。 - 吞吐界：每轮需要 1 条
mla+ 1 条mul，若只有一个乘法类端口，两条乘法的发射占用是 2 + 3：吞吐界 = (1 mla + 1 mul) / (2 + 3 周期) = 5 周期/迭代，此时 IPC = 5/5 = 1.0。 - 实际性能 ≈ max(3, 5) = 5 周期/迭代：这就是讲义”结构冒险把一轮压成 5 个周期”的定量来源。
- 若把乘法端口增加到 2 个（或让
mla/mul分配在不同端口）：吞吐界降到 ≤3，程序重新变成延迟受限，回到 3 周期/迭代。
结论：同一段代码的瓶颈可以在”延迟界”和”吞吐界”之间切换，取决于发射宽度、端口数量、以及关键路径长度。判断当前处于哪一侧，是优化的第一步。
4.3 算例 B：为什么需要硬件多线程——Little 定律与在途窗口
Little 定律（Little’s Law）：要在给定延迟下维持给定吞吐，必须有足够的”在途工作”：
在途工作数 = 延迟 × 目标吞吐
只靠 OoO 单线程：目标是每周期发射 4 条指令（IPC = 4），一次 DRAM 访问的延迟是 248 周期，那么需要
在途指令数 = 248 周期 × 4 条/周期 = 992 条而讲义指出高性能 OoO 的缓冲”hundreds of instructions”（数百条）。992 > 数百 ⇒ 单线程 OoO 无法隐藏一次完整的 DRAM 缺失。这也解释了讲义给出的经验数：”4 宽 × 20 级流水线 = 80 条在途”——离 992 差一个数量级。
用硬件多线程补足：若每个线程的模式是”3 条算术 + 1 次 12 周期 load”，单线程的端口利用率只有
利用率 = 3 / (3 + 12) = 20%需要的线程数 = ⌈(3 + 12) / 3⌉ = 5 个线程才能到 100%。（补充讲义给了完全相同的示例与答案。）把模型推广到真实 DRAM 延迟 248 周期、每次访存携带约 15 个周期的算术工作：
线程数 = ⌈(15 + 248) / 15⌉ = ⌈17.5⌉ = 18 个线程这就是 GPU 一个 SM 里塞 64 个 warp 上下文、CPU 上跑 SMT + 多核的定量理由。
关键性质（讲义强调）：多线程没有改变访存延迟，它只是让延迟不再导致处理器停机。这就是”吞吐导向（throughput computing）”的根本权衡：允许单个线程的完成时间变长，以换取系统整体吞吐提高。
4.4 算例 C：算术强度与 Roofline——什么时候 ILP 完全无用
取一台”16 核 × 8 宽 SIMD × 2（FMA）× 3.0 GHz”的机器：
峰值算力 = 16 × 8 × 2 × 3.0e9 = 768 GFLOP/s (单精度)
取内存带宽 = 20 GB/s，则机器的平衡点（ridge point）：
ridge = 768 GFLOP/s ÷ 20 GB/s = 38.4 FLOP/byte
现在看一个典型内核：遍历一个 256 MB 的 double 数组，每个元素做 1 次 FMA。
- 访存量：256 MB = 2.56×10⁸ B；元素数 = 2.56×10⁸ / 8 = 3.2×10⁷ 个 double。
- 计算量：3.2×10⁷ × 2 FLOP（1 FMA = 2 FLOP）= 6.4×10⁷ FLOP = 64 MFLOP。
- 纯计算的理想时间：64×10⁶ / 768×10⁹ = 83 µs。
- 纯访存的下限时间：2.56×10⁸ B / 20×10⁹ B/s = 12.8 ms。
- 算术强度：2 FLOP ÷ 8 B = 0.25 FLOP/byte，远低于平衡点 38.4。
- 有效性能上限：20 GB/s × 0.25 FLOP/B = 5 GFLOP/s，仅峰值的 0.65%。
结论：这个内核比”纯计算时间”慢 154 倍，而且再多核、再宽的 SIMD、再深的 OoO 窗口都无济于事——瓶颈是 DRAM 带宽。Roofline 的判据非常直接：
算术强度 < ridge 点 => 带宽受限 (bandwidth-bound)，优化目标是减少访存/提高复用
算术强度 > ridge 点 => 计算受限 (compute-bound)，此时才轮到 ILP/SIMD/多核发力
把同样的分析套回第 3 节的 omp_sum：其算术强度是 1 FLOP / 8 B = 0.125 FLOP/byte，所以无论用多少线程，实测都会停在”800 MB ÷ 带宽”那个数量级（约 21–40 ms），而不会接近”0.52 ms”的理想延迟界。
4.5 算例 D：Amdahl 定律与”每核效率”的复合效应
设程序中可并行部分占 p = 0.95，串行部分 s = 0.05，用 T 个核：
Speedup(T) = 1 / (s + p/T)
T = 16 : 1 / (0.05 + 0.95/16) = 1 / 0.1094 = 9.15x
T = 64 : 1 / (0.05 + 0.95/64) = 1 / 0.0648 = 15.4x
T -> ∞: 1 / 0.05 = 20x <-- Amdahl 上限
再把”每核效率”叠进去：如果每核因为延迟界只能达到 IPC = 1.67，而机器峰值是 4 宽（IPC = 4），则每核效率只有 42%。于是 T = 16 时的真实加速比 ≈ 9.15 × 0.42 ≈ 3.8×。
这一条把本讲与课程整体串起来了：并行加速比不仅是”核数”和”串行比例”的函数，还受每个核内部的 ILP 效率（延迟界/吞吐界）制约。OoO 好，是为了让这个 0.42 尽量接近 1；多核好，是为了让 T 尽量大。两者不可偏废。
4.6 算例 E：超标量调度复杂度与流水线深度的双重上限
讲义给出的两个硬件开销公式：
调度复杂度 = O(W^2) W = 发射宽度
控制冒险惩罚 = O(N_pipeline) 每次误预测约丢弃 N 级在途指令
在途指令数 = W × N_pipeline
- W = 4、N = 20 ⇒ 在途 80 条指令，调度要比较 C(4,2) = 6 对寄存器组。
- W = 8、N = 20 ⇒ 在途 160 条，比较 28 对——复杂度增长 4.7 倍，而讲义明确说”即便完美调度，>8 宽也没有帮助”。
- 若平均每 20 条指令就遇到一次误预测（即每个分支都猜错，随机数据分支的典型情形），每次损失 20 个周期：理想情况 4 宽机器发射 20 条指令只需 5 周期，实际需要 5 + 20 = 25 周期 ⇒ 有效 IPC = 20/25 = 0.8，W = 4 的收益被完全吃掉（甚至不如单发射）。
结论：ILP 的三个上限——程序本身 ILP 有限（~8 宽）、流水线深度有限（N≈15）、调度复杂度 O(W²)——共同把单核性能封了顶。这正是讲义结尾”Limitations of ILP → Multicore”的完整论证。
5. 关键要点
流水线只提高吞吐，不降低延迟；N 级流水线最多带来 N× 吞吐，但受数据/控制/结构三类冒险制约，实际上在 N≈15 附近触顶。旁路转发能消除大多数（不是全部）数据冒险停顿，而它在深流水线中本身成本高昂；分支冲刷的代价随深度线性增长。
乱序执行 = “按数据流顺序执行 + 保持顺序执行的幻觉”。指令只按程序序进入和离开指令缓冲/ROB，中间完全乱序；前端与提交端被超额配置，因此程序员通常只需关注执行阶段，唯一例外是本质上不可预测的控制流。
性能分析用两个界，取慢的那个：延迟界 = 跨迭代关键路径（拆依赖链才能改善），吞吐界 = 操作数 / 执行端口发射率（加端口或换更宽的 SIMD 才能改善）。OoO 让这套分析比 in-order 机器简单得多，也让性能在不同微架构间的可移植性更好。
寄存器重命名消灭伪依赖（WAR/WAW），只保留真依赖（RAW）；数据流视角是理解乱序、推测与编译器重排的统一语言。真依赖构成的关键路径无法被任何硬件技巧绕过，只能由程序员/编译器改写算法来缩短。
ILP 撞墙的直接后果是多核：程序 ILP 有限（>8 宽无益）、流水线不能更深、频率受功耗限制、OoO 调度是 O(W²)。工业界的答案是”简化微架构、增加核数、并用硬件多线程（SMT）与 SIMD 填补每核的利用率空洞”，代价是并行软件更难写。当代码进入带宽界（算术强度低于 Roofline 平衡点）时，上述一切硬件技巧都失效，唯一的出路是提高数据复用。
6. 常见陷阱与注意事项
把”流水线”误解为”降低延迟”：
N级流水线不改变单条指令的端到端延迟（仍是 N·t），只提高稳态吞吐。若程序只有极少量指令（或每次都要冲刷），流水线反而带来更差的启动/排空开销。同理，“IPC = 4” 的机器不等于单线程快 4 倍，它取决于程序里有没有 4 条独立指令可发射。以为”乱序执行 = 可以放心写串行代码”：OoO 只能利用真实存在的 ILP。第 3 节示例一证明，一条 8192 长的严格依赖链在任何 OoO 宽度下都只能得到约 1 的 IPC，把关键路径砍半（双链）才能拿到 2× 加速。OoO 降低了对”指令调度技巧”的依赖，但不解决算法级的依赖结构问题。
用”平均分支预测率 >95%”推断自己的程序：数据相关分支（随机、哈希、压缩、稀疏矩阵遍历、图算法中的条件插入）会退化到约 50% 命中率，每次误预测丢弃 15–20 个周期，足以造成 10 倍量级的差距。此类内核应改写为无分支（branchless / cmov / 掩码）或数据重排，而不是指望硬件或加核。
忽视延迟界与吞吐界的切换，盲目优化：给一个延迟受限的内核加核、加 SIMD 宽度、堆更多线程，收益为零甚至为负；对一个吞吐受限的内核去”拆分依赖链”同样白费。正确顺序永远是：先判断处在哪一侧（第 4.2 节的两条公式），再选择对应的优化手段。
只算 FLOPs 而不算字节数（忽略带宽）：第 4 节算例 C 中，算术强度 0.25 FLOP/byte 的内核只能发挥 0.65% 的峰值算力。报告”我的程序达到了 X GFLOPS”之前，必须同时报告”它搬了多少字节、实际带宽是多少”，否则该数字毫无意义。同理，”我的并行程序有 16 个线程”不等于”16 倍加速”——先看它是不是带宽受限。
为并行而破坏访存局部性 / 引入伪共享或数据竞争：为了让累加器线程私有而改用
stride = 线程数的跨步访问，会摧毁预取与 DRAM 行局部性，带宽可能腰斩；反过来，为图省事让多线程写同一个缓存行里的不同变量（例如struct { long cnt[N]; }相邻元素）会触发伪共享（false sharing），每一次写都让别的核的缓存行失效。多线程写共享累加器时还应避免用#pragma omp atomic/互斥锁做热路径累加（串行化 + 缓存行乒乓），应使用每线程私有副本 + 末尾归约（如reduction(+:)）。错误理解内存序与编译器优化边界：OoO 硬件重排的是单线程内的指令，多线程之间的可见性由内存序（memory ordering） 与同步原语决定——写一个
volatile变量不构成同步，也不能替代 acquire/release 或锁。另一方面，-O3 -ffast-math会让编译器重结合浮点运算（可能自动把你精心构造的串行链变成并行链，或反之改变结果），做性能实验或要求逐位可复现时必须显式关闭它。
7. 思考题（带答案）
思考题 1：判断延迟界与吞吐界
某机器的循环体如下（每轮 4 条指令），执行端口配置为：1 个整数端口（cmp、bne 各占 1 周期）、1 个乘法端口（mul 占 2 周期）、1 个 FMA 端口（fma 占 1 周期发射、4 周期延迟）：
loop:
fma f0, f2, f4, f0 // acc = acc + w * x (延迟 4 周期, 依赖上一轮的 f0)
addi r3, r3, 4 // 指针推进
cmp r3, r1 // 边界比较
bne loop
问：(a) 延迟界是多少周期/迭代？(b) 吞吐界是多少周期/迭代？(c) 实际性能约为多少，IPC 是多少？(d) 如果程序需要跑 10⁶ 次迭代，在 3.0 GHz 下大约耗时多久？
【答案】
(a) 延迟界：跨迭代的真依赖只有 fma 链（f0 依赖上一轮的 f0），addi/cmp/bne 的链长都是 1 周期且远短于 FMA 链。所以关键路径 = 4 周期/迭代。
(b) 吞吐界：把每类操作的需求量除以对应端口的服务能力：
- FMA 端口：1 条
fma/ 1 周期 = 1 周期 - 乘法端口：本轮没有
mul= 0 周期 整数端口：
addi+cmp+bne= 3 条整数操作，端口 1 条/周期 = 3 周期吞吐界 = max(1, 0, 3) = 3 周期/迭代。
(c) 实际性能 ≈ max(延迟界, 吞吐界) = max(4, 3) = 4 周期/迭代，即 延迟受限。IPC = 4 条指令 / 4 周期 = 1.0。
(d) 10⁶ 迭代 × 4 周期 = 4×10⁶ 周期；在 3.0 GHz 下 = 4×10⁶ / 3×10⁹ s ≈ 1.33 ms。
追问：如果给这台机器再加一个整数端口（整数吞吐变成 2 条/周期），会变快吗？不会——吞吐界变成 max(1, 0, 1.5) = 1.5 周期，仍小于延迟界 4 周期，程序依旧是延迟受限，性能不变。只有缩短 FMA 依赖链（例如用 2 个累加器交替累加、循环结束后合并）才能提速：2 个累加器把 FMA 链变成 2 周期/迭代，此时瓶颈切换到吞吐界的 3 周期/迭代，性能从 4 → 3 周期/迭代，提升 1.33×；再用 4 个累加器则 FMA 链 1 周期/迭代 < 3 周期，彻底变成吞吐受限，无论如何加速比都止步于 4/3 ≈ 1.33×。这就是”延迟界与吞吐界在优化过程中会互相转换”的典型例证。
思考题 2：为什么单核 OoO 掩盖不了 DRAM 延迟？
某处理器：发射宽度 W = 4 条指令/周期，ROB 可容纳 256 条指令，一次 DRAM 访问延迟 248 周期（@4 GHz），程序在两次访存之间有约 20 条相互独立的指令。
问：(a) 用 Little 定律计算，要维持 IPC = 4 需要多少条指令在途？(b) 该机器能提供多少？(c) 如果你是架构师，有哪三种手段补上这个缺口，各自代价是什么？
【答案】
(a) Little 定律：在途指令数 = 延迟 × 目标吞吐 = 248 周期 × 4 条/周期 = 992 条指令。
(b) 该机器只有 256 条 ROB 条目，仅能支撑 992 条的约 26%。等效地，可持续的吞吐 ≈ 256 / 248 ≈ 1.03 条/周期，即 IPC 掉到约 1——发射宽度 4 的硬件在这里只发挥了 1/4。
(c) 三种手段：
- 硬件多线程（SMT / interleaved multithreading）：在同一核上放 2–8 个执行上下文，A 线程等 DRAM 时发射 B 线程的指令。缺口 992 条需要约 992/256 ≈ 4 个线程（或按”每次访存携带 20 条独立指令”的模型：⌈(20+248)/20⌉ = 14 个线程才达 100% 利用率——这正是 GPU 一个 SM 放 64 个 warp 的原因）。代价：每个上下文的寄存器/存储开销，芯片面积与功耗；单线程的完成时间变长（吞吐导向的权衡）。
- 增加 ROB 深度 / 重命名寄存器数：把窗口从 256 扩到 1024。代价：面积与功耗按超线性增长，且调度复杂度与唤醒逻辑（wakeup/select）本身成为关键路径，频率会被拖低——讲义明确指出”动态调度开销显著”。
- 提高缓存命中率 / 软件预取：把 248 周期的 DRAM 延迟换成 L2 的 12 周期，缺口立刻变成 12×4 = 48 条，256 条的 ROB 绰绰有余。代价：需要程序员或编译器做分块（tiling）/ 预取 / 提高数据复用，改动算法结构；且缓存不命中的最坏情形仍存在。
补充结论：手段 3 是唯一不依赖硬件的，也是本课程反复强调的”利用局部性”。硬件手段 1 和 2 都直接消耗面积/功耗，而片上的功耗预算有限——这正是”ILP 撞墙、转向多核”的经济学根源。
思考题 3：一个 ILP 优化为什么在双核上几乎没加速？
程序 A：对一个 512 MB 的数组做 out[i] = f(in[i])，f 是 20 次浮点运算，in 和 out 都是 double。 某同学做了两项优化：（i）把 f 内部原本串行的表达式重排，使关键路径从 20 次 FMA 降到 5 次；（ii）用 OpenMP 把数组分给 2 个线程。 机器：2 核 × 8 宽 SIMD × 2（FMA）× 3.0 GHz（峰值 96 GFLOP/s 单精度；double 视为一半 = 48 GFLOP/s），DRAM 带宽 20 GB/s。
问：(a) 计算这个内核的算术强度。(b) 分别计算”带宽下限时间”与”双核计算下限时间”（元素数按 512 MB / 8 B = 6.4×10⁷）。(c) 预测优化 (i) 和 (ii) 各自的实际收益，并解释为什么”关键路径砍到 1/4”几乎没有帮助。
【答案】
(a) 算术强度：每个元素 20 FLOP，访存 8 B 读 + 8 B 写 = 16 B。
AI = 20 FLOP / 16 B = 1.25 FLOP/byte
机器平衡点 = 48 GFLOP/s ÷ 20 GB/s = 2.4 FLOP/byte。1.25 < 2.4 ⇒ 带宽受限。
(b) 元素数 N = 512 MB / 8 B = 6.4×10⁷。
带宽下限时间 = 总字节 / 带宽 = (6.4e7 × 16 B) / 20e9 B/s = 1.024e9 / 20e9 = 51.2 ms
计算下限时间(2 核) = 总 FLOP / 峰值 = (6.4e7 × 20) / 48e9 = 1.28e9 / 48e9 = 26.7 ms
计算下限时间(1 核) = 53.3 ms
带宽下限 51.2 ms 大于双核计算下限 26.7 ms ⇒ 用 2 个核时，程序卡在 51.2 ms 附近。
(c) 预测：
- 优化 (ii)（双核）：串行版受限于 1 核计算下限 53.3 ms（略大于带宽下限 51.2 ms），所以理论上限约 53.3/51.2 ≈ 1.04×……但由于单核实际很难达到理论峰值（延迟界、发射宽度、SIMD 利用率），串行版实测大概率在 70–90 ms，双核能压到约 51 ms 的带宽墙，实测约 1.4–1.7×，而非 2×。
- 优化 (i)（关键路径从 20 降到 5）：几乎没有帮助。原因是该内核的瓶颈是带宽（AI = 1.25 < 2.4），算术运算早就”藏在”访存后面了；而且 20 次 FMA 分布在 8 宽 SIMD 上只需要约 2.5 条向量指令，关键路径缩短带来的 ILP 收益根本无法越过 51.2 ms 的带宽地板。
诊断方法论：拿到任何内核，先算 AI 与 ridge point：
- AI < ridge ⇒ 先做带宽优化：数据复用（分块/融合循环）、减小数据宽度（float 代替 double、必要时量化）、避免多余的写-读往返（例如
a = a + b就地运算，而不是c = a + b再拷贝）、提高访存连续性以吃满 DRAM 行缓冲。- AI > ridge ⇒ 才轮到计算优化：缩短关键路径（抬升延迟界）、增加并行度（抬升吞吐界）、扩大 SIMD 宽度。
本讲（ILP/OoO）提供的全部是第二类工具；用错类别的优化，收益为零，这正是第 6 节”常见陷阱”中最贵的一条。