并发与并行基础

并发：关键在共享数据（卷 I 4.1.1）

• 并发软件用多个控制流解决一个问题，控制流可以是同一进程内的多个线程、单机或多机上协作的多个进程，也可以是纤程或协程。
• 区分并发与顺序编程的主要因素是对共享数据的读和/或写。两个控制流各自处理完全独立的数据，严格说不算并发，只是「同时计算」。
• 核心问题是协调多个读者/写者，保证结果可预测、正确。其中心是数据竞争 (data race)：两个以上控制流争着「读-改-写」同一块共享数据。识别并消除数据竞争是并发问题的关键（详见 线程同步原语、无锁编程与内存序）。

并行的几种分类（卷 I 4.1.2–4.1.4）

• 1989 年前的消费级处理器（6502、8086/80286/80386）都是串行的；如今并行无处不在，粒度从单 CPU 内的多个 ALU 到计算机集群。
• 隐式 vs 显式：隐式并行在 CPU 内部用并行部件加速单条指令流（ILP）；显式并行复制硬件以同时运行多条指令流，目的是让并发软件跑得更高效。GPU 也大量使用隐式并行。
• 任务并行 vs 数据并行：在一个核上算动画、另一个核上做碰撞检测是任务并行（异构操作并行）；把 1000 个蒙皮矩阵分成 4 份、每核算 250 个是数据并行（同一操作作用于多个数据）。真实程序两者都用。
• 弗林分类 (Flynn's Taxonomy)（Michael J. Flynn，1966）按指令流数与数据流数分四象限。注意「单数据」对二元运算指一对输入和一个输出。

• 书中称 SIMT 设计（大量轻量 SIMD 核）为 manycore，与 CPU 的 multicore（较少的重量级通用核，MIMD）相对。GPU 的 SIMT 细节见 GPU 并行架构、GPGPU 编程入门。

并发与并行正交（卷 I 4.1.5）

并发软件不需要并行硬件：多线程程序可以靠抢占式多任务跑在单个串行核上；反过来，ILP 加速的是单线程，对顺序程序和并发程序都有益。只要系统里有共享数据对象的多个读者/写者，就是并发系统；无论靠时间片还是真并行实现，本章的技巧都适用。

隐式并行：流水线（卷 I 4.2.1–4.2.3）

每条指令都要经过取指 (Fetch)、译码 (Decode)、执行 (Execute)、访存 (Memory access)、写回 (Register write-back) 五个阶段，各阶段由 CPU 内不同电路负责（控制单元与内存控制器取指、CU 译码、ALU/FPU/VPU 执行、内存控制器访存、寄存器写回）。非流水线 CPU 里一个阶段工作时其余都闲着；流水线每个时钟周期发射一条新指令，让多条指令同时「在飞」，就像洗衣机和烘干机同时运转。

flowchart LR
  F["取指"] --> D["译码"] --> E["执行"] --> M["访存"] --> W["写回"]

上图是五级流水线；理想情况下第 n 个周期取指第 n 条指令，同时第 n-1 条在译码，以此类推。

• 理论上 N 级流水线比串行快 N 倍，但指令间的依赖会打折扣，所以写高性能代码的程序员不能对 ILP 视而不见。
• 延迟与吞吐：单条指令的延迟是各级延迟之和 $T_{pipeline}=\sum_{i=0}^{N-1}T_i$；吞吐（每秒指令数）由最慢的一级决定 $f=\frac{1}{\max(T_i)}$。
• 流水线深度：把慢的级拆开能平衡各级延迟、提高吞吐，但级数越多，总延迟越高，停顿代价越大。实际 CPU 在 4–5 级到约 30 级之间折中。

停顿与三类依赖（卷 I 4.2.4–4.2.6）

某周期无法发射新指令叫停顿 (stall)，产生的空闲「气泡」逐级向后传播，也叫延迟槽 (delay slot)。三类依赖会导致停顿：数据依赖、控制依赖（分支依赖）、结构依赖（资源依赖）。

• 数据依赖：imul eax,10 后紧跟 add eax,7，add 要等 imul 走完流水线，五级流水线浪费 4 个周期。
  • 指令重排：在依赖指令之间塞入无关指令填满气泡。现代优化编译器很擅长自动做；但仍应看反汇编确认，并遵循 80/20 规则只优化真正影响性能的代码。
  • 乱序执行 (Out-of-Order Execution)：CPU 在「前瞻窗口」里分析寄存器使用，找不依赖在飞指令的指令提前发射。所以程序员不能指望 CPU 按书写顺序执行指令。编译器与 CPU 都保证单线程行为不变，但重排会让并发程序出错（见 无锁编程与内存序）。
• 分支依赖：cmp 与 jz 之间的依赖，CPU 得等比较结果才能决定跳转。
  • 推测执行 / 分支预测：猜一个分支继续发射，猜错就冲刷流水线从正确分支重来，即分支惩罚。最简单的静态猜法是「永不跳转」（对指令缓存友好）；稍好的是「向后跳转总跳、向前跳转不跳」（循环末尾是向后跳转）。高端 CPU 有能识别模式的分支预测硬件。PS3 的 Cell 分支预测器很差，而 PS4/Xbox One 的 AMD Jaguar 与 PS5/Xbox Series 的 Zen 2 都很先进。
  • 谓词化 (Predication)：两条路径都算，用全 0/全 1 掩码选结果（也叫 select 操作）。书中例子 SafeFloatDivide_pred：mask = 0U - (unsigned)(b != 0.0f)，用 memcpy 把浮点位模式转成无符号整数，(qu & mask) | (du & ~mask)。前提是两条路径都能安全执行：浮点除以零不会崩溃，整数除以零会抛异常导致崩溃（除非被捕获），所以例子改成浮点。书中称浮点除以零产生 QNaN（代码注释也写「b == 0.0f 时 q 为 QNaN」）——原书问题：按 IEEE 754，非零有限数除以 ±0 得到带符号的无穷大（并置除零标志），只有 0/0 才得到 QNaN；对本例无影响，因为 b == 0 时结果反正被掩码丢弃。
  • 取舍：这可能白费力气，x64 Clang 3.0.0 在 -O1 以上会看穿意图照样生成分支。谓词化只有在 ISA 提供 select 指令时才真正有用，如 PowerPC 的 isel、fsel、vecsel（PS3），在 PowerPC 平台上确实能带来性能提升。书中 Clang 3.0.0 的输出用 ucomiss + setp/setne + je 仍然分支。

超标量与 VLIW（卷 I 4.2.7–4.2.8）

• 标量处理器每周期最多发射一条指令；超标量 (Superscalar) 复制流水线各级电路，每周期从同一指令流取并发射两条以上。书中脚注：流水线和超标量是两种独立的并行，但多数超标量 CPU 也是流水线的。
• 超标量需要前端控制逻辑（通常带乱序与推测执行的调度器），并引入第三类依赖——资源依赖：例如两个整数 ALU 但只有一个 FPU 时，连续两条浮点指令不能同周期发射。
• 双路超标量约需两倍芯片面积，为了腾出晶体管，多数超标量 CPU 是 RISC（指令少而专一），与 CISC（指令多且复杂）相对。
• VLIW（超长指令字）：去掉复杂调度逻辑，由程序员/编译器把多个操作编进一条指令字的多个「槽」，省下的晶体管用于更多计算单元或更大缓存；编译器能从整个函数范围挑指令，窗口比 CPU 前瞻大得多。例：PS2 的向量单元 VU0、VU1 每条指令有 low/high 两个槽，手写汇编很难填满，后来有工具帮助把「每周期一条指令」的程序转换为高效的每周期两条格式。取舍：硬件更简单、潜在并行度更高，但把串行程序改造成能吃满 VLIW 的形式很难；可变宽 VLIW 等改进缓解了部分限制。

显式并行（卷 I 4.3）

按粒度从细到粗：

• 书中 PS4 架构图：CPU 1.6 GHz，8 GiB GDDR5，CPU 总线 20 GiB/s，缓存一致的「Onion」总线（每方向 10 GiB/s）与非缓存一致的「Garlic」总线（176 GiB/s）连接 GPU（约相当于 Radeon 7870，800 MHz，1152 个流处理器）。Xbox One：CPU 1.75 GHz，8 GiB 主存（图中标 GDDR3；原书问题：Xbox One 实际使用 8 GiB DDR3（带宽约 68 GB/s），而非 GDDR3，见 Digital Foundry《Project Scorpio tech revealed》(2017) 规格对比表，Wikipedia「Xbox One」硬件规格同），CPU 与 GPU 间缓存一致的通路 30 GiB/s、非一致通路 68 GiB/s，32 MiB eSRAM（最高 204 GiB/s），GPU 约相当于 7790（853 MHz，768 个流处理器）。缓存层次与一致性见 计算机硬件与内存层次。

与其他来源的关系

多线程渲染与任务系统（RTR4）从渲染应用阶段角度讲「多处理器流水线（时间并行）」与「并行处理（空间并行）」；GEA 这里讲的是 CPU 内部的指令流水线与硬件分类。两者用词相近但层次不同。