Lecture 3: A Modern Multi-Core Processor

目录 · ← l2 · l4 →

Lecture 3: A Modern Multi-Core Processor

1. 章节标题与概述

Lecture 3: A Modern Multi-Core Processor

• 本讲核心问题：现代处理器靠什么获得高吞吐（throughput）？讲义把它归结为”四个核心概念”——其中两个关于并行执行（多核 multi-core、SIMD 单指令多数据），两个关于访问内存的挑战（内存延迟 memory latency、内存带宽 memory bandwidth）。更具体地说：(1) 单核性能为什么不再增长，而芯片却继续把晶体管花在”更多核、更宽的 SIMD、更多的硬件线程”这三件事上？(2) 一台”16 核 × 每核 8 宽 SIMD × 每核 4 个硬件线程”的机器，需要程序暴露多少独立工作才跑得满？(3) 为什么绝大多数并行程序最终不是被算力卡住，而是被内存带宽卡住——”带宽受限（bandwidth limited）”意味着再多延迟隐藏手段也救不了？

• 涉及的主要硬件/软件机制：
  • 硬件侧：取指/译码（fetch/decode）与执行上下文（execution context，即 PC + 寄存器组）、超标量（superscalar）与乱序执行（out-of-order）、指令级并行（ILP）、多核（multi-core）、SIMD 功能单元（一条指令广播给多个 ALU）、向量寄存器（SSE 128 位 / AVX 256 位 / AVX-512 512 位）、掩码（mask）与发散执行（divergent execution）、缓存层次（L1/L2/L3 + DRAM）、硬件预取（prefetch）、硬件多线程（交织式 interleaved / 同时多线程 SMT）、GPU 的 SM（streaming multiprocessor）与 warp。
  • 软件侧：把串行循环改写成并行循环的三种表达方式（pthreads 显式线程、数据并行 forall 声明、SIMD intrinsics 显式向量化）、SPMD（single program multiple data）/ gang 抽象、工作划分策略（静态划分 vs 动态划分）、以及”写代码时必须同时知道硬件怎么执行它”这一心智模型。

• 在并行计算知识体系中的角色：本讲是从”为什么并行”（Lecture 1）与”指令级并行/流水线”（Lecture 2）过渡到”程序怎么写”（Lecture 4 起的编程模型）的关键桥梁。它建立了后续全课程反复使用的三块地基：(1) 四种并行执行形式的分类学（超标量 / SIMD / 多核 / 硬件多线程），之后所有并行编程模型（ISPC、CUDA、OpenMP、Cilk）都可视为”用某种方式把这四种硬件并行暴露出来”；(2) 延迟与带宽的区分——延迟靠”隐藏”（多线程、预取），带宽只能靠”少访问”（数据复用、算术强度），这一区分在 Lecture 7/8 的性能优化、Lecture 20 的异构计算中反复出现；(3) 算术强度（arithmetic intensity）与 Roofline 思想，它在 Lecture 8（性能优化）中被正式化成定量工具。此外，本讲还给出了三个”通用吞吐计算原理”（并行工作要够多、同组工作要走同一条指令序列、独立工作要多于 ALU 数），它们等价于 GPU/CUDA 编程的核心约束。

• 配套材料：
  • extracted/03_basicarch.txt —— CMU 15-418/618 Fall 2026 Lecture 3 讲义（共 81 页）逐页抽取文本；对应 PDF 为 lectures/03_basicarch.pdf，位于 https://www.cs.cmu.edu/~418/lectures/ 之下，属已公开（可直接下载）。首页标注 “CMU 15-418/15-618, Fall 2026”，副标题为 “(Forms of parallelism + understanding latency and bandwidth)”。Fall 2026 日程表（https://www.cs.cmu.edu/~418/schedule.html）中本讲日期为 Aug 28。讲义内部结构清楚：slide 3–41 是 Part 1「并行执行」，slide 42–68 是 Part 2「访问内存」，slide 69–81 是术语清单与四组”把所有机制拼在一起”的复习图。
  • cs149_supp/multicore1.txt —— Stanford CS149 Lecture 2 “A Modern Multi-Core Processor (Part I)”（108 页）逐页抽取文本，属已公开支持材料。它把 CMU 版一带而过的缓存与延迟细节补全了：缓存用 LRU 替换的逐次访问演算、空间/时间局部性（spatial / temporal locality）、Kaby Lake 各级访问延迟（L1 = 4、L2 = 12、L3 = 38、DRAM ≈ 248 个 4 GHz 周期）、数据移动的能耗（整数运算 ~1 pJ、浮点运算 ~20 pJ、从片上 SRAM 读 64 位 ~26 pJ、从 LPDDR 读 64 位 ~1200 pJ；10 GB/s ≈ 1.6 W），以及”用 3 条算术 + 12 周期访存需要几个线程才能跑满”的定量算例（答案：5 个）。
  • cs149_supp/multicore2.txt —— Stanford CS149 Lecture 3 “Multi-Core Architecture, Part II (latency/bandwidth issues) + Parallel Programming Abstractions”（56 页）逐页抽取文本，属已公开。本讲 2.9/2.10/2.12 节的类比与定量模型主要来自这里：高速公路的”车速 vs 车道数 vs 车距”、洗衣房的”延迟 vs 吞吐”、两根串联水管的流量上界、带宽受限的稳态时间线（每时钟 8 字节、64 字节的 load 要 8 个时钟、每次 load 只喂 3 条数学指令 → ALU 利用率 37.5%）、4 级指令流水线 IF/D/EX/WB，以及 abstraction vs implementation 与 ISPC/SPMD 的介绍。
  • cs149_supp/dataparallel.txt —— Stanford CS149 Lecture 8 “Data-Parallel Thinking”（51 页）逐页抽取文本，属已公开。第 4 节的 work/span 记号（例如并行 scan：Work = O(N log N)、Span = O(log N)）与”工作高效但 SIMD 利用率低”的权衡来自这里，可视为本讲”并行度要够多”这一结论的延伸与形式化。
  • 未公开部分：Fall 2026 的录像（Panopto/YouTube）在日程表中被注释隐藏，属未发布；Ed 讨论区、Autolab、Canvas 均需登录。Performance Analysis/Profiling、Transactional Memory、AI in System Design 等讲座的 Fall 2026 讲义尚未在公开目录发布；历史学期的对应 PDF 位于 /afs/cs/academic/class/15418-*/public/ 之下，需要 CMU 登录，属未公开。讲义首页有时写有历史学期（如 Fall 2025）字样，这是因为讲义沿用，属正常现象。

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

2.1 全讲地图：四个核心概念，三种并行执行形式

• 定义与目的：讲义开篇即声明”今天讲四个核心概念，两个关于并行执行、两个关于访问内存”，并说明动机：理解这些架构基础，才能优化并行程序性能，也才能直觉判断哪类负载会从快速并行机器上受益。四个概念可以列成一个 2×2 的坐标：

   Lecture 3: four key concepts

┌────────────────┬────────────────────────┬──────────────────────┐
│  HARDWARE gives│PARALLEL EXECUTION      │ACCESSING MEMORY      │
├────────────────┼────────────────────────┼──────────────────────┤
│                │(1) multi-core          │(3) HW multi-threading│
│                │(2) SIMD wide vector ALU│    + prefetch        │
├────────────────┼────────────────────────┼──────────────────────┤
│  SOFTWARE must │enough independent work;│arithmetic intensity  │
│                │coherent control flow   │high enough, else you │
│                │for SIMD groups         │are BANDWIDTH BOUND   │
└────────────────┴────────────────────────┴──────────────────────┘

   中文对照: 硬件给的是 (1)多核 (2)SIMD (3)硬件多线程 + 预取;
             软件必须提供 "足够多、够齐、有余量" 的独立工作与足够高的算术强度。

• 直观解释（”它是什么？”）：把现代多核处理器想象成一座中央厨房。过去（pre multi-core era）的做法是雇一位米其林大厨，给他配最好的刀、最好的灶、最大的操作台（大缓存、乱序逻辑、分支预测器），让他一个人做菜越来越快。2004 年前后这条路的收益到顶了，于是厨房改策略：雇 16 个普通厨师（多核），每人配几把一样的刀、同时切好几样菜（SIMD），而且每人在等汤炖好（访存延迟）的时候就去处理别的菜（硬件多线程）。厨房变了，但菜谱（程序）如果只写给一个人看，新厨房不会更快——这正是讲义用 sinx 这个例子要说明的第一件事。

• 架构/机制图解：下面是讲义在最后”复习”部分（slide 72–80）一路拼出来的机器演进链条，从这里可以一眼看出四种并行执行形式各自加在哪一层。

 (1) very simple processor                                IPC = 1
    ┌───────────────────────────────────────────────┐
    │ [Fetch/Decode] ──▶ [ ALU ] ◀──▶ [Exec Context]│
    └───────────────────────────────────────────────┘
                         │                        ▲
                         ▼                        │ load/store
            ┌─────────────────────────┐
            │            Memory (DRAM)│
            └─────────────────────────┘

 (2) superscalar (ILP)                                    IPC <= 2
    ┌──────────────────────────────────────┐
    │ [Fetch/Decode 1] ──▶ [Exec 1] ◀─┐    │
    │ [Fetch/Decode 2] ──▶ [Exec 2] ◀─┤    │
    │        (out-of-order control)   │    │
    │                        [Exec Context]│
    └──────────────────────────────────────┘
     * 讲义批注: "No ILP exists in this region of the program"
       (sinx 的这一段代码里没有可并行的独立指令)

 (3) multi-core (Idea #1: 4 cores)                        TLP
     ┌────────────┬────────────┬────────────┬────────────┐
     │ F/D  + ALU │ F/D  + ALU │ F/D  + ALU │ F/D  + ALU │
     │  Exec Ctx  │  Exec Ctx  │  Exec Ctx  │  Exec Ctx  │
     └────────────┴────────────┴────────────┴────────────┘
      4 条互相独立的指令流 (4 simultaneous instruction streams)
      单核变简单 => 每条流变慢 (讲义取 0.75x); 2 x 0.75 = 1.5 是潜在收益

 (4) 4 核 x 8-wide SIMD (Idea #2)                         SIMD
    ┌─────────────────────┐
    │ [Fetch/Decode]      │
    │ [ALU0 ALU1 ... ALU7]│
    │ [Exec Context]      │
    └─────────────────────┘
      x4 份  <- 一条控制流喂 8 个 ALU, 控制开销被 8 个 ALU 摊薄

 (5) 4 核 x 8-wide SIMD x 2-way MT (Idea #3)      LATENCY HIDING
    ┌───────────────────────┐
    │ [F/D] [F/D]           │
    │ [SIMD Exec 2] [Exec 1]│
    │ [Exec Ctx] [Exec Ctx] │
    └───────────────────────┘
      x4 份  <- 每个核 2 个执行上下文, 遇到 stall 就切到另一条线程
      最大 8 条并发指令流; 每时钟最多 2 条指令(其中 1 条是 8-wide SIMD)

• 关键操作与性能特征：这五种结构是叠加而不是替代关系。一台 2025 年的桌面 CPU（例如讲义提到的 Intel Arrow Lake，2025 年，20 个 CPU 核 = 8 个性能核 + 12 个能效核）同时具备多核、SIMD、超标量、多线程与深缓存层次；一台 GPU（例如讲义提到的 NVIDIA B200，2025 年，144 个 SM、18944 个 “CUDA core”）则把后三种推到极端。判断一段代码”能不能跑满机器”要同时回答三个问题：够不够多（多核）、齐不齐（SIMD 一致性）、有没有余量（多线程隐藏延迟）。

2.2 示例程序 sinx：从 C 代码到指令流

• 定义与目的：全讲用一个程序贯穿：对长度为 N 的浮点数组逐元素计算 sin(x)（用 Taylor 展开 sin(x) = x - x³/3! + x⁵/5! - x⁷/7! ...）。选它是因为它同时具备三个特征：(a) 循环体内部是一条”看起来没什么可并行”的连乘/累加依赖链；(b) 外层 for i 的迭代彼此完全独立；(c) 每个元素只读 4 字节、写 4 字节，算术强度极低——因此既能用来讲并行执行，又能用来讲带宽。

• 直观解释（”它是什么？”）：把它想成一条流水线上的 100 万个零件。每个零件都要经过同样的 5 道工序（terms=5 的 5 次迭代），每个零件的 5 道工序必须按顺序做（value、numer、denom 都是递推），但零件与零件之间毫无关系。这恰好是 SIMD 最适合的形状：同一条指令序列作用在 8 个不同零件上。

• 架构/机制图解：从源码到”处理器真正看到的东西”要经过编译器这一层翻译，理解这一层是理解后面所有优化的前提。

 C source (讲义 slide 4)
 ┌────────────────────────────────────┐
 │void sinx(int N, int terms,         │
 │          float* x, float* result)  │
 │{ for (int i=0;i<N;i++) {           │
 │    float value = x[i];             │
 │    float numer = x[i]*x[i]*x[i];   │
 │    int denom = 6;   // 3!          │
 │    int sign  = -1;                 │
 │    for (int j=1; j<=terms; j++) {  │
 │      value += sign * numer / denom;│
 │      numer *= x[i] * x[i];         │
 │      denom *= (2*j+2) * (2*j+3);   │
 │      sign  *= -1; }                │
 │    result[i] = value; }}           │
 └────────────────────────────────────┘
                    │  编译器 gcc / clang -O3
                    ▼
 标量指令流 (scalar instruction stream): 一次处理 1 个数组元素
 ┌───────────────────────────────────────────┐
 │ld   r0, addr[r1]    ; x[i]                │
 │mul  r1, r0, r0                            │
 │mul  r1, r1, r0                            │
 │...    (inner loop: ~10 instructions per j)│
 │st   addr[r2], r0    ; result[i]           │
 └───────────────────────────────────────────┘
                        │
                        ▼
┌───────────────────────────────────────────────────────────────────┐
│ [ Fetch/Decode ] ──▶ [ ALU (Execute) ] ◀──▶ [ Exec Context ]      │
│      PC -> next instruction    ↑            R0 R1 R2 ...          │
│                                └── 1 instruction per clock (IPC=1)│
└───────────────────────────────────────────────────────────────────┘
      一台"极简处理器": 每时钟执行 1 条指令; PC 与寄存器组构成执行上下文。

• 关键操作与性能特征：这台”教学用极简处理器”的规格是每时钟执行一条指令（1 IPC）。它的性能模型就是 T = 指令数 / (IPC × 时钟频率)；编译器生成的指令数、以及处理器每时钟能发射几条指令（IPC），是本讲前半部分反复出现的两个杠杆。注意讲义特别标注的一点：sinx 的这段代码里没有 ILP 可用（内层循环的 numer、denom、sign、value 全是依赖链），所以这台机器即使升级到两路超标量也拿不到 2 倍。

2.3 并行执行形式之一：超标量（superscalar）与 ILP

• 定义与目的：超标量指处理器在同一时钟周期内取指、译码并发射多条来自同一条指令流的独立指令到多个执行单元。它的目的是利用指令级并行（ILP, instruction-level parallelism）——同一线程内部本来就存在、但只有硬件才能动态发现的并行性。

• 直观解释（”它是什么？”）：这是一位厨师同时照看两口锅。菜谱（指令流）只有一份，但”等水开”和”切葱花”这两步互不依赖，可以同时做。关键限制是：菜谱里必须真有互不依赖的步骤，否则厨师再能干也只能干等——sinx 的内层循环恰好就是这种”每步都要用上一步结果”的菜谱，所以超标量在这里无能为力（讲义原文标注 “No ILP exists in this region of the program”）。

• 架构/机制图解：讲义把预多核时代与多核时代的芯片晶体管预算画成了两幅对照图，这是理解”为什么转向多核”的核心。

 PRE MULTI-CORE ERA                    MULTI-CORE ERA (Idea #1)
┌──────────────────────────────┐   ┌───────────────┬───────────────┐
│  [Fetch/Decode]              │   │ [F/D]         │ [F/D]         │
│  [ ALU ]  ◀── [Exec Context] │   │ [ ALU ]       │ [ ALU ]       │
│  +--------------------------+│   │ [Exec Context]│ [Exec Context]│
│  | Data cache (a big one)   |│   └───────────────┴───────────────┘
│  | Out-of-order control     |│
│  | Fancy branch predictor   |│
│  | Memory pre-fetcher       |│
│  +--------------------------+│
└──────────────────────────────┘

 多数晶体管用于让"一条指令流"更快         用增加的晶体管去"加更多的核",
 (更大缓存/更聪明的乱序与分支预测)         而不是让单条指令流的逻辑更复杂

 讲义原文: "Idea #1: Use increasing transistor count to add more cores to the
            processor, rather than use transistors to increase the sophistication
            of processor logic that accelerates a single instruction stream."

• 关键操作与性能特征：这里有一个容易被忽略的定量论证，讲义把它讲得很直白：简单核比复杂核慢，但多核的总和更大。假设立方体（”fancy core”）跑一条指令流的速度指数为 1.0，而简单核只有 0.75；那么两核系统的潜在吞吐是 2 × 0.75 = 1.5——但如果程序里没有并行（例如原封不动编译的 sinx），性能就变成 0.75，也就是”加速比 0.75x”，即更慢了。这个”0.75 倍”的设定是讲义用来制造反差的虚构数值，但它揭示的规律是真的：体系结构转向吞吐（throughput-oriented）之后，”不提并行”的程序会自动变慢。

  2.4 想法 #1：多核（Multi-core）

• 定义与目的：多核处理器在单个芯片上放多个完整的处理核，每个核有自己的取指/译码单元与执行上下文，能同时执行完全不同的指令流。它解决的问题是：当单线程性能无法继续靠”更复杂的核 + 更高主频”提升时，如何继续提高芯片级吞吐。软件侧对应的是线程级并行（TLP），由软件决定何时创建线程。

• 直观解释（”它是什么？”）：多核就是把一个大厨换成 16 个小厨，每人一口锅、一本自己的菜谱。好处是各自做各自的菜（不同指令流），坏处是如果你只有一本菜谱（串行程序），另外 15 个人只能看着。把工作分给他们是程序员的责任，硬件不会自动帮你切分一个串行循环。

• 架构/机制图解：讲义给出的最小多核改写是把循环切成两半，一半给新线程、一半留给主线程——这是 fork-join（分叉-汇合）执行模型最朴素的形态。

 软件执行模型: fork-join (pthreads 版本, 讲义 slide 16 / slide 74)

   main thread
   ────┬───────────────────────────────────────────────┬──────▶ time
       │ pthread_create(tid, my_thread_start, &args)   │
       │        │                                      │
       │        └──▶ [ worker thread: sinx(N/2, x, res) ]──┐
       │                                                   │  (两条线程并发执行)
       └──▶ [ main thread: sinx(N-N/2, x+N/2, res+N/2) ] ──┤
                                                           │
       ◀────────────── pthread_join(tid, NULL) ────────────┘
       │
       ▼ 恢复单线程执行 (resume sequential execution)

   工作切分:  args.N = N/2; args.x = x; args.result = result;
              worker 处理 [0, N/2) ; main 处理 [N/2, N)  <- 两个半区互不重叠
   两条线程访问同一个大数组的不同片段, 因此不需要任何同步原语。

• 关键操作与性能特征：pthread_create / pthread_join 是昂贵的（微秒级系统调用 + 线程栈分配），所以现实中不会对 N 个元素创建 N 个线程，而是”创建 ≈ 核数个线程、每个线程处理一大块”（示例二）。多核的性能上限由 Amdahl 定律决定（见第 4 节）：S(P) = 1 / (f + (1-f)/P)，其中 f 是无法并行的比例。还有一个常见误解：多核之间的指令流可以完全不同，因此多核不需要指令流一致性（coherence）——这一点与 SIMD 形成鲜明对比。

  2.5 想法 #2：SIMD（单指令多数据）

• 定义与目的：SIMD（Single Instruction, Multiple Data，单指令多数据） 指用一条指令驱动多个 ALU 同时处理多个数据元素。讲义给出的动因是 “Idea #2: Amortize cost/complexity of managing an instruction stream across many ALUs”——把”取指、译码、控制、调度”这套复杂逻辑的开销摊薄到很多个 ALU 上，从而以极小的额外成本获得数倍算力。它解决的问题是：算力提升不再依赖”把单条指令流做得更快”，而是”用一条流喂饱更多执行单元”。

• 直观解释（”它是什么？”）：把标量处理器想成一位老师只教一个学生，SIMD 就是一位老师对着 8 个学生讲同一句话，8 个学生同时做同一道题。老师的时间（取指/译码）只花一次，学生（ALU）有 8 个。代价很明确：如果学生被要求做不同的题（分支发散），老师就只能一个一个来，其他学生闲着。

• 架构/机制图解：讲义用 8 个 ALU 共享一个取指/译码单元来画 SIMD，然后又给出 AVX intrinsics 版本对应的向量寄存器模型。

 SIMD 执行单元 (一个核内, 8-wide)

  ┌────────────────────────────────────────────────────────────┐
  │ [ Fetch / Decode ]  <- ONE control stream, shared by 8 ALUs│
  │        │                                                   │
  │        │ same instruction broadcast to all ALUs            │
  │        ▼                                                   │
  │   ALU0  ALU1  ALU2  ALU3  ALU4  ALU5  ALU6  ALU7           │
  │    ▲     ▲     ▲     ▲     ▲     ▲     ▲     ▲             │
  │    +-----+-----+-----+-----+-----+-----+-----+             │
  │                        │                                   │
  │            [ Execution Context: 256-bit vector regs ]      │
  └────────────────────────────────────────────────────────────┘

 AVX 的寄存器视角 (__m256 = 256 bit = 8 x float32)

   标量寄存器 r0:      [ x[i] ]                    <- 1 个元素
   向量寄存器 ymm0:    [x[i] x[i+1] ... x[i+7]]    <- 8 个元素

   vloadps  ymm0, addr[r1]      ; 一条指令装载 8 个 float
   vmulps   ymm1, ymm0, ymm0    ; 一条指令做 8 个乘法
   vmulps   ymm1, ymm1, ymm0
   ...                          (内层 Taylor 迭代, 见示例一)
   vstoreps addr[ymm2], ymm0    ; 一条指令写回 8 个 float

   标量指令序列 x 8 个元素  ≈  向量指令序列 x 1 遍   =>  ~8x 吞吐
   注意: 取指/译码只花 1 次, 这就是讲义说的 "amortize control cost"

• 关键操作与性能特征：SIMD 宽度由指令集决定：SSE = 128 位（4×32 位或 2×64 位）、AVX = 256 位（8×32 位或 4×64 位）、AVX-512 = 512 位（16×32 位）、ARM Neon = 128 位。向量指令有两条产生路径——程序员用 intrinsics 显式请求、用并行语言语义（如 forall）传达给编译器、或编译器通过依赖分析自动向量化（讲义明确指出这是难题，”即使最好的编译器在任意 C/C++ 代码上也不太行”）。术语上，编译期完成的 SIMD 化叫 explicit SIMD（显式 SIMD），其特征是可以直接在二进制里看到 vmulps/vstoreps 这类指令。讲义给的机器实例：Intel Core i9（Coffee Lake）= 8 核 × 每核 8 个 SIMD ALU（AVX2）；NVIDIA GTX 480 = 15 核 × 每核 32 个 SIMD ALU、1.3 TFLOPS。

  2.6 条件执行、掩码与指令流一致性

• 定义与目的：SIMD 与分支是天然冲突的：一条指令要广播给 8 个 ALU，但 if 可能让 8 个元素走不同路径。硬件/编译器的解决方案是串行化两条分支路径 + 用掩码（mask）丢弃不该写回的结果。由此引出本讲最重要的术语之一：指令流一致性（instruction stream coherence，讲义也写作 coherent execution）——”同一段指令序列适用于所有被同时处理的元素”。
• 直观解释（”它是什么？”）：回到”一位老师教 8 个学生”。如果 8 个学生做同一道题，老师讲一遍就行（满效率）。如果 3 个学生做 A 题、5 个学生做 B 题，老师必须先讲 A 题——那 5 个学生只能假装在听（掩码掉输出）；再讲 B 题时，那 3 个学生又只能闲着。最坏情况下，8 个 ALU 只有 1 个在真正干活，效率 1/8。
• 架构/机制图解：下面是讲义 slide 32–35 的三张连续图合并成的”时间线 + 掩码”示意。

 8-wide SIMD 执行 if (x > 0) {A} else {B}, 其中只有 3 个 lane 满足条件
                     ALU 时间线 (每一行 = 1 个时钟周期, 每格 = 1 个 lane)
 time
  |   lane:   1     2     3     4     5     6     7     8
  v
┌────────────────────────────────────────────────────────────┐
│  <unconditional code>    (T = lane predicate is true)      │
│   T     T     T     F     F     F     F     F              │
├────────────────────────────────────────────────────────────┤
│  if-branch: only lanes 1-3 do useful work                  │
│  [A]   [A]   [A]    x     x     x     x     x              │
│  [A]   [A]   [A]    x     x     x     x     x              │
├────────────────────────────────────────────────────────────┤
│  else-branch: only lanes 4-8 work                          │
│   x     x     x    [B]   [B]   [B]   [B]   [B]             │
│   x     x     x    [B]   [B]   [B]   [B]   [B]             │
├────────────────────────────────────────────────────────────┤
│  <resume unconditional code>  <- full width again          │
│  [ ]   [ ]   [ ]   [ ]   [ ]   [ ]   [ ]   [ ]             │
└────────────────────────────────────────────────────────────┘

 结论: 分支本身不致命; 致命的是"同一批元素的控制流不一致"(divergent execution)。
       成本 ≈ 两条路径长度之和 / SIMD 宽度; 最坏情况只有 1/8 的 ALU 在做有用功。
       分支结束后立刻恢复全宽执行, 所以"短小而少量"的发散是可以接受的。

• 关键操作与性能特征：讲义用两句话把这里的分寸讲清楚了，值得逐字记住：

  1. 指令流一致性是”高效使用 SIMD 资源”的必要条件（coherent execution IS necessary for efficient use of SIMD processing resources）；
  2. 指令流一致性不是”跨核高效并行”的必要条件（coherent execution IS NOT necessary for efficient parallelization across cores），因为每个核都能独立取指/译码不同的指令流。

  另外讲义特别提醒：不要把”指令流一致性（instruction stream coherence）”和后面课程要讲的”缓存一致性（cache coherence）”混为一谈——它们是完全无关的两个概念，只是英文都叫 coherence。

• 表格：四种并行执行形式对比

2.7 显式 SIMD 与隐式 SIMD：两种截然不同的实现策略

• 定义与目的：讲义用两个术语区分 SIMD 的两种落地方案。explicit SIMD（显式 SIMD）：并行化发生在编译期，编译器真的生成向量指令（可反汇编看到 vmulps）。implicit SIMD（隐式 SIMD）：编译器生成的是标量二进制，但N 份程序实例总是被硬件一起执行（execute(my_function, N)），对硬件而言接口本身就是数据并行的——由硬件（不是编译器）负责让多个实例的同一指令落到不同数据上。这个区分的目的，是让”编程模型”与”硬件实现”这两个层次解耦。

• 直观解释（”它是什么？”）：显式 SIMD 像老师自己把 8 道题抄成一张大卷子，让学生一次做完（编译期就把”8 个元素”打包成向量）。隐式 SIMD 像学校规定全班必须同步做同一道题（硬件保证 32 个线程同进同退），老师则按”一个学生一张卷子”来备课（写标量代码）。

• 架构/机制图解：这两种策略对应的”程序看到的机器”完全不同，下面把它和 GPU 的 warp 机制画在一起。

 EXPLICIT SIMD (CPU, 编译期向量化)      IMPLICIT SIMD (GPU, 运行期同步)
┌──────────────────────────────┐        ┌──────────────────────────────┐
│C source (intrinsics / forall)│        │C source (scalar only)        │
│            │                 │        │            │                 │
│            ▼  compiler       │        │            ▼  compiler       │
│  +--------------------------+│        │  +--------------------------+│
│  | vloadps / vmulps / ...   |│        │  | ld / mul / st  (scalar)  |│
│  +--------------------------+│        │  +--------------------------+│
│binary contains vector instrs │        │binary contains scalar instrs │
└──────────────────────────────┘        └──────────────────────────────┘

                                                          │
                                                          ▼  硬件(hardware)负责同步
                         ┌───────────────────────────────────────────────────────┐
                         │  32 HW threads (one warp) execute the same instruction│
                         │  lane:  0    1    2   ... 30   31                     │
                         │        [ALU][ALU][ALU] ... [ALU]    <- 32-wide        │
                         │  if lane 6 takes another path -> lane 6 is masked     │
                         └───────────────────────────────────────────────────────┘
   宽度: SSE 4 / AVX 8 / AVX-512 16      宽度: 现代 GPU 8 ~ 32

• 表格：显式 SIMD vs 隐式 SIMD

2.8 内存侧的挑战之一：延迟（latency）与停顿（stall）

• 定义与目的：内存延迟（memory latency）是”一个访存请求（load/store）从处理器发出到被内存系统满足所需的时间“，讲义给的量级是 100 个周期 / 100 纳秒。停顿（stall）指处理器因为”下一条指令依赖前面尚未完成的指令”而无法继续。这一节要解决的核心问题是：访问内存是停顿的最大来源，而延迟无法被消除，只能被”隐藏”或”减少”。

• 直观解释（”它是什么？”）：讲义在 CS149 版本里用厨房/洗衣房类比，但更贴切的是”去地下室仓库取食材“：CPU 是厨房，寄存器是案板（1 步就能拿到），L1 是冰箱（4 步），L2 是储物间（12 步），L3 是楼下的冷库（38 步），DRAM 是开车 20 分钟去的批发市场（~248 步）。关键在于：你一旦开车去批发市场（发起 load），在车回来之前，案板上的菜就只能等——除非你有别的活可以干。

• 架构/机制图解：下面把讲义与 CS149 支撑材料里的缓存层次、延迟、带宽、能耗画在一张图上。

                  ┌─────────────────────────────────────────┐
                  │              Core (x4)                  │
                  └───────────────────┬─────────────────────┘
                                    ▼
                              ┌───────────────────┐   L1: 32 KB
                              │  L1 cache         │   latency ~4 cycles @4GHz
                              └─────────┬─────────┘
                                    ▼
                              ┌───────────────────┐   L2: 256 KB
                              │  L2 cache         │   latency ~12 cycles
                              └─────────┬─────────┘
                                    ▼
        ┌────────────────────────────────────────────────┐
        │  L3 cache (shared)   8 MB    latency ~38 cycles│
        └────────────────────────────────────────────────┘
                                    ▼
        ┌───────────────────────────────────────────────────────┐
        │  DRAM (DDR3, Gigabytes)   latency ~248 cycles         │
        │  bandwidth ~25 GB/s       energy: 64-bit read ~1200 pJ│
        └───────────────────────────────────────────────────────┘

 层次规律: 越靠近处理器 => 容量越小、延迟越低、带宽越高、每字节能耗越低
 数据访问延迟 (Kaby Lake @4 GHz, CS149 表): L1=4, L2=12, L3=38, DRAM≈248 周期
 数据移动能耗 (CS149, 来源 Bill Dally/Tom Olson):
     整数运算 ~1 pJ | 浮点运算 ~20 pJ | 片上 SRAM 读 64 bit ~26 pJ
     低功耗 DRAM(LPDDR) 读 64 bit ~1200 pJ  =>  从内存读 10 GB/s ≈ 1.6 W
 对付延迟的三种手段: 缓存(降低成本) / 预取(提前搬) / 硬件多线程(藏起来)

• 关键操作与性能特征：讲义给出对付延迟的三种手段，其中前两种属于”减少/掩盖”、第三种属于真正的”隐藏”：
  1. 缓存（cache）——减少延迟的长度：处理器只在数据已经在缓存里时才跑得高效。讲义的表述是 “Caches reduce memory access latency”，并补充”缓存同时提供高带宽的数据传输”。缓存还带来两种局部性红利（CS149 的演算）：空间局部性（载入一个 cache line 会”预载”同一行内后续要用的地址）与时间局部性（重复访问同一地址命中）。以一个容量 8 字节、行宽 4 字节、LRU 替换的两行缓存为例，顺序扫描一个 16 字节数组会得到 4 次 cold miss + 12 次 hit，而再一次扫描整个数组时，由于容量只有两行，地址 0x0/0x4 的数据早已被逐出，产生的是”容量缺失（capacity miss）”而不是命中——这解释了为什么”数组太大、重复使用距离太远”时缓存帮不上忙。
  2. 预取（prefetching）——把延迟挪走：现代 CPU 动态分析访问模式，”预测 r2 的值并提前发起 load”，等真正执行到 ld r0, mem[r2] 时数据已经在缓存里，于是这两条 load 变成 cache hit。讲义同时警告：预取猜错会降低性能（白白占用带宽、污染缓存）。
  3. 硬件多线程（multi-threading）——用别人的活填满等待时间：见 2.10。讲义特别强调：多线程和预取一样，是”隐藏延迟”而不是”降低延迟”的技术。

     2.9 内存侧的挑战之二：带宽（bandwidth）

• 定义与目的：内存带宽（memory bandwidth）是”内存系统向处理器提供数据的速率“，讲义给的量级是 20 GB/s。与延迟不同，带宽不是可以通过”多找点活干”绕开的：如果处理器请求数据的速度超过了内存系统的供给速率，那么再多的延迟隐藏也没有用（讲义原文：”No amount of latency hiding helps this.”）。这一节的目的，是让”性能瓶颈”这个概念从”算力不够”扩展到”数据供不上”。
• 直观解释（”它是什么？”）：讲义用两组类比，配合起来看非常清晰。
  • 高速公路（CS149）：旧金山到 Stanford 约 50 km，车速 100 km/h。那么延迟 = 0.5 小时（一辆车从 SF 开到 Stanford 要多久），若”路上同时只能有一辆车”，吞吐 = 2 辆车/小时。提高吞吐有三条路：(a) 开快点（200 km/h → 4 辆/小时）；(b) 多修车道（2 车道 @100 km/h → 8 辆/小时）；(c) 让车挨近点（车距 1 km、车速 100 km/h → 100 辆/小时）。请注意 (a) 与 (c) 的差别：开车快既降延迟又升吞吐，而压缩车距只升吞吐、不降延迟——这正是”吞吐导向系统愿意牺牲单任务延迟”的本质。用公式说：吞吐 = 车速 / 车距。
  • 洗衣房（CS149）：一次洗衣 = 洗 45 分钟 + 烘 60 分钟 + 叠 15 分钟，延迟 2 小时。要吞吐翻倍，可以买两台洗衣机两台烘干机再叫个朋友（资源翻倍）；也可以流水化：不等第一批全做完就开始洗第二批，于是只有一台洗衣机一台烘干机也能做到 1 批/小时的吞吐——流水线（pipelining）用相同的资源换来了吞吐。这就是指令流水线的原型。
  • 串联水管（CS149）：一根最大流量 100 L/s 的管子接一根 50 L/s 的管子，系统最大流量是 50 L/s——系统的吞吐由最慢的一环（瓶颈）决定。把它对应到程序上：内存带宽常常就是那根 50 L/s 的管子。
• 架构/机制图解：讲义的核心图是”带宽受限的稳态”（steady state）：一段只有 3 条数学指令、却要 load 64 字节的程序，在”内存每时钟供 8 字节”的机器上会发生什么。 ```text 假设 (CS149 multicore2): 核每时钟执行 1 条数学指令; 内存每时钟供 8 字节; 程序模式 = load 64 字节, 然后 3 条依赖的数学指令; 有足够的硬件线程隐藏延迟

time(clock) –> 0 8 16 24 32 40 memory: ┌────┬────┬────┬────┬────┐ │XXXX│XXXX│XXXX│XXXX│XXXX│ 每 8 个时钟完成一次 64 B 传输 └────┴────┴────┴────┴────┘ 8 B/clk x 8 clk = 64 B ▲ ▲ ▲ │数据到达 │数据到达 │ core: [aaa][…..][aaa][…..][aaa][…..] ^^^ = 3 条数学指令 ….. = 停顿 (stall)

ALU 利用率 = 3 条 / 8 个时钟 = 37.5% <– 与延迟大小、未完成请求数无关! memory 利用率 = 100% (它已经在满负荷送数据, 不可能更快)

对照 (CS149 multicore1): 3 条算术 + 12 周期访存延迟 1 个硬件线程 = 3/15 = 20% ; 2 个 = 6/15 = 40% ; 5 个 = 15/15 = 100% 若改为 6 条算术 + 12 周期延迟: 单线程 6/18 = 33%, 只要 3 个线程就 100%

- **关键操作与性能特征**：这张图给出三条可迁移的结论。
  1. **稳态下，核的利用率只取决于"指令吞吐率"与"内存吞吐率"的比值**，而**与内存延迟、未完成访存请求数无关**（CS149 原文请读者自行说服自己这一点）。直觉是：延迟决定的是"要开多少个并发的请求才能把管子填满"（Little 定律 `并发数 = 带宽 × 延迟`），一旦填满，剩下的就只看管子有多粗。
  2. **提高算术强度可以降低对带宽的依赖**：把每次 load 之后的数学指令从 3 条提高到 6 条，利用率就从 37.5% 提到 75%。
  3. **带宽受限是吞吐型系统上最常见的性能天花板**："Overcoming bandwidth limits are a common challenge for application developers on throughput-optimized systems."

- **表格：延迟 vs 带宽——两种完全不同的瓶颈**

| 维度 | 内存延迟（latency） | 内存带宽（bandwidth） |
|---|---|---|
| 定义 | 一个访存请求被满足所需的时间 | 内存系统提供数据的速率 |
| 讲义举例 | 100 cycles / 100 nsec | 20 GB/s |
| 谁能改善它 | 缓存（降低）、预取（掩盖）、硬件多线程（隐藏）、提高 ILP | **只有"少访问数据"**：复用（同线程时间局部性、跨线程共享）+ 提高算术强度 |
| 典型症状 | 单线程停顿多、ALU 利用率低、增加线程后立刻改善 | 增加线程/ALU 后性能不再上升；memory 已 100% 忙碌 |
| 增加线程数的效果 | **有救**（隐藏延迟） | **无救**（讲义："No amount of latency hiding helps this."） |
| 相关公式 | `需要的并发请求数 ≈ 带宽 × 延迟`（Little 定律） | `可达性能 = 带宽 × 算术强度` |

#### 2.10 想法 #3：硬件多线程（Hardware Multi-threading）

- **定义与目的**：**硬件多线程**指**一个核内保存多份执行上下文（execution context，即多组 PC + 寄存器）**，由**硬件（而不是操作系统）**在每个时钟周期决定执行哪一份上下文的指令。它解决的问题是 2.8 节留下的空白：**当某条线程因为长延迟访存而停顿，核的 ALU 就空转了；如果核上有另一条线程的工作，就可以立刻顶上。**核心限制是：**核的 ALU 数量没有变**——多线程只是让现有 ALU 在遇到高延迟操作时被用得更充分。

- **直观解释（"它是什么？"）**：这是一位厨师的**"边等水开边切葱"**。水壶放上去（发起 load）之后有 100 个周期的空档，厨师不必傻等，可以切葱花（执行另一条线程的算术指令）；水一开（数据到达），再回头处理。讲义在 CS149 版本里的表述最精炼：**"当你没法在当前线程上推进时，就去推进另一个线程。"** 代价是：**你手上要多备几份菜谱和几个碗（执行上下文的片上存储是有限资源），而且这个厨师做单道菜的时间会变长**。

- **架构/机制图解**：下面是 CS149 用"3 条算术 + 12 周期访存延迟"做的经典算例的甘特图（它是把讲义的时间线重画得可读）。

```text
 每个核: 每时钟 1 条标量指令; 线程模式 = [3 条算术指令][12 周期访存延迟]

 (a) 1 个硬件线程                            -->  利用率 3/15 = 20%
 clk   0    3              15   18             30
 T0    [aaa][stall ........][aaa][stall ........]
       ^^^=3 math           ^^^ stall = 12 周期

 (b) 2 个硬件线程                            -->  利用率 6/15 = 40%
 T0    [aaa][stall ........][aaa][stall ........]
 T1    [....][aaa][stall ...][....][aaa][stall ..]
                   ^ T0 此刻是 "runnable 但未被处理器执行"
                     (核正在执行另一条线程的指令)

 (c) 4 个硬件线程                            -->  利用率 12/15 = 80%
 T0    [aaa][stall ........][aaa][stall ........]
 T1    [....][aaa][stall ...][....][aaa][stall ..]
 T2    [....][....][aaa][st..][....][....][aaa]
 T3    [....][....][....][aaa][stall ........] ...

 (d) 5 个硬件线程  -->  15/15 = 100%   (再加线程无益, 已经跑满)

 关键: 内存延迟本身一点没变! 变的是它不再导致处理器利用率下降。

• 关键操作与性能特征：
  • 片上执行上下文存储是有限资源，这带来一个根本的设计取舍（讲义用两张图对比）：要么 1 个核 16 个小的硬件线程（能隐藏很高的延迟，但每个线程的工作集很小），要么 1 个核 4 个大的硬件线程（单线程工作集大，但隐藏延迟的能力低）。GPU 走的是前者（V100 的 SM 用 256 KB 寄存器保存最多 64 个 warp），CPU 走后者（Skylake 2 路 SMT）。
  • 两种硬件多线程：交织式多线程（interleaved multi-threading，又称 temporal multi-threading）——每个时钟从一个线程取一条指令；同时多线程（SMT, Simultaneous Multi-Threading）——每个时钟从多个线程各取指令同时发射，是超标量设计的扩展，Intel 的 Hyper-Threading 就是 2 线程/核的 SMT。
  • 收益与代价（讲义 slide 60 的清单）：收益是更充分地使用 ALU 资源（隐藏访存延迟、在单线程 ILP 不足时填满超标量的多个功能单元）。代价包括：需要更多存储保存线程上下文；延长任何单一线程的运行时间（在吞吐型并行应用中通常可接受）；需要程序里有比 ALU 数更多的独立工作；高度依赖内存带宽；以及”线程越多 → 工作集越大 → 每线程分到的缓存越小 → 可能更频繁访问内存（但延迟可以隐藏）”。
• 表格：交织式多线程 vs 同时多线程（SMT） | 对比项 | 交织式 / 时间多线程 | 同时多线程（SMT） | |—|—|—| | 每个时钟执行几条线程的指令 | 1 条（来自被选中的那一个线程） | 多条（来自多个线程，同周期发射） | | 与超标量的关系 | 独立机制 | 是超标量设计的扩展（共用发射逻辑） | | 能否填满多个功能单元 | 不能（该时钟只有 1 条指令） | 能（这正是 SMT 的主要收益） | | 典型实例 | 讲义描述的”每时钟挑一个线程”的核 | Intel Hyper-Threading（2 线程/核） | | 对单线程延迟的影响 | 单线程变慢 | 单线程变慢 | | 需要的软件条件 | 独立工作数 > ALU 数 | 同上（且需多线程 ILP 互补） |

  2.11 一台现代多核处理器的全貌

• 定义与目的：把前面所有机制叠起来，就得到讲义 slide 61 与 slide 80 的两张”整机图”。它是本讲最重要的定量直觉来源：一台机器的”有效并行度”是各层并行度的乘积，而”要跑满它”所需的独立工作数也是这个乘积。
• 直观解释（”它是什么？”）：把芯片想成一栋办公楼：16 个部门（核），每个部门 8 个工位（SIMD lane），每个工位有 4 个员工的轮班表（硬件线程）。要让整栋楼一刻不闲，你手上必须同时有 16 × 8 × 4 = 512 件互不依赖的活——活少于这个数，就一定有工位在等。
• 架构/机制图解：下面是讲义 slide 80 的”四核整机图”的可读重绘。

   CHIP (quad-core example)
   ┌──────────────┐  ┌──────────────┐  ┌──────────┐  ┌──────────┐
   │ CORE 0       │  │ CORE 1       │  │ CORE 2   │  │ CORE 3   │
   │ [F/D] [F/D]  │  │ [F/D] [F/D]  │  │  (same)  │  │  (same)  │
   │ [Exec1][SIMD]│  │ [Exec1][SIMD]│  └──────────┘  └──────────┘
   │ [Ctx0][Ctx1] │  │ [Ctx0][Ctx1] │
   │ L1 + L2 priv │  │ L1 + L2 priv │   每核: 最多 2 条指令/时钟
   └──────┬───────┘  └──────┬───────┘   (其中 1 条是 8-wide SIMD)
        │                 │            每核 2 个执行上下文
        └────────┬────────┘            => 全芯片最多 8 条活跃线程
                 ▼
        ┌───────────────────────┐
        │ on-chip interconnect  │
        └───────────┬───────────┘
                    ▼
        ┌───────────────────────┐
        │ L3 cache (shared)     │
        └───────────┬───────────┘
                    ▼
        ┌───────────────────────┐
        │ Memory Controller     │
        └───────────┬───────────┘
                    ▼
            Memory Bus (to DRAM)
  

• 表格：有效并行度与”跑满机器所需的独立工作数” | 机器配置 | 核数 | 每核 SIMD 宽度 | 每核硬件线程 | 指令流数 | 需要多少独立工作才”跑满” | 出处 | |—|—|—|—|—|—|—| | 讲义”虚构多核芯片” | 16 | 8 | 4 | 16 条同时 + 共 64 条并发 | 512 份独立工作 | 03_basicarch slide 61 | | 讲义四核整机图 | 4 | 8 | 2 | 最多 8 条活跃线程 | 4 × 8 × 2 = 64 | 03_basicarch slide 80 | | Intel Core i9 (Coffee Lake) | 8 | 8 | —（讲义未给） | — | —（讲义未给） | 03_basicarch slide 39 | | Intel i7-7700K (Kaby Lake) | 4 | 8 × 3 个向量 ALU = 24 | 2 (SMT) | — | —（讲义未给） | cs149 multicore1 | | NVIDIA GTX 480 | 15 | 16（32 ALU 分两组） | 最多 48 warp/核 | 15 × 48 warp | 每核 1500+ 元素，全芯片 23,000 份数据 | 03_basicarch slide 62–64 | | NVIDIA V100 | 80 | 16 | 最多 64 warp/SM | 80 × 64 | 每 SM 2048，全芯片 163,840 | cs149 multicore1/2 |

  2.12 软件执行模型：fork-join、forall 与 SPMD gang

• 定义与目的：硬件提供了上述并行资源，但程序必须用某种”模型”来表达并行。讲义在本讲引入了两种最基本的表达方式（后续 Lecture 4 起的编程模型讲座会系统展开）：显式线程（pthreads / C++ threads）的 fork-join，以及数据并行声明（forall）。CS149 支持材料进一步给出了它的实现形式：SPMD（single program multiple data）/ gang。
• 直观解释（”它是什么？”）：
  • fork-join 像临时招工：主线程招一批临时工（fork），大家分头干，干完登记收工（join）。招工本身有开销，所以是”少招工、每人多干”。
  • forall 像下订单：”把这 N 件衣服全部熨一遍”——你只声明”这些迭代互不相关”，谁去熨、怎么分工由实现决定。
  • SPMD gang 像广播体操：一次性启动 programCount 个体操队员（gang），每个人拿到自己的编号 programIndex，然后所有人一起做同一套动作（同一条指令流），只是各自的位置不同（数据不同）。
• 架构/机制图解：下面把 forall/SPMD 抽象与其 SIMD 实现画在一起，这是本讲”软件模型 ↔ 硬件执行”的关键对照。 ```text 软件层 (程序员看到的抽象) 硬件层 (实现) ┌───────────────────────────┐ ┌──────────────────────────┐ │forall (i = 0 … N-1) { │ │gang = 8 program instances│ │ // iterations are │ │ == 8-wide SIMD lanes │ │ // mutually independent│ │programIndex = 0..7 │ │} │ │programCount = 8 │ └───────────────────────────┘ └──────────────────────────┘ │ 编译器/运行时选择一种实现 ▼ ┌─────────────────────────────────────────────────────────────────┐ │Implementation 1: instance 0 runs all iterations (no parallelism)│ │Implementation 2: INTERLEAVED assignment │ │ for (loop_i=0; loop_i<N; loop_i+=programCount) │ │ i = loop_i + programIndex; │ │ -> 8 instances touch CONTIGUOUS words -> one packed vload │ │Implementation 3: BLOCKED assignment │ │ count = N/programCount; start = programIndex*count; │ │ -> 8 instances touch FAR-APART words -> needs gather (costly)│ │Implementation 4: DYNAMIC assignment (atomic_add_local) │ │ -> best load balance, but pays synchronization cost │ └─────────────────────────────────────────────────────────────────┘

交错划分 (interleaved): instance: 0 1 2 3 4 5 6 7 | 8 9 10 … iteration: 0 1 2 3 4 5 6 7 | 8 9 10 … <- 连续 分块划分 (blocked): instance 0 -> iterations [0..7] instance 1 -> iterations [8..15] … <- 地址相隔远

- **关键操作与性能特征**：
  - **交错划分 vs 分块划分的性能差异来自访存指令的形态**：交错划分下 8 个 instance 访问的是**连续 8 个 float**，一条 `vmovaps`（packed vector load）即可完成；分块划分下 8 个访问地址**彼此相隔 N/8 个元素**，需要 **gather 指令（`vgatherdps`）**——`gather`/`scatter` 是"更复杂、更昂贵"的 SIMD 访存指令（AVX2 在 2013 年支持 gather 但**不支持 SIMD scatter**，scatter 到 AVX-512 才有；GPU 上两者都有硬件支持，但仍远贵于连续向量的 load/store）。
  - **数据并行的语义陷阱**：CS149 给了一个极好的例子——`foreach (i) { if (x[i]<0) y[2*i] = -x[i]; else y[2*i]=x[i]; y[2*i+1]=y[2*i]; }` 是正确的，而 `shift_negative`（当 `x[i]<0` 时写 `y[i-1]`）**输出未定义**，因为**多个迭代可能写同一内存位置**。这说明 `forall` 的语义要求是**迭代之间既没有数据依赖、也不写同一位置（race-free）**。
  - **跨实例通信必须显式表达**：SPMD 里的局部变量是 per-instance 的（ISPC 称之为 "varying"），把 `foreach` 里的 per-instance 值累加到一个变量在类型上就是错的（编译期报错）；正确写法是**每个实例先算自己的部分和（partial），再用 `reduce_add()` 这类归约原语合并成 uniform 值**。这恰好就是 Lecture 1 里"通信是所有并行程序的核心成本"的具体化。
  - **gang 内的 SPMD 抽象只在 SIMD 层面实现**：ISPC 的 gang 由**一个** x86 核上的一条线程里的 SIMD 指令实现，所以"用 ISPC 写的数据并行代码"默认只用了**一个核**；要多核执行需要额外的抽象（ISPC 的 "task"）。

#### 2.13 GPU：把吞吐计算推到极致

- **定义与目的**：讲义用 GPU 作为"同一套吞吐计算思想的极端版本"来自我对照。理解 GPU 的 SM 结构，能反过来把 CPU 上"多核 + SIMD + 多线程"三件套的作用看得更清楚。

- **直观解释（"它是什么？"）**：CPU 是**少数几位博士**（大缓存、深乱序、聪明分支预测、少量大线程），GPU 是**几千名熟练工人**（小缓存、简单控制、海量线程）。讲义的原话总结得非常准确：**CPU 靠"缓存 + 预取"，GPU 靠"海量多线程"。**

- **架构/机制图解**：下面是讲义 slide 62–63 的 NVIDIA GTX 480（Fermi）SM 结构。

```text
 NVIDIA GTX 480 SM (Fermi, 讲义 slide 62-63)
┌───────────────────────────────────────────────────────────────┐
│   ┌──────────────┐   ┌──────────────┐                         │
│   │ Fetch/Decode │   │ Fetch/Decode │  <- control shared by 16│
│   └──────┬───────┘   └──────┬───────┘     ALUs (1 MUL-ADD/clk)│
│          ▼                  ▼                                 │
│   ┌────────────────┐ ┌────────────────┐                       │
│   │ ALU0 ... ALU15 │ │ ALU0 ... ALU15 │  = 16-wide SIMD units │
│   └────────────────┘ └────────────────┘  => 32 ALUs per core  │
│                                                               │
│   "Shared" memory (16+48 KB)     <- on-chip scratchpad        │
│   Execution contexts (128 KB)    <- holds many warp contexts  │
│                                                               │
│   * one instruction operates on 32 data items = one "warp"    │
│   * up to 48 warps interleaved per core                       │
│   * over 1500 elements processed concurrently per core        │
│   * 15 cores x 32 ALUs = 480 ALUs per chip                    │
│   * 15 x 48 warps x 32 lanes = ~23,000 data items concurrently│
└───────────────────────────────────────────────────────────────┘

 内存层次对照 (讲义 slide 65)
 CPU: 大缓存, 少线程, 中等带宽          GPU: 小缓存, 海量线程, 巨大带宽
      L1 32KB / L2 256KB / L3 8MB           texture 12KB / scratchpad+L1 64KB
      DDR3, ~25 GB/s                        L2 768KB / DDR5 ~1GB, 177 GB/s
      主要靠: 缓存 + 预取                    主要靠: 多线程

• 关键操作与性能特征：GPU 侧的关键数字是 warp = 32 个线程共用一条指令，因此 implicit SIMD 的发散惩罚上限是 1/32（讲义原文：写得很差的代码可能只能跑到机器峰值的 1/32）。另一个数字是”为了跑满机器需要多少并发数据”：GTX 480 约 23,000，V100 高达 163,840——这两个数字解释了为什么”并行度不足或算术强度低的程序在 GPU 上跑不快”。

2.14 带宽受限与算术强度（arithmetic intensity）

• 定义与目的：带宽受限（bandwidth limited） 指”处理器请求数据的速度过高，导致内存系统跟不上”的状态。算术强度（arithmetic intensity） 是讲义明确给出的一个”有用的术语”：指令流中”数学运算次数”与”数据访问次数/字节数”的比值。引入它是为了给出一个可操作的优化目标：要高效使用现代处理器，程序必须有高的算术强度。

• 直观解释（”它是什么？”）：这就像买菜做饭的”每斤食材出几道菜”。如果你每买 1 斤菜只做 1 道菜，那你的产出完全被”去菜市场的速度”限制（带宽受限）；如果你能用 1 斤菜做出 20 道菜（高算术强度），那限制就回到你的厨艺（算力）。讲义的名言是 “do more arithmetic: it’s free”——在现代芯片上，多算几次比多读一次内存便宜得多（回忆 2.8 节的能耗表：一次浮点运算 ~20 pJ，而从 LPDDR 读 64 位要 ~1200 pJ）。

• 架构/机制图解：讲义用一个极简的”逐元素向量乘法”思想实验把带宽瓶颈的存在性证明得非常干净。

 任务: C[i] = A[i] * B[i]，A/B/C 各有数百万个元素

   读 A[i] (4 B) --+
   读 B[i] (4 B) --+--> [ MUL ] --> 写 C[i] (4 B)

   每做 1 次乘法需要 3 次内存操作 = 12 字节移动
   => 算术强度 AI = 1 flop / 12 B = 0.083 flop/byte   (极低!)

 反推"跑满算力需要多少带宽" (讲义 slide 66 的数字):
   GTX 480: 480 MUL/clock @ 1.2 GHz => 480 x 1.2e9 x 12 B/s ≈ 6.4 ~ 6.9 TB/s
   实有 177 GB/s  =>  只有约 2.6% 的峰值效率 (讲义写 "~3% efficiency")
   但它依然比四核 CPU 快约 7 倍:
        GTX 480 有效算力 = 177 GB/s / 12 B = 14.75 GMUL/s
        四核 CPU (2.6 GHz Core i7 Gen4 + 25 GB/s) = 25/12 = 2.08 GMUL/s
        14.75 / 2.08 ≈ 7.1x  <- 讲义 "7x faster than quad-core CPU" 的来源

 可达性能 = min( P_peak , BW x AI )
      ▲                     .........  <- compute bound: P_peak
      │                 .../
      │              ../   <- memory bound: slope = BW
      │           ../
      │        ../
      └──────────────────────────────▶ 算术强度 AI (flop/byte)
                     ^
                AI* = P_peak / BW   (machine balance, 拐点)

 三条优化准则 (讲义 slide 68):
   1 组织计算, 少从内存取数据: 同线程复用(时间局部性) + 跨线程共享(线程间协作)
   2 请求更少的次数, 改为多算: "do more arithmetic: it's free"
   3 主结论: 程序必须有高算术强度, 才能高效利用现代处理器

• 关键操作与性能特征：这一节把本讲前半部分（并行执行）和后半部分（内存）合成了一个完整的因果链：更多核 + 更宽 SIMD 提高了峰值算力 → 峰值算力越高，喂饱它所需的带宽就越大 → 而带宽增长远慢于算力增长 → 所以”现代芯片上的许多并行应用（无论 CPU 还是 GPU）都是带宽受限的”（讲义 Summary 原话）。CPython 式的直觉是”算力是免费的，数据移动是昂贵的”。

3. 代码示例与性能分析

3.1 示例一：AVX2 显式 SIMD 的 sinx（讲义 slide 28 的 intrinsic 版本）

• 代码（已实测：g++ 12.2 -O3 -mavx2 -mfma 编译通过并运行，输出 max\|err\|=1.192e-07，与 sinf 一致到 float 精度）：

// 编译: g++ -O3 -mavx2 -mfma sinx_avx2.cpp -o sinx_avx2
//   (release 优化: -O3; AVX2 需 -mavx2, FMA 需 -mfma, 也可用 -march=native 一次性打开本机全部指令集)
//   要求: N 是 8 的倍数; x / result 按 32 字节对齐 (用 _mm_malloc 分配)
#include <immintrin.h>      // AVX / AVX2 intrinsics
#include <cstdio>
#include <cstdlib>
#include <cmath>

void sinx_avx2(int N, int terms, const float* __restrict x, float* __restrict result)
{
    for (int i = 0; i < N; i += 8) {                 // 每次处理 8 个元素
        __m256 origx = _mm256_load_ps(&x[i]);        // 1 条 vmovaps: 载入 8 个 float
        __m256 value = origx;                        // value = x
        __m256 x2    = _mm256_mul_ps(origx, origx);  // x^2
        __m256 numer = _mm256_mul_ps(x2, origx);     // x^3   (= 第一项的分子)
        __m256 denom = _mm256_set1_ps(6.0f);         // 3!    (广播成 8 份)
        float  sign  = -1.0f;
        for (int j = 1; j <= terms; j++) {
            // value += sign * numer / denom
            __m256 t = _mm256_div_ps(_mm256_mul_ps(_mm256_set1_ps(sign), numer), denom);
            value = _mm256_add_ps(value, t);
            numer = _mm256_mul_ps(numer, x2);        // 分子 *= x^2
            denom = _mm256_mul_ps(denom,
                        _mm256_set1_ps((float)((2 * j + 2) * (2 * j + 3))));
            sign  = -sign;                           // 交替正负号
        }
        _mm256_store_ps(&result[i], value);          // 1 条 vmovaps: 写回 8 个 float
    }
}

int main()
{
    const int N     = 8 * 1000;   // 必须是 8 的倍数
    const int terms = 5;
    float* x      = (float*)_mm_malloc(N * sizeof(float), 32);   // 32B 对齐
    float* result = (float*)_mm_malloc(N * sizeof(float), 32);

    for (int i = 0; i < N; i++) x[i] = -1.0f + 2.0f * (float)i / (float)(N - 1);
    sinx_avx2(N, terms, x, result);

    float max_err = 0.0f;
    for (int i = 0; i < N; i++) {
        float e = std::fabs(result[i] - std::sin(x[i]));
        if (e > max_err) max_err = e;
    }
    std::printf("N=%d terms=%d  max|err|=%.3e  result[0]=%.6f\n",
                N, terms, max_err, result[0]);

    _mm_free(x); _mm_free(result);
    return 0;
}

• 【代码做什么？】
  1. _mm_malloc(..., 32) 分配 32 字节对齐的数组——_mm256_load_ps/_mm256_store_ps 是对齐访存指令（_ps = packed single），地址不对齐会触发通用保护错误（要用非对齐版本得换成 _mm256_loadu_ps）。
  2. 外层循环 i += 8：一次迭代处理 8 个数组元素，这正是”用一条指令流处理多个数据元素”。
  3. __m256 是 256 位向量类型（8 × float32）。_mm256_load_ps 一条指令把 x[i..i+7] 载入一个向量寄存器；_mm256_set1_ps(6.0f) 把一个标量广播成 8 份（对应 denom = 6）。
  4. 内层 j 循环就是 Taylor 递推的向量版：t = sign*numer/denom 后累加到 value，再更新 numer *= x²、denom *= (2j+2)(2j+3)、sign 取反——与讲义 slide 4 的标量代码逐步一一对应，只是每个操作同时作用于 8 个元素。
  5. main 用 x ∈ [-1, 1] 初始化并逐元素与 std::sin 对比，验证向量化没有改变语义（浮点误差 ~1e-7 属 float 正常范围）。
  6. 编译命令中的 -O3 是必须的：-O0 下 intrinsics 依然能编译，但不会得到任何流水/调度优化；-mavx2 -mfma 打开指令集（用 -march=native 更省事）。
• 【并行机制与性能解说】
  • 硬件上如何并行：这段代码只用了 SIMD 这一种并行（一维、一个核内的 8 个 lane）。它没有创建任何线程，也（在 -O3 下）不依赖超标量——因为 8 个 lane 已经由向量指令显式并行，且向量内部各 lane 天然独立；但 value/numer/denom 三条递推链在内层 j 循环里是串行依赖的，所以这段代码没有 ILP 可用（与讲义对 sinx 的批注一致）。要达到全芯片峰值，还需要在外面再套一层多核并行（把 i 的范围切开，见示例二）和一层多线程延迟隐藏。
  • 工作如何分配：lane k 处理元素 i + k，即交错划分（interleaved assignment），因此访存是连续 8 个 float，正好一条 packed load 完成——这是 SIMD 分工的最佳形态。
  • 共享数据如何处理：8 个 lane 不共享任何数据，每个 lane 有自己的一份 value/numer/denom/sign（模拟为向量寄存器中的 8 个槽位）。不需要任何同步，也不存在数据竞争：输出 result[i..i+7] 互不重叠。这正是”数据并行”的最干净形态。
  • Work / Span / 并行度（以”向量指令”为计量单位，terms=5）：
    • 一次外层迭代的指令数 ≈ 装载 1 + 初始化 4 + 内层 5 次 × 约 7.5 条（set1、mul、div、add、mul、set1、mul）+ 写回 1 ≈ 43 条向量指令。
    • Work W = 43 × (N/8) ≈ 5.4N 条向量指令（等价于 43N 条标量指令级的运算量，只是因为 SIMD 宽 8 而只需要 1/8 的指令条数）。
    • Span（关键路径）S = 43：因为内层 j 循环是三条递推链，单个 chunk 内部无法再并行，跨 chunk 之间才可以并行。
    • 并行度 W/S = N/8。对 N = 1.6e7，并行度约 210 万——远远超过机器的 ALU 数（讲义的虚构芯片 128 个），所以并行度不是瓶颈。
  • 瓶颈分析：真正的瓶颈有两处。
    1. 除法器：vdivps（256 位浮点除）在 Skylake 级别 CPU 上延迟约 11 周期、吞吐约 5 周期/条，而普通向量乘法吞吐约 0.5 周期/条。本例每个 chunk 有 5 条除法（terms=5），仅除法就至少占用 5 × 5 = 25 个周期，而其余 ~38 条指令在 2–3 条向量流水线上只需约 13–19 个周期。除法是这段代码最慢的一环（对应 2.9 节”串联水管”的瓶颈原理）。改进：denom 的取值序列是确定的整数（6, 120, 5040, …），可以预算出倒数，把 div 换成 mul；同样 sign 是 ±1，可以用一次 xor 翻转符号位代替 set1 + mul。
    2. 内存带宽：每个元素读 4 字节写 4 字节，算术强度只有 2 flops / 8 B = 0.25 flop/byte（远超 0.083 的向量乘，但依然很低）。按讲义虚构芯片 25 GB/s 的带宽，N = 1.6e7 个元素需要移动 128 MB，仅带宽就需要 5.4 ms——如果算力允许更快，程序就会撞上这堵墙（见 4.5 节的 Roofline 计算）。
  • 可扩展性上限：并行度 N/8 极大，所以加核、加线程都不会缺活；扩展的上限由 max(除法吞吐, 内存带宽) 决定，而不是由并行度决定——这就是本讲要传达的核心直觉。

3.2 示例二：OpenMP 多核 sinx——工作划分策略与缩放

• 代码（已实测：g++ 12.2 -O3 -fopenmp 编译通过、运行结果与串行逐位相同（verify = ok））：

// 编译: g++ -O3 -fopenmp sinx_omp.cpp -o sinx_omp
// 运行: OMP_NUM_THREADS=16 ./sinx_omp
#include <omp.h>
#include <cstdio>
#include <cstdlib>

// 讲义 slide 4 的 sin(x)(Taylor 展开), 一次处理 1 个元素
static inline float sinx_one(float x, int terms)
{
    float value = x;
    float numer = x * x * x;
    int   denom = 6;                       // 3!(terms <= 6 时不会溢出 int)
    int   sign  = -1;
    for (int j = 1; j <= terms; j++) {
        value += sign * numer / denom;
        numer *= x * x;
        denom *= (2 * j + 2) * (2 * j + 3);
        sign  *= -1;
    }
    return value;
}

// (a) 串行版本: 整个数组由 1 个线程负责  -- 对应 "program expresses no parallelism"
static void sinx_serial(int N, int terms, const float* __restrict x,
                        float* __restrict result)
{
    for (int i = 0; i < N; i++) result[i] = sinx_one(x[i], terms);
}

// (b) 静态划分: 把 N 个迭代均分成 P 块, 每线程一块, 无运行时调度开销
static void sinx_static(int N, int terms, const float* __restrict x,
                        float* __restrict result)
{
    #pragma omp parallel for schedule(static)
    for (int i = 0; i < N; i++) result[i] = sinx_one(x[i], terms);
}

// (c) 动态划分: 每 4096 个迭代为一块, 用原子计数器把块分派给空闲线程
static void sinx_dynamic(int N, int terms, const float* __restrict x,
                         float* __restrict result)
{
    #pragma omp parallel for schedule(dynamic, 4096)
    for (int i = 0; i < N; i++) result[i] = sinx_one(x[i], terms);
}

int main()
{
    const int N     = 1 << 24;             // 16.7M 元素: x 与 result 共 128 MB
    const int terms = 5;
    float* x      = (float*)std::malloc((size_t)N * sizeof(float));
    float* ref    = (float*)std::malloc((size_t)N * sizeof(float));
    float* result = (float*)std::malloc((size_t)N * sizeof(float));
    for (int i = 0; i < N; i++) x[i] = -1.0f + 2.0f * (float)i / (float)(N - 1);

    double best_serial = 1e30;                       // 取 3 次最小值, 降低噪声
    for (int rep = 0; rep < 3; rep++) {
        double t0 = omp_get_wtime();
        sinx_serial(N, terms, x, ref);
        double dt = omp_get_wtime() - t0;
        if (dt < best_serial) best_serial = dt;
    }
    std::printf("serial: %7.2f ms   working set = %.1f MB\n",
                best_serial * 1e3, 2.0 * N * sizeof(float) / 1e6);
    std::printf("%5s %11s %11s %9s %9s %10s\n",
                "thr", "static/ms", "dyn/ms", "speedup", "GB/s", "verify");

    const int max_t = omp_get_max_threads();   // 必须先取: omp_set_num_threads 会改它
    for (int p = 1; p <= max_t; p *= 2) {
        omp_set_num_threads(p);
        double bs = 1e30, bd = 1e30;
        for (int rep = 0; rep < 3; rep++) {
            double t0 = omp_get_wtime(); sinx_static(N, terms, x, result);
            double t1 = omp_get_wtime(); if (t1 - t0 < bs) bs = t1 - t0;
            t0 = omp_get_wtime(); sinx_dynamic(N, terms, x, result);
            t1 = omp_get_wtime(); if (t1 - t0 < bd) bd = t1 - t0;
        }
        long bad = 0;                                   // 逐位校验并行结果 == 串行结果
        for (int i = 0; i < N; i++) if (result[i] != ref[i]) bad++;
        std::printf("%5d %11.2f %11.2f %8.2fx %9.1f %10s\n",
                    p, bs * 1e3, bd * 1e3, best_serial / bs,
                    2.0 * N * sizeof(float) / bs / 1e9, bad ? "FAIL" : "ok");
    }
    std::free(x); std::free(ref); std::free(result);
    return 0;
}

• 【代码做什么？】
  1. sinx_one 是逐元素的标量函数，与讲义 slide 4 的内层逻辑完全一致（int denom 在 terms ≤ 6 时最大为 13! 仍是 3.9e8 < 2³¹，不会溢出；terms ≥ 7 会溢出，应改成 float/double）。
  2. 三个 kernel 体现三种”并行执行形式”的叠加关系：sinx_serial 就是讲义里”程序不表达任何并行”的版本（编译后会作为一个线程跑在一个核上）；sinx_static / sinx_dynamic 用 #pragma omp parallel for 把外层循环的迭代分给 P 个线程——这正是讲义用 pthreads 手写 pthread_create/pthread_join 所做之事的声明式版本（软件负责创建线程、硬件提供 TLP）。
  3. schedule(static) = 静态划分：把 0..N-1 均分成 P 块，每线程一块，运行期零调度开销，但如果各迭代耗时不同就会负载不均。schedule(dynamic, 4096) = 动态划分：以 4096 个迭代为一块，线程干完一块就用原子计数器抢下一块，自动均衡负载，但每次抢任务都有原子操作与同步开销。
  4. main 先跑串行基线并保存到 ref，再对 1、2、4、8、… 个线程分别计时（各取 3 次最小值），最后逐位比较并行结果与 ref（bad 应为 0）——这一步用来证明这个数据并行改写没有引入任何数值差异。
  5. 注意 const int max_t = omp_get_max_threads(); 必须在循环之前取一次：omp_set_num_threads(p) 会把 omp_get_max_threads() 的返回值也改掉，写成 for (p = 1; p <= omp_get_max_threads(); p *= 2) 会导致循环在第一轮后就退出（这是一个实际踩过的坑）。
• 【并行机制与性能解说】
  • 硬件上如何并行：#pragma omp parallel for 展开为 fork-join——进入并行区时创建/唤醒 P 个线程（每个线程被操作系统映射到一个线程执行上下文上，讲义 slide 81 的问题”谁来把 pthread 映射到执行上下文？答案是操作系统”正是指这一层），每个线程执行 sinx_one 的一个范围，退出并行区时join 并同步。如果机器支持 SMT（例如 Kaby Lake 的 2 线程/核），P 甚至可以大于物理核数；此时 P 个软件线程被映射到 核数 × 每核上下文数 个硬件执行上下文上。
  • 工作如何分配：静态划分下线程 t 处理 [t·N/P, (t+1)·N/P)；动态划分下用 dynamic, 4096 的 chunk 抢占。注意这里的 chunk 划分是”块状”的——与示例一 SIMD 的交错划分相反。对纯数组遍历而言，块状划分依然能让每个线程顺序访问内存（空间局部性好），只是 SIMD 通道内不再连续（若再叠加 #pragma omp simd 就需要交错划分或让编译器插入 gather）。
  • 共享数据如何处理：x 和 result 是共享的，但读写区间互不重叠（线程只写自己的那段 result），因此在 cache line 层面也不共享（只要每段的边界大致对齐到 cache line，就不出现伪共享）。循环体内部没有共享可变量，不需要锁、不需要原子操作、不需要内存栅栏——唯一的同步点是并行区末尾的隐式 barrier。这是”数据并行”最高的理想形态：只分数据、不通信。
  • Work / Span / 并行度（以”标量指令”为计量单位，terms=5）：
    • 每个元素的指令数 w ≈ 函数序言（~3）+ 内层 5 次迭代 × 约 10 条（sign*numer 乘、int→float 转换、除法、加法、x*x、乘、两次整数乘、整数乘、符号取反、循环比较/跳转）+ 读/写 ≈ 55 条。
    • Work W = Θ(N · terms) ≈ 55N。对 N = 1.6e7 约 9.2e8 条标量指令。
    • Span（关键路径）S = Θ(terms) ≈ 55：单个元素的 Taylor 递推是串行的（value、numer、denom 都是循环携带依赖），所以关键路径就是”一个元素走完全部 5 次迭代”。
    • 并行度 W/S = N ≈ 1.67e7。机器的 ALU 数是几百到几千——并行度有 4 个数量级的余量，所以”并行度不足”绝不是这个程序的瓶颈。
  • 瓶颈分析：
    1. Amdahl 上限来自串行开销：线程创建/销毁、并行区 barrier、以及 main 里的初始化和校验都是串行的。若串行部分占 f，则 S(P) = 1/(f + (1-f)/P)；要让 16 线程拿到 15x，必须有 f < 1/(16·15-16+1) ≈ 0.0025——串行部分必须压到 0.25% 以下。这解释了为什么在长期运行的程序里要复用线程池（OpenMP 默认就会让线程池常驻）而不是反复 create/join。
    2. 内存带宽：每个元素 8 字节（读 4 + 写 4），N = 1.6e7 → 134 MB 的流量。按讲义虚构芯片的 25 GB/s，光带宽就要 5.4 ms；这就是为什么在算术强度低的代码上”加核”很快就不再有用（见 4.4 的定量推导）。
    3. 负载不均 vs 调度开销：本程序的每个迭代代价完全一样，所以 static 与 dynamic 差别很小（dynamic 只会更慢）；但如果各迭代代价差异大（例如后面的三角形循环），static 就会出现”一个线程干了一半活”的长尾，此时 dynamic 才划算。判断依据是迭代代价的方差，不是直觉。

  • 实测观察（本机 g++ 12.2 -O3，共享的 128 硬件线程 x86 机器，仅供定性参考）：

    线程数	static /ms	dynamic /ms	相对串行 speedup	有效带宽 GB/s	校验
    串行基线	22.56（best of 3）	—	1.00x	5.9	—
    1	126.46	112.80	0.18x	1.1	ok
    2	65.20	57.42	0.35x	2.1	ok
    4	32.75	28.80	0.69x	4.1	ok
    8	16.55	14.40	1.36x	8.1	ok
    16	9.13	7.23	2.47x	14.7	ok

    这张表里最重要的信息不是加速比数字，而是第一行与第二行的对比：同一个循环，串行版本被 GCC 自动向量化了（4 宽 SSE），而放进 omp parallel for 之后该循环没有被向量化（-fopt-info-vec 报告里串行循环显示 optimized: loop vectorized using 16 byte vectors，并行版本的循环则没有）。用一个更干净的对照实验（N = 2²⁴、terms = 5、取 7 次最小值、单线程）可以确认这一点：

    实验	时间	说明
    串行循环 for(i) r[i]=sinx_one(x[i])	22.7 ms	GCC 自动向量化（16 字节向量）
    同一循环放进 #pragma omp parallel for（1 线程）	119.9 ms	向量化报告显示该循环未被向量化
    两者都加 -fno-tree-vectorize	84.8 ms / 117.9 ms（比值 1.39x）	关掉自动向量化后差距从 5.3x 缩到 1.39x，证明确实是代码生成差异而非算法差异

    结论（可迁移的工程规则）：“并行化”和”向量化”是两个独立的优化，必须分别验证；比较加速比时必须与”同一种代码生成质量”的基线比，否则会得到荒谬的结论（比如”1 线程的并行版比串行版慢 5 倍”）。正确做法是查编译器的向量化报告（-fopt-info-vec）、必要时看反汇编，或者干脆像示例一那样显式写 intrinsics。

3.3 示例三：算术强度扫描 + ILP 对算力利用的影响

• 代码（已实测：g++ 12.2 -O3 -mavx2 -mfma -fopenmp 编译并运行）：

// 编译: g++ -O3 -mavx2 -mfma -fopenmp ai_sweep.cpp -o ai_sweep
// 运行: OMP_NUM_THREADS=16 ./ai_sweep
#include <omp.h>
#include <cstdio>
#include <cstdlib>

// 单次 kernel: 读一遍 N 个 float, 每个元素做 R 次 FMA(2 flops)。
// 算术强度 AI = 2R flops / 4 bytes = R/2  (flop/byte)
static void kernel(int N, int R, const float* __restrict a, float* __restrict sink_out)
{
    float sink = 0.0f;
    #pragma omp parallel for schedule(static) reduction(+:sink)
    for (int i = 0; i < N; i++) {
        float v = a[i];
        for (int r = 0; r < R; r++)
            v = v * 1.0000001f + 0.5f;      // 2 flops, 依赖链: 每次都用上一次的 v
        sink += v;
    }
    *sink_out = sink;
}

// 同一 kernel, 但用 4 条互相独立的累加链 -> 暴露 ILP
static void kernel_ilp4(int N, int R, const float* __restrict a, float* __restrict sink_out)
{
    float sink = 0.0f;
    const int nq = N / 4;                    // 可被 4 整除的主体长度
    // 注意: OpenMP 要求规范的循环形式, 所以主体写成 [0, nq), 尾部单独处理
    #pragma omp parallel for schedule(static) reduction(+:sink)
    for (int q = 0; q < nq; q++) {
        const int i = 4 * q;
        float v0 = a[i], v1 = a[i+1], v2 = a[i+2], v3 = a[i+3];
        for (int r = 0; r < R; r++) {
            v0 = v0 * 1.0000001f + 0.5f;
            v1 = v1 * 1.0000001f + 0.5f;
            v2 = v2 * 1.0000001f + 0.5f;
            v3 = v3 * 1.0000001f + 0.5f;
        }
        sink += (v0 + v1) + (v2 + v3);
    }
    // 尾部余数 (N % 4 个元素): 串行处理, 不影响结论
    for (int i = 4 * nq; i < N; i++) {
        float v = a[i];
        for (int r = 0; r < R; r++) v = v * 1.0000001f + 0.5f;
        sink += v;
    }
    *sink_out = sink;
}

int main()
{
    const int N = 1 << 22;                      // 4M floats = 16 MB
    float* a = (float*)std::malloc((size_t)N * sizeof(float));
    for (int i = 0; i < N; i++) a[i] = 0.5f + 1e-6f * (float)i;

    std::printf("%4s %8s %14s %14s %10s\n",
                "R", "AI", "1-acc GFLOP/s", "4-acc GFLOP/s", "ratio");
    for (int R = 1; R <= 64; R *= 4) {
        float s1, s4; double b1 = 1e30, b4 = 1e30;
        for (int rep = 0; rep < 5; rep++) {                 // 取 5 次最小值
            double t = omp_get_wtime(); kernel(N, R, a, &s1);
            t = omp_get_wtime() - t; if (t < b1) b1 = t;
            t = omp_get_wtime(); kernel_ilp4(N, R, a, &s4);
            t = omp_get_wtime() - t; if (t < b4) b4 = t;
        }
        std::printf("%4d %8.2f %14.1f %14.1f %9.2fx\n",
                    R, R / 2.0, 2.0 * R * N / b1 / 1e9,
                    2.0 * R * N / b4 / 1e9, b1 / b4);
    }
    std::free(a);
    return 0;
}

• 【代码做什么？】
  1. kernel 对数组做一遍流式读（a[i] 各读一次），每个元素执行 R 次”乘加”（v * c + d 会被编译器融合成一条 FMA 指令、记 2 flops）。因为每个元素只读 4 字节，调大 R 就等价于调高算术强度 AI = 2R / 4 = R/2 (flop/byte)，这就把一个”AI 扫描（AI sweep）”实验做出来了——它正是 Roofline 模型的实验版。
  2. kernel_ilp4 是同一个计算，但同时维护 4 条互不相关的累加链 v0..v3。这样做的意义是：一条 FMA 依赖链只能”每 4 个周期出一结果”（FMA 延迟 ≈ 4 周期），而 FMA 流水线每周期能吞一条，所以单链最多只能用掉 1/4 的算力；4 条独立链才能把流水线填满。
  3. main 用 5 次最小值消除噪声，同时报告 GFLOP/s 与两条链的比值 ratio。
• 【并行机制与性能解说】
  • 硬件上如何并行：这里同时用了三种并行——#pragma omp parallel for 提供多核 TLP（16 线程）；每次 float 运算由编译器打包成 SIMD（-mavx2 下 8 宽）；v0..v3 四条独立链给超标量/乱序执行提供了 ILP。这正是本讲”四种并行形式叠加”的直接演示。注意 reduction(+:sink) 让每个线程先在私有副本上累加、最后再合并——避免了共享变量上的原子竞争（这是比”加锁”更好的做法）。
  • 工作如何分配：静态划分 schedule(static)，每个线程拿到一段连续区间。这里负载完全均匀（每个元素代价一致），所以静态划分是最优选择。
  • 共享数据如何处理：输入 a 只读、全区共享（只读数据无竞争）；sink 通过 reduction 变成每线程私有的部分和，只在并行区结束处合并一次。这是”避免共享可变状态”的标准范式。
  • Work / Span / 并行度：
    • Work（以 FMA 次数计）W = R·N；kernel_ilp4 的 Work 相同。
    • Span：kernel 的每个元素是 R 条 FMA 的串行链，所以 S = R + 一次装载；kernel_ilp4 的每个元素是 4 条长度 R 的链，S = R（4 条链并行）。
    • 并行度 W/S = N（两者都是）。
    • 但注意：并行度大 ≠ 算力用满。kernel 的并行度 N = 4M 远超机器的 lane 数，却仍然只跑到峰值的很小一部分——因为每个 lane 内部只有 1 路 ILP，而 FMA 延迟/吞吐比是 4。这说明第 4 节的”并行度 = Work/Span”必须细分到执行单元的粒度才有意义：N 路并行的粒度是元素，而填满 FMA 流水线需要的是每个 lane 内 ≥4 路 ILP。

  • 实测结果（本机，OMP_NUM_THREADS=16，-O3 -mavx2 -mfma，N = 4M，best of 5）：

    内层重复次数 R	1	4	16	64
    算术强度 AI (flop/byte)	0.5	2	8	32
    单累加链：GFLOP/s	31.9	72.3	73.8	42.7
    四独立累加链：GFLOP/s	101.9	189.9	178.0	116.0
    比值（ILP 收益）	3.19x	2.63x	2.41x	2.72x

    R = 1 那一列的对比最能说明问题：算术强度只有 0.5 flop/byte 的 kernel，即使开了 16 个线程、8 宽 SIMD，单累加链也只有 31.9 GFLOP/s，把 ILP 从 1 加到 4 立刻变成 101.9 GFLOP/s（3.19x）。这与”FMA 延迟 4 周期 / 吞吐 1 周期 → 单链最多用到 25% 流水线”的硬件事实定量吻合（理想值 4x，实测 2.4–3.2x 是受端口数、装载单元与内存系统共同限制的结果）。R 很大时 GFLOP/s 反而下降，是因为此时时间几乎全部花在纯计算上，频率/功耗与访存流的交互开始显现（并且这台机器是共享的，数字有噪声）。

  • 瓶颈分析：R 小时是内存带宽受限（GB/s 接近本机流式读取上限）；R 大时是执行端口/延迟受限。这个”先向上、后走平、再回落”的形状，就是第 4 节 Roofline 折线在真实机器上的样子。

3.4 示例四：ISPC 的 SPMD / gang 抽象（软件执行模型的另一种表达）

• 代码（来自 CS149 支撑材料；本环境未安装 ISPC 工具链，未做编译验证，编译命令按 ISPC 官方用法给出）：

// 文件 sinx.ispc
// 编译(需要 Intel SPMD Program Compiler, https://ispc.github.io):
//   ispc sinx.ispc --target=avx2-i32x8 -O3 -h sinx_ispc.h -o sinx_ispc.o
//   g++ -O3 main.cpp sinx_ispc.o -o sinx
export void ispc_sinx(uniform int N, uniform int terms,
                      uniform float* x, uniform float* result)
{
    // 假设 N % programCount == 0
    for (uniform int i = 0; i < N; i += programCount) {   // uniform: 整个 gang 一致
        int idx = i + programIndex;                       // varying: 每个实例不同
        float value = x[idx];
        float numer = x[idx] * x[idx] * x[idx];
        uniform int denom = 6;                            // 3!
        uniform int sign  = -1;
        for (uniform int j = 1; j <= terms; j++) {
            value += sign * numer / denom;
            numer *= x[idx] * x[idx];
            denom *= (2 * j + 2) * (2 * j + 3);
            sign  *= -1;
        }
        result[idx] = value;
    }
}

// 文件 main.cpp —— 顺序 C++ 代码, 只负责调用 ISPC 函数
#include "sinx_ispc.h"
#include <cstdio>
int main()
{
    const int N     = 1024;
    const int terms = 5;
    float* x      = new float[N];
    float* result = new float[N];
    for (int i = 0; i < N; i++) x[i] = -1.0f + 2.0f * (float)i / (float)(N - 1);

    ispc_sinx(N, terms, x, result);       // 调用 ISPC 函数 -> 启动一个 "gang"

    std::printf("result[0]=%f\n", result[0]);
    delete[] x; delete[] result;
    return 0;
}

• 【代码做什么？】
  1. export void ispc_sinx(...) 是 ISPC 的”可被 C/C++ 调用”的函数。调用它时，运行时启动一个 “gang”（一帮 programCount 个 program instance），所有实例并发执行同一份 ISPC 代码，每个实例有自己的局部变量副本，返回时所有实例一起结束——这就是 SPMD（single program, multiple data）。
  2. programCount 是 gang 里同时执行的实例数（uniform 值，所有实例相同）；programIndex 是当前实例在 gang 中的编号（varying 值，每个实例不同）。uniform 类型修饰符只是给编译器的优化提示（”这个变量的值所有实例都一样”），去掉它程序依然正确。
  3. 循环写成 for (uniform int i=0; i<N; i+=programCount) { int idx = i + programIndex; ... }，即交错划分：实例 k 处理元素 k, k+programCount, k+2·programCount, ...。因为 programCount 个实例在同一次迭代里访问的是连续地址，编译器可以为 x[idx] 生成一条 packed vector load。
  4. main.cpp 完全是顺序 C++，只把 ISPC 函数当普通函数调用——这正是该抽象的价值：把数据并行代码隔离在一个函数里。
• 【并行机制与性能解说】
  • 硬件上如何并行：抽象层是 SPMD（programCount 条逻辑指令流），实现层是 SIMD（一条向量指令）——ISPC 编译器把 gang 的语义编译成 AVX2/Neon 等向量指令，programCount 通常等于硬件的 SIMD 宽度（或它的一个小倍数）。如果写成 --target=avx2-i32x8，programCount 就是 8，8 个实例映射到 8 个 lane。条件控制流由编译器转换成掩码（讲义 2.6 节的机制，ISPC 手册称”分支是顺序执行两条路径并掩码”）。
  • 工作如何分配：交错划分（interleaved）→ packed load。若改成分块划分（count = N/programCount; start = programIndex*count; for(i<count) idx = start+i;），8 个实例访问的地址会相隔很远，编译器就必须生成 gather 指令（vgatherdps），而 gather 明显比连续向量的 load/store 更贵。同一份 SPMD 代码，仅因”实例到数据的映射方式”不同，就会产生数倍的访存开销差异——这是本讲”软件模型必须考虑硬件实现”的最好例证。

  • 共享数据如何处理：gang 内的局部变量是每实例私有的（varying），因此不需要同步。要跨实例通信必须用显式原语：reduce_add()（gang 内求和）、reduce_min()、broadcast(value, index)、rotate(value, offset) 等。一个经典的反面例子是用 foreach 直接累加：

    // 错误写法 1: sum 是 uniform, x[i] 是 varying -> 编译期类型错误
    uniform float sum = 0.0f;
    foreach (i = 0 ... N) { sum += x[i]; }      // ERROR: 不知道该把哪个实例的值写进 sum
    
    // 错误写法 2: sum 是 varying -> 返回值类型不匹配
    float sum = 0.0f;                            // 每个实例一份私有 sum
    foreach (i = 0 ... N) { sum += x[i]; }
    return sum;                                  // ERROR: 无法把一个 varying 值返回成 float
    
    // 正确写法: 每实例先算部分和, 再用归约原语合并
    uniform float sum;
    float partial = 0.0f;
    foreach (i = 0 ... N) { partial += x[i]; }
    sum = reduce_add(partial);                   // 跨实例通信, 返回 uniform 值
    

    reduce_add 在 SIMD 实现上等价于”把向量寄存器的 8 个 lane 横向相加”（通常是 log₂(8) = 3 次 shift+add），这就是”通信”在 SIMD 上的物理形式。讲义用 SPMD 里的这种跨实例操作说明了”用高阶原语做规约”的思想，它和 Lecture 8 数据并行（map/fold/scan）是同一件事。

  • Work / Span / 并行度：
    • Work = N × w（与示例二相同），w ≈ 55 条标量操作。
    • Span = w（一个元素的 Taylor 链）。
    • 并行度（抽象层）= N；但实现层的有效并行度 = gang 宽度 × 线程数：若只用 ISPC 而不使用它的 task 抽象，gang 只在一个 x86 核的一条线程里跑，有效并行度只有 programCount = 8。这是最容易犯的错——”写了 ISPC 就以为用了整台机器”。要吃到多核必须叠加 ISPC 的 task（或外层 OpenMP）。
  • 瓶颈：programCount 是编译期固定的（如 avx2-i32x8 下恒为 8），因此 N % programCount != 0 的边界要么被假设整除（示例注释里的”assume N % programCount = 0”），要么就需要掩码处理尾部——尾部处理是 SIMD 代码里最常见的 bug 源与性能损失源。

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

4.1 Work–Span（工作量–关键路径）模型

定义：把并行程序看成一个 DAG。

• Work（W）：所有操作的总数——用 1 个处理器执行所需的时间（也就是串行时间 T₁）。
• Span（S，也叫 critical path / depth）：DAG 中最长的依赖链——用无限多处理器执行所需的时间（T∞）。
• 并行度（parallelism）：W / S，即”平均可以同时进行的操作数”。它是程序固有属性，与机器无关。

两个界（CS149 的 scan 例子明确给出了这套记号）：

• 用 P 个处理器，T_P ≥ max(W/P, S)，因此 T_P = O(W/P + S)。
• 加速比 S(P) = T₁/T_P ≤ min(P, W/S)。当 P > W/S 时再加处理器毫无收益——这直接对应讲义”512 个独立工作才能跑满虚构芯片”的结论。
• 效率 E = S(P)/P ≤ min(1, (W/S)/P)。

例（示例二的 sinx）：W ≈ 55N，S ≈ 55，并行度 W/S = N。对 N = 1.6e7，W/S = 1.67e7。哪怕机器有 10 万个硬件 lane，也远小于 1.67e7，所以这个程序永远不会因”并行度不够”而受限。

反例（关键路径很长的算法）：并行 exclusive scan 的朴素版本（Hillis–Steele）在 CS149 支撑材料里给出的分析是 Work = O(N log N)、Span = O(log N)——Work 比串行算法的 O(N) 更差（”Inefficient compared to sequential algorithm!”），但 Span 极短。工作高效的版本（up-sweep + down-sweep）把 Work 降到 O(N)、Span 仍是 O(log N)，代价是常数更大、SIMD 利用率更低（CS149 在 CUDA warp scan 一节明确说：work-efficient 版本在 32-wide SIMD 上需要两倍以上的指令数，所以实践中反而更慢）。这给出一个重要的工程判断：选择算法时要在”Work 小”和”Span 小”之间权衡，而 SIMD 的利用率可以让”Work 更大但更规整”的算法胜出。

4.2 Amdahl 定律

                       1
  S(P) = ───────────────────────────        f = 不可并行(串行)部分的比例
          f + (1 - f) / P                   P = 处理器数

  上限:  lim  S(P) = 1 / f
         P→∞

• 数值算例：设 f = 5%（并行区的 95% 可完美并行），则 P→∞ 时 S → 20x。 | P | 1 | 2 | 4 | 8 | 16 | 32 | ∞ | |—|—|—|—|—|—|—|—| | S(P)（f=0.05） | 1.00 | 1.90 | 3.48 | 5.93 | 9.14 | 12.55 | 20.0 | | S(P)（f=0.01） | 1.00 | 1.98 | 3.88 | 7.48 | 13.91 | 24.24 | 100.0 | | S(P)（f=0） | 1.00 | 2.00 | 4.00 | 8.00 | 16.00 | 32.00 | ∞ |

  解读：f = 5% 时，16 核只能拿到 9.14x（57% 的效率），并且再加到 32 核只多 3.4x。这解释了为什么并行程序优化中”消灭串行瓶颈”（I/O、初始化、全局同步、归约）往往比”再买几个核”更有效。

• 讲义版本的 Amdahl（多核的收益 vs 单核变慢）：复杂核速度 1.0，简单核 0.75（讲义取的虚构系数）。
  • 有并行：T(2 核) = 0.75/2 = 0.375，相对原来 1.0 的加速比 = 2.67x（讲义写作”潜力 2 × 0.75 = 1.5”，即吞吐/单位时间的工作量提升 1.5 倍）。
  • 无并行：T = 0.75，加速比 0.75x，即变慢了 33%。
  • 结论：多核时代”不提并行”是负优化。
• Amdahl 的补充（Gustafson）：Amdahl 假设问题规模固定，因此串行部分占比不随 P 变；而实际中人们常常同时扩大问题规模，此时可扩展性会好得多。讲义的思想实验（向量乘、sinx）都是”数组越大越有利”的例子——大数组摊薄了固定开销。

4.3 延迟隐藏需要多少线程？

这是本讲最实用的一组定量公式。设：

• 一条线程在做完 k 条可执行指令后必须等待一次访存，等待期 L 个周期；
• 核每个周期最多执行 1 条指令（吞吐 1/cycle）。

则单线程利用率 u₁ = k / (k + L)，要跑满核所需的线程数 P* = ceil((k + L)/k) = ceil(1 + L/k)。

数值算例（CS149 的原始算例）：

结论两条（CS149 明确写出的 takeaway）：

1. 多线程并没有改变访存的延迟，它只是让延迟不再导致处理器利用率下降（”the latency of the memory operation is not changed by multi-threading, it just no longer causes reduced processor load”）。
2. 每次访存之间的算术越多，隐藏延迟所需的线程就越少（P* = 1 + L/k 随 k 增大而减小）。这正是”提高算术强度”在延迟侧的收益。

与现代机器对照：DRAM 延迟约 248 个周期（Kaby Lake @4 GHz）。若每 10 条指令一次访存，P* = ceil(1 + 248/10) = 26 个线程才能跑满一个核——这直接解释了为什么 GPU 每个 SM 要挂 48–64 个 warp（GTX 480 是 48，V100 是 64），也解释了为什么 CPU 的 2-way SMT 只能拿到有限的收益（2 个线程远远不够填满长延迟的等待）。反过来，如果代码把数据全部放在寄存器里做大量复用（k 很大），一个线程就够了。

4.4 带宽受限的稳态分析

设核每时钟执行 1 条数学指令；内存每时钟提供 B 字节；程序每 k 条数学指令需要一次 m 字节的访存。

稳态下（延迟已被充分隐藏）：

  内存完成一次访存需要的时钟数  =  m / B
  这段时间内核能做的数学指令数  =  k
  => 核的指令吞吐 = k / (m/B) = k·B/m   (条/时钟)
  => ALU 利用率  = (k·B/m) / (每时钟指令数) = k·B/(m·1)

数值算例（CS149 multicore2 的原例）：B = 8 字节/时钟，m = 64 字节（一次 load），k = 3 条数学指令：

  一次 load 需要 64/8 = 8 个时钟
  这 8 个时钟里核只能做 3 条数学指令
  => 吞吐 = 3/8 = 0.375 条/时钟   =>  ALU 利用率 = 37.5%
  内存利用率 = 100%(它已经在满负荷送数据, 不可能更快)

关键洞见：稳态利用率 k·B/m 只依赖”指令流里的访存密度”和”内存吞吐率”，与内存延迟、未完成请求数无关。延迟只决定”需要多少并发请求才能把带宽填满”（Little 定律：并发请求数 ≈ 带宽 × 延迟）。用讲义虚构芯片的数字验证一下：带宽 25 GB/s、延迟 100 周期 @ 3 GHz = 33 ns，则 需要的并发请求数 ≈ 25e9 × 33e-9 ≈ 833 字节在途——这就是为什么”延迟隐藏”需要成百上千个独立的访存（对应 2.11 节”512 份独立工作”的量级）。

数值算例（带宽下限）：

• 一个 256 MB 的数组，只用 20 GB/s 的带宽做一次遍历（只读），至少需要 256 MB / 20 GB/s = 12.8 ms。
• 若是 sinx 这类”读一遍写一遍”的 kernel，N = 6.4e7 个 float（256 MB 输入 + 256 MB 输出 = 512 MB），至少需要 512 MB / 20 GB/s = 25.6 ms。
• 若机器只有 16 核 × 8 宽 SIMD = 128 lane @3 GHz，则单次遍历 6.4e7 个元素的算力时间为 6.4e7 × 5.4 向量指令/元素 / (16 核 × 3e9) ≈ 7.2 ms。7.2 ms < 25.6 ms ⇒ 这个 kernel 是带宽受限的，加速比上限被钉在 25.6/7.2 ≈ 3.6x（相对 1 核的算力时间），不管你有 16 个核还是 128 个核。

数据的现实感（讲义 slide 44 的”真实世界例子”，原样记录其算式）：任务是把数据从匹兹堡的数据中心搬到纽约（两地相距 370 英里 ≈ 6.5 小时车程）。讲义给出两条算式——1e+11 B / 25 mb/s = 1.1 hours（该项标注为 “100 PB”，算式中实际使用的是 1e11 字节）与 1e+18 B / 25 mb/s = 1,267 years（1 EB，即 1e18 字节）。两条算式内部是自洽的：数据量相差 1e7 倍，所需时间也正好相差 1e7 倍（1.1 小时 vs 约 1267 年）。结论是：在极大规模下，”用网络搬数据”会输给”用卡车搬存储”——这正是 AWS Snowmobile 这类服务存在的理由。这个类比在计算机内部同样成立：带宽是系统中真正稀缺的资源，”减少数据移动”往往比”提高算力”更有效（讲义 slide 68 的三条优化准则正由此而来），也与 CS149 支撑材料里”数据移动的能耗”（从 LPDDR 读 64 位 ≈ 1200 pJ，而一次浮点运算 ≈ 20 pJ）互相印证。

4.5 算术强度与 Roofline 模型（核心数值算例）

模型：给定机器的峰值算力 P_peak（FLOP/s）与内存带宽 BW（Byte/s），一个算术强度为 AI（FLOP/Byte）的 kernel 的可达性能为

      P_achieved = min( P_peak ,  BW × AI )

  两个区域:
    AI < AI*   => 带宽受限 (memory bound)   P = BW × AI
    AI > AI*   => 计算受限 (compute bound)  P = P_peak
  拐点(机器平衡点):  AI* = P_peak / BW   (FLOP/Byte)

假设参数（取自讲义 slide 61 的”虚构多核芯片” + slide 47/65 的内存带宽）：

峰值算力：

  P_peak = 16 核 × 8 lane/核 × 2 FLOP/(lane·clk, 即 FMA) × 3.0e9 clk/s
         = 16 × 8 × 2 × 3.0e9 = 7.68e11 FLOP/s = 768 GFLOPS

拐点（机器平衡点）：

  AI* = P_peak / BW = 768e9 / 25e9 = 30.7 FLOP/Byte

数值算例表（同一台机器上不同 kernel 的可达性能）：

解读：

1. 逐元素向量运算（这正是讲义 slide 66 的思想实验）的 AI 只有 0.083，比拐点低了 370 倍，所以它只能用到 0.27% 的峰值算力。这不是”编译器不够聪明”，而是物理约束：要跑满 768 GFLOPS 需要 768e9 / 0.083 ≈ 9.2 TB/s 的带宽，而机器只有 25 GB/s——缺 370 倍。（讲义对 GTX 480 做的正是同一个计算：需要约 6.4 TB/s，实有 177 GB/s。）
2. 分块（blocking/tiling）是提高 AI 的标准手段：把矩阵乘的块大小从 64 提到 123，AI 从 16 提到 30.7，跨过拐点，性能从 52% 跳到 100%。注意 T* = 4·AI* = 123 这个结论——它给了一个非常具体的”缓存块该切多大”的目标。
3. 为什么 GPU 比多核 CPU 快 7 倍（讲义 slide 66 的数字）：两者的逐元素乘 kernel 都是带宽受限的，所以性能之比 ≈ 带宽之比：177 GB/s ÷ 25 GB/s ≈ 7.1x。把讲义里的两个数字按同一公式算一遍即可复现（见 2.14 节的推导）。这是”带宽是唯一瓶颈”这一论断最有说服力的定量证据。
4. 反过来，低带宽的并行机器会被高带宽的机器在”低 AI”负载上碾压，即使前者的峰值算力更高——这是异构计算（Lecture 20）与存储层次设计的核心动机。

4.6 第 4 节算例汇总

5. 关键要点

1. 现代处理器的算力来自四种并行执行形式的叠加，而不是单条指令流变快：多核（Idea #1，线程级并行，软件创建线程） + SIMD（Idea #2，一条指令广播给多个 ALU，把控制开销摊薄） + 硬件多线程（Idea #3，用别的线程的指令填满访存等待） + 超标量/ILP（同一指令流内的独立指令，硬件自动发现）。其中多核与超标量不需要指令流一致性，而 SIMD（无论显式还是隐式）必须有——这是后面所有 SIMD/GPU 代码优化的根本约束。

2. “够多、够齐、有余量”是跑满吞吐型机器的三个必要条件（CS149 的三条总结）：(a) 有足够多的并行工作去喂满所有执行单元（跨核、跨 lane）；(b) 成组的并行工作要走同一条指令序列，否则 SIMD 会被掩码浪费（最坏 1/8，GPU 上 1/32）；(c) 独立工作数必须多于 ALU 数，否则没有余量去隐藏内存停顿。定量版本就是：”16 核 × 8 lane × 4 线程 = 需要 512 份独立工作”。

3. 延迟与带宽是两个性质完全不同的瓶颈，必须分开诊断：延迟（100 周期量级）可以被缓存降低成本、预取提前搬数据、硬件多线程藏起来；带宽（20 GB/s 量级）无法被任何延迟隐藏手段拯救，只能靠”少访问”——同线程复用（时间局部性）、跨线程共享、以及多做算术（”the math is free”）。诊断口诀：加线程后性能不再涨、内存利用率已达 100% ⇒ 你撞上的是带宽墙，不是延迟墙。

4. 算术强度（arithmetic intensity = 数学运算数 / 数据访问字节数）是”能不能高效利用现代机器”的单一定量指标，它的形式化就是 Roofline：可达性能 = min(峰值算力, 带宽 × 算术强度)。逐元素数组运算的 AI 低到 0.083，在 25 GB/s 的机器上只能拿到峰值的不到 1%；要跨过拐点（本讲虚构芯片的 AI* = 30.7），必须靠分块/复用把每个字节的运算量提高一到两个数量级。这也是为什么”GPU 比同代多核 CPU 快 7 倍”在低 AI 负载上可以精确地由 177/25 ≈ 7.1 解释。

5. 性能的上限要么由并行度决定，要么由资源带宽决定，要先用模型算清楚是哪一个：Work/Span 给出并行度上限（S(P) ≤ min(P, W/S)），Amdahl 给出串行部分的封顶（S(∞) = 1/f），Roofline 给出带宽/算力的封顶。在写优化之前先把这三个界算一遍——本讲里 sinx 的并行度有 4 个数量级余量，所以它的瓶颈一定不在并行度，而在内存系统与除法器。

6. 常见陷阱与注意事项

• 陷阱 1：把”指令流一致性（instruction stream coherence）”与”缓存一致性（cache coherence）”混为一谈。 讲义明确提醒二者无关。前者说的是”同一组被同时处理的数据是否走同一条指令序列”（影响 SIMD 效率）；后者说的是”多个核的缓存副本如何保持一致”（Lecture 10–12 的主题）。英文都叫 coherence，但它们没有任何关系，理解错会导致完全错误的优化方向。

• 陷阱 2：以为”多线程能解决一切访存问题”。 硬件多线程只隐藏延迟，不改变延迟，也不增加带宽。它的代价是实打实的：需要额外的片上存储保存执行上下文；延长任何单一线程的完成时间（吞吐导向的取舍）；需要程序里有比 ALU 数更多的独立工作；更多线程 → 更大的工作集 → 每线程分到的缓存更小 → 可能更频繁访问内存。当程序已经带宽受限时，加线程会毫无收益（讲义原文：No amount of latency hiding helps this）。

• 陷阱 3：并行化 ≠ 向量化 ≠ 用满机器，三者必须分别验证。 本笔记 3.2 节的实测是一个具体教训：同一条循环，串行版本被 GCC 自动向量化（22.7 ms），放进 #pragma omp parallel for 后该循环没有被向量化（119.9 ms，1 线程），于是”并行版本”在 1 线程时比串行版慢 5.3 倍，表面加速比只有 0.18x。两个后果：(a) 加速比必须与”同代码质量”的基线比，否则结论荒谬；(b) 必须主动检查向量化——用 -fopt-info-vec/-Rpass=loop-vectorize 看报告，或反汇编确认 vmulps/vfmadd 是否真的生成（讲义对 explicit SIMD 的定义就是”能在二进制里看到向量指令”）。

• 陷阱 4：忽略数据依赖性而写出不确定结果。 数据并行的合法性前提是”迭代之间无依赖、不写同一位置”。CS149 的例子极具代表性：absolute_repeat（每个迭代只写 y[2i]、y[2i+1]）是对的；而 shift_negative（当 x[i]<0 时写 y[i-1]）输出未定义，因为多个迭代可能写同一位置。判断标准是”写集合是否互不相交、且读集合不被其他迭代写”——sinx 之所以可以任意并行，正是因为第 i 个迭代只碰 x[i] 与 result[i]。

• 陷阱 5：忽略内存带宽与伪共享（false sharing）。 两个独立的坑：(a) 带宽——把串行代码改成并行后，如果每个线程都在流式扫描大数组，加速比会在”内存带宽饱和”处停止增长，此时继续加线程只会更慢（本笔记 4.4 节的 k·B/m 公式能预告这一点）。(b) 伪共享——即使两个线程写的是不同变量，只要这两个变量落在同一个 cache line 上，缓存一致性协议就会让该 line 在两个核之间反复弹跳（cache line ping-pong），产生几十倍的性能损失。常见触发形态是”每个线程往一个全局数组的相邻下标写累加值”——正确写法是把每线程的部分和放在各自独立的 cache line 上（padding 到 64 字节），或用 reduction 让编译器处理（示例三就是这么做的）。

• 陷阱 6：把”平均情况”当成”最坏情况”，尤其在有分支的 SIMD 代码里。 SIMD 的代价不是”分支”，而是”同一批数据的控制流不一致“：if/else 会被顺序执行两条路径并掩码，最坏只有 1/8（GPU 上 1/32）的 ALU 做有用工作。因此写向量化代码时应尽量：(a) 用无分支（branchless）写法（select/条件移动而非跳转）；(b) 让数据按类别排序或分组后再处理，使同批数据的路径一致；(c) 记住分支结束后会立刻恢复全宽执行——所以”少量、短小的发散”是可以接受的，真正致命的是”长分支体内的高发散”。

7. 思考题（带答案）

思考题 1

讲义用 sinx 演示了一个从”1 个复杂核”到”2 个简单核”的转变：设复杂核跑一条指令流的速度是 1.0，而简单核只有 0.75。现在你有一段完全没有并行的代码，想让它在这台新机器上更快。请回答：

(a) 如果你什么都不做，直接在新机器上运行原来的串行程序，性能是原来的多少？ (b) 如果你把它改成 2 个线程、每个线程处理一半的数据，理论加速比是多少（相对于原来的复杂单核机器）？请分别按讲义的口径（吞吐/单位时间完成的工作量）和标准加速比口径（T₁/T₂）计算。 (c) 要把这个 2 核机器的算力完全用上，程序必须满足什么硬性条件？如果数组只有 10 个元素、每个元素的计算量很小，会发生什么？

【答案】

(a) 0.75x，即比原来慢 25%。原因很直接：串行程序在 2 核机器上只会用到 1 个核（讲义原话：这个程序用 gcc 编译后会”run as one thread on one of the processor cores”），而每个简单核跑单条指令流只有复杂核的 0.75 倍速。多核时代”不提并行”是负优化——这是讲义 slide 15 用大字标出的结论。

(b) 两个口径的答案不同，要分清：

• 讲义口径（单位时间能完成的工作量，即吞吐）：2 个核各自以 0.75 的速度干活，所以 2 × 0.75 = 1.5，即吞吐提升 1.5 倍（相对于 1 个复杂核）。
• 标准加速比口径（S = T₁/T₂，其中 T₁ 是同一台新机器上跑串行的时间）：T₁ = 0.75（用 1 个简单核），T₂ = 0.75/2 = 0.375（2 个核并行），所以 S = 0.75/0.375 = 2.0x。这里的 2.0x 是”用满 2 个核”的完美结果（Amdahl 中 f = 0 的情形）。
• 注意两者的区别：1.5 是”新旧机器之间”的比较，2.0 是”新机器上串行 vs 并行”的比较。教科书里说”2 核理论加速比 2.0”，隐含的是跟本机的串行版本比；而”投资这一代新机器划不划算”要看 1.5。混用这两个口径是性能报告中极常见的错误（本笔记 3.2 节的实测表就踩到了”基线选错”这个坑：因为串行基线被自动向量化而快了 5 倍，所以看起来”加速比只有 0.18x”）。

(c) 硬性条件是要有足够多的、彼此独立的工作。 具体到本讲，一台机器跑满所需独立工作数是各层并行度的乘积：如果这台机器是”2 核 × 每核 8 lane SIMD × 每核 2 个硬件线程”，则需要 2 × 8 × 2 = 32 份独立工作；讲义的虚构芯片是 16 × 8 × 4 = 512 份。数组只有 10 个元素时，连”每核一个线程”都喂不饱（10 < 32），更不用说 SIMD 的 8 个 lane 和硬件多线程的 2 个上下文——结果是绝大部分 ALU 空转，实际性能可能还不如原来的单复杂核（因为简单核本身慢 0.75 倍，而且 pthread_create/join 的开销相对于 10 个元素的计算量是巨大的）。教训：并行化有一个最小问题规模的门槛（N 必须远大于”总 lane 数 × 每 lane 需要的独立迭代数”），这也是 Lecture 1 中”粒度（granularity）”概念的来源。

思考题 2

某 kernel 在一台机器上执行：机器有 8 个核，每核 8 宽 SIMD，不支持 FMA（一次只能 1 flop），主频 2.5 GHz，内存带宽 20 GB/s。kernel 对长度为 N = 1e8 的 float 数组做：out[i] = a[i] * a[i] + 3.0f（读 4 字节、写 4 字节）。

请回答： (a) 这个 kernel 的算术强度 AI 是多少？ (b) 机器的峰值算力是多少 GFLOPS？机器平衡点 AI* 是多少？ (c) 这个 kernel 的理论可达性能是多少 GFLOPS？是计算受限还是带宽受限？ (d) 它的执行时间下限是多少毫秒？这个下限由什么决定？ (e) 为了让这个 kernel 变成计算受限，最直接的手段是什么？请给出一个量化目标。

【答案】

(a) AI = 2 flops / 8 bytes = 0.25 FLOP/Byte。 推导：每个元素需要 1 次乘法（a[i]*a[i]）和 1 次加法（+3.0f），共 2 flops；内存流量是读 4 字节 + 写 4 字节 = 8 字节。（若编译器把 a*a+3 融合成一条 FMA，指令数会减半，但flops 数与字节数不变，所以 AI 不变。）

(b) 峰值算力 P_peak = 8 核 × 8 lane × 1 flop/(lane·clk) × 2.5e9 clk/s = 1.6e11 FLOP/s = 160 GFLOPS。 机器平衡点 AI* = P_peak / BW = 160e9 / 20e9 = 8 FLOP/Byte。

(c) P_achieved = min(160, 20 × 0.25) = min(160, 5) = **5 GFLOPS**。因为 AI = 0.25 < AI* = 8，所以它是带宽受限（memory bound），只用到 5/160 = 3.1% 的峰值算力。注意这个 3% 与讲义中对 GTX 480 估计的 “~3% efficiency” 是同一个数量级的现象——低算术强度的逐元素运算是普适的带宽杀手，与机器是 CPU 还是 GPU 无关。

(d) 流量 = 8 字节/元素 × 1e8 元素 = 8e8 字节 = 800 MB。t ≥ 800 MB / 20 GB/s = 0.04 s = **40 ms**。这个下限完全由内存带宽决定，与核数、SIMD 宽度、主频无关——把核数从 8 加到 80 也不会让 40 ms 变短。（顺带验证：算力时间是 2e8 flop / 160e9 = 1.25 ms，远小于 40 ms，所以计算确实不是瓶颈。）

(e) 最直接的手段是提高算术强度：让每个从内存取来的字节被更多地复用（而不是想办法把计算做得更快）。量化目标：需要 AI ≥ AI* = 8 FLOP/Byte。由于内存流量 = 读 4 字节 + 写 4 字节（写通常不可复用），最现实的做法是让每个读入的元素参与更多运算——例如把 kernel 改成 out[i] = f^k(a[i]) 这种”每个输入元素做 k 次运算”的形式，其中每次运算是 1 flop，则 AI = (1 + k)/8，要 ≥ 8 需要 k ≥ 63。这就是循环融合/计算重用（compute reuse）：把 64 个独立的逐元素 kernel（a*a+3、a*a-2、…）合并成一个循环，每个元素只读一次内存、却在寄存器里做 128 次运算，AI 从 0.25 提到 16，超过拐点，性能从 5 GFLOPS 升到 160 GFLOPS（32 倍）。另一个方向是做分块（blocking）让数据在缓存中被多次使用（如 4.5 节的分块矩阵乘，T* = 4·AI* = 32）。注意优化的方向不是”更快的乘法”，而是”更少的访存”——这正是讲义 “do more arithmetic: it’s free” 的确切含义。

思考题 3

讲义最后留下一个思考题：“你写了一个 C 程序，创建了 2 个 pthread，程序运行在一台’2 核、每核 2 个执行上下文、每时钟最多 2 条指令（其中一条是 8 宽 SIMD）’的处理器上。谁负责把你的 pthread 映射到处理器的线程执行上下文上？如果你有 5 个 pthread 呢？” 请回答这三个问题，并解释”软件线程数”与”硬件执行上下文数”之间的关系。

【答案】

问题 1：谁负责映射？答案是操作系统（the operating system）。 讲义对这个问题的回答是明确的。程序员写的 pthread_create 只是向操作系统请求”给我一个可运行的线程实体”；操作系统调度器（scheduler）决定这个线程何时、在哪个硬件执行上下文上运行。处理器本身只提供”若干个能保存 PC + 寄存器的执行上下文槽位”，并在每时钟从这些槽位中挑选指令执行（这部分由硬件自主决定，不经操作系统）。因此存在两级调度：

• OS 级：软件线程（可能成百上千个）→ 硬件执行上下文（本机只有 4 个），按时间片轮转，粒度为毫秒级，切换成本高；
• 硬件级：硬件执行上下文（4 个）→ ALU（每时钟 1–2 条指令），每个时钟都重新挑选，零软件开销（这正是 2.10 节”多线程隐藏停顿”能奏效的原因）。

问题 2：只有 2 个 pthread、却有 4 个执行上下文，怎么分配？ 合理答案是把两个线程放到不同核——即在 4 个上下文 {核0-ctx0, 核0-ctx1, 核1-ctx0, 核1-ctx1} 中，把线程 A 放到 核0-ctx0、线程 B 放到 核1-ctx0。原因是这样能真正用到 2 个核的算力（TLP）。反面做法是把两个线程都放在同一个核的两个上下文上：那样只用了 1 个核，虽然可以靠硬件多线程互相隐藏访存延迟（在带宽未饱和时利用率可能还不错），但算力上限被砍了一半。一般原则：先按”核”分散、再考虑”同核内多个上下文”（Linux 的调度器正是这么做的，它会尽量让线程优先占据空闲的物理核）。这也解释了为什么”软件线程数 = 硬件线程数”通常不是最优配置——SMT 的收益来自”两个线程的停顿恰好互补”，而当两个线程都是纯计算密集型、ILP 又都很高时，SMT 几乎没有收益，反而共享 L1/L2 造成相互干扰。

问题 3：如果是 5 个 pthread 呢？ 这时软件线程数（5）> 硬件执行上下文数（4），操作系统必须分时复用：4 个上下文先各跑一个线程，第 5 个线程等某个上下文空出来（或被抢占）后再运行。映射策略由 OS 决定，程序员无法直接控制（只能通过亲和性 affinity 提示）。后果是：

1. 存在”可运行但未被执行的线程”——这正是 2.10 节甘特图里的状态：”During this time, this thread is runnable, but it is not being executed by the processor (the core is running some other thread).” 它在观感上等价于额外的停顿，但它与访存停顿有本质区别：访存停顿可以用更多的独立工作填满，而”线程多于上下文”造成的等待只能靠减少线程数或增大每线程的并行度来缓解。
2. 超订（oversubscription）通常有害：5 个计算密集型线程抢 4 个上下文，会引入上下文切换开销与缓存抖动，总吞吐通常低于恰好 4 个线程。
3. 正确的做法是让”软件线程数 ≈ 硬件执行上下文数”，然后在每个线程内部用 SIMD + ILP（多累加器）来提高每时钟的指令数——也就是本笔记 3.3 节实测的那个实验：在 16 线程之外，把 1 条累加链改成 4 条，吞吐就提高 2.4–3.2 倍，而这个提升不需要任何额外的软件线程，只需要给硬件提供更多 ILP。这就是讲义”要跑满 512 份独立工作”这一结论的实践含义：独立工作的来源不只是”更多线程”，也可以是”同一线程内更多的独立指令”。