Lecture 1: Why Parallelism? Why Efficiency?

目录 · ← l0 · l2 →

第二部分：逐讲学习笔记

Lecture 1: Why Parallelism? Why Efficiency?

1. 章节标题与概述

Lecture 1: Why Parallelism? Why Efficiency?

• 本讲核心问题：为什么从 2004 年前后开始，”等下一代机器变快”这条免费午餐（the free lunch is over）彻底消失，程序员必须自己写并行代码？以及更进一步——“更快”不等于”更高效”（FAST != EFFICIENT）：在 10 个处理器的机器上拿到 2 倍加速比，究竟算不算好结果？本讲用三个课堂演示（DEMO 1/2/3）说明并行程序的性能上限由通信（communication）、负载均衡（load balance）和计算/通信比决定，而不是由处理器数量决定。

• 涉及的主要硬件/软件机制：硬件侧包括指令级并行（ILP, Instruction-Level Parallelism）、超标量（superscalar）与乱序（out-of-order）执行、时钟频率与动态功率（dynamic power ∝ capacitive load × voltage² × frequency）、多核（multi-core）与片上异构/专用单元（GPU、TPU/NPU）、以及缓存层次（cache hierarchy）与 DRAM 带宽/延迟。软件侧包括问题的分解（decomposition）、把工作分配给处理器（work assignment）、处理器之间的通信与同步（communication / synchronization）管理，以及在多核 CPU、GPU 等不同并行编程环境（SIMD、多线程、CUDA、消息传递）中表达这些抽象。

• 在并行计算知识体系中的角色：本讲是全课程的动机与坐标系。它确立了三条贯穿整个学期的主题（course themes）：(1) 设计并写出可扩展的并行程序；(2) 理解并行硬件的实现机制与设计权衡（performance vs. convenience vs. cost）；(3) 始终以效率为目标。同时它给出后续所有讲座反复使用的两个度量：加速比 speedup(P) = T(1) / T(P) 与”数据移动是性能与能耗的主要成本”。后续的 ILP/基础架构（Lecture 2–3）、编程模型（Lecture 4–7）、一致性/同步（Lecture 10–17）、异构与专用化（Lecture 20）都在本讲划定的框架内展开。

• 配套材料：

  • extracted/01_whyparallelism.txt —— CMU 15-418/618 Fall 2026 Lecture 1 讲义（共 39 页）的逐页抽取文本，讲义 PDF 为 lectures/01_whyparallelism.pdf，位于 https://www.cs.cmu.edu/~418/lectures/ 之下，属已公开（可直接下载）。首页标注 Fall 2026，授课教师为 Brian Railing 与 Dimitrios Skarlatos；课程由 Kayvon Fatahalian 创建。讲义内容为课程行政信息（作业、考试、评分构成、协作政策，见 slide 3–12）与三条课程主题（slide 35–38）。
  • cs149_supp/efficiency.txt —— Stanford CS149 Lecture 1 “Why Parallelism? Why Efficiency?”（共 86 页，Kayvon Fatahalian 讲授的同一主题讲义）逐页抽取文本，属已公开的支持材料。它把 CMU 版压缩掉的技术论证细节补全了：程序=指令序列的处理器视角、ILP 与超标量的收益递减、功率墙（power wall）与频率封顶、缓存层次与数据访问延迟表、以及”数据移动的能耗”。本笔记中凡是标注了具体数值/图表来源的技术细节，均来自这份补充讲义。
  • 未公开部分：Fall 2026 的录像（Panopto/YouTube）在日程表中被注释隐藏，属未发布；Ed 讨论区（https://edstem.org/us/courses/102588/）、Autolab、Canvas 均需登录。Performance Analysis/Profiling、Transactional Memory、AI in System Design 等讲座的 Fall 2026 讲义尚未在公开目录发布；历史学期的对应 PDF 位于 /afs/cs/academic/class/15418-*/public/，需要 CMU 登录，属未公开。（本讲的讲义本身不受此限制，已公开。）
  • 课程背景（来自讲义 slide 3–12，仅记录讲义明写的事实）：四次编程作业（第 1 次独立完成，其余两人一组），分别使用 SIMD+多核并行、CUDA on NVIDIA GPU、共享地址空间模型、消息传递模型；一个 5 周的自选期末项目（默认 2 人一组）；约五次同行互评的 homework exercise；两次期中考试、无期末考试；成绩构成 25% 编程作业 / 40% 考试 / 25% 期末项目 / 10% quiz 与 exercise。

2. 核心概念与硬件/软件架构图解

2.1 程序与处理器：一切都从”指令序列”开始

• 定义与目的：从处理器的视角看，一个程序就是一张要顺序执行的指令列表（a program is just a list of processor instructions）。一条指令描述处理器要执行的一个操作，执行指令会修改计算机的状态（state）——状态即程序数据的取值，保存在处理器的寄存器或内存里。理解并行，第一步就是把”程序”从高级语言的语法结构降维成”状态 + 操作 + 依赖”。

• 直观解释（”它是什么？”）：把处理器想象成一位照着菜谱做菜的厨师：菜谱就是程序，每一步（切菜、下锅、调味）就是一条指令；厨师手边的小碗（寄存器）就是”执行上下文（execution context）”，装着当前要用的原料值；炉灶/刀具（ALU，算术逻辑单元 / execution unit）就是真正干活的地方；而”决定下一句菜谱读哪一行”的部分就是取指/译码（fetch/decode）。串行程序的加速史，本质上就是”把菜谱的每一步做得更快”——直到 2004 年前后这条路走不通了。

• 架构/机制图解：下面是最简单的单发射处理器（讲义中的 “very simple processor”）与”一条 add 指令的四个步骤”。

   ┌──────────────────────────────────────────────────────────┐
   │                    Processor (1 IPC)                     │
   │                                                          │
   │   ┌────────────────┐        ┌─────────────────────────┐  │
   │   │ Fetch / Decode │        │  Execution Context      │  │
   │   │  "next instr?" │◄──────►│  R0  R1  R2  R3  ...    │  │
   │   └───────┬────────┘        │  (= program state)      │  │
   │           │ instruction     └───────┬─────────▲───────┘  │
   │           ▼                         │ operands │ result  │
   │   ┌────────────────┐                ▼         │         │
   │   │  ALU / Exec    │──────────────────────────┘         │
   │   │  Unit          │                                    │
   │   └───────┬────────┘                                    │
   └───────────┼─────────────────────────────────────────────┘
               │ load / store
               ▼
        ┌──────────────┐
        │    Memory    │   byte-addressable array of bytes
        │  (DRAM/...)  │   e.g. addr 0x10 -> value 128
        └──────────────┘

  Executing "add R0 <- R0, R1" (R0=32, R1=64) in 4 steps:
    step 1: fetch next instruction from memory  (what to do next)
    step 2: read operands from registers        (R0=32, R1=64)
    step 3: ALU performs the arithmetic         (result = 96)
    step 4: write result back to register R0    (R0 := 96)

• 关键操作与性能特征：这台理想机器每个时钟周期执行一条指令（1 IPC）。于是”程序有多快”退化为两个可乘的因子：

        execution_time  =  instruction_count  ×  CPI  ×  clock_period
                             (程序/算法决定)     (微架构)   (工艺/功率)

只要把 CPI 从 3.5 降到 1.1、把频率从 10 MHz 拉到 3 GHz，即使指令数不变，程序也能快上百倍——这正是 1980–2000 年代发生的事（讲义 slide 18：更宽的数据通路 4→8→16→32→64 bit、更高效的流水线、ILP、更快的时钟）。延迟（一次访存 ~100+ 周期）会成为 CPI 的主要来源；吞吐量与带宽则由数据通路宽度、发射宽度和存储层次共同决定，这三个指标的关系构成了后面所有性能分析的骨架。

2.2 指令级并行（ILP）与超标量执行：处理器自己找并行

• 定义与目的：ILP（Instruction-Level Parallelism，指令级并行）指同一条指令流内部、互相没有依赖的指令可以被并行执行的程度。超标量（superscalar）处理器在一个时钟周期内取指/译码并发射多条指令到多个执行单元，由乱序控制逻辑（out-of-order control logic）自动在指令序列里找出可以并行的指令；编译器也可以在编译期找出独立指令并显式编码依赖关系。

• 直观解释（”它是什么？”）：想象一个厨房里有两口灶：菜谱要求”切三个土豆、然后把三个土豆倒进锅里、最后加盐”。两口灶可以同时处理互不相干的前三步，但”倒锅”必须等”切”完成。超标量处理器就是那个自动发现”这三步互不相干”并同时开火的厨师长；他的能力上限由 ILP 决定，而不是由灶的数量决定——加第三口灶对这道菜已经没用了。

• 架构/机制图解：以讲义中的 a = x*x + y*y + z*z 为例，五条指令的依赖图与实际排程（两个执行单元 + 一个执行单元的情形）。

   Program (R0=x, R1=y, R2=z)         Dependency DAG            ILP
   1  mul R0, R0, R0   (x*x)              (1)  (2)  (3)        <- ILP = 3
   2  mul R1, R1, R1   (y*y)                \   |   /
   3  mul R2, R2, R2   (z*z)                 (4) add R0 <- R0+R1  <- ILP = 1
   4  add R0, R0, R1   (x*x + y*y)            |
   5  add R3, R0, R2   (a)                   (5) add R3 <- R0+R2  <- ILP = 1
   R3 holds 'a'

   Schedule with 2 exec units          Schedule with 3 exec units
   time ->  1     2     3     4         time ->  1     2     3
   EU1    [ 1 ] [ 4 ] [ - ] [ ..]       EU1    [ 1 ] [ 4 ] [ 5 ]
   EU2    [ 2 ] [ 3 ] [ 5 ] [ ..]       EU2    [ 2 ] [ - ] [ - ]
                                        EU3    [ 3 ] [ - ] [ - ]
   total = 3 clocks (vs 5 with 1 EU)    total = 3 clocks (no gain!)

• 关键操作与性能特征：两个关键结论。
  1. 并行排程必须”尊重程序序”（respect program order）：若指令 X 依赖 Y 的结果，X 必须在 Y 之后执行；但只要最终对外可观察的结果（寄存 器/内存的最终取值、输出）与顺序执行一致，执行顺序本身可以任意重排。
  2. 超标量的收益递减（diminishing returns）：讲义引用 Culler & Singh（数据来自 Johnson 1991）的曲线指出，每周期发射 4 条指令的处理器已经榨取了大部分可用 ILP，再提高发射宽度几乎没有性能收益。ILP 在 2004 年前后”用尽”（ILP tapped out）——这是”免费午餐结束”的第一根支柱。

2.3 功率墙（Power Wall）与频率封顶：第二根支柱

• 定义与目的：动态功率（dynamic power） ∝ capacitive load × voltage² × frequency；此外还有静态功率（static power / leakage）——晶体管即使不翻转也会因漏电而耗电。功率直接转化为热量，而芯片能承受的温度决定了最高频率与核心电压上限。因此”提高频率”这条路在 2004 年前后撞墙。

• 直观解释（”它是什么？”）：把芯片想象成一口锅：火力（频率/电压）越大，菜熟得越快，但锅也会烧穿。火开到某个点以后，你不能再靠加大火力提高产量，只能多摆几口锅（多核），或者换更省火的专用炊具（专用加速器）。这就是为什么现代桌面 CPU 的 TDP 停在 95 W 量级（Intel Core i9 10900K），笔记本芯片只有 13 W（Apple M1），而手机处理器只有 0.5–2 W——它们不是不想更快，而是散热与电池不允许。

• 架构/机制图解：把”晶体管密度 / 时钟频率 / ILP / 功率”四条曲线放在同一时间轴上（讲义引用 Herb Sutter《The Free Lunch is Over》，Dr. Dobb’s 2005）。

  relative                                   ___________  transistor density
  performance                              /            (Moore's law continues)
      ^                                 ___/
      |                          ______/     <-- clock frequency FLATTENS (~2004)
      |                     ____/
      |                ____/  _______  <-- ILP extraction saturates (~2004)
      |           ____/  ____/
      |      ____/  ___/  ________________________  power per chip keeps rising
      | ____/  ___/      /                          (but is CAPPED by cooling)
      |/  ___/          /
      |__/              * 2004: Intel hits the power-density wall
      +-----------------------------------------------------------> time
       1980    1990    2000  2004        2010        2020

  Consequence (slide 38 of the CMU deck):
    Before 2004: within the chip-area budget, MAXIMIZE PERFORMANCE
                 (aggressive speculative execution for ILP)
    After  2004: area matters (limits # of cores/chip)
                 -> MAXIMIZE PERFORMANCE PER AREA
                 power is critical (battery life, datacenters)
                 -> MAXIMIZE PERFORMANCE PER WATT

• 关键操作与性能特征：架构师改变策略——增加并行运行的执行单元（多核） 或 增加专用执行单元（图形/音视频/DNN 加速器）。这对程序员意味着一条硬性结论：“软件必须是并行的，才能看到性能提升”（software must be written to be parallel to see performance gains）。讲义用一句程序员视角的对比概括（slide 22）：2004 年前的答案是”等 6 个月买台新机器”，2004 年后的答案是”你得写出快的、并行的软件”。

2.4 内存层次与缓存：延迟、局域性与数据移动的真实代价

• 定义与目的：内存是一个按字节寻址的大数组，load/store 指令负责在寄存器与内存之间搬运数据。但 DRAM 的访问延迟高达数百个时钟周期（讲义表格：L1 命中 ~4 周期、L2 ~12、L3 ~38、DRAM 最好情况 ~248 周期，均为 4 GHz 的 Kaby Lake 上的量级），处理器会因为等待依赖数据而停顿（stall）。缓存（cache）是片上存储，保存内存中一部分数据的副本；它纯粹是实现细节——不影响程序输出，只影响性能。

• 直观解释（”它是什么？”）：内存像城里的总仓库（DRAM），又大又远；缓存像你厨房冰箱与案板上的小份食材。你不可能每一次都跑一趟仓库，所以把最近用过的、以及”同一箱里”的食材先搬到手边。空间局域性（spatial locality） = 你从箱子里取货时，顺手把同一箱的其他东西也拿来了（缓存行 cache line 的预取效应）；时间局域性（temporal locality） = 反复用同一样东西，就不用再跑仓库。

• 架构/机制图解：现代机器把”线性内存地址空间”这个抽象用多级缓存层次实现（讲义给出的是 32 KB L1 / 256 KB L2 / 20 MB L3 / 64 GB DRAM 的典型组织）。

                       ┌─────────────────────────────────────────┐
                       │  越大、越远、越慢、越便宜                │
                       └─────────────────────────────────────────┘
   ┌────────┐   ~4 cyc   ┌────────┐  ~12 cyc  ┌────────┐ ~38 cyc ┌──────────┐
   │ Core / │◄──────────►│  L1    │◄─────────►│  L2    │◄────────►│   L3     │
   │ Regs   │  (32 KB)   │ cache  │ (256 KB)  │ cache  │ (20 MB)  │  cache   │
   └────────┘            └────────┘           └────────┘          └────┬─────┘
        ▲                                                             │
        │  ~248 cycles (best case, 4 GHz Kaby Lake)                   │
        │                                                             ▼
        └───────────────────────────────────────────────────  ┌──────────────┐
                                                              │  DRAM 64 GB  │
                                                              └──────────────┘

   Cache line granularity (LRU, 8-byte cache, 4-byte lines):
     time ->
     access 0x0 0x1 0x2 0x3 0x2 0x1 0x0 | 0x4 0x5 0x6 0x7
            [---- line 0x0 resident ----]  [--- line 0x4 ---]
            cold miss | hits (spatial) |   cold miss | hits (spatial)
                              ^
                     temporal locality: 0x2, 0x1, 0x0 hit again
     Sliding window over 0x0..0xF with only 2 lines -> "capacity miss"
     after touching 0x8, 0xC, then 0x0 again (the working set > cache)

• 关键操作与性能特征：缓存的收益有两层：降低延迟（命中时把数百周期降到几个周期）和提供高带宽数据传输。但必须记住三条量化事实：
  • 数据访问延迟用数百个时钟周期计；每隔一次访存停顿数百周期，即使有超标量也无济于事——并行/流水才能隐藏延迟。
  • 数据移动的能耗远比”做运算”贵：一次整数运算 ~1 pJ，一次浮点运算 ~20 pJ，从片上 1 mm 处的 SRAM 读 64 bit ~26 pJ，而从低功耗移动 DRAM（LPDDR）读 64 bit 需要 ~1200 pJ（约 46 倍）。
  • 直接推论：以 10 GB/s 的速率从内存读数据，仅这部分就消耗约 1.6 W；而一个移动 GPU 的整个功率预算只有约 1 W（手机还要同时跑 CPU、显示、无线）。所以”高效处理几乎总是归结为高效地访问数据”（achieving efficient processing almost always comes down to accessing data efficiently）。

2.5 软件执行模型：分解、分配、通信（fork-join / SPMD）

• 定义与目的：并行思维（parallel thinking）需要三件事：1) 把工作分解成可以安全并行执行的小块；2) 把这些工作分配给各个处理器；3) 管理处理器之间的通信与同步，使其不成为加速比的瓶颈。软件抽象（线程、任务图、SPMD、向量通道）就是为这三件事提供机制。

• 直观解释（”它是什么？”）：讲义用课堂演示来解释——让一群学生一起数数。DEMO 1：每人分一段、最后互相报出部分和（partial sums），结果发现通信限制了最大加速比；把学生叫近一点、或者允许他们”喊出来”，通信变便宜、加速比上升。DEMO 2：扩展到更多”处理器”（学生）后，工作分配不均——有人手里没活了（idle），有人还在忙——改进了分配就提高了加速比。DEMO 3：大规模并行，但问题的通信量相对计算量太大，通信开销压倒了并行计算，严重限制加速比。三次演示的教训是同一句话：并行不只是”人多”，而是通信与负载的艺术。

• 架构/机制图解：下面是本课程后面会反复出现的两个软件执行模型骨架：fork-join（分叉-汇合） 与 SPMD（单程序多数据），并叠加了 work-span DAG 的视角。

 (A) Fork-Join model (shared address space)          (B) SPMD model (e.g. CUDA / MPI)
                                                    rank 0      rank 1      rank 2
  main thread                                        │            │           │
      │  ┌──────────┐                                ├─ same program text ─────┤
      ├──┤ fork     │                                │  if (rank==0) ...      │
      │  └────┬─────┘                                │  all ranks compute     │
      │       ├──────────┬──────────┐                │  on their own data     │
      │       ▼          ▼          ▼                ▼           ▼           ▼
      │    worker0    worker1    worker2           chunk0      chunk1      chunk2
      │   [work A]   [work B]   [work C]              │           │           │
      │       │          │          │                 └──── exchange / barrier ┘
      │       └──────────┴──────────┘                        (communication)
      ├──┤ join (barrier) │
      │  └────────────────┘
      ▼  main thread continues                          Same code, different data
      (OpenMP parallel for, Cilk spawn/sync,            (CUDA threads/blocks, MPI ranks,
       pthread_create/pthread_join)                      ISPC gang of program instances)

 (C) Work-span DAG of parallel sum over 8 elements
     Work W = 7 adds          Span S = 3 levels (log2 8)
     Parallelism = W / S = 7/3 ~ 2.3      Amdahl-style limit on this DAG

        a0 a1  a2 a3  a4 a5  a6 a7      level 0
         \ /    \ /    \ /    \ /
         a0+a1  a2+a3  a4+a5  a6+a7     level 1
            \    /        \    /
             s01 s23      s45 s67       level 2
                \          /
                 TOTAL (s)              level 3

• 关键操作与性能特征：fork-join 模型中，fork 是并行度的来源，join 是同步点；join 处所有工作线程必须等待最慢的那个，因此fork-join 之间的关键路径（span）决定了无法再压缩的时间。SPMD 模型中，同一份程序文本在不同数据分片上执行，通信发生在显式的数据交换或 barrier 上。两者共同的性能特征是：
  • 加速比受通信限制（DEMO 1 / DEMO 3）；
  • 加速比受负载不均限制（DEMO 2）；
  • 并行度 = Work / Span，它给出”即使处理器无限多，也最多能快多少倍”的上限——这个量在 §3、§4 里会用于每个代码示例。

2.6 效率与专用化：多核 + 异构是当代答案

• 定义与目的：效率（efficiency）有两种视角。程序员视角：让程序真正用上机器提供的能力（用满 SIMD 宽度、用满所有核心、用满内存带宽）。硬件设计者视角：在每单位面积的成本 / 每瓦功耗的约束下，选择把什么能力放进系统（cost = silicon area? power?）。专用化（specialization）就是硬件设计者对这个问题的回答：与其造一个”什么都能干但什么都不快”的通用核心，不如造一批只对某类任务极高效的单元。

• 直观解释（”它是什么？”）：通用核心像瑞士军刀——什么都能对付，但没有一样顺手；专用单元像开瓶器、刨丝器——只干一件事，但干得又快又省力。现代 SoC 里专用单元无处不在：手机里除了 2 个”大核” + 4 个”小核”的 CPU，还有多核 GPU、Neural Engine（NPU，DNN 加速）、图像/视频编解码器、运动（传感器）处理器；数据中心的 Google TPU 是专为 ML 计算设计的处理器（讲义 slide 16：TPU v4 芯片 275 TeraFlops，一个 pod 装 4096 颗芯片）。

• 架构/机制图解：下面是当代”多核 + 专用单元”机器的抽象结构，以及并行机器简史的时间线。

 ┌─────────────────────────── one chip / one package ───────────────────────────┐
 │  ┌──────┐ ┌──────┐ ┌──────┐ ┌──────┐        ┌──────────────────────────────┐ │
 │  │Core 0│ │Core 1│ │Core 2│ │Core 3│        │  Specialized units           │ │
 │  │ SIMD │ │ SIMD │ │ SIMD │ │ SIMD │        │  - multi-core GPU            │ │
 │  │ 2x SMT│ │ 2x SMT│ │2x SMT│ │2x SMT│       │  - NPU / TPU (DNN)           │ │
 │  └───┬──┘ └───┬──┘ └───┬──┘ └───┬──┘        │  - video encode/decode       │ │
 │      └────────┴────┬───┴────────┘           │  - sensor / motion processor │ │
 │                    │                        └──────────────────────────────┘ │
 │            ┌───────▼────────┐                                                 │
 │            │ Shared L3 cache│  on-chip interconnect (ring/mesh)               │
 │            └───────┬────────┘                                                 │
 └────────────────────┼──────────────────────────────────────────────────────────┘
                      ▼
              ┌───────────────┐   Memory bandwidth is a FIRST-CLASS limit:
              │     DRAM      │   ~20-100 GB/s per socket, ~248 cycle latency
              └───────────────┘

 ==== brief history of parallel machines (CMU deck, slides 13-16) ====
 1971  C.mmp @ CMU                    16 PDP-11 processors
 1984  Cray XMP                       4 vector processors
 1987  Thinking Machines CM-2         65,536 1-bit processors + 2048 FP coprocessors
     Bridges @ Pittsburgh Supercomputer Center   800+ compute nodes (heterogeneous)
 ~1997 Sun Enterprise 10000           16 UltraSPARC-II processors   (databases)
 today Oracle Supercluster M7         4 x 32-core SPARC M2          (RIP 2019:
                                       killed by cloud computing)
 2000- cloud computing: many simple processors on a LAN, programmed with
       distributed-system models (the subject of 15-440, not this course)
 2023  Google TPU v4                  275 TeraFlops/chip, 4096 chips per pod

• 关键操作与性能特征：多样性带来的是对程序员的更高要求：同一份计算要能映射到不同粒度的并行资源上——SIMD 向量通道（数据并行，宽度 8/16）、超线程（SMT，隐藏停顿）、多核（任务/线程并行）、GPU（数千个轻量线程隐藏长延迟）、多处理器/机群（消息传递）。这四层”并行资源”的延迟/带宽/能耗特征各不相同，把它们按”成本-收益”最优地组合起来，正是本课程第 1 次作业到第 4 次作业的线索：SIMD + 多核 → CUDA → 共享地址空间 → 消息传递。

3. 代码示例与性能分析

示例 1：把”学生互相报数”变成代码——串行基线 vs. OpenMP 并行归约

// 编译: g++ -O3 -fopenmp -march=native parallel_sum.cpp -o parallel_sum
// 运行: OMP_NUM_THREADS=8 ./parallel_sum 268435456
// 说明: 串行基线（-O3，不做 -ffast-math）与 OpenMP 并行归约对比
#include <omp.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

static double now_sec(void) {
    struct timespec ts;
    clock_gettime(CLOCK_MONOTONIC, &ts);
    return (double)ts.tv_sec + 1e-9 * (double)ts.tv_nsec;
}

int main(int argc, char **argv) {
    const long N = (argc > 1) ? atol(argv[1]) : (1L << 28);   // 2^28 = 268,435,456
    float *a = (float *)malloc((size_t)N * sizeof(float));
    if (!a) { fprintf(stderr, "alloc failed\n"); return 1; }
    for (long i = 0; i < N; i++) a[i] = 1.0f;   // 预热：先触碰所有页

    /* ---------------- serial baseline ---------------- */
    double t0 = now_sec();
    double s = 0.0;
    for (long i = 0; i < N; i++) s += (double)a[i];
    double t1 = now_sec();

    /* ---------------- OpenMP parallel reduction ---------- */
    double p = 0.0;
    double t2 = now_sec();
    #pragma omp parallel for reduction(+:p) schedule(static)
    for (long i = 0; i < N; i++) p += (double)a[i];
    double t3 = now_sec();

    printf("N = %ld  (%.1f MB of floats, %.1f MB read per pass)\n",
           N, N * 4.0 / (1024.0 * 1024.0), N * 4.0 / (1024.0 * 1024.0));
    printf("serial  : %8.3f ms   sum = %.0f   (%.2f GB/s)\n",
           (t1 - t0) * 1e3, s, N * 4.0 / (t1 - t0) / 1e9);
    printf("openmp  : %8.3f ms   sum = %.0f   threads = %d   (%.2f GB/s)\n",
           (t3 - t2) * 1e3, p, omp_get_max_threads(), N * 4.0 / (t3 - t2) / 1e9);
    printf("speedup : %8.2fx   (efficiency = %.2f of %d threads)\n",
           (t1 - t0) / (t3 - t2),
           ((t1 - t0) / (t3 - t2)) / omp_get_max_threads(),
           omp_get_max_threads());

    free(a);
    return 0;
}

【代码做什么？】

1. 分配 N 个 float（默认 2^28 个 = 1 GiB），并先用一个循环把所有页写入 1.0f。这一步是预热：避免第一次触碰页面时的缺页（page fault）开销污染后面两次测量。
2. 串行基线：用单调时钟 CLOCK_MONOTONIC 记录起止时间，跑一个朴素累加循环。注意累加器是 double——这是正确性要求，不是性能优化：float 只有 24 bit 有效位，累加 2^28 个 1.0 会因舍入误差得到错误结果。同时，因为没有开 -ffast-math，编译器不允许重结合浮点加法，所以这个循环不会被自动向量化，串行基线是真正的”一次一个元素”。
3. OpenMP 并行归约：#pragma omp parallel for reduction(+:p) 让运行时把 [0, N) 的迭代空间静态切分（schedule(static)）给各线程；每个线程在私有副本上累加，循环结束时由 OpenMP 运行时把各私有副本按顺序合并回 p。这一句 reduction 就是 DEMO 1 里的”互相报出部分和”。

【并行机制与性能解说】

• 线程如何创建、工作如何分配：parallel for 在进入循环前 fork 出一组工作线程（讲义中的 fork-join 模型），把 N 个迭代按 schedule(static) 均分为 P 个连续区间（chunk）。每个线程只访问自己那段连续内存——这是顺序访问 + 无共享写的理想模式：不会伪共享，也不会出现原子操作。
• 共享数据如何处理：数组 a 是只读共享的；唯一的跨线程通信是循环结束时的归约合并（P 个部分和相加，成本 O(P)）。这正是”最小化通信成本”的教科书例子：通信量从 DEMO 1 的”每个人都要向大家报数”降到 O(log P) 或 O(P)。
• Work / Span / 并行度：设元素数 N，线程数 P，每个线程分到 n = N/P 个元素。
  • Work（总工作量） W = N - 1 次加法（约等于 N）。
  • Span（关键路径） S = n + ⌈log₂ P⌉：每个线程必须顺序走完自己的 n 个元素（这是长为 n 的串行链，无法并行），然后归约树需要 ⌈log₂ P⌉ 层。
  • 并行度 W / S = (N-1) / (N/P + ⌈log₂P⌉)。当 N ≫ P·log P 时，W/S → P——也就是说这个分解方式的并行度上限就是 P，再多的处理器也用不上，因为每个线程内部是串行的。
  • 代入 N = 2^28、P = 8：W ≈ 2.68e8，S = 2^25 + 3 = 33,554,435，W/S ≈ 8.00。看上去很完美（并行度 = 8），但真实运行达不到 8 倍——原因见下面的瓶颈。
• 瓶颈：① 内存带宽。这个 kernel 每读一个元素只做 1 次加法，算术强度 ≈ 1 flop / 4 byte = 0.25 flop/byte，远低于现代 CPU 的带宽-算力平衡点，所以它必然是带宽受限（bandwidth bound）的：总时间 ≈ 1 GiB / 实测带宽。单核串行往往已经能吃满相当一部分带宽（乱序执行 + 硬件预取），8 线程一起抢同一条内存总线，加速比常常只有 3–5 倍。② NUMA/内存通道不均：schedule(static) 的连续分块在某些机器上映射到不同的内存控制器，若线程被调度到远端 socket，延迟更高。③ 归约的结果顺序：reduction 是非确定性顺序的浮点加法，每跑一次结果最后几位可能不同——这是并行归约的常见”陷阱”（见 §6）。

示例 2：伪共享（false sharing）——当”划分工作”变成性能杀手

// 编译: g++ -O3 -pthread -march=native falseshare.cpp -o falseshare
// 运行: ./falseshare 4 200000000
// 说明: 同一个 cache line 上的多个独立计数器 -> 缓存行乒乓，慢若干倍
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAXT 64

typedef struct { int tid; long iters; } arg_t;

/* 版本 A: 计数器紧挨在一起 —— 一个 cache line (通常 64 B) 装得下 8 个 long */
static long g_tight[MAXT];

/* 版本 B: 每个计数器独占一个 cache line */
struct padded { long v; char pad[64 - sizeof(long)]; };
static struct padded g_padded[MAXT];

static void *worker_tight(void *p) {
    arg_t *a = (arg_t *)p;
    for (long i = 0; i < a->iters; i++) g_tight[a->tid]++;
    return NULL;
}

static void *worker_padded(void *p) {
    arg_t *a = (arg_t *)p;
    for (long i = 0; i < a->iters; i++) g_padded[a->tid].v++;
    return NULL;
}

static double now_sec(void) {
    struct timespec ts; clock_gettime(CLOCK_MONOTONIC, &ts);
    return (double)ts.tv_sec + 1e-9 * (double)ts.tv_nsec;
}

/* 用函数指针选择要跑哪个版本，避免代码重复 */
static double run(int nt, long iters, void *(*fn)(void *)) {
    pthread_t th[MAXT]; arg_t args[MAXT];
    double t0 = now_sec();
    for (int i = 0; i < nt; i++) {
        args[i].tid = i; args[i].iters = iters;
        pthread_create(&th[i], NULL, fn, &args[i]);
    }
    for (int i = 0; i < nt; i++) pthread_join(th[i], NULL);
    return now_sec() - t0;
}

int main(int argc, char **argv) {
    int  nt    = (argc > 1) ? atoi(argv[1]) : 4;
    long iters = (argc > 2) ? atol(argv[2]) : 200000000L;
    if (nt > MAXT) nt = MAXT;

    double tt = run(nt, iters, worker_tight);
    double tp = run(nt, iters, worker_padded);

    printf("threads=%d  iters/thread=%ld\n", nt, iters);
    printf("tightly packed counters : %7.3f s  (%6.2f Mops/s total)\n",
           tt, nt * (double)iters / tt / 1e6);
    printf("cache-line padded       : %7.3f s  (%6.2f Mops/s total)\n",
           tp, nt * (double)iters / tp / 1e6);
    printf("false-sharing penalty   : %7.2fx\n", tt / tp);
    return 0;
}

【代码做什么？】

1. 定义了两种计数器布局：g_tight[MAXT]（8 个 long 挤在 64 B 的一个缓存行内）与 g_padded[MAXT]（每个计数器带 56 B padding，独占一个缓存行）。
2. run() 负责 fork nt 个 pthread（pthread_create），每个线程拿到自己的 tid 与迭代次数，然后 pthread_join 汇合；now_sec() 包住 fork 到 join 的整个区间来计时（含线程创建开销，在 iters 很大时可忽略）。
3. 两个 worker 都是纯自增：每个线程只写”自己的”计数器 g_tight[tid] / g_padded[tid].v——逻辑上完全没有数据竞争，也不需要任何锁。
4. 主函数先跑 tight 再跑 padded，打印两者耗时与总是操作速率，并给出伪共享的惩罚倍数。

【并行机制与性能解说】

• 工作如何分配与共享数据：nt 个线程各自独立地在一个私有计数器上自增；没有共享写（从软件语义看），但从硬件看，版本 A 的 8 个计数器共用同一缓存行。缓存一致性协议以缓存行为单位维护所有权：线程 1 写 g_tight[1] 会使该行在其他核心的副本失效，线程 2 想要写 g_tight[2] 就要把整行重新取回并取得独占权——这行数据就在各核心的 L1 之间来回弹跳（cache-line ping-pong）。版本 B 通过 padding 让每个计数器独占一行，这个”假”的共享就消失了。
• Work / Span / 并行度：每个线程 iters 次自增，共 P 个线程。
  • Work W = P × iters 次自增。
  • Span S = iters（每个线程内部是严格串行的依赖链：读-改-写同一地址；线程之间无依赖）。
  • 并行度 W / S = P——理论上限就是线程数，非常理想。但版本 A 的实际加速比远低于 P，甚至可能比单线程还慢：每次自增都要付出一次跨核缓存行传输（数十到上百周期），有效吞吐被一致性流量而不是 ALU 吞吐限制。
  • 代入 P = 4、iters = 2e8：Work = 8e8 次自增，Span = 2e8。若缓存行传输约 100 周期、频率 3 GHz，则版本 A 每 4 次”逻辑独立”的自增被迫串行化约 33 ns，总时间至少 2e8 × 100 / 3e9 ≈ 6.7 s；而版本 B 的自增落在 L1 命中（~4 周期），总时间 ≈ 2e8 × 4 / 3e9 ≈ 0.27 s，量级差距 25 倍——这与实测的”几十倍惩罚”相符。
• 瓶颈：伪共享（false sharing） 是本例唯一但致命的瓶颈。它也是 DEMO 2”负载不均”之外的第二类”分配工作”错误：分配工作时必须同时考虑数据的物理布局（cache line 粒度），而不仅是逻辑上的独立性。第二个瓶颈是线程创建/销毁开销：iters 太小（例如 1e5）时，pthread_create + join 的微秒级开销会占主导，此时应该用线程池或 OpenMP 的持久线程。

示例 3：带宽受限的 STREAM triad——算术强度决定上限

// 编译: g++ -O3 -fopenmp -march=native triad.cpp -o triad
// 运行: OMP_NUM_THREADS=8 ./triad 67108864      # 64M floats = 256 MB 每数组
// 说明: a[i] = b[i] + s * c[i]  —— 每元素 12 B 流量、2 次浮点运算
#include <omp.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

static double now_sec(void) {
    struct timespec ts; clock_gettime(CLOCK_MONOTONIC, &ts);
    return (double)ts.tv_sec + 1e-9 * (double)ts.tv_nsec;
}

int main(int argc, char **argv) {
    const long N = (argc > 1) ? atol(argv[1]) : (1L << 26);   // 2^26 = 64M
    const float s = 3.0f;
    float *a = (float *)malloc(N * sizeof(float));
    float *b = (float *)malloc(N * sizeof(float));
    float *c = (float *)malloc(N * sizeof(float));
    if (!a || !b || !c) { fprintf(stderr, "alloc failed\n"); return 1; }
    for (long i = 0; i < N; i++) { b[i] = 1.0f; c[i] = 2.0f; a[i] = 0.0f; }

    double best = 1e30;
    for (int rep = 0; rep < 3; rep++) {                 // 取 3 次中最好的一次
        double t0 = now_sec();
        #pragma omp parallel for schedule(static)
        for (long i = 0; i < N; i++) a[i] = b[i] + s * c[i];
        double dt = now_sec() - t0;
        if (dt < best) best = dt;
    }

    const double bytes = (double)N * 12.0;              // 2 reads + 1 write, 4 B each
    const double flops = (double)N * 2.0;               // 1 mul + 1 add per element
    printf("N = %ld (%.0f MB working set)\n", N, (double)N * 12.0 / (1024 * 1024));
    printf("best time      : %8.3f ms\n", best * 1e3);
    printf("bandwidth      : %8.2f GB/s\n", bytes / best / 1e9);
    printf("throughput     : %8.2f GFLOP/s\n", flops / best / 1e9);
    printf("arith. intensity: %6.3f flop/byte\n", flops / bytes);
    free(a); free(b); free(c);
    return 0;
}

【代码做什么？】

1. 分配三个 N 元素的 float 数组（默认每个 256 MB，三数组合计 768 MB，远大于任何 L3 缓存），初始化后进入测量。
2. 重复 3 次 a[i] = b[i] + s*c[i]（经典的 STREAM triad），每次都重新计时并保留最快的一次——单次测量易受其他进程、频率调节、页迁移干扰，取最小值是对”机器能力”的更稳健估计。
3. 打印时间、实测带宽（总流量 = 2 读 + 1 写 = 12 B/元素）、实测算力（2 flop/元素）以及算术强度（arithmetic intensity，flop/byte）。

【并行机制与性能解说】

• 工作如何分配、数据如何处理：schedule(static) 把 [0, N) 均分给 P 个线程，每个线程处理一段连续的 a/b/c（三者的下标区间相同，所以每个线程仍然只触碰自己那段内存）。没有任何线程间数据共享（除了只读的 s），没有同步（除循环末尾隐含的 barrier），因此这个 kernel 的”通信”成本几乎为零——它的全部上限来自内存系统。
• Work / Span / 并行度：
  • Work W = N 次迭代，每次 1 乘 + 1 加（2N flop）+ 12N 字节流量。
  • Span S = N / P：每个线程内部的迭代完全独立，但一个线程串行执行它所分到的所有迭代，所以最长的依赖链就是这个 chunk 的长度。
  • 并行度 W / S = P。同样的结论：静态均分的 for 循环并行度上限 = 线程数。
• 瓶颈是内存带宽，不是算力。代入具体数字（假设单路内存可提供 20 GB/s 的可持续带宽）：
  • 总流量 = 2^26 × 12 B = 805 MB ≈ 0.79 GB。
  • 若带宽 20 GB/s，则 t ≥ 0.79 GB / 20 GB/s = 39.4 ms。此时实测吞吐 ≈ 2^26×2/0.0394 ≈ 3.4 GFLOP/s。
  • 而一台 16 核、3.0 GHz、8 宽 SIMD、支持 FMA 的机器峰值是 16 × 3.0e9 × 8 × 2 = 768 GFLOP/s（详见 §4.4）。也就是说这个 kernel 只能跑到机器峰值的 0.4% 左右——不是代码写得不好，而是算术强度太低：每字节只做 0.167 次浮点运算，机器必须”喂”进海量数据才能不饿死执行单元。把处理器从 8 核加到 16 核，如果带宽没变，时间几乎不变——加速比被外部资源卡死在 1 倍附近（对于带宽受限段）。
  • 这也是讲义那句”高效处理几乎总是归结为高效地访问数据”的定量版本。

4. 性能模型与复杂度分析

4.1 加速比、效率与 Amdahl 定律

讲义给出的核心定义（slide 29）：

                    execution time (using 1 processor)      T(1)
   speedup(P)  =   -----------------------------------  =  ------
                    execution time (using P processors)     T(P)

   efficiency  =  speedup(P) / P            (0 < efficiency <= 1)

Amdahl 定律（Amdahl’s Law）：设程序中无法并行的比例为 f（串行部分，包括不可避免的通信与同步），则可并行部分为 1 - f：

   T(P) = (f + (1 - f)/P) · T(1)
   speedup(P) = 1 / ( f + (1 - f)/P )        ->   1 / f     (P -> infinity)

数值算例（假设内存带宽充裕，忽略通信开销）：

表中 f = 0.05, P = 16 的计算：1 / (0.05 + 0.95/16) = 1 / (0.05 + 0.059375) = 9.14×，效率 9.14/16 = 57%。关键洞察：只要 5% 的代码串行，16 核的机器最多也只能给出 9 倍；如果串行部分来自”每次迭代都要全局同步”，那么处理器越多、同步越贵，f 反而随 P 增长（Gustafson 视角下的强/弱扩展问题，本课程后续会专门讨论）。

这也直接回答了讲义 slide 37 的提问：“在 10 个处理器的机器上 2 倍加速比是好结果吗？” 用效率衡量：2/10 = 20%。抛掉理论 Amdahl 限制外，通常说明存在严重的通信、同步或负载不均问题——FAST != EFFICIENT。

4.2 Work-Span 模型与并行度

把并行程序表示成一个有向无环图（DAG, Directed Acyclic Graph）：节点是指令/任务，边是依赖。定义：

   Work  W = DAG 中所有节点的总执行成本      ("1 个处理器要干多少活" = T(1))
   Span  S = DAG 中最长路径的成本 (critical path, 关键路径)
   Parallelism  P_inf = W / S               ("无限多处理器时的加速比上限")

三类基本组合（n 为规模，P 为处理器数）：

调度定理（greedy scheduler）：使用贪心调度器在 P 个处理器上执行一个 work 为 W、span 为 S 的 DAG，总时间满足

   T(P)  <=  W/P + S          (下界是 max(W/P, S))
   speedup(P) = T(1)/T(P)  <=  W / (W/P + S)  =  P / (1 + P·S/W)

数值算例：示例 3 的 triad，N = 2^26，P = 8。W = 2^26 = 67,108,864，”单位任务成本 = 1 次迭代”，S = N/P = 8,388,608。若忽略内存瓶颈，则 T(8) ≤ W/8 + S = 8,388,608 + 8,388,608 = 2S，即加速比上界 = 8（因为这里 S = W/8，与 W/P 相等，说明该分解刚好”卡在”完美扩展的边界）。但实测加速比只有 3–5 倍——Work-span 模型只描述了”计算”的并行性，它不包含带宽和一致性流量。这正是本课程反复强调的一点：模型是上界，真实机器有额外约束。若把每次迭代的成本换成”实际需要的时间”（含内存等待），Work 会显著变大，而 Span（关键路径上串行的内存延迟链）也变大，二者比例随之改变。

4.3 算术强度与 Roofline 模型

算术强度（arithmetic intensity, AI）定义为每字节内存流量对应的浮点运算数：AI = FLOPs / Bytes moved。

Roofline 模型：

   attainable_performance  =  min( peak_math_throughput ,  AI × peak_memory_bandwidth )

  GFLOP/s
   768 |*******************************  <-- compute roof (peak math)
       |                             *
       |                            *     <-- sloped memory roof (AI x BW)
       |                          *
       |                        *
       |                      *   RIDGE POINT: AI* = peak_math / BW
       |                    *                 = 768 / 20 = 38.4 flop/byte
       |                  *
       |                * : memory-bound region
       |              *   : (left of the ridge: optimize DATA MOVEMENT)
       |            *     : compute-bound region
       |          *       : (right of the ridge: optimize MATH/ILP/SIMD)
       +-------------------------------------------> arithmetic intensity (flop/byte)
        0.167   1     8   38.4        100
         ^     ^
         |     triad-like kernels
         |
   示例3 triad: AI = 2 flop / 12 B = 0.167 -> 3.3 GFLOP/s = 0.4% of peak

数值算例（用一组明确假设）：

• 机器假设：16 核、每核 3.0 GHz、每周期 8 个 float 宽度的 SIMD（AVX2 级别的 256 bit）、支持 FMA（fused multiply-add，一条指令完成 a*b+c，计 2 flop）；可持续内存带宽 20 GB/s。
• 峰值算力：16 × 3.0e9 × 8 × 2 = 7.68e11 = 768 GFLOP/s。
• Ridge point：AI* = 768 / 20 = 38.4 flop/byte。低于这个强度的一切 kernel 都是带宽受限；高于它才是算力受限。
• 示例 3（triad，AI = 0.167）：受限于 0.167 × 20 = 3.34 GFLOP/s，只有峰值的 0.43%。
• 示例 1（求和，AI ≈ 0.25）：受限于 0.25 × 20 = 5 GFLOP/s，同样极度带宽受限。
• 一个 256 MB 数组的单次遍历（只读，无重用）：256 MB / 20 GB/s = 12.8 ms。任何涉及这块数组的算法，至少付 12.8 ms；如果你的计算只需要 1 ms 的算力，那么这个 kernel 的效率上限就是 7%。只要能用分块（blocking/tiling）把数据留在缓存里重用，把 AI 从 0.25 抬到 4，性能就能提高 16 倍，而不用改一个字节的并行代码。

4.4 数据移动的能耗与”能量墙”

讲义（CS149 补充材料，来源 Bill Dally (NVIDIA)、Tom Olson (ARM)）给出的一组量级估计（”ballpark” numbers）是设计直觉的基石：

数值算例：

• 以 10 GB/s 从 DRAM 读数据：1200 pJ / 8 B = 150 pJ/B，150e-12 J/B × 10e9 B/s = 1.5 W ≈ 1.6 W（讲义结论）。
• 对比：移动 GPU 的总功率预算约 1 W，手机电池约 7 Wh（iPhone 6 量级，而一台 MacBook Pro 有 99 Wh）。也就是说，持续以 10 GB/s 读内存这一件事，就能吃掉整个移动 GPU 的功率预算。
• 从 DRAM 读 64 bit 相对从 SRAM 读，能耗差 ~46 倍。所以缓存的收益不只是”低延迟”，更是”低能耗”；这也是为什么”always seek to reduce amount of data movement”被写成现代系统设计的经验法则。

4.5 一个综合的定量推演：把 DEMO 的教训算式化

设 DEMO 3 的场景：P 个处理器，每个处理器分到 n 个单位工作（每单位耗时 t_c），并把结果与邻居交换（每单位通信耗时 t_m），最后需要 ⌈log₂ P⌉ 次归约，每次归约耗时 t_r。

   T(P) = n · (t_c + t_m·α) + ⌈log₂ P⌉ · t_r        α = 通信/计算 强度比
   理想加速比(通信可忽略): T(1)/T(P) = (P·n·t_c) / (n·t_c) = P

代入一组具体数字：P = 64、n = 10^6、t_c = 1 ns、t_m = 100 ns（跨核通信慢两个数量级，量级参考缓存行传输）、α = 1（每单位工作对应一次通信）、t_r = 1 µs：

• T(64) = 10^6 × (1 + 100) ns + 6 µs ≈ 101 ms + 0.006 ms ≈ 101 ms
• T(1) = 64 × 10^6 × 1 ns = 64 ms
• 加速比 = 64/101 ≈ 0.63 ——用了 64 个处理器，反而比 1 个处理器慢！

把问题换成”通信比计算低 100 倍”（t_m = 1 ns，例如在共享 L2 上做规约）：T(64) = 10^6 × 2 ns + 6 µs ≈ 2.006 ms，T(1) = 64 ms，加速比 ≈ 31.9×（效率 50%，仍被 ⌈log₂P⌉·t_r 与未并行的 1 ns/单位拖累）。

这段推演就是讲义三句结论的算式版：

1. Communication limited the maximum speedup（通信限制最大加速比）——DEMO 1；
2. Imbalance in work assignment limited speedup（负载不均限制加速比）——DEMO 2（上述模型假设了理想均分，若最大块是平均块的两倍，则 T(P) 直接翻倍）；
3. Communication costs can dominate（通信开销可以压垮并行计算）——DEMO 3。

5. 关键要点

1. 单线程性能已经停止指数增长，”免费午餐”结束：ILP 在每周期约 4 条发射后收益递减（Culler & Singh / Johnson 1991 的曲线），时钟频率被功率墙封顶（Intel 在 2004 年撞上 power density wall），因此要显著提速就必须使用多个处理单元或专用硬件——这从”可选优化”变成了”编程必需”。
2. 并行思考的三步法：① 把工作分解成可以安全并行的片段；② 把片段分配给处理器；③ 管理通信与同步，使其不成为瓶颈。任何一步做错，加速比都会被 Amdahl 定律 与 T(P) ≤ W/P + S 死死卡住。
3. FAST != EFFICIENT：在并行机器上跑得更快，不等于用好了硬件。用 speedup/P 衡量效率：10 核上 2 倍加速比只有 20% 效率。程序员要”用满机器提供的能力”（SIMD 宽度、核心数、带宽），硬件设计者要在面积与功耗预算内”最大化每面积/每瓦性能”。
4. 高效 = 高效的数据访问：cache 命中把几百周期降到几个周期；而从 DRAM 读 64 bit 的能耗（~1200 pJ）是片上 SRAM（~26 pJ）的 ~46 倍、整数运算（~1 pJ）的上千倍。算术强度决定你受限于算力还是带宽——Roofline 的 ridge point（本笔记例中 38.4 flop/byte）就是那条分界线。
5. 性能模型是上界，机器现实是下界：work-span/并行度给出的并行度上限（W/S）不含带宽、一致性流量、同步代价；静态分块 for 循环的并行度上限恰好是线程数 P。要拿到真实的加速比，必须同时解决带宽、负载均衡、伪共享、同步粒度。

6. 常见陷阱与注意事项

• “更快的机器会解决一切”：2004 年后这个假设失效。优化必须来自并行与效率（用满 SIMD/核心/带宽），而不是等下一代工艺。
• 数据竞争（data race）：多个线程对同一地址并发访问且至少有一个是写、又没有同步时，程序行为未定义。注意示例 2 的反面：没有数据竞争也不代表快——伪共享（false sharing）在语义上完全正确，却能让性能掉几十倍；把”逻辑独立的变量”放进同一个 cache line 就是典型错误。
• 忽略通信与同步成本：T(P) = W/P + S，其中 S 是关键路径（含所有 barrier、归约、锁等待）。示例 1 中一次 reduction 的 O(P) 通信在 P 大时不可忽略；每次迭代都加一次全局同步会把 f 推高，Amdahl 上限随之崩塌（见 §4.5：64 核 + 100 ns 通信 → 加速比 0.63×）。
• 负载不均（load imbalance）：静态均分在迭代成本相近时才好用；样例成本差异大（如三角形循环、稀疏矩阵、不规则的 N 体问题）时，必须用动态/引导式调度（schedule(dynamic, k)、任务队列、work stealing），否则总时间由最慢的线程决定——这正是 DEMO 2 的教训。
• 忽视带宽与缓存效应：示例 3 的 triad 只用到峰值算力的 0.4%；把 8 核换成 16 核几乎不会更快。看到”加核不提速”先查算术强度与实测带宽，再用分块（tiling）/融合（fusion）/数据复用来提高重用率。
• 错误地理解内存序（memory ordering）与同步：不是”用了一个 volatile 或者 atomic 就对了”。并非所有平台都是顺序一致（sequential consistency）；锁要保证互斥与可见性；归约/自增要用原子操作或正确的 reduction 语义，否则会得到偶尔错误的结果（且难以复现）。此外，并行浮点归约的加法顺序不确定，结果不可逐位复现——这不是 bug，但依赖逐位确定性的测试会误判。
• 测量方法错误：只测一次、用挂钟时间（wall-clock）夹住含线程创建的开销、不预热页面/缓存、不做 -O3 的 release 编译就下结论，都会得到误导性的加速比。测量必须写明：编译命令、优化级别、线程数、问题规模、重复次数与取值方式（如示例 3 取 3 次最优）。

7. 思考题（带答案）

Q1. 一台 16 核、3.0 GHz、每周期 8 宽 SIMD、支持 FMA 的机器，理论峰值 768 GFLOP/s。你的 kernel 算术强度是 0.25 flop/byte（像示例 1 的求和），实测内存可持续带宽 20 GB/s。请问：(a) 性能上限是多少？(b) 如果老板要求你把 kernel 加速 4 倍，最有希望的两条改造方向是什么？

【答案】 (a) 这是典型的带宽受限点。按 Roofline：attainable = min(768, 0.25 × 20) = 5 GFLOP/s，只有峰值的 0.65%。等价地，按流量算：遍历 256 MB 的只读数组，256 MB / 20 GB/s = 12.8 ms 是硬下界，无论你开多少线程、用多宽的 SIMD 都绕不过去。 (b) 方向一：降低数据流量 / 提高数据重用——分块（tiling）让数据留在 L1/L2 里被反复使用，或做循环融合（fusion）避免中间数组来回写内存；把算术强度从 0.25 提到 1.0，理论上界就从 5 GFLOP/s 提高到 20 GFLOP/s（4 倍）。方向二：降低数据宽度 / 提高精度效率——在结果可接受的前提下用更窄的表示（如把 float 换成量化后的 int8/bf16，或只读必要字段，避免结构体数组 AoS→SoA 造成无效字节搬运），减少每元素字节数。注意”堆更多核心”或”加宽 SIMD”在这条曲线上完全没有用（它们改进的是屋顶高度，而你现在贴着斜屋顶）。

Q2. 你的并行求和程序在 8 核机器上只跑了 3 倍加速比。请给出一份至少三项的排查清单，每项说明它对应哪个可量化的模型/指标，以及如何验证。

【答案】 ① 串行比例 f（Amdahl 定律）：用 speedup(P) = 1/(f + (1-f)/P) 反推：3 = 1/(f + (1-f)/8) → f + (1-f)/8 = 0.3333 → f·(7/8) = 0.3333 - 0.125 = 0.2083 → f ≈ 0.238。也就是说约 24% 的时间是串行的。验证：用 perf/profiler 看单线程热点，或把线程数从 1 扫到 8 画出实际加速比曲线与 Amdahl 理论曲线对比，若曲线在大 P 处明显变平，就是串行/同步部分主导。 ② 内存带宽（Roofline / 算术强度）：示例 1 的 AI ≈ 0.25 flop/byte，1 GiB 数据在 20 GB/s 下需 12.8 ms × 4 = 51.2 ms；若单线程已经跑出大部分带宽，那么多线程的加速比上限就是 单线程带宽/总带宽 的比值。验证：在程序里统计流量并除以时间得到实测 GB/s；同时跑 STREAM-like microbenchmark 测该机器的可持续带宽作为分母。若多线程实测带宽已达到单线程的 3 倍并饱和，则瓶颈是内存而非代码。 ③ 负载不均（work-span，T(P) ≤ W/P + S）：如果线程之间工作量不等，总时间由最慢线程决定。验证：在每个线程内部记录起止时间打印甘特图，或者改用 schedule(dynamic, k) / work stealing 再测；如果提速，则为负载不均。同时检查是否出现伪共享（用 perf 的 cache-misses/HITM 事件，或把每线程结果数组做 cache-line padding，见示例 2）。 ④（补充）测量误差：确认是 release 编译（-O3）、预热过页面与缓存、重复多次取最优、并且计时不含线程池创建的一次性开销。

Q3. 讲义说”FAST != EFFICIENT”，并追问”在 10 个处理器的机器上 2 倍加速比是不是好结果”。请从程序员和硬件设计者两个视角分别说明”效率”的含义，并举一个两者会给出不同结论的场景。

【答案】

• 程序员视角：效率 = speedup(P)/P = 我是否用满了机器已经提供的能力（SIMD 宽度、FMA、所有核心、内存带宽、专用单元）。10 核上 2 倍 = 20% 效率，通常意味着通信、同步或负载不均吃掉了大部分收益，是不好的结果；而”好”的判据不是绝对加速比，而是把实测性能与 Roofline 上界（min(peak_math, AI × BW)）对比，看还差多少。
• 硬件设计者视角：效率 = 每单位成本（硅面积、功耗、成本）换来的性能，即在给定面积/功耗预算下选择放入什么能力（更大缓存？更多核心？SIMD 宽度？专用 NPU？）。对设计者来说，”20% 的效率”未必是坏消息——如果这 20% 的服务对象是使用频率最高的负载，或者这颗芯片的功耗已经逼近散热极限，那么为它增加通用核心反而是错的。
• 结论不同的场景：一个只需要 2 倍加速的延迟敏感型移动负载（如相机中的人脸检测），在 10 核芯片上只用到 2 个核心、加速比 2×。程序员视角会判定”低效，应该把另外 8 核用起来”；硬件设计者视角可能认为这是最佳设计——如果把这个负载的剩余部分交给 1 W 预算的 NPU（专用化）完成，那么”只用了 2 个通用核心”恰恰意味着 CPU 的其余面积可以留给其他任务，整机功耗与成本才是最优。这正是讲义 slide 38 的转向：2004 年后设计目标从”在面积预算内最大化性能”变成”最大化每面积性能”与”最大化每瓦性能”，而程序员的任务是在这个已经被优化过的机器上，把它提供的能力真正用满。