Lecture 1: Why Parallelism? Why Efficiency?（日期：Sep 23, 2025）

目录 · ← l0 · l2 →

Lecture 1: Why Parallelism? Why Efficiency?（日期：Sep 23, 2025）

概述：本讲是 CS149 的开篇，回答两个问题——为什么要并行（因为单核性能增长已几乎停滞，只能用更多处理单元来换取速度）与为什么要效率（FAST ≠ EFFICIENT，跑得快不等于用好了硬件）。课堂通过三个”人类处理器”演示（DEMO 1/2/3）直观展示并行编程的三大挑战：通信开销、负载不均与通信/计算比过高，并由此引出本课程的三大主线：并行思维（分解工作、分配工作、管理通信/同步）、并行硬件实现、以及效率思维。后半讲复习处理器与内存基础（指令、寄存器、ALU、cache、延迟与停顿），为后续课程打下硬件直觉。

一、核心概念与定义

1. Parallel Computer（并行计算机）

• 定义：A parallel computer is a collection of processing elements that cooperate to solve problems quickly —— 一组相互协作、共同快速求解问题的处理单元（processing elements）的集合。注意两个关键词：既要”多”（multiple processing elements），又要”协作”（cooperate），孤立的处理器堆在一起不构成并行计算机。
• 现实类比：一间厨房里多位厨师分工做一顿饭。只把 10 个厨师塞进厨房而不分工、不传菜，他们只会互相碍事；真正并行是每人负责一道工序（切菜、炒菜、装盘）并有序协作。
• 公式/图示：无固定公式，但”cooperate”一词暗含后续所有主题——如何分解（decompose）、如何分配（assign）、如何通信/同步（communicate/synchronize）。

2. Speedup（加速比）

• 定义：使用 P 个处理器相比使用 1 个处理器所获得的执行时间缩减倍数： speedup(using P processors) = execution time (using 1 processor) / execution time (using P processors)。 这是衡量”并行化是否值得”的第一指标。加速比 = 串行时间 ÷ 并行时间。
• 现实类比：一个工人搬 100 块砖要 100 分钟（T₁）；5 个工人一起搬只要 25 分钟（T₅）；speedup = 100/25 = 4。若因为搬砖时互相挡路只省了一半时间，speedup = 2。
• 公式/图示：

  speedup(P) = T(1) / T(P)
  

  课堂提问：在 10 个处理器的机器上只获得 2x speedup 算好结果吗？（答案是：绝对速度提升了，但效率只有 2/10 = 20%，远未用好硬件——见第 3 条。）

3. Efficiency（效率）

• 定义：加速比除以使用的处理器数：efficiency = speedup / P。它衡量每个处理器平均贡献了多少加速，是”用没用好硬件”的度量。
• 现实类比：10 个厨师做一道菜只比 1 个厨师快 2 倍——效率 = 2/10 = 20%，说明 8 个厨师基本在打酱油（等菜、闲聊、没活干）。
• 公式/图示：

  efficiency(P) = speedup(P) / P = T(1) / (P · T(P))
  

  理想并行效率为 1（线性加速），实际总是小于 1。

4. Amdahl’s Law（Amdahl 定律）

• 定义：设程序可并行部分占比为 p（0 ≤ p ≤ 1），不可并行（串行）部分占比为 1−p，则使用 P 个处理器时理论上限为： speedup_max(P) = 1 / ((1 − p) + p / P)；当 P → ∞ 时，speedup_max → 1 / (1 − p)。 也就是说：串行部分决定了加速比的天花板。本讲幻灯片本身没有给出 Amdahl’s Law 公式，而是通过三个课堂演示建立了”通信/负载不均这类开销会限制加速比”的直觉——Amdahl’s Law 正是把这种直觉形式化的经典分析工具，后续课程（L4–L6 关于工作分配、调度、局部性）会系统使用它。
• 现实类比：一个 5 人小组做汇报，其中 1 页幻灯片只有组长能写（串行部分）。无论其他 4 人把各自部分做得多快，总时间至少是”组长写那一页”的时间——这就是 1/(1−p) 的天花板。
• 公式/图示：

  串行部分占比 (1-p) ──► 不可并行，决定下限
  可并行部分占比 p   ──► 时间最多除以 P
  T(P) ≥ (1-p)·T(1) + p·T(1)/P
  speedup(P) ≤ 1 / ((1-p) + p/P)      (Amdahl's Law)
  

5. Communication Overhead（通信开销）

• 定义：并行单元之间传递数据（本讲演示中是”互相告诉对方 partial sum”）所花的时间。通信是限制最大加速比的首要因素——DEMO 1 的课堂观察：通信限制了能达到的最大加速比；把”处理器”（学生）挪近、或允许喊话（降低通信代价）后加速比提升。
• 现实类比：几个同学合写一份报告，每人写完一部分后要互相传文件、开会对齐。传文件、开会的时间就是通信开销；大家坐得越近、沟通越顺畅（”shout”），开销越小。
• 公式/图示：无固定公式；直觉上 T(P) ≈ 计算时间 + 通信时间 + 空闲时间。通信占比越高，加速比上限越低（DEMO 3 的结论）。

6. Load Imbalance（负载不均）

• 定义：工作没有平均分给各处理器，导致一部分”处理器”早早干完（idle），另一部分还在忙。负载不均会限制加速比——DEMO 2 的课堂观察：有的学生（处理器）没活干闲下来，而其他人还在忙；改善工作分配后加速比提升。
• 现实类比：自助餐厅只有一个打菜窗口，前面的人点得慢，后面排长队——窗口（处理器）忙死，排队的人（其它处理器）闲死。改成多个窗口按队伍平均分流后，整体吞吐立刻改善。
• 公式/图示：

  处理器 0: [##########] 忙
  处理器 1: [####] 忙完闲置
  处理器 2: [##############] 仍在忙 ← 拖慢整体
  完成时间 = max(各处理器耗时) —— 由最慢者决定！
  

7. 并行思维三步骤（Decompose / Assign / Communicate & Synchronize）

• 定义：本课程主线一”编写可扩展的并行程序”的三个步骤：
  1. Decompose（分解工作）：把问题拆成可以安全地并行执行的若干块；
  2. Assign（分配工作）：把工作块分配给各处理器；
  3. Manage communication/synchronization（管理通信与同步）：让处理器之间的通信/同步不成为加速比的瓶颈。
• 现实类比：组织一次搬家——先拆解任务（打包、搬运、布置），再分配给人（谁搬哪间房），最后约定协调方式（谁先到、走哪个门），否则楼下堵车（通信）或有人闲着（负载不均）。
• 公式/图示：无公式；它是全课程的思维框架，DEMO 1/2/3 分别对应第 3、2、1 步的失败案例。

8. FAST ≠ EFFICIENT（快 ≠ 高效）

• 定义：程序在并行计算机上跑得更快，并不代表它高效利用了硬件。课程主线三的核心口号。判断标准：是不是把机器提供的能力都用上了（程序员视角）；机器该配哪些能力（硬件设计者视角：performance vs convenience vs cost，cost = silicon area / power）。
• 现实类比：10 个工人搬砖，你只让 2 个人干活、8 个人在旁边看——速度确实比 1 个人快 2 倍，但效率只有 20%。
• 公式/图示：FAST != EFFICIENT。课堂提问：”2x speedup on a computer with 10 processors——good result?”（从效率看：不是）。

9. Instruction-Level Parallelism（ILP，指令级并行）与 Superscalar Execution（超标量执行）

• 定义：一条指令流内互不依赖的指令可以并行执行。超标量（superscalar）处理器在硬件上自动找出一段指令序列中的独立指令，把它们放到多个执行单元（ALU）上并行执行。示例：a = x*x + y*y + z*z 中三条 mul 互不依赖，ILP = 3，可同时执行；但第 4、5 条 add 依赖前面的乘法结果，只能串行等待。
• 现实类比：做菜时”烧水”和”切菜”互不依赖，可以同时进行（ILP=2）；但”等水开再下面条”是依赖关系，必须排队。
• 公式/图示：

  指令 1: mul R0,R0,R0   ─┐
  指令 2: mul R1,R1,R1   ─┼─► 三条乘法互相独立（ILP = 3）
  指令 3: mul R2,R2,R2   ─┘
  指令 4: add R0,R0,R1   ← 依赖 1、2
  指令 5: add R3,R0,R2   ← 依赖 4
  

10. Power Wall（功耗墙）

• 定义：动态功耗 dynamic power ∝ capacitive load × voltage² × frequency；静态功耗来自晶体管即使不工作也在漏电（leakage）。功耗高 = 发热高，散热成了硬约束，因此不能无限提高时钟频率——这是”单核性能停止增长”的两大原因之一（另一个是 ILP 挖掘殆尽）。
• 现实类比：CPU 超频就像把跑步机调快——跑得更快但发热更猛，最后必须降速散热（clock down to cool off），否则烧坏。
• 公式/图示：

  P_dynamic ∝ C_load × V² × f      (电压的平方！降电压是降功耗最有效的杠杆)
  

  课堂数据：Intel Core i9 10900K（台式机）95W；Apple M1 笔记本 13W；NVIDIA RTX 4090 GPU 450W；微波炉 900W；手机处理器 0.5–2W；世界最快超算 Frontier 达兆瓦级（21 MW）。

11. Memory Address Space、Load 指令与 Memory Access Latency（内存地址空间、装载指令与访存延迟）

• 定义：内存可视为字节数组，每个字节用地址（数组下标）标识（假设 byte-addressable）。处理器用 load 指令把内存数据搬进寄存器（如 ld R0 ← mem[R2]），用 store 写回。Memory access latency（访存延迟） 是内存系统把数据交给处理器所需的时间（如 100 个时钟周期 / 100 nsec），远大于算术指令的时间。
• 现实类比：图书馆取书——从书架上拿一本（寄存器）是瞬间的；从地下书库调书（DRAM）要等几分钟（几百个周期）。
• 公式/图示：

  ld  r0, mem[r2]   ← 从内存取数据，需要 ~100+ 周期
  ld  r1, mem[r3]
  add r0, r0, r1    ← 依赖上面两条 load，必须等它们完成 → "stall"（停顿）
  

12. Stall（停顿）

• 定义：当指令流中后续指令依赖一条尚未完成的指令时，处理器无法推进，称为 stall。访存是停顿的主要来源。缓存（cache）的存在就是为了缩短停顿长度（降低访存延迟），让处理器多数时间访问”驻留在 cache 里的数据”。
• 现实类比：流水线上”等料”——上一道工序还没做完，下一道工序只能干等，整条线空转。
• 公式/图示：见第 11 条示例：add 必须等两个 load 完成，期间处理器空转。

13. Cache、Cache Line 与两种 Locality（缓存、缓存行与局部性）

• 定义：cache 是芯片上的存储，保存内存中一部分值的副本；若地址在 cache 中，处理器访问它就远快于访问 DRAM。cache 按 cache line（缓存行） 粒度工作（如每行 4 字节）。替换策略（如 LRU：最近最少使用）决定腾出空间时淘汰谁。两种数据局部性：
  • Spatial locality（空间局部性）：装入一条 cache line 会”顺带预载”同一行里相邻地址的数据，后续访问不同地址也能命中；
  • Temporal locality（时间局部性）：反复访问同一地址导致命中。
• 现实类比：去超市买一打鸡蛋——店员从仓库（DRAM）搬来一整箱（cache line），你拿一个（命中）后剩下的都在手边（空间局部性）；明天还要鸡蛋，又去同一家店（时间局部性）。
• 公式/图示（课堂 Cache 示例 1：总容量 8 字节、4 字节 cache line、LRU）：

  访问序列: 0x0, 0x1, 0x2, 0x3, 0x4, 0x5, 0x0 ...
  cache 状态（2 条 line）:
  load 0x0 → "cold miss"，装入 line 0x0（含地址 0x0-0x3）
  访问 0x1/0x2/0x3 → 同一行内命中（空间局部性）
  load 0x4 → "cold miss"，装入 line 0x4（含地址 0x4-0x7）
  再次访问 0x0 → 命中（时间局部性，line 0x0 还在）
  

14. Cache Hierarchy（缓存层级）

• 定义：现代机器的线性内存地址空间抽象由多级缓存 + DRAM 共同实现：L1 → L2 → L3 → DRAM。离处理器越近、容量越小、延迟越低。课堂数据（Kaby Lake CPU @ 4 GHz）：L1 命中 4 周期，L2 12 周期，L3 38 周期，DRAM 最佳情况约 248 周期。
• 现实类比：厨房手边调料架（L1，随手拿）、橱柜（L2，走两步）、楼下超市（L3）、城外仓库（DRAM）——越近越快，但能放的东西越少。
• 公式/图示：

         处理器
           │
       L1 cache (32 KB)      ~4 cycles
           │
       L2 cache (256 KB)     ~12 cycles
           │
       L3 cache (20 MB)      ~38 cycles
           │
       DRAM (64 GB)          ~248 cycles
  

15. 数据移动的能耗成本（Data Movement Energy Cost）

• 定义：现代系统设计的经验法则：总是尽量减少计算机中的数据移动。粗算数值：整数运算 ~1 pJ；浮点运算 ~20 pJ；从片内 1mm 外的小 SRAM 读 64 位 ~26 pJ；从低功耗移动 DRAM（LPDDR）读 64 位 ~1200 pJ。推论：以 10 GB/s 读内存约耗 1.6 W——而整个移动 GPU 的功耗预算才约 1 W。利用局部性至关重要（Exploiting locality matters!!!）。
• 现实类比：把文件从自己电脑拷到 U 盘（片内）几乎不费电；上传到云再从云下载（DRAM 级别）既慢又耗电——能本地复用的数据绝不要来回搬运。
• 公式/图示：

  整数 op ~1 pJ  <  浮点 op ~20 pJ  <  片内 SRAM 读 64bit ~26 pJ  <  LPDDR 读 64bit ~1200 pJ
  （相差约两个数量级 → 少搬数据 = 最有效的省电手段）
  

16. 课堂演示汇总（DEMO 1 / 2 / 3）

• 定义：三次”人类处理器”课堂实验的观察与结论汇总： | 演示 | 实验设置 | 课堂观察 | 结论 | |—|—|—|—| | DEMO 1（第一个并行程序） | 多名学生各算一部分 partial sum，再汇总 | 通信（互相告诉 partial sum）限制了能达到的最大加速比；把学生挪近/允许喊话（降低通信代价）后加速比提升 | 通信开销是加速比的首要瓶颈，最小化通信成本 = 提升加速比 | | DEMO 2（扩展到 4 个”处理器”） | 4 名学生分工算 | 工作分配不均限制了加速比——有人提前干完闲置，有人还在忙；改善分配后加速比提升 | 负载不均让处理器空转，均衡分配是关键 | | DEMO 3（大规模并行） | 全班一起算一个通信占比高的问题 | 该问题通信相对计算的比例很大；通信成本可以主导并行计算，严重限制加速比 | 通信/计算比过高的问题不适合并行（对问题本身的选择很重要） |
• 现实类比：三个演示分别对应”传话太慢”（通信）、”有人闲有人忙”（负载不均）、”全程都在传话没人在干活”（通信/计算比过高）三种失败模式。
• 公式/图示：无公式；直觉式结论——加速比 ≈ 计算时间 / (计算时间 + 通信时间 + 空闲时间)。

17. 现代并行硬件全景（Motivation: why parallel hardware is everywhere）

• 定义：单核性能停滞的背景下，并行 + 专用硬件遍布各类设备（幻灯片数据）： | 硬件 | 关键参数 | 用途/说明 | |—|—|—| | Intel Core i9-10900K（Comet Lake, 2020） | 10 核 CPU | 消费级多核 CPU | | AMD Ryzen Threadripper 3990X | 64 核、4.3 GHz、4 个 8 核 chiplet | 工作站级多核 | | NVIDIA AD102 / GeForce RTX 4090（2022） | 18,432 个 fp32 乘法器、144 个 SM、760 亿晶体管 | 消费级 GPU | | Frontier（Oak Ridge 国家实验室） | 9472 × 64 核 AMD CPU（606,208 核）+ 37,888 块 Radeon GPU，21 MW | 2022 年秋季世界第一超算 | | Apple A15 Bionic（iPhone 13/14） | 150 亿晶体管：2 大 + 4 小 CPU 核、多核 GPU、Neural Engine（NPU）、图像/视频编解码、传感器处理器 | 移动端并行 + 专用处理 | | Raspberry Pi 3 | 四核 ARM A53 CPU | 嵌入式/教育平台 |
• 现实类比：从手机（A15 的 6 核 CPU + GPU + NPU）到超算（Frontier 的 60 万核），”并行 + 专用化”是唯一能继续提升性能的路线——软件必须配合（写并行代码），否则新硬件毫无用处。
• 公式/图示：见概念 10 的功耗墙公式；设计驱动力 = 性能（更多并行单元）÷ 成本（硅面积、功耗、散热）。

二、代码示例与详细解说（本讲重点）

示例 1：从 C 程序到指令流，再到 ILP 调度（汇编）

代码（汇编）：

// 原始 C 代码（课堂幻灯片示例）
int main(int argc, char** argv) {
    int x = 1;
    for (int i = 0; i < 10; i++) {
        x = x + x;
    }
    printf("%d\n", x);
    return 0;
}

; 编译后（x86-64 汇编片段，摘自幻灯片）——程序就是处理器指令的列表！
_main:
  pushq %rbp
  movq  %rsp, %rbp
  subq  $32, %rsp
  movl  $1, -20(%rbp)      ; x = 1
  movl  $0, -24(%rbp)      ; i = 0
.L1:
  cmpl  $10, -24(%rbp)     ; i < 10 ?
  jge   .L2                ; 不成立则跳出循环
  movl  -20(%rbp), %eax
  addl  -20(%rbp), %eax    ; x = x + x
  movl  %eax, -20(%rbp)
  movl  -24(%rbp), %eax
  addl  $1, %eax           ; i = i + 1
  movl  %eax, -24(%rbp)
  jmp   .L1
.L2:
  leaq  fmt(%rip), %rdi
  movl  -20(%rbp), %esi
  callq printf             ; printf("%d\n", x)
  ...
  ret

; ILP 关键示例（幻灯片核心）：计算 a = x*x + y*y + z*z
; 假设寄存器初值 R0 = x, R1 = y, R2 = z
  mul R0, R0, R0    ; 指令 1：R0 = x*x
  mul R1, R1, R1    ; 指令 2：R1 = y*y
  mul R2, R2, R2    ; 指令 3：R2 = z*z
  add R0, R0, R1    ; 指令 4：R0 = x*x + y*y
  add R3, R0, R2    ; 指令 5：R3 = x*x + y*y + z*z = a

【代码做了什么？】

• 第一段 C 程序 x = x + x 循环 10 次：每次迭代把 x 翻倍，最终 x = 2¹⁰ = 1024 并打印。编译后变成一段 x86-64 汇编——从处理器的视角看，程序只是一串指令（取指、译码、执行、写回），幻灯片借此纠正”程序 = 高级语言代码”的直觉。
• 第二段汇编实现 a = x*x + y*y + z*z：先分别对三个输入平方（3 条 mul），再两次加法合并。若处理器每时钟只能执行一条指令，这段程序需要 5 个时钟。
• 课堂问题：”能做得更好吗？”——如果处理器有多个执行单元（ALU）呢？

【并行机制解说】

• 这演示的是 ILP（指令级并行）+ superscalar（超标量）执行，对应本讲”历史上两大单核提速手段之一”。
• 三条 mul 指令互相独立（各自的输入来自不同寄存器），可以同时发射到多个执行单元。若有 3 个 ALU：

  时间 t=1:  mul R0,R0,R0   mul R1,R1,R1   mul R2,R2,R2   （3 条并行，ILP=3）
  时间 t=2:  add R0,R0,R1                                    （依赖 1、2，只能等）
  时间 t=3:  add R3,R0,R2                                    （依赖 4）
  → 3 个时钟完成，而不是 5 个！
  

• 但注意：指令 4 依赖指令 1、2 的结果，指令 5 依赖指令 4——依赖关系是硬约束，并行调度必须满足”若 X 依赖 Y，则 X 必须比 Y 晚执行”（幻灯片”respect program order”问题的核心：无论怎样乱序调度，程序输出必须与按程序顺序执行完全一致）。
• 对应概念：ILP 的”并行”发生在单条指令流内部，由硬件（out-of-order control logic）自动发现，程序员无需显式表达——这与后面要学的 multi-core（多指令流并行）和 SIMD（数据并行）有本质区别。

示例 2：串行 vs 并行求和（std::thread + Amdahl’s Law 分析）

代码（cpp）：

// parallel_sum.cpp —— 对应课堂 DEMO 1/2 的"人类处理器"演示
// 编译运行：g++ -O2 -std=c++17 parallel_sum.cpp -o parallel_sum -pthread
//           ./parallel_sum [线程数 P]
#include <iostream>
#include <vector>
#include <thread>
#include <numeric>
#include <chrono>
#include <cstdlib>

// 串行实现：单线程顺序累加
double serial_sum(const std::vector<double>& v) {
    double sum = 0.0;
    for (double x : v) sum += x;      // 一个"处理器"干完全部活
    return sum;
}

// 每个线程负责一段连续区间 [begin, end)，把局部和写回独立槽位
void partial_sum(const std::vector<double>& v, size_t begin, size_t end, double* out) {
    double s = 0.0;
    for (size_t i = begin; i < end; ++i) s += v[i];
    *out = s;                          // 各写各的槽位，无需锁（无共享写）
}

double parallel_sum(const std::vector<double>& v, int P) {
    const size_t n = v.size();
    const size_t chunk = (n + P - 1) / P;      // 1) 分解 + 2) 均分分配（blocked assignment）
    std::vector<double> partials(P, 0.0);
    std::vector<std::thread> threads;
    threads.reserve(P);
    for (int t = 0; t < P; ++t) {
        size_t begin = t * chunk;
        size_t end   = std::min(begin + chunk, n);
        threads.emplace_back(partial_sum, std::cref(v), begin, end, &partials[t]);
    }
    for (auto& th : threads) th.join();        // 3) 同步点：等待所有线程完成
    return std::accumulate(partials.begin(), partials.end(), 0.0);  // 通信：归约 partial sums
}

int main(int argc, char** argv) {
    const size_t N = 10'000'000;             // 1e7 个 double ≈ 80 MB
    const int P = (argc > 1) ? std::atoi(argv[1]) : 4;
    std::vector<double> v(N);
    for (size_t i = 0; i < N; ++i) v[i] = (i % 7) * 0.5;

    auto t0 = std::chrono::steady_clock::now();
    double s1 = serial_sum(v);
    auto t1 = std::chrono::steady_clock::now();
    double sp = parallel_sum(v, P);
    auto t2 = std::chrono::steady_clock::now();

    auto ms = [](auto a, auto b) {
        return std::chrono::duration<double, std::milli>(b - a).count();
    };
    std::cout << "P = " << P
              << "  serial = " << ms(t0, t1) << " ms"
              << "  parallel = " << ms(t1, t2) << " ms"
              << "  speedup = " << ms(t0, t1) / ms(t1, t2) << "\n";
    std::cout << "sum check: " << (s1 == sp ? "OK" : "MISMATCH") << "\n";
    return 0;
}

【代码做了什么？】

• serial_sum：一个”处理器”从头到尾累加 1 千万个元素，作为基准时间 T₁。
• parallel_sum：把数组按线程数 P 切成 P 个连续块（分解工作）；每个 std::thread 执行 partial_sum 负责自己那块（分配工作），把局部和写进 partials[t]（互不冲突的独立槽位）；主线程 join() 等待所有线程完成（同步点），最后把 P 个局部和相加得到总和（通信/归约）。
• 输出三个关键数字：串行时间、并行时间、speedup = T₁/T_P，并校验两种结果一致。

【并行机制解说】

• 这段代码把课堂 DEMO 1/2/3 的三个观察全部实体化：
  • 通信开销（DEMO 1）：最终把所有 partials 归约相加、以及线程创建/join 的开销，就是”互相告诉对方 partial sum”的代价。P 越大，这部分在总时间里占比越高——这正是 Amdahl’s Law 里”串行部分”的一种来源（speedup ≤ 1/(1−p)，其中 1−p 包含线程启动、join、最终归约）。
  • 负载分配（DEMO 2）：均分 chunk = (n+P-1)/P 是”改善分配”的体现；若数组长度不能被 P 整除，某些线程多算一个元素，整体完成时间由最慢线程决定（max 而非 average）——负载不均的直接后果。
  • 同步点：join() 是显式同步——主线程必须等所有 worker 完成才能归约，这就是”管理 communication/synchronization 使其不限制 speedup”的主题。
• 一个值得做的实验：P = 1、2、4、8 分别跑一次。你通常会发现 speedup 不是线性增长的，且随 P 增大收益递减——因为线程创建/join/归约这些串行部分不变，Amdahl 定律开始起作用。
• 对应概念：本讲三大主题（分解工作、分配工作、管理通信/同步）+ speedup 定义 + Amdahl’s Law。

示例 3：Cache 模拟器——复现课堂 Cache 示例 1/2（LRU + 局部性）

代码（c）：

// cache_sim.c —— 模拟幻灯片中的 cache：总容量 8 字节、4 字节 cache line、LRU 替换
// 编译运行：gcc -O2 cache_sim.c -o cache_sim && ./cache_sim
#include <stdio.h>
#include <string.h>

#define LINES 2          /* cache 容量：2 行 */
#define LINE_BYTES 4     /* 每行 4 字节 */
#define MEM_SIZE 16      /* 内存：16 字节数组 */

/* 用 cache 执行一次 load 访问，返回是否命中；命中则更新 LRU 顺序 */
/* LRU 约定：lru_order[i] 越小越"新"（0 = 最近使用），越大越"旧" */
static int access_cache(unsigned addr, unsigned cache_lines[LINES],
                        int lru_order[LINES], int* misses) {
    int i, hit_line = -1;
    for (i = 0; i < LINES; i++)          /* 查找地址所在行是否在 cache 中 */
        if (cache_lines[i] == addr - addr % LINE_BYTES) { hit_line = i; break; }

    if (hit_line >= 0) {
        /* 命中：被访问的行变成"最新"（=0），其余行变旧（+1） */
        for (i = 0; i < LINES; i++)
            if (i != hit_line) lru_order[i]++;
        lru_order[hit_line] = 0;
        return 1;                        /* hit */
    }
    /* miss：按 LRU 淘汰最旧行（lru_order 值最大者），装入新行 */
    int victim = 0;
    for (i = 1; i < LINES; i++)
        if (lru_order[i] > lru_order[victim]) victim = i;
    cache_lines[victim] = addr - addr % LINE_BYTES;
    for (i = 0; i < LINES; i++)
        if (i != victim) lru_order[i]++;
    lru_order[victim] = 0;
    (*misses)++;
    return 0;                            /* miss */
}

int main(void) {
    /* 幻灯片 Cache 示例 1：访问序列 0x0..0x5 附近 —— 展示空间/时间局部性 */
    unsigned seq1[] = {0x0, 0x1, 0x2, 0x3, 0x0, 0x1, 0x4, 0x5, 0x0};
    /* 幻灯片 Cache 示例 2：顺序读完整 16 字节，再读一遍 —— 展示 capacity miss */
    unsigned seq2[32];
    for (int i = 0; i < 16; i++) seq2[i] = i;
    for (int i = 0; i < 16; i++) seq2[16 + i] = i;   /* 第二遍：同样的 0..15 */

    unsigned lines[LINES] = {0xFFFFFFFF, 0xFFFFFFFF};
    int order[LINES] = {0, 1}, misses = 0;
    printf("== 示例 1（局部性）==\n");
    for (size_t i = 0; i < sizeof(seq1) / sizeof(seq1[0]); i++) {
        int hit = access_cache(seq1[i], lines, order, &misses);
        printf("访问 0x%x: %s\n", seq1[i], hit ? "hit" : "MISS");
    }
    printf("共 %d 次 miss\n", misses);

    misses = 0;
    memset(lines, 0xFF, sizeof(lines));
    order[0] = 0; order[1] = 1;
    printf("\n== 示例 2（第二遍为何不命中）==\n");
    for (size_t i = 0; i < sizeof(seq2) / sizeof(seq2[0]); i++) {
        int hit = access_cache(seq2[i], lines, order, &misses);
        if (i < 16 || !hit)   /* 第一遍全部打印；第二遍只打印 miss */
            printf("访问 0x%x: %s\n", seq2[i], hit ? "hit" : "MISS");
    }
    printf("两遍共 %d 次 miss（第二遍的 miss 即 capacity miss）\n", misses);
    return 0;
}

【代码做了什么？】

• 程序用 2 行 × 4 字节、LRU 策略的软件 cache 模拟器，复现幻灯片 Cache 示例 1/2 的两次实验。
• 示例 1：访问序列 0x0, 0x1, 0x2, 0x3, 0x0, 0x1, 0x4, 0x5, 0x0——第一次访问 0x0 是 cold miss（装入 line 0x0，顺带覆盖 0x0–0x3），随后访问 0x1/0x2/0x3 命中（空间局部性）；再次访问 0x0 命中（时间局部性）。
• 示例 2：顺序读完整 16 字节（0x0–0xF）后再读一遍。第一遍 4 个 cold miss（每行一次）；第二遍读 0x0 时它早已被 0x8 逐出——因为 2 行的 cache 只装得下最后两行（0x8、0xC），这就是幻灯片讨论题”为什么第二遍读 0x0 不是 hit”的答案：capacity miss。若 cache 有 4 行，整个 16 字节数组全部驻留，第二遍全部命中。
• 注意：模拟器里那个看似多余的 LRU 循环是故意的教学注释占位，实际更新逻辑在 miss/hit 分支内完成——建议读者自己把 access_cache 的 LRU 维护简化重写一遍（练习：改成 4 行 cache，观察第二遍全命中）。

【并行机制解说】

• 对应概念：cache / cache line / cold miss / capacity miss / spatial & temporal locality / LRU。cache 是”实现内存抽象”的硬件细节——只影响性能、不影响程序输出；本模拟器正是把这个”性能层”单独拿出来观察。
• 为什么对并行编程重要？多核机器上每个核都有自己（或共享）的 cache 层级，数据在 cache 里的位置直接决定访存是 4 周期（L1）还是 ~248 周期（DRAM）；后续课程（L6 局部性与通信）会看到：并行程序的数据布局、线程间数据共享方式，本质上都在操纵”数据落在哪一级 cache”。
• 联系第 15 条概念：数据移动能耗比计算高 1–3 个数量级，因此”提高 cache 命中率 = 减少昂贵的数据搬运 = 同时省时省电”。

三、关键要点

1. 单线程性能增长已几乎停止，软件必须自己并行化：历史上单线程 CPU 性能约每 18 个月翻倍（”软件开发者什么都不做，代码明年自动变快”）；如今频率提升受功耗墙限制、ILP 挖掘已见顶（”The Free Lunch Is Over”，Herb Sutter），架构师只能靠加更多并行执行单元或专用单元提速——软件不并行就没有免费午餐。
2. 并行编程的三大挑战 = 通信开销、负载不均、通信/计算比：DEMO 1 证明通信限制加速比；DEMO 2 证明负载不均限制加速比；DEMO 3 证明当问题本身通信远多于计算时，并行几乎无济于事。对应并行思维三步骤：分解工作、分配工作、管理通信/同步。
3. FAST ≠ EFFICIENT：2x speedup 在 10 处理器机器上只是”快”，效率 = 20% 才是”用好了硬件”。效率思维贯穿全课程。
4. 程序 = 一串指令；处理器 = 取指/译码 + 寄存器 + ALU：理解 ILP 从”指令依赖图”出发——互不依赖的指令可并行（superscalar 自动发现），依赖关系必须按序。但 ILP 的收益递减（4 发射宽度基本吃光可用 ILP）。
5. 访问数据的方式决定性能与功耗：cache 层级（L1/L2/L3/DRAM）把”线性内存”抽象实现为 4→12→38→~248 周期的阶梯；数据移动能耗比计算高 1–3 个数量级——”高效的处理器几乎总是归结为高效地访问数据（accessing data efficiently）”。

四、常见陷阱与注意事项

1. 混淆 FAST 与 EFFICIENT：看到”程序在并行机上快了 2 倍”就欢呼，却不检查 speedup/P（效率）。在 10 核机器上 2x speedup 意味着 8 个核在闲置，不是好结果。
2. 忽视通信开销：并行化时只盯着计算拆分，忘了线程间传数据（partial sums、共享结果）的时间。DEMO 1 的教训：通信是加速比的第一杀手；降低通信代价（更近、更高效的数据交换）比增加处理器数更有效。
3. 负载不均 = 最慢者决定一切：并行完成时间由 max（最慢处理器）而非平均决定。即使只有 10% 的尾部工作，也会拖垮整体加速比——分配工作要尽量均衡。
4. 并行开销大于收益：线程创建、join、同步、归约都是”串行部分”。对小问题（N 很小），并行化的固定开销可能超过收益，甚至比串行更慢——先算 Amdahl 上限再动手。
5. 误解 Amdahl’s Law：误以为”p=0.9 就一定能接近 10 倍加速”。注意：(a) p 是可并行部分占比，串行部分 1−p 决定天花板 1/(1−p)；(b) 通信/同步/负载不均造成的低效相当于放大了 1−p；(c) P→∞ 时加速比收敛到 1/(1−p)，再多处理器也无济于事。
6. 把 cache 当成”正确性”问题：cache 是实现细节——它不改变程序输出，只影响性能（”does not impact the output of a program, only its performance”）。写程序时不要依赖 cache 行为保证正确性；但要用局部性（时间/空间）换取性能。

五、思考题（带答案）

Q1. 课堂 DEMO 1 中，把学生（处理器）挪近一点、或允许他们喊话，为什么能提升加速比？这对应并行编程的哪个环节？

• 答案：DEMO 1 中每个学生计算一部分总和，然后需要把 partial sum 告诉组长合并。通信（传 partial sum）的时间占用了总时间，限制了加速比；挪近/喊话降低了通信代价，使加速比提升。这对应并行思维第三步”管理 communication/synchronization，使其不限制 speedup”——通信开销是加速比的实际瓶颈，降低通信成本是提升并行性能的第一抓手。

Q2. 某程序 90% 可并行（p = 0.9）。用 4 个处理器理论加速比上限是多少？若实际只测到 2x speedup，效率是多少？可能的原因有哪些？

• 答案：由 Amdahl’s Law，speedup_max(4) = 1 / (0.1 + 0.9/4) = 1 / 0.325 ≈ 3.08。实际 2x speedup 的效率 = 2/4 = 50%。原因可能是：通信开销、负载不均、同步/启动开销——这些都等效于扩大了串行部分（1−p），把上限从 3.08 进一步压低到 2。

Q3. 为什么说”数据移动”是效率问题的核心？用课堂给出的能耗数字说明。

• 答案：整数运算约 1 pJ，而从低功耗 DRAM（LPDDR）读 64 位约 1200 pJ——搬一次数据比算一次数贵三个数量级。以 10 GB/s 读内存约 1.6 W，已超过整个移动 GPU 的功耗预算（~1 W）。因此”高效处理几乎总是归结为高效访问数据”：尽量让数据留在 cache 里（时间/空间局部性）、减少跨层级的数据搬运，是性能和功耗双赢的关键。

注意：本讲内容直接服务于 Assignment 1（Analyzing Parallel Program Performance on a Quad-Core CPU，10 月 6 日截止）——该作业在四核 Intel CPU 上使用 ISPC 分析并行程序性能，幻灯片预告的对照基线是”单线程 C 程序（-O3 编译）”vs”用上全部并行资源（4 核 + AVX SIMD + hyper-threading）的程序”，预期可达约 32–40x 加速。AVX、hyper-threading 等术语将在 Lecture 2 讲解。