课程全称：15-418/15-618 Parallel Computer Architecture and Programming 学期：Fall 2026（课程主页 https://www.cs.cmu.edu/~418/，日程表 https://www.cs.cmu.edu/~418/schedule.html） 授课：Brian Railing、Dimitrios Skarlatos（课程由 Kayvon Fatahalian 创建） 上课时间/地点：MWF 09:30–10:50am, Baker Hall (BH) A51 学分/考核：12 units；两次当堂闭卷考试（Exam 1 = 9/25，覆盖 Lecture 1–13；Exam 2 = 11/2，覆盖 Lecture 14–24，不含 guest lecture）+ 4 次编程作业（权重不同）+ 4 次书面作业（同伴互评）+ 期末项目 先修：15-213（严格先修）；需要扎实的 C/C++ 能力；18-447 有帮助但非必需

本笔记基于该课程网站上公开可访问的讲义 PDF、日程表、作业与项目页面整理而成，并为每一讲补充了硬件架构分析、可运行代码示例与定量性能模型。

目录

第一部分：课程概览

• 1. 课程定位与知识地图
• 2. 课程材料获取情况（公开性说明）
• 3. 完整的 Fall 2026 课程日程
• 4. 作业、考试与项目
• 5. 如何使用本笔记

第二部分：逐讲学习笔记（26 讲）

• Lecture 1: Why Parallelism? Why Efficiency?
• Lecture 2: Out-of-order Processor & Pipeline
• Lecture 3: A Modern Multi-Core Processor
• Lecture 4: Parallel Programming Models
• Lecture 5: GPU Architecture and CUDA Programming
• Lecture 6: GPU Architecture and CUDA Programming (continued)
• Lecture 7: Parallel Programming Basics
• Lecture 8: Performance Optimization I: Work Distribution and Scheduling
• Lecture 9: Performance Optimization II: Locality, Communication, Contention
• Lecture 10: Interconnection Networks
• Lecture 11: Snooping-Based Cache Coherence
• Lecture 12: Directory-Based Cache Coherence
• Lecture 13: Snooping-Based Multiprocessor Design
• Lecture 14: Performance Analysis / Profiling
• Lecture 15: Implementing Synchronization
• Lecture 16: Fine-Grained Synchronization, Lock-Free Programming
• Lecture 17: Transactional Memory
• Lecture 18: Heterogeneous Parallelism, Hardware Specialization
• Lecture 19: Virtual Memory
• Lecture 20: Guest Lecture (无公开材料)
• Lecture 21: Memory Consistency
• Lecture 22: Parallel Deep Learning (Data Parallelism)
• Lecture 23: Parallel Deep Learning (Model and Pipeline Parallelism)
• Lecture 24: AI in System Design
• Lecture 25: Under the Hood: Message Passing Implementation
• Lecture 26: MPI, OpenMP, Cilk Implementation
• Lecture 27: Deep Neural Networks and ML Accelerators（归档主题）
• 附录 A：Exam 1 复习笔记（Lecture 1–13）

第三部分：速查表与附录

• 速查表 A：并行编程模型速查表
• 速查表 B：性能公式速查表
• 速查表 C：硬件架构参数速查表
• 速查表 D：优化技巧速查表
• 速查表 E：同步原语与一致性协议速查表
• 速查表 F：常见性能陷阱速查表
• 附录 B：课程资源清单

第一部分：课程概览

1. 课程定位与知识地图

1.1 这门课要解决什么问题

CMU 15-418/618 的课程自述写得非常直白：

“From smart phones, to multi-core CPUs and GPUs, to the world’s largest supercomputers, parallel processing is ubiquitous in modern computing. The goal of this course is to provide a deep understanding of the fundamental principles and engineering trade-offs involved in designing modern parallel computing systems as well as to teach parallel programming techniques necessary to effectively utilize these machines. Because writing good parallel programs requires an understanding of key machine performance characteristics, this course will cover hardware design and how that affects software design.”

翻译过来，这门课有三个不可分割的目标：

1. 理解并行硬件：CPU 流水线与乱序执行、多核、SIMD 向量单元、GPU 的 SM/warp 结构、互连网络、缓存一致性与内存一致性模型、虚拟内存与 TLB、专用加速器。
2. 掌握并行编程：fork-join、SPMD、数据并行、共享地址空间 + 锁、消息传递（MPI）、CUDA、OpenMP、ISPC、pthreads、Cilk 风格工作窃取运行时。
3. 建立性能工程方法论：work-span 模型、Amdahl 定律、算术强度与 Roofline、延迟与带宽分解、负载均衡、通信-计算重叠、伪共享与竞争诊断。

1.2 知识地图

                     ┌──────────────────────────────────────────────┐
                     │          为什么需要并行？为什么效率重要？        │
                     │   Lecture 1：功率墙 + 免费午餐结束              │
                     └───────────────────┬──────────────────────────┘
                                         │
        ┌────────────────────────────────┼────────────────────────────────┐
        ▼                                ▼                                ▼
┌──────────────────┐          ┌──────────────────┐          ┌──────────────────┐
│  硬件执行层面      │          │  编程抽象层面      │          │  性能工程层面      │
├──────────────────┤          ├──────────────────┤          ├──────────────────┤
│ L2  ILP/流水线/OoO│          │ L4  编程模型       │          │ L7  并行编程基础    │
│ L3  多核+SIMD     │          │ L5-6 CUDA/GPU      │          │ L8  工作分配/调度   │
│ L10 互连网络      │          │ L15 同步实现       │          │ L9  局部性/通信/竞争│
│ L11 监听一致性    │          │ L16 细粒度/无锁    │          │ L14 剖析与测量      │
│ L12 目录一致性    │          │ L17 事务内存       │          │ L22-23 并行深度学习 │
│ L13 监听实现      │          │ L19 虚拟内存       │          │ L24 AI in System   │
│ L18 异构/专用化   │          │ L21 内存一致性     │          │ L25-27 运行时/加速器│
└────────┬─────────┘          └────────┬─────────┘          └────────┬─────────┘
         │                             │                             │
         └─────────────────────────────┼─────────────────────────────┘
                                       ▼
                    ┌──────────────────────────────────────┐
                    │   统一的分析语言（贯穿全课的"三把尺子"）  │
                    │  ① Work / Span / 并行度  → 可扩展性    │
                    │  ② Amdahl 定律           → 加速比上限  │
                    │  ③ 算术强度 + Roofline   → 瓶颈类型    │
                    └──────────────────────────────────────┘

1.3 三条学习主线

主线一：从硬件到软件的单向约束链。 硬件的物理约束（功耗、延迟、带宽）决定了抽象的形状。例如：

• 光子传输速度 + 功耗墙 ⇒ 多核而非单核更宽 ⇒ 需要并行软件 ⇒ 需要同步 ⇒ 需要一致性协议。
• DRAM 延迟（约 200+ 周期）远高于计算 ⇒ 必须用 cache 隐藏 ⇒ cache 私有化破坏共享内存语义 ⇒ 必须有缓存一致性（Lecture 11–13）。
• 带宽增长远慢于算力增长 ⇒ 几乎所有有趣的程序都是带宽受限 ⇒ 必须讲算术强度与 Roofline（Lecture 3、8、9、14）。

主线二：抽象的代价。 每一层抽象（共享地址空间、虚拟内存、事务内存、垃圾回收、DSL）都在换取可编程性的同时引入性能不确定性。课程的反复主题是”抽象距离（abstraction distance）”——离硬件太远则性能不可预测，太近则不可移植。

主线三：一切都是权衡。 静态 vs 动态分配、粗粒度 vs 细粒度同步、失效 vs 更新协议、SMP vs NUMA、带宽换延迟、空间换时间。笔记中每一讲都会显式标出”关键权衡”。

1.4 与其他系统课程的关系

1.5 一门课的”核心 10 个问题”

如果只能记住 10 件事，应该是这 10 个问题及其答案：

1. 为什么 2004 年之后”换新机器就变快”结束了？—— ILP 与频率双双撞墙（L1、L2）。
2. 现代多核 CPU 靠什么提高吞吐？—— 多核 + SIMD + 硬件多线程 + 大 cache（L3）。
3. GPU 和 CPU 有什么本质不同？—— 弱核心 + 大量硬件多线程换吞吐，SIMT/warp 执行（L5、L6）。
4. 如何判断一个并行程序的加速比上限？—— Amdahl（串行比例）+ work-span（并行度 T₁/T∞）（L7、L8）。
5. 工作该怎样分配到执行资源上？—— 静态（blocked/interleaved）、半静态、动态队列、工作窃取（L8）。
6. 通信为什么贵？怎样减少？—— α-β 模型；改变分配、blocking、fusion、sharing、消息粒度（L9）。
7. 多核的 cache 为什么不破坏共享内存语义？—— 缓存一致性协议（MSI/MESI/MOESI）与目录协议（L11–13）。
8. 怎样才能写对自己的同步代码？—— 内存一致性模型 + 原子操作 + 正确放置 fence（L15、L16、L21）。
9. 程序为什么慢、慢在哪里？—— 测量方法论 + PMU 计数器 + Roofline + 高水位实验（L14）。
10. 未来的性能来自哪里？—— 专用化/异构（10–1000× perf/W）+ 更聪明的调度与算法（L18、L22–24、L27）。

2. 课程材料获取情况（公开性说明）

本节如实记录 2026-09 抓取时该网站材料的公开状态，便于读者了解笔记中哪些部分有官方讲义原文支撑。

2.1 公开可访问（已下载）

2.2 未公开 / 需登录（仅记录名称）

注：Lecture 8、9 的讲义虽未在 Fall 2026 日程表行内链接，但 lectures/07_progperf1.pdf 与 lectures/08_progperf2.pdf 本身可在公开目录直接下载（首页标注为历史学期版本，属讲义沿用），因此本笔记的 L8/L9 有官方原文支撑。Lecture 14、17、24 则由公开的姊妹课程（Stanford CS149）同主题讲义与公开成熟知识构建，笔记中已逐处标注来源。

3. 完整的 Fall 2026 课程日程

来源：https://www.cs.cmu.edu/~418/schedule.html（”The exact topics of the lectures are subject to change.”）。下表为去除 HTML 注释后的可见日程。

日程表中还有若干被 HTML 注释包裹的历史条目（如 “Heterogenous parallelism”、”Under the Hood: Message Passing Implementation”、”MPI, OpenMP, Cilk implementation”、”Deep neural networks”、”ML accelerators at Amazon”），它们是往期课程的遗留行，本笔记将其整理为 Lecture 25–27 与归档主题，作为知识补充。

4. 作业、考试与项目

4.1 四次编程作业（”The assignments are the heart of this course”）

作业策略（官方规定）：全部 11:59pm 截止；迟交每天扣 10%；每人一学期有 5 个 late-day points；最多迟交 3 天；一人团队用 1 点延 1 天，两人团队用 2 点延 1 天；作业通过 GitHub 发放，Autolab + Gradescope 提交。

Waitlist 机制：教室容量封顶，Assignment 1 的表现是能否从 waitlist 转正的主要依据；越早提交影响很小（”This is not a race”）。

4.2 四次书面作业（Written Assignments）

面向考试准备，Canvas 发放与提交，个人独立完成（匿名同伴互评，不要写名字）。成绩构成：1/3 按时提交合理解答 + 1/3 认真互评他人 + 1/3 同伴给你的平均分。无 late days。每份有两个截止点：提交解答截止 + 完成同伴互评截止（逾期提交则不能参与互评）。

4.3 两次考试

官方备考提示：简答题多，”choose and explain” 题型中解释的分值远高于选项本身。

4.4 期末项目

往届优秀项目方向（课程页面公开列出的 Fall 2024 / Fall 2022 例子）非常能说明这门课的”落地面”：无锁数据结构（lock-free AVL tree、无锁优先队列、并发哈希表）、多核 cache 模拟器与 ZSim 优化、并行内存优化（prefetching、可扩展无锁分配器）、图像处理（seam carving、Hough 变换、gradient domain fusion）、图形渲染（ray tracing、voxel octree、path tracing）、并行 AI 算法（K-means、RRT、车辆路径）、并行科学计算（流体模拟、化学反应）、并行图算法（Delaunay 三角化、图着色）、并行求解器（SAT、LP、FFT、QR）等。

4.5 教学团队与求助渠道

• 教师：Brian Railing（bpr@cs.cmu.edu，GHC 6005）、Dimitrios Skarlatos（dskarlat@cs.cmu.edu，GHC 9125）
• 求助：优先使用 Ed 讨论区（默认私密）而非邮件；office hours TBA
• 课程目录：/afs/cs/academic/class/15418-f26/

5. 如何使用本笔记

1. 按讲顺序精读。每讲都遵循同一 7 段结构：概述 → 核心概念与架构图解 → 代码示例与性能分析 → 性能模型与复杂度分析 → 关键要点 → 常见陷阱 → 思考题。建议先读第 2 节建立硬件直觉，再动手跑第 3 节的代码。
2. 亲手跑代码。笔记中的代码示例为完整可编译版本，多数标注了 g++ -O3 -march=native -fopenmp / nvcc -O3 / mpicc -O3 之类命令。没有实测条件的（如 CUDA）笔记里已明确标注为模型预测。
3. 把”三把尺子”随时带在手边。任何并行程序都问三个问题：Work 和 Span 各是多少（并行度够不够）？串行比例是多少（Amdahl 上限多少）？算术强度是多少（是算力受限还是带宽受限）？
4. 注意抽象距离。看到任何”高性能”抽象都追问一句：它离硬件有多远？编译器/运行时会生成什么指令？
5. 用速查表复习。考试前用第三部分的六张速查表做最后一遍串讲。
6. 材料公开性已逐讲标注。凡是依据未公开讲义”重述”的部分，笔记中都会说明其依据来自公开的姊妹课程材料或公开成熟知识，请以课程实际讲授为准。

第二部分：逐讲学习笔记

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 年后设计目标从”在面积预算内最大化性能”变成”最大化每面积性能”与”最大化每瓦性能”，而程序员的任务是在这个已经被优化过的机器上，把它提供的能力真正用满。

Lecture 2: Out-of-order Processor & Pipeline

1. 章节标题与概述

Lecture 2: Out-of-order Processor & Pipeline

• 本讲核心问题：硬件如何在没有程序员显式说明的情况下，从一段顺序代码里自动挖掘并行性？既然”程序必须看起来是按程序序、一条一条执行的”，处理器又如何能在内部乱序、重叠、甚至猜测性地执行多条指令，从而让单个指令流的吞吐率远高于”一条指令走完四个阶段”的朴素模型？

• 涉及的主要硬件/软件机制：
  • 流水线（pipelining）：把指令执行切成 Fetch / Decode / Execute / Commit 等阶段，让不同指令处于不同阶段，从而把一个阶段的时间变成整个处理器的吞吐周期。
  • 冒险与消解（hazards）：数据冒险（data hazard）、控制冒险（control hazard）、结构冒险（structural hazard）分别用 旁路转发（forwarding）、停顿插泡（stall / bubble）、分支预测与推测（speculation）、流水线冲刷（flush）、以及增加执行端口来处理。
  • 数据流（dataflow）与乱序执行（out-of-order, OoO）：用寄存器重命名把程序序翻译成”真依赖图”，在保留顺序幻觉的前提下按数据就绪顺序发射；前端取指/译码与后端提交保持顺序，中间的执行完全乱序。
  • 超标量（superscalar）：加宽发射宽度 W，使 IPC 可以大于 1；代价是调度复杂度按 O(W²) 增长。
  • 硬件多线程 / SIMD / 多核（CS149 补充视角）：当 ILP 在 8 宽左右”榨干”之后，工业界转向线程级、数据级并行，并用硬件多线程（SMT）隐藏内存延迟。

• 在并行计算知识体系中的角色：本讲是整门课的”硬件底座”。它解释了为什么”并行”不只是多线程和多核——单核内部本身就是一个复杂的并行机器（流水线并行 + 乱序并行 + 推测并行），也解释了为什么这套机制最终会撞墙（ILP 有限、调度复杂度 O(W²)、频率受功耗限制），从而把历史推向多核。同时它给出了两个贯穿全课程的性能分析工具：延迟界（latency bound，关键路径） 与 吞吐界（throughput bound，执行端口数量与发射率）——后面分析 SIMD、GPU、缓存、带宽时都会反复使用。

• 配套材料：
  • lectures/02_ilp.pdf（讲义正文标题页写作 “Lecture 2: Instruction-Level Parallelism”，共 112 页幻灯片抽取文本 extracted/02_ilp.txt）：已公开，可在 https://www.cs.cmu.edu/~418/lectures/ 下直接下载（课程主页 https://www.cs.cmu.edu/~418/，日程表 https://www.cs.cmu.edu/~418/schedule.html，Fall 2026 日期 Aug 26）。讲义页脚沿用历史学期（如 Fall 2025）字样属于正常的讲义复用现象，不是错误。
  • cs149_supp/multicore1.txt：Stanford CS149 Fall 2025 Lecture 2 “A Modern Multi-Core Processor (Part I)”（共 108 页）——公开的补充读物，用于补足”乱序之后怎么办”的部分（缓存层次、SIMD、多核、硬件多线程、GPU SM 结构）。
  • 讲课录像（Panopto / YouTube）：Fall 2026 日程表中被注释隐藏，属 未发布。
  • Ed 讨论区、Autolab、Canvas：需登录，非公开。
  • 历史学期 PDF（如 Performance Analysis/Profiling、Transactional Memory、AI in System Design 等 Fall 2026 尚未发布的讲义）位于 /afs/cs/academic/class/15418-*/public/ 之下，需要 CMU 登录，属未公开。
  • 本讲 Fall 2026 授课教师为 Brian Railing 与 Dimitrios Skarlatos；课程由 Kayvon Fatahalian 创建。

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

2.1 ISA 与微架构：接口与实现的分离

• 定义与目的：指令集架构（ISA, Instruction Set Architecture） 是硬件与软件之间的功能契约，它规定”每条指令做什么”，但不规定”怎么做”。微架构（microarchitecture） 是 ISA 的具体实现方式。讲义给出的关系式是：

  Architecture : Microarchitecture  ::  Interface : Implementation
  

  这个分离是所有性能优化的前提：同一份二进制可以在完全不同的微架构上运行，因此“快”是实现的属性，不是 ISA 的属性。本讲讨论的流水线、乱序、推测全部属于微架构层面，对程序员”不可见”（不改变程序输出），但极大地改变性能。

• 直观解释（”它是什么？”）：把 ISA 想象成餐厅菜单，微架构想象成厨房。菜单上写着”A 套餐包含汤、主菜、甜点”（功能契约），但厨房可以是一个人从头做到尾（顺序执行、无流水线），也可以是一个流水线厨房：有人专管煮汤、有人专管煎牛排、有人专管摆盘（五级流水线）；甚至可以是一个”提前猜客人要点什么就先把牛排下锅”的厨房（推测执行）。客人（软件）看到的永远是同一份菜单。

• 架构/机制图解：

     软件 / 编译器                                   （ISA: 接口层）
     ------------------------------------------------------------------
        "ldr r5, [r3], #4"    "mla r0, r4, r5, r0"    "bne .L3"
        ^ 只规定语义：从 r3 取 4 字节，写 r5，r3+=4，等等
     ------------------------------------------------------------------
     微架构实现层（对程序员不可见，可任意重排/重叠/猜测）
        Fetch -> Decode -> [ 乱序发射 ] -> Execute -> Commit
        多宽？多深？哪些执行端口？ROB 多大？分支预测器多聪明？
        ★ 这些选择只影响性能，不影响程序语义 ★
  

  关键操作与性能特征：ISA 固定了”每条指令的功能延迟”这一语义概念，但微架构决定了真实延迟与吞吐。例如同一条 FMA（乘加）指令，在不同实现上执行延迟可能是 4 或 5 个时钟周期，而吞吐可以是每周期 0.5 条或 2 条。本讲后半段的所有”延迟界/吞吐界”分析，都是在微架构层面对 ISA 指令流的定量刻画。

2.2 流水线（Pipelining）：用阶段并行换吞吐

• 定义与目的：把一条指令的执行过程切分成若干阶段（stage），让多条指令的不同阶段在时间上重叠。讲义给出的最简模型是四级：

  1. Fetch  – 从内存取指令
  2. Decode – 确定要做什么并读取输入寄存器
  3. Execute – 执行运算
  4. Commit  – 把结果写回寄存器/内存
  

  （真实处理器的流水线级数远多于此。）讲义用多项式求值循环体

  .L3:
    ldr     r5, [r3], #4      // r5 <- coef[j]; r3 <- r3 + 4   (两个操作)
    cmp     r1, r3            // j < terms ?
    mla     r0, r4, r5, r0    // value += r5 * power  (乘 + 加)
    mul     r4, r2, r4        // power *= x
    bne     .L3               // 循环回边
  

  演示：非流水线时每条指令延迟 4 ns、吞吐 1 条/4 ns；四级流水线后延迟仍是 4 ns，但吞吐变成 1 条/ns，即 4× 加速。这就是”N 级流水线最多给出 N× 加速”的来源。

• 直观解释（”它是什么？”）：流水线就像洗衣房。洗一桶衣服要 30 分钟洗 + 30 分钟烘 + 30 分钟叠，一个人从头做到尾，每 90 分钟出一桶；但如果洗、烘、叠分别是三台机器/三个人，第 1 桶仍然要 90 分钟（延迟不变），但从第 2 桶开始每 30 分钟就出一桶（吞吐提高 3 倍）。你自己的衣服并没有变快，但洗衣房单位时间的产量变成了 3 倍。

• 架构/机制图解：

  cycle:        1     2     3     4     5     6     7     8     9
              +-----+-----+-----+-----+-----+-----+-----+-----+-----+
  instr i   F |  F  |  D  |  E  |  C  |     |     |     |     |     |
  instr i+1   |     |  F  |  D  |  E  |  C  |     |     |     |     |
  instr i+2   |     |     |  F  |  D  |  E  |  C  |     |     |     |
  instr i+3   |     |     |     |  F  |  D  |  E  |  C  |     |     |
  instr i+4   |     |     |     |     |  F  |  D  |  E  |  C  |     |
              +-----+-----+-----+-----+-----+-----+-----+-----+-----+
                非流水线: 1 条 / 4 周期, 延迟 4 周期
                流水线  : 1 条 / 周期  , 延迟仍为 4 周期  => 吞吐 4x
                处理器同时在处理 4 条指令（4 份"在途"工作）
  

  关键操作与性能特征：设 stage 时间为 t、级数为 N，则

  • 延迟（单条指令完成时间）= N·t，不被流水线改善；
  • 吞吐 = 1/t（理想情况），改善 N 倍；
  • 在途指令数 = N（在理想满流情况下）。

  但理想情况要求每一级都始终有独立工作可做。只要相邻指令之间存在依赖（见 2.3），流水线就会出现气泡，实际吞吐下降到 1/(t + 停顿)。

2.3 冒险（Hazards）：三种让流水线停下来的原因

• 定义与目的：冒险是阻止下一条指令在下一个周期进入其应属阶段的条件。讲义把限制并行性的冒险分为三类：

  冒险类型	触发条件	讲义中的例子	主要消解手段
  数据冒险 (data hazard)	后续指令需要读取前面指令尚未写回的结果（RAW 读后写）	ldr ra, [rb], #4 写 rb；紧邻的 cmp rc, rd 要读 rb	停顿插泡、旁路转发 (forwarding)、寄存器重命名
  控制冒险 (control hazard)	分支尚未执行完，处理器不知道下一条该取谁	bne .L3 之后仍顺序取到了 pop / bx	流水线冲刷 (flush)、推测执行 + 分支预测
  结构冒险 (structural hazard)	数据已就绪，但没有空闲硬件端口可以发射	Mem / Int / Mult 三类端口分别只有 1 个，而循环体每轮需要 1 个 ldr、2 个整数 op、2 个乘法 op	增加执行端口数量、调整指令组合（编译器调度）

• 直观解释（”它是什么？”）：
  • 数据冒险像接力赛交接棒：第二棒选手必须在第一棒把棒子递到手上才能起跑。如果两人离得太近，第二棒就得原地等一下（stall）；旁路转发相当于第一棒选手在跑动中直接把棒子往前扔过去——不必等他把棒子放回存放区（Commit）再让第二棒去取。
  • 控制冒险像开车到岔路口却看不清路牌。你要么减速停车看清（冲刷+重取，代价大），要么”凭经验猜左转”（分支预测），猜错了就得倒车重来（misprediction penalty）。
  • 结构冒险像只有一台收银机的超市：顾客（指令）已经选好商品、钱也准备好了（数据就绪），但收银台被占着，只能排队。

• 架构/机制图解：下面是讲义中的数据冒险停顿与控制冒险冲刷两个时序图（ldr 写 r3，因此紧随其后的 cmp 不能立刻发射）：

  (a) 数据冒险 -> 停顿插泡 (bubble)              (b) 控制冒险 -> 冲刷 (flush)
  
  cycle:  1    2    3    4    5    6            cycle:  1    2    3    4    5    6
         +----+----+----+----+----+----+              +----+----+----+----+----+----+
  ldr    | F  | D  | E  | C  |    |    |        mla   | F  | D  | E  | C  |    |    |
  cmp    |    |    | ?? | ?? | F  | D  |        mul   |    | F  | D  | E  | C  |    |
  mla    |    |    |    |    |    |    |        bne   |    |    | F  | D  | E  | C  |
         +----+----+----+----+----+----+              +----+----+----+----+----+----+
         ldr 写 r3 -> cmp 读 r3                      pop   |    |    |    | F  | D  | <- 错误取指!
         中间插入 NOP 气泡, 吞吐下降                   bx    |    |    |    |    | F  | <- 错误取指!
                                                       ^^^ 分支跳转后必须丢弃, 从 .L3 重取
                                                            惩罚随流水线深度线性增长
  
  (c) 旁路转发 (forwarding) 消除停顿
         +----+----+----+----+----+
  ldr    | F  | D  | E  | C  |    |     Execute 阶段算出的 r3+4
  cmp    |    | F  | D  | E  | C  |  <- 直接从 E 的输出"抄近路"送到 D 的输入
         +----+----+----+----+----+     不必等 C 阶段写回寄存器堆
         数据在 Execute 之后就已可用 => 大多数(不是全部)停顿可被消除
  

  关键操作与性能特征：

  • 停顿（stall）：注入 NOP 气泡，代价 = 插入的周期数；但有些停顿不可避免——长延迟指令（除法、缓存缺失）无法靠转发解决。
  • 转发（forwarding）：在 Execute 之后、Commit 之前就把结果前送。讲义明确指出：转发不是免费的——流水线越深越复杂，需要的转发通路数量急剧增长，所以”转发能消掉多少停顿”这件事本身随流水线加深而恶化。
  • 冲刷（flush）：代价随流水线加深而线性增长（要丢弃的在途指令更多）。讲义因此总结：流水线深度在 N≈15 附近触顶，再深下去，转发成本与冲刷成本会吃掉所有收益。

2.4 推测执行与分支预测（Speculation）

• 定义与目的：程序必须”看起来按程序序执行”，因此所有指令看似都依赖前一条——但分支会跳转，处理器不能在等分支结果的同时空转。推测（speculation） 就是”猜一个方向，先把指令取进来执行，猜错就整体回滚（roll back）”。其目的是为流水线创造本不存在的独立工作，把控制冒险的代价从”串行等待分支解决”降为”猜错时的一次性惩罚”。

• 直观解释（”它是什么？”）：像考试时先做后面的题。你读到一道需要长时间计算的选择题，于是先”假设答案是 A”，然后按 A 往下推（推测执行）；如果后面发现 A 错了，就擦掉所有基于 A 写下的内容重做（回滚/冲刷），而不是从第一题一直卡在那里等。

• 架构/机制图解：

      静态指令序列 (内存中的程序布局)
      +----------------------+  <-- .L3 循环体
      | ldr  r5, [r3], #4    |
      | cmp  r1, r3          |
      | mla  r0, r4, r5, r0  |
      | mul  r4, r2, r4      |
      | bne  .L3   ----------+----(1) 预测"跳转" (taken)
      +----------------------+         |
      | pop  {r4, r5}        |  <-- 顺序流(错误路径)      |
      | bx   lr              |                             v
      +----------------------+                  继续投机执行 .L3 循环体
                                                 (2) 分支在 Execute 阶段出结果
                                                     ├─ 预测正确 (>95% 的情况): 零代价, 满载
                                                     └─ 预测错误: 冲刷错取指令, 从正确 PC 重取
                                                        惩罚 = 流水线深度（现代 CPU ~15-20 周期）
  

  关键操作与性能特征：

  • 现代处理器会在 Fetch 阶段就做预测——甚至还没译码出”这是一条分支”就已经按预测的 PC 取指。
  • 讲义给出的预测准确率量级是 >95%，但分支误预测仍然是主要性能问题：4 宽 × 20 级流水线的机器，每次误预测约损失 15–20 个周期，意味着可发射 60–80 条指令的窗口被浪费掉。
  • 一个极端情形（讲义明确点名）：依据随机数据分支的代码——预测器无法学习规律，性能会被 fetch 停顿主导。这正是后面代码示例 branch_pred.cpp 要量化的现象。

2.5 数据流（Dataflow）与真假依赖

• 定义与目的：程序序在寄存器层面引入了大量伪依赖（false dependency）。数据流（dataflow） 的思想是：只看指令之间真正的数据依赖关系（真依赖 = 读后写 RAW, read-after-write），忽略只由”复用了同一个寄存器名”造成的顺序约束，从而暴露出更多并行性。讲义的原话是：”Dataflow increases parallelism by eliminating unnecessary dependences.”

  依赖类型速查（本章表格之一）：
  +-------+----------------------+----------------------------+------------------+
  | 类型  | 含义                 | 反例（同一个寄存器名复用）   | 是否真依赖       |
  +-------+----------------------+----------------------------+------------------+
  | RAW   | 读后写 (read-after-   | I1: r0 = a + b             | 真依赖，必须保留 |
  |       | write)               | I2: c  = r0 * 2            |                  |
  | WAR   | 写后读 (write-after-  | I1: c  = r0 * 2            | 伪依赖，重命名消除|
  |       | read)                | I2: r0 = a + b             |                  |
  | WAW   | 写后写 (write-after-  | I1: r0 = a + b             | 伪依赖，重命名消除|
  |       | write)               | I2: r0 = c * d             |                  |
  | 控制  | 分支决定后继          | bne .L3 之后的所有指令      | 推测+预测+冲刷处理|
  | 结构  | 端口/资源冲突         | 两条乘法指令争 1 个乘法端口 | 增加端口或用别类指令顶上 |
  +-------+----------------------+----------------------------+------------------+
  

• 直观解释（”它是什么？”）：把寄存器想成白板上的编号格子。程序序规定”必须先擦掉 1 号格子的旧内容再写新的”，但这只是因为大家共用了那块白板。数据流说：再拿一块新白板写下新值就行了，需要旧值的人继续看旧白板，需要新值的人看新白板——两块白板互不干扰，于是原本必须排队的两步可以同时做。这就是寄存器重命名（register renaming） 的直觉。

• 架构/机制图解：以多项式循环体为例，讲义给出的数据流执行图（假设完美调度、无限执行单元）：

                          loop iteration j
     ==================================================================
        r3(j-1) ---> [ ldr ] --(2c)--> r5 ------------------------+
                       |                                          |
                       +------> r3(j) ---> [ cmp ] --(1c)         |
                                              |                   |
                                              v                   v
                                          [ bne ] --(1c)     [ mla ] --(3c)--> r0(j+1)
                                                                  ^
                                                    r4(j-1) ------+
                                                                  ^
                                                    [ mul ] --(2c)-+--> r4(j+1)
     ==================================================================
  
     指令延迟（讲义给定）: ldr = 2c, mul = 2c, cmp = 1c, bne = 1c, mla = 3c
     跨迭代关键路径:
        r0 链  mla(j) 依赖 mla(j-1) : 3 周期/迭代   <== 瓶颈
        r4 链  mul(j) 依赖 mul(j-1) : 2 周期/迭代
        => 迭代下界 = max(3, 2) = 3 周期/迭代
           每轮 5 条指令 => IPC = 5/3 ≈ 1.67
           （对比: 完美流水线 IPC = 1）
  

  关键操作与性能特征：

  • 关键路径（critical path） 的定义（讲义原文）：数据流图中跨迭代的最长路径。在上例中就是 mla 链。
  • 关键路径给出性能上限，且是”延迟界”（latency bound）：即使执行单元无限多、端口无限宽，也无法快过 3 周期/迭代，因为mla 必须等前一次 mla 的结果。这个程序是延迟受限的（latency-bound）。
  • 讲义强调这只是一个心智模型与分析工具：真实 CPU 未必达到该界限，但用它来分析程序非常有用。

2.6 乱序执行（Out-of-Order, OoO）微架构

• 定义与目的：OoO 的核心思想是”按数据流顺序执行，但保持顺序执行的幻觉“。指令按程序序进入和离开一个指令缓冲/重排序缓冲（instruction buffer / reorder buffer, ROB），而在缓冲内部，发射顺序完全由操作数是否就绪决定。这样既拿到了数据流的并行性，又对软件保留了”顺序单发射机器”的语义。

• 直观解释（”它是什么？”）：像餐厅的出菜口。顾客（程序）按点单顺序排队（in-order frontend），厨房内部可以任意乱序地同时炒五道菜（out-of-order execute），但摆盘上菜必须按点单顺序（in-order commit）——1 号桌的菜没好，2 号桌的菜做好了也得先放在保温台上等着。顾客看到的永远是”按顺序上菜”，但厨房的吞吐被最大化了。

• 架构/机制图解：

  +-------------------------------------------------------------------------+
  |                                CPU core                                 |
  |                                                                         |
  |  PC --> [ Fetch ] --> [ Decode ] --> +---------------------------+      |
  |          in-order      in-order      |  Instruction Buffer / ROB |      |
  |                                      |  (W 条/周期进入, 乱序发射) |      |
  |                                      +-------------+-------------+      |
  |                                                    |                    |
  |                     +------------------------------+---------------+    |
  |                     |  out-of-order issue (数据就绪即发射)          |    |
  |                     v              v              v               v    |
  |              [ EXE: ALU ]  [ EXE: FMA ]  [ EXE: FMA ]  [ EXE: LD/ST ]   |
  |                     |              |              |               |    |
  |                     +--------------+------+-------+---------------+    |
  |                                           v                             |
  |                             [ Commit / Retire ]  <-- in-order           |
  |                                           |                             |
  +-------------------------------------------|-----------------------------+
                                              v
                                       寄存器堆 / 内存状态
       ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
       前端 in-order  |  执行 out-of-order  |  提交 in-order
       讲义原话: "Instructions only enter & leave instruction buffer in
                  program order; all bets are off in between!"
  

  关键操作与性能特征：

  • 发射（issue）：一条指令只有在所有源操作数就绪且存在空闲执行端口时才会被发射。
  • 写回/旁路：执行结果既可写寄存器堆，也可直接前送给等待它的指令（转发在 OoO 中依然重要）。
  • 提交（commit）：按程序序退役，这是”顺序幻觉”的最后一道防线，也是精确异常（precise exception）和推测回滚的锚点。
  • 设计目标（讲义原文）：OoO 设计的目标是”只受数据流执行限制“；Fetch 与 Commit 被超额配置（over-provisioned），使它们通常不成为瓶颈。因此程序员通常可以忽略取指与提交阶段。
  • 重大例外：控制流本质上不可预测的程序（例如依据随机数据分支）会被取指停顿主导——这是唯一需要程序员重新关注前端的场景。
  • 软件收益（讲义”Software Takeaway”）：OoO 对”好代码”的敏感度低得多，性能可移植性更好；编译器仍然重要，但远不如 in-order 机器上那么关键。

2.7 超标量（Superscalar）：让 IPC 突破 1

• 定义与目的：前面的 OoO 模型里每周期只能发射 1 条指令，因此即使数据流可以给出 1.67 的并行度，实际也会被”发射宽度 = 1”卡死在 IPC = 1。超标量（superscalar） 就是加宽流水线：每周期取指/译码/发射/提交多条指令，配合多个执行单元，使 IPC 可以大于 1。讲义的原话：”Must increase pipeline width to increase IPC > 1.”

• 直观解释（”它是什么？”）：单发射是单车道收费站，不管后面的车多想同时通过，一次只放一辆；超标量是把收费站扩成 4 条车道，并且装了一个”智能调度员”（乱序发射逻辑），实时判断哪几辆车可以同时放行（彼此独立、且各自的车道类型匹配：有的是 ETC（整数口）、有的是货车通道（乘法口）、有的要走称重（访存口））。

• 架构/机制图解（讲义把 OoO + 多执行单元纵向堆叠；下面是同一循环体在超标量 OoO 上的时序，见”结构冒险”一节）：

  每周期可发射 2 条指令的"示例"超标量 OoO（讲义用 2 宽示意图）:
  
  cycle:      1    2    3    4    5    6    7    8    9   10   11
  ------------------------------------------------------------------
  Mem  port:  L0        L1        L2        L3        L4
  Int  port:  C0   B0   C1   B1   C2   B2   C3   B3   C4
  Mul  port:  M0   U0   M1   U1   M2   U2   M3   U3   M4
              \____ j=0 ___/\____ j=1 ___/\____ j=2 ___/
  ------------------------------------------------------------------
  L = ldr   C = cmp   B = bne   M = mla   U = mul
  乘法类端口每轮要处理 (1 个 mla + 1 个 mul)，若它们的发射占用
  分别是 2 和 3 个周期 => 5 周期/迭代（结构冒险主导）
  若配置了足够的乘法端口 => 回到延迟界 3 周期/迭代
  

  关键操作与性能特征：

  • 代价（讲义重点）：判断”两条指令能否同时发射”需要比较它们的输入/输出寄存器对，复杂度是 O(W²)（W = 发射宽度）——”Not great!”
  • 收益递减：讲义明确指出，即便调度完美，超过 8 宽也没有帮助（程序本身 ILP 有限）。
  • 在途窗口：4 宽 × 20 级流水线 = 80 条指令在途；高性能 OoO 的缓冲可以容纳数百条指令。
  • 结构冒险是真实的墙：执行单元是专用化的（浮点加/乘、整数加/乘/比较、访存），设计者必须选择包含哪些、各几个。数据就绪但没有空闲端口时只能等。

2.8 延迟界与吞吐界：讲义给出的两把尺子

• 定义与目的：讲义把 OoO 机器的性能分析归结为两个界，取二者较慢者即可很好地近似真实性能：

  界	定义（讲义原文）	组成要素	典型瓶颈
  延迟界 (latency bound)	数据流图中跨迭代的最长路径所决定的下界	真依赖链上各操作延迟之和	mla 依赖链（3c/迭代）
  吞吐界 (throughput bound)	ops / issue rate，即操作数除以执行端口发射率	每类操作的数量 + 执行端口数量与发射率	乘法端口需 (1 mla + 1 mul) / (2 + 3 周期) = 5c/迭代

  实际性能 ≈ max(延迟界, 吞吐界)。讲义强调真实 CPU 未必精确达到这些界，但作为分析工具非常有用。

• 直观解释（”它是什么？”）：
  • 延迟界像一条只能单人通行的吊桥：桥上有多少人排队不重要，重要的是队首到队尾要走多久。加宽桥面（更多执行单元）毫无帮助，只能缩短链条（拆分依赖链）。
  • 吞吐界像只有 3 条收银通道的超市：顾客之间毫无依赖（可以任意并行），但收银台数量决定了每秒最多结账多少单。这时增加顾客的独立性没用，只能加通道（加端口）或换更快的收银员（提高发射率）。

• 架构/机制图解：

  (a) 延迟界: 一条长依赖链 —— 执行端口大量空闲, 加宽无用
    t:   1   2   3   4   5   6   7   8   9  10  11  12
    op1 [===== FMA (4c) =====]
    op2                     [===== FMA (4c) =====]
    op3                                             [===== FMA (4c) =====]
        |<-------- 关键路径 = 3 x 4 = 12 周期 -------->|
        端口空闲率极高, IPC 低; 想加速只能"拆链"
  
  (b) 吞吐界: 依赖链被拆成 8 条独立链 —— 端口成为瓶颈
    t:   1   2   3   4   5   6   7   8   9  10
    op1 [FMA]
    op2 [FMA]
    op3 [FMA]
    op4 [FMA]
    op5     [FMA]
    op6     [FMA]
        |<-- 每周期都在发射, 端口 100% 占用 -->|
        IPC 高, 想加速只能"加端口/加宽 SIMD"
  
  (c) 真实程序: 两个界同时存在, 取 max
        +--------------------------+
        | 实际性能 ≈ max(延迟界, 吞吐界) |
        +--------------------------+
  多项式循环: 延迟界 3c/迭代, 吞吐界 5c/迭代 => 预期 5c/迭代
  

  关键操作与性能特征：这两个界是整个课程反复使用的分析框架。在后面的 SIMD/GPU 讲座中，”吞吐界”会变成”SIMD 通道数 × FMA 端口数”，”延迟界”会变成”寄存器依赖链长度”；在缓存/带宽讲座中，二者之上还会再加一个带宽界。

2.9 从 ILP 到 TLP：多核、SIMD 与硬件多线程（CS149 补充视角）

• 定义与目的：讲义最后给出了”为什么 ILP 会撞墙、为什么工业界转向多核”的完整论证链：

  1. 程序的 ILP 有限：即便完美调度，>8 宽也无收益；
  2. 流水线不能无限加深：分支误预测惩罚随深度增长；
  3. 频率受功耗限制：不能靠提频解决；
  4. 动态调度开销显著：OoO 硬件本身昂贵、O(W²) 复杂。 => 从硬件角度，多核效率高得多；但并行软件很难写。工业界”尽可能久地抵制多核”，最终多核到来时，CPU 微架构反而被简化以塞进更多核。

  CS149 的补充讲义把”现代处理器上可用的并行形式”整理为三类，并额外增加硬件多线程用于隐藏内存延迟：

  并行形式	粒度/来源	谁发现并行	硬件代价	对程序的要求
  超标量 / ILP	指令级、隐式、细粒度（核内）	硬件运行时动态发现	昂贵复杂（O(W²) 调度、重命名、ROB）	顺序代码即可，性能可移植性好
  SIMD	数据级（核内）	编译器静态向量化，或 GPU 硬件运行时（implicit SIMD）	中等（宽 ALU + 宽寄存器）	需要控制流一致（coherent execution），否则掩码浪费，最差降到 1/8（CPU 8 宽）或 1/32（GPU 32 宽）
  多核 / 线程级	线程级、显式、粗粒度	软件显式创建线程	每核一套前端+执行资源	需要足够的并行工作与正确的同步
  硬件多线程 (SMT/交错)	同一核上的多个上下文	软件给线程，硬件交错发射	额外的上下文存储	需要远多于 ALU 数量的独立工作来隐藏延迟

• 直观解释（”它是什么？”）：
  • 多核像把一间大厨房隔成 4 间小厨房，每间自己买菜、自己炒（各自独立的指令流）；比”一间超级厨房里塞满自动炒菜机器人”（复杂 OoO 单核）更容易扩建。
  • SIMD 像流水线上一个字模同时盖 8 个盒子：只有 8 个盒子都走同一步骤（同一条指令）时才高效；如果第 3 个盒子要求换个图案（控制流发散），字模得停下重来，其余通道只能空转（掩码丢弃）。
  • 硬件多线程像一位厨师同时照看 4 口锅：第 1 口锅在炖（等内存，12 个周期），厨师立刻去翻第 2 口锅（发射另一个线程的算术指令）。锅并没有变快，但厨师不再闲着。

• 架构/机制图解（把四种并行叠在一张图上）：

  +---------------------------------------------------------------------------+
  |  Chip —— 多核 (multi-core): M 个核, M 条并发指令流, 软件显式建线程          |
  |                                                                           |
  |  +---------------------------------+   +---------------------------------+ |
  |  | Core 0                          |   | Core 1                          | |
  |  |  +---------------------------+  |   |  +---------------------------+  | |
  |  |  | SMT: exec ctx 0 | ctx 1   |  |   |  | SMT: exec ctx 0 | ctx 1   |  | |
  |  |  |  (每周期从多个线程选指令)  |  |   |  |                           |  | |
  |  |  +---------------------------+  |   |  +---------------------------+  | |
  |  |  | OoO engine (ILP)          |  |   |  | OoO engine (ILP)          |  | |
  |  |  |   issue width W, ROB 深 D |  |   |  |   issue width W, ROB 深 D |  | |
  |  |  +---------------------------+  |   |  +---------------------------+  | |
  |  |  | 8-wide SIMD ALU x 3       |  |   |  | 8-wide SIMD ALU x 3       |  | |
  |  |  |  (每周期 8 个 float 一条指令)| |   |  |  (每周期 8 个 float 一条指令)| | |
  |  |  +---------------------------+  |   |  +---------------------------+  | |
  |  +---------------------------------+   +---------------------------------+ |
  +---------------------------------------------------------------------------+
        M=16 核 x 8 宽 SIMD x 2 (FMA) x 3.0 GHz = 768 GFLOPS 峰值(单精度)
  

  关键操作与性能特征（来自 CS149 补充讲义的关键数字）：

  • Kaby Lake 系列核心：2 路 SMT；每核每周期最多 4 条独立标量指令、最多 3 条 8 宽向量指令（其中最多 2 条向量乘或 3 条向量加）。
  • 4 核 × 8 宽 SIMD × 3 单元 × 4.2 GHz ≈ 400 GFLOP/s（讲义按”每条 SIMD 通道操作记 1 FLOP”计；若把 FMA 记作 2 FLOP 则约 800 GFLOP/s）。
  • 数据访问延迟（Kaby Lake, 4 GHz）：L1 = 4 周期、L2 = 12 周期、L3 = 38 周期、DRAM 最好情况 ≈ 248 周期。带宽约 38 GB/s。
  • 硬件多线程的必要线程数：若每线程执行”3 条算术指令 + 一次 12 周期延迟的 load”，单线程利用率仅 3/15 = 20%；两线程 40%；需要 5 个线程才能到 100%。若算术指令增至 6 条，则只需 3 个线程。→ “每次访存携带的算术越多，隐藏延迟所需线程越少”（这正是算术强度/计算访存比的直觉来源）。
  • GPU 极端吞吐导向：以补充讲义给出的 V100 为例，一个 SM（Streaming Multiprocessor） 拥有 64 个 warp 执行上下文、4 个 sub-core、每个 sub-core 有 16 宽 fp32 SIMD 单元（每 2 个周期完成一次 32 宽操作）、256 KB 寄存器、128 KB 共享内存+L1；80 个 SM，HBM 带宽约 900 GB/s。

3. 代码示例与性能分析

3.1 示例一：多项式求值——从”延迟界”到 ILP 显式重构

讲义整场都在用多项式求值讲解流水线、数据流、乱序。下面把它写成一个可以真正跑出差异的基准测试：Horner 串行链（纯延迟界）对比偶/奇双链重构（把关键路径砍半）。

// ---------------------------------------------------------------
// poly_ilp.cpp
// 编译 (release):
//   g++ -O3 -march=native -fno-tree-vectorize poly_ilp.cpp -o poly_ilp
//   # -march=native 打开 FMA (vfmadd...), 使 mla 变成单条 FMA 指令
//   # 注意: 不要加 -ffast-math, 否则编译器可自由重结合浮点, 实验失去意义
// 运行:
//   ./poly_ilp 8192 2000        # 8192 个系数, 重复 2000 次
// 观察:
//   two_chain 的耗时约为 horner 的一半 => 关键路径被砍半
// ---------------------------------------------------------------
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <chrono>
#include <cmath>

// (a) 朴素 Horner: value = ((c[n-1]*x + c[n-2])*x + ...)*x + c[0]
//     关键路径 = (n-1) 次 FMA 串行依赖 -> 纯 latency bound
static inline float poly_horner(const float* c, int n, float x) {
    float value = c[n - 1];
    for (int j = n - 2; j >= 0; --j)
        value = value * x + c[j];       // 编译为 vfmadd213ss 等
    return value;
}

// (b) 偶/奇双链:  poly(x) = B(u) + x * A(u),  u = x^2
//     A(u) 收集所有奇数下标项, B(u) 收集所有偶数下标项 (要求 n 为偶数)
//     关键路径 ≈ 1 次 mul + (n/2) 次 FMA + 1 次 add -> 并行度 ~2
static inline float poly_two_chain(const float* c, int n, float x) {
    const float u = x * x;
    float A = 0.0f, B = 0.0f;
    for (int j = n - 1; j >= 1; j -= 2) {
        A = A * u + c[j];               // 奇数下标链 (与 B 链完全独立)
        B = B * u + c[j - 1];           // 偶数下标链
    }
    return B + x * A;
}

int main(int argc, char** argv) {
    const int    n = (argc > 1) ? std::atoi(argv[1]) : 8192;
    const int    repeat = (argc > 2) ? std::atoi(argv[2]) : 2000;
    if (n % 2) { std::fprintf(stderr, "n must be even\n"); return 1; }

    std::vector<float> c(n);
    for (int j = 0; j < n; ++j)
        c[j] = std::sin(0.001f * (float)j);   // 任意非平凡系数

    auto bench = [&](const char* name, float (*fn)(const float*, int, float)) {
        volatile float sink = 0.0f;                 // 防止整个循环被优化掉
        float x = 1.0009765625f;                    // 略大于 1, 避免溢出
        auto t0 = std::chrono::steady_clock::now();
        for (int r = 0; r < repeat; ++r) {
            sink = sink + fn(c.data(), n, x);
            x += 1e-7f;                             // 让各次调用的 x 不同
        }
        auto t1 = std::chrono::steady_clock::now();
        double sec = std::chrono::duration<double>(t1 - t0).count();
        double perCall = sec / repeat;
        // 用 3.0 GHz 估算关键路径周期数 (仅作量级参考)
        std::printf("%-12s : %8.3f ms/call   %8.2f cycles/FMA (@3.0GHz)   sink=%.6f\n",
                    name, perCall * 1e3, perCall * 3.0e9 / (double)n, (double)sink);
    };

    bench("horner",    poly_horner);
    bench("two_chain", poly_two_chain);
    return 0;
}

【代码做什么？】

1. 构造 n 个系数（n 取偶数），保证两个版本计算的是同一个多项式。
2. poly_horner 从最高次项开始向下迭代，每一步 value = value*x + c[j]。这是一个严格的串行依赖链：第 j 步必须等第 j+1 步的 value。
3. poly_two_chain 先把 偶数下标项 与 奇数下标项 分成两个独立的多项式（都关于 u = x*x），各自做 Horner，最后 B + x*A 合并。两条链之间没有任何数据依赖，因此可以同时推进。
4. 两个函数都在 repeat 次调用中被计时，用 volatile sink 阻止死代码消除，用 x += 1e-7f 阻止编译器把重复调用”折叠”成一次。
5. 输出每次调用的毫秒数，并按 3.0 GHz 折算成”每个 FMA 的周期数”，便于对照讲义给出的 FMA 延迟 4 个周期。

【并行机制与性能解说】

• 硬件上如何并行：两个版本编译出的都是一串标量 FMA 指令，没有 SIMD、没有多线程。它们的唯一并行性来自 OoO 引擎发现的 ILP。poly_horner 的指令之间全部 RAW 依赖，OoO 窗口里根本没有可同时发射的指令；poly_two_chain 则交替发射 A 链与 B 链的两条 FMA，每周期可发射 2 条（受 FMA 端口数限制，Skylake 级机器通常 2 个 FMA 端口）。

• Work / Span / 并行度分析（设 n 个系数，一次调用）：

  版本	Work（总操作数）	Span（关键路径）	并行度 = Work/Span
  poly_horner	(n−1) 次 FMA	(n−1)·L_FMA	≈ 1
  poly_two_chain	2 mul + n 次 FMA + 1 add = n+3	L_mul + (n/2)·L_FMA + L_mul + L_add	≈ 2

  取 n = 8192、L_FMA = L_mul = L_add = 4 周期：

  • Horner: Span = 8191 × 4 ≈ 32 764 周期/次调用；
  • two_chain: Span ≈ 4 + 4096×4 + 4 + 4 = 16 396 周期/次调用；
  • 理论上限加速比 ≈ 2.0×，而 Work 增加了约 3 次操作（<0.04%）。
• 瓶颈诊断：这是教科书式的延迟界（latency bound）。执行端口几乎全程空闲，加宽机器、加更多 FMA 单元完全没有用；唯一有效的优化就是缩短关键路径。想继续加速就要继续拆链（Estrin 方案、4 链、8 链…），但每拆一层 Work 都会略微上涨，收益按 2^k 递减。
• 另一个真实世界的坑：如果加了 -ffast-math，编译器可能自己就把 Horner 重组成 Estrin，两个函数耗时相同——这不是实验失败，而是”编译器替你做了 ILP 重构”。反过来，不加 -ffast-math 时编译器不允许重结合浮点，所以它会老老实实保留串行链。这正是”什么时候必须手工暴露 ILP”的经典案例。

3.2 示例二：求和——延迟界 → 吞吐界 → 带宽界的连续迁移

同一个”求和”内核，用三种写法展示性能瓶颈的迁移：串行单累加器（延迟界）→ 串行多累加器（ILP 显式化）→ OpenMP 多线程多累加器（可能进入带宽界）。

// ---------------------------------------------------------------
// omp_sum.cpp
// 编译 (release):
//   g++ -O3 -march=native -fopenmp omp_sum.cpp -o omp_sum
// 运行:
//   OMP_NUM_THREADS=16 ./omp_sum 100000000      # 1 亿个 double = 800 MB
// ---------------------------------------------------------------
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <chrono>
#include <omp.h>

// (a) 串行, 单累加器: 关键路径 = N 次加法串行依赖 => 纯 latency bound
static double sum_serial(const double* a, size_t n) {
    double s = 0.0;
    for (size_t i = 0; i < n; ++i) s += a[i];
    return s;
}

// (b) 串行, 4 个独立累加器: 关键路径 = N/4 次加法, 依赖链 4 条并行
//     编译器通常会把这样的写法直接向量化成 4 宽 SIMD (AVX2)
static double sum_serial_ilp(const double* a, size_t n) {
    double s0 = 0, s1 = 0, s2 = 0, s3 = 0;
    size_t i = 0;
    for (; i + 4 <= n; i += 4) {
        s0 += a[i]; s1 += a[i + 1]; s2 += a[i + 2]; s3 += a[i + 3];
    }
    double s = (s0 + s1) + (s2 + s3);
    for (; i < n; ++i) s += a[i];          // 尾部
    return s;
}

// (c) OpenMP + 每线程 4 个累加器: 线程级并行 x ILP 显式化
//     用 reduction(+:total) 让 OpenMP 负责最后合并, 避免手工加锁
static double sum_omp_ilp(const double* a, size_t n, int nthreads) {
    double total = 0.0;
    #pragma omp parallel num_threads(nthreads) reduction(+:total)
    {
        const int    tid = omp_get_thread_num();
        const int    nth = omp_get_num_threads();
        const size_t chunk = (n + (size_t)nth - 1) / (size_t)nth;
        const size_t lo = (size_t)tid * chunk;
        const size_t hi = (lo + chunk < n) ? (lo + chunk) : n;

        double s0 = 0, s1 = 0, s2 = 0, s3 = 0;
        size_t i = lo;
        for (; i + 4 <= hi; i += 4) {
            s0 += a[i]; s1 += a[i + 1]; s2 += a[i + 2]; s3 += a[i + 3];
        }
        double s = (s0 + s1) + (s2 + s3);
        for (; i < hi; ++i) s += a[i];
        total += s;
    }
    return total;
}

int main(int argc, char** argv) {
    const size_t n = (argc > 1) ? std::strtoull(argv[1], nullptr, 10) : 100000000ULL;
    std::vector<double> a(n);
    for (size_t i = 0; i < n; ++i) a[i] = 1.0 + 1e-9 * (double)(i & 1023);

    const double bytes = (double)n * sizeof(double);
    auto run = [&](const char* name, double (*fn)(const double*, size_t)) {
        auto t0 = std::chrono::steady_clock::now();
        volatile double r = fn(a.data(), n);
        auto t1 = std::chrono::steady_clock::now();
        double sec = std::chrono::duration<double>(t1 - t0).count();
        std::printf("%-16s : %8.2f ms   %7.2f GB/s   sum=%.1f\n",
                    name, sec * 1e3, bytes / sec / 1e9, (double)r);
    };

    run("serial",     sum_serial);
    run("serial_ilp", sum_serial_ilp);
    {
        auto t0 = std::chrono::steady_clock::now();
        volatile double r = sum_omp_ilp(a.data(), n, omp_get_max_threads());
        auto t1 = std::chrono::steady_clock::now();
        double sec = std::chrono::duration<double>(t1 - t0).count();
        std::printf("%-16s : %8.2f ms   %7.2f GB/s   sum=%.1f   (threads=%d)\n",
                    "omp_ilp", sec * 1e3, bytes / sec / 1e9, (double)r,
                    omp_get_max_threads());
    }
    return 0;
}

【代码做什么？】

1. 分配 n 个 double（默认 1 亿个 = 800 MB），填充成互不相同的数（防止编译器把”常量数组求和”折叠成乘法）。
2. sum_serial：一次遍历，单累加器 s += a[i]，形成长度为 n 的加法依赖链。
3. sum_serial_ilp：用 4 个累加器同时累加 4 个元素，最后两两合并；尾部剩余元素单独处理。
4. sum_omp_ilp：#pragma omp parallel ... reduction(+:total) 把区间按线程切分（块划分），每个线程内部再用 4 个累加器，最后由 OpenMP 的 reduction 把各线程的 total 合并（实现上等价于每线程私有副本 + 末尾层次化合并，不存在热点的原子操作）。
5. 三种写法都统计时间、实际带宽（GB/s）与校验和。

【并行机制与性能解说】

• sum_serial 在硬件上如何执行：只有 1 条依赖链，OoO 完全无指令可重叠。每次加法延迟约 4 个周期（Skylake 级），所以吞吐受延迟限制为 4 周期/元素。
• sum_serial_ilp 如何加速：4 条独立链让 OoO 每周期都能发射 1 条加法，同时编译器大概率把它向量化为 256 位 SIMD（4 个 double 一条 vaddpd）。于是瓶颈从”延迟界”转到”吞吐界“：每条 SIMD 加法只花 1 个周期，每周期消耗 32 字节。

• sum_omp_ilp 如何并行：创建 T 个线程，每个线程拿到连续的一块区间（块划分 = 顺序访问，对预取器与 DRAM 行缓冲友好），线程之间没有共享可写数据（各自私有累加器），只在末尾做一次 reduction。无数据竞争、无伪共享。

• Work / Span / 并行度分析（N 个元素、T 个线程、每线程 4 个累加器）：

  版本	Work	Span	并行度
  sum_serial	N 次加法	N·L_add	1
  sum_serial_ilp	N 次加法（+3 次合并）	(N/4)·L_add + 2·L_add	≈ 4
  sum_omp_ilp	N 次加法	(N/(4T))·L_add + log₂(T)·L_add	≈ 4T

  取 N = 10⁸、T = 16、L_add = 4 周期、f = 3.0 GHz：

  • sum_serial: Span = 4×10⁸ 周期 = 133 ms
  • sum_serial_ilp: Span = 10⁸ 周期 = 33 ms（理想 4× 加速）
  • sum_omp_ilp: Span = 10⁸/(4×16) ≈ 1.56×10⁶ 周期 ≈ 0.52 ms（理想 256× 加速）
  • 但物理下限是：800 MB ÷ 38 GB/s ≈ 21 ms（用讲义给出的 Kaby Lake 38 GB/s）。即便用 20 GB/s 的保守带宽，也要 40 ms。
• 瓶颈诊断（本示例最重要的结论）：当 T = 16 时，Work/Span 的并行度是 256，但实测只会落在 21–40 ms 区间，而非 0.52 ms。此时程序已经彻底从延迟界迁移到带宽界：再增加线程、再拆累加器、再宽 SIMD 都毫无收益（甚至因为超过内存控制器并发能力而变慢）。这就是”算术强度”概念要解决的问题——见第 4 节 Roofline 分析。
• 附带陷阱提示：如果为了让”每线程 4 个累加器”更细而把切分改成 a[i] += ... 的跨步访问（stride = T），虽然累加器线程私有、没有伪共享，但访存变成非连续，会破坏预取与 DRAM 行局部性，带宽可能掉一半以上。这是”为了并行而牺牲局部性”的典型错误。

3.3 示例三：分支预测——控制冒险的量化实验

讲义在”控制冒险/推测”一节点名了最坏情况：基于随机数据的分支。下面的实验用同一份代码、同一份数据，仅改变数据的排列顺序，就能观察到数量级的差异。

// ---------------------------------------------------------------
// branch_pred.cpp
// 编译 (release):
//   g++ -O2 -march=native branch_pred.cpp -o branch_pred
// 建议同时检查反汇编, 确认 if 没有被改写成无分支代码:
//   objdump -d branch_pred | grep -A30 '<_Z12sum_branchy'
// 运行:
//   ./branch_pred 40000000
// ---------------------------------------------------------------
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <chrono>
#include <cstdint>

// 数据相关的 if: 分支方向由数据决定
// 两个副作用 (s 与 hits 同时更新) 可降低编译器 if-conversion 成 cmov 的概率
static long long sum_branchy(const uint8_t* d, size_t n) {
    long long s = 0, hits = 0;
    for (size_t i = 0; i < n; ++i) {
        if (d[i] >= 128) {          // <-- 数据相关分支
            s += d[i];
            ++hits;
        }
    }
    return s + hits;
}

// 等价的无分支写法: 用条件表达式, 期望被编译成 cmov / 掩码运算
static long long sum_branchless(const uint8_t* d, size_t n) {
    long long s = 0;
    for (size_t i = 0; i < n; ++i) {
        const uint8_t v = d[i];
        s += (v >= 128) ? (long long)v : 0LL;
    }
    return s;
}

int main(int argc, char** argv) {
    const size_t n = (argc > 1) ? std::strtoull(argv[1], nullptr, 10) : 40000000ULL;
    std::vector<uint8_t> data(n);
    unsigned seed = 12345u;
    for (size_t i = 0; i < n; ++i) {                 // 简单 xorshift 伪随机
        seed ^= seed << 13; seed ^= seed >> 17; seed ^= seed << 5;
        data[i] = (uint8_t)(seed >> 24);             // 均匀分布 0..255
    }

    auto time_it = [&](const char* tag, long long (*fn)(const uint8_t*, size_t)) {
        auto t0 = std::chrono::steady_clock::now();
        volatile long long r = fn(data.data(), n);
        auto t1 = std::chrono::steady_clock::now();
        double sec = std::chrono::duration<double>(t1 - t0).count();
        std::printf("%-26s : %8.2f ms  %6.3f ns/elem  %5.2f cyc/elem(@3.5GHz)  r=%lld\n",
                    tag, sec * 1e3, sec / (double)n * 1e9,
                    sec / (double)n * 3.5e9, (long long)r);
    };

    std::printf("--- 未排序 (分支方向随机, 预测器几乎无法学习) ---\n");
    time_it("branchy / unsorted",   sum_branchy);
    time_it("branchless / unsorted", sum_branchless);

    std::sort(data.begin(), data.end());
    std::printf("--- 已排序 (前一半全不跳, 后一半全跳, 预测几乎全中) ---\n");
    time_it("branchy / sorted",     sum_branchy);
    time_it("branchless / sorted",  sum_branchless);
    return 0;
}

【代码做什么？】

1. 用 xorshift 生成 4×10⁷ 个均匀分布于 0..255 的字节，保证 d[i] >= 128 大约一半为真、且彼此独立——这正是分支预测器最讨厌的模式（没有可学习的规律）。
2. 先对未排序数据跑 sum_branchy 与 sum_branchless，再 std::sort 后跑同样的两个函数（排序后分支行为变成”长段全不跳 + 长段全跳”，预测器能学得很好）。
3. 由于结果与顺序无关（加法可交换），排序不改变正确性，只改变分支的动态行为——这正是讲义所说”依据随机数据分支”的可控实验版本。

【并行机制与性能解说】

• 硬件上发生了什么：sum_branchy 的循环体里有一条数据相关分支。当数据未排序时，处理器每两次迭代就会误预测一次；每次误预测要冲刷流水线并从正确路径重取指，代价约 15–20 个周期。排序之后，同样的分支几乎全中，误预测惩罚消失。
• branchless 版本：条件表达式被编译成 cmov（或 SIMD 掩码），没有任何控制冒险。它在未排序数据上应当明显快于 branchy，而在排序数据上两者接近——这个”排序后差距消失”的现象，是判断”瓶颈到底是分支还是数据依赖”的关键证据。

• Work / Span / 并行度分析（N 次迭代）：

  版本	Work	Span	并行度
  sum_branchy（预测正确）	N 次比较 + N 次加法（+ 若干）	N·L_add + N·L_branch_ok	≈ 1
  sum_branchy（未排序）	同上	N·L_add + (N/2)·P_mispredict	≈ 1，且 Span 被放大
  sum_branchless	N 次比较 + N 次条件选择 + N 次加法	N·L_add	≈ 1

  取 N = 4×10⁷、f = 3.5 GHz、L_add = 1 周期（累加是短延迟）、P_mispredict ≈ 17 周期、误预测率 = 50%：

  • 理想（无分支代价）：4×10⁷ 周期 ≈ 11 ms
  • 加上误预测：4×10⁷ + 2×10⁷×17 = 3.8×10⁸ 周期 ≈ 109 ms
  • → 仅一个数据相关分支就能让这个内核慢 ~10 倍，而它的并行度始终是 1（s 的依赖链），所以即使有 16 个核可以帮忙，也不会有任何加速——除非改变算法（例如分块并行 + 树形归约）。
• 瓶颈诊断：这是控制冒险主导的场景。讲义给出的”分支预测准确率 >95%”是针对典型整数程序的平均值；对随机数据分支则接近 50%——预测器失效。此时 OoO 无能为力，因为乱序执行也无法越过一条它不知道目的地何时才确定的分支（分支解析前，后端根本不知道该执行哪些指令）。
• 工程结论：对这类内核，正确做法是去分支（branchless）或数据重排，而不是加核、加 SIMD 宽度或调 OoO 参数。

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

本节用讲义与补充讲义给出的数字，把第 2、3 节的定性结论算成具体数字。

4.1 机器参数假设（全部取自讲义/补充讲义）

4.2 算例 A：多项式循环的延迟界 vs 吞吐界（讲义的完整推理）

循环体 5 条指令：ldr(2c)、cmp(1c)、mla(3c)、mul(2c)、bne(1c)。

• 延迟界：跨迭代关键路径是 mla 链（每次 mla 依赖上一次的 r0）：3 周期/迭代。此时 IPC = 5/3 ≈ 1.67（完美流水线是 1）。
• 吞吐界：每轮需要 1 条 mla + 1 条 mul，若只有一个乘法类端口，两条乘法的发射占用是 2 + 3：吞吐界 = (1 mla + 1 mul) / (2 + 3 周期) = 5 周期/迭代，此时 IPC = 5/5 = 1.0。
• 实际性能 ≈ max(3, 5) = 5 周期/迭代：这就是讲义”结构冒险把一轮压成 5 个周期”的定量来源。
• 若把乘法端口增加到 2 个（或让 mla/mul 分配在不同端口）：吞吐界降到 ≤3，程序重新变成延迟受限，回到 3 周期/迭代。

结论：同一段代码的瓶颈可以在”延迟界”和”吞吐界”之间切换，取决于发射宽度、端口数量、以及关键路径长度。判断当前处于哪一侧，是优化的第一步。

4.3 算例 B：为什么需要硬件多线程——Little 定律与在途窗口

Little 定律（Little’s Law）：要在给定延迟下维持给定吞吐，必须有足够的”在途工作”：

   在途工作数  =  延迟  ×  目标吞吐

• 只靠 OoO 单线程：目标是每周期发射 4 条指令（IPC = 4），一次 DRAM 访问的延迟是 248 周期，那么需要

  在途指令数 = 248 周期 × 4 条/周期 = 992 条
  

  而讲义指出高性能 OoO 的缓冲”hundreds of instructions”（数百条）。992 > 数百 ⇒ 单线程 OoO 无法隐藏一次完整的 DRAM 缺失。这也解释了讲义给出的经验数：”4 宽 × 20 级流水线 = 80 条在途”——离 992 差一个数量级。

• 用硬件多线程补足：若每个线程的模式是”3 条算术 + 1 次 12 周期 load”，单线程的端口利用率只有

  利用率 = 3 / (3 + 12) = 20%
  

  需要的线程数 = ⌈(3 + 12) / 3⌉ = 5 个线程才能到 100%。（补充讲义给了完全相同的示例与答案。）把模型推广到真实 DRAM 延迟 248 周期、每次访存携带约 15 个周期的算术工作：

  线程数 = ⌈(15 + 248) / 15⌉ = ⌈17.5⌉ = 18 个线程
  

  这就是 GPU 一个 SM 里塞 64 个 warp 上下文、CPU 上跑 SMT + 多核的定量理由。

• 关键性质（讲义强调）：多线程没有改变访存延迟，它只是让延迟不再导致处理器停机。这就是”吞吐导向（throughput computing）”的根本权衡：允许单个线程的完成时间变长，以换取系统整体吞吐提高。

4.4 算例 C：算术强度与 Roofline——什么时候 ILP 完全无用

取一台”16 核 × 8 宽 SIMD × 2（FMA）× 3.0 GHz”的机器：

峰值算力 = 16 × 8 × 2 × 3.0e9 = 768 GFLOP/s (单精度)

取内存带宽 = 20 GB/s，则机器的平衡点（ridge point）：

ridge = 768 GFLOP/s ÷ 20 GB/s = 38.4 FLOP/byte

现在看一个典型内核：遍历一个 256 MB 的 double 数组，每个元素做 1 次 FMA。

• 访存量：256 MB = 2.56×10⁸ B；元素数 = 2.56×10⁸ / 8 = 3.2×10⁷ 个 double。
• 计算量：3.2×10⁷ × 2 FLOP（1 FMA = 2 FLOP）= 6.4×10⁷ FLOP = 64 MFLOP。
• 纯计算的理想时间：64×10⁶ / 768×10⁹ = 83 µs。
• 纯访存的下限时间：2.56×10⁸ B / 20×10⁹ B/s = 12.8 ms。
• 算术强度：2 FLOP ÷ 8 B = 0.25 FLOP/byte，远低于平衡点 38.4。
• 有效性能上限：20 GB/s × 0.25 FLOP/B = 5 GFLOP/s，仅峰值的 0.65%。

结论：这个内核比”纯计算时间”慢 154 倍，而且再多核、再宽的 SIMD、再深的 OoO 窗口都无济于事——瓶颈是 DRAM 带宽。Roofline 的判据非常直接：

   算术强度 < ridge 点  =>  带宽受限 (bandwidth-bound)，优化目标是减少访存/提高复用
   算术强度 > ridge 点  =>  计算受限 (compute-bound)，此时才轮到 ILP/SIMD/多核发力

把同样的分析套回第 3 节的 omp_sum：其算术强度是 1 FLOP / 8 B = 0.125 FLOP/byte，所以无论用多少线程，实测都会停在”800 MB ÷ 带宽”那个数量级（约 21–40 ms），而不会接近”0.52 ms”的理想延迟界。

4.5 算例 D：Amdahl 定律与”每核效率”的复合效应

设程序中可并行部分占 p = 0.95，串行部分 s = 0.05，用 T 个核：

   Speedup(T) = 1 / (s + p/T)

   T = 16 :  1 / (0.05 + 0.95/16) = 1 / 0.1094 = 9.15x
   T = 64 :  1 / (0.05 + 0.95/64) = 1 / 0.0648 = 15.4x
   T ->  ∞:  1 / 0.05             = 20x      <-- Amdahl 上限

再把”每核效率”叠进去：如果每核因为延迟界只能达到 IPC = 1.67，而机器峰值是 4 宽（IPC = 4），则每核效率只有 42%。于是 T = 16 时的真实加速比 ≈ 9.15 × 0.42 ≈ 3.8×。

这一条把本讲与课程整体串起来了：并行加速比不仅是”核数”和”串行比例”的函数，还受每个核内部的 ILP 效率（延迟界/吞吐界）制约。OoO 好，是为了让这个 0.42 尽量接近 1；多核好，是为了让 T 尽量大。两者不可偏废。

4.6 算例 E：超标量调度复杂度与流水线深度的双重上限

讲义给出的两个硬件开销公式：

   调度复杂度      = O(W^2)              W = 发射宽度
   控制冒险惩罚    = O(N_pipeline)        每次误预测约丢弃 N 级在途指令
   在途指令数      = W × N_pipeline

• W = 4、N = 20 ⇒ 在途 80 条指令，调度要比较 C(4,2) = 6 对寄存器组。
• W = 8、N = 20 ⇒ 在途 160 条，比较 28 对——复杂度增长 4.7 倍，而讲义明确说”即便完美调度，>8 宽也没有帮助”。
• 若平均每 20 条指令就遇到一次误预测（即每个分支都猜错，随机数据分支的典型情形），每次损失 20 个周期：理想情况 4 宽机器发射 20 条指令只需 5 周期，实际需要 5 + 20 = 25 周期 ⇒ 有效 IPC = 20/25 = 0.8，W = 4 的收益被完全吃掉（甚至不如单发射）。

结论：ILP 的三个上限——程序本身 ILP 有限（~8 宽）、流水线深度有限（N≈15）、调度复杂度 O(W²)——共同把单核性能封了顶。这正是讲义结尾”Limitations of ILP → Multicore”的完整论证。

5. 关键要点

1. 流水线只提高吞吐，不降低延迟；N 级流水线最多带来 N× 吞吐，但受数据/控制/结构三类冒险制约，实际上在 N≈15 附近触顶。旁路转发能消除大多数（不是全部）数据冒险停顿，而它在深流水线中本身成本高昂；分支冲刷的代价随深度线性增长。

2. 乱序执行 = “按数据流顺序执行 + 保持顺序执行的幻觉”。指令只按程序序进入和离开指令缓冲/ROB，中间完全乱序；前端与提交端被超额配置，因此程序员通常只需关注执行阶段，唯一例外是本质上不可预测的控制流。

3. 性能分析用两个界，取慢的那个：延迟界 = 跨迭代关键路径（拆依赖链才能改善），吞吐界 = 操作数 / 执行端口发射率（加端口或换更宽的 SIMD 才能改善）。OoO 让这套分析比 in-order 机器简单得多，也让性能在不同微架构间的可移植性更好。

4. 寄存器重命名消灭伪依赖（WAR/WAW），只保留真依赖（RAW）；数据流视角是理解乱序、推测与编译器重排的统一语言。真依赖构成的关键路径无法被任何硬件技巧绕过，只能由程序员/编译器改写算法来缩短。

5. ILP 撞墙的直接后果是多核：程序 ILP 有限（>8 宽无益）、流水线不能更深、频率受功耗限制、OoO 调度是 O(W²)。工业界的答案是”简化微架构、增加核数、并用硬件多线程（SMT）与 SIMD 填补每核的利用率空洞”，代价是并行软件更难写。当代码进入带宽界（算术强度低于 Roofline 平衡点）时，上述一切硬件技巧都失效，唯一的出路是提高数据复用。

6. 常见陷阱与注意事项

• 把”流水线”误解为”降低延迟”：N 级流水线不改变单条指令的端到端延迟（仍是 N·t），只提高稳态吞吐。若程序只有极少量指令（或每次都要冲刷），流水线反而带来更差的启动/排空开销。同理，“IPC = 4” 的机器不等于单线程快 4 倍，它取决于程序里有没有 4 条独立指令可发射。

• 以为”乱序执行 = 可以放心写串行代码”：OoO 只能利用真实存在的 ILP。第 3 节示例一证明，一条 8192 长的严格依赖链在任何 OoO 宽度下都只能得到约 1 的 IPC，把关键路径砍半（双链）才能拿到 2× 加速。OoO 降低了对”指令调度技巧”的依赖，但不解决算法级的依赖结构问题。

• 用”平均分支预测率 >95%”推断自己的程序：数据相关分支（随机、哈希、压缩、稀疏矩阵遍历、图算法中的条件插入）会退化到约 50% 命中率，每次误预测丢弃 15–20 个周期，足以造成 10 倍量级的差距。此类内核应改写为无分支（branchless / cmov / 掩码）或数据重排，而不是指望硬件或加核。

• 忽视延迟界与吞吐界的切换，盲目优化：给一个延迟受限的内核加核、加 SIMD 宽度、堆更多线程，收益为零甚至为负；对一个吞吐受限的内核去”拆分依赖链”同样白费。正确顺序永远是：先判断处在哪一侧（第 4.2 节的两条公式），再选择对应的优化手段。

• 只算 FLOPs 而不算字节数（忽略带宽）：第 4 节算例 C 中，算术强度 0.25 FLOP/byte 的内核只能发挥 0.65% 的峰值算力。报告”我的程序达到了 X GFLOPS”之前，必须同时报告”它搬了多少字节、实际带宽是多少”，否则该数字毫无意义。同理，”我的并行程序有 16 个线程”不等于”16 倍加速”——先看它是不是带宽受限。

• 为并行而破坏访存局部性 / 引入伪共享或数据竞争：为了让累加器线程私有而改用 stride = 线程数 的跨步访问，会摧毁预取与 DRAM 行局部性，带宽可能腰斩；反过来，为图省事让多线程写同一个缓存行里的不同变量（例如 struct { long cnt[N]; } 相邻元素）会触发伪共享（false sharing），每一次写都让别的核的缓存行失效。多线程写共享累加器时还应避免用 #pragma omp atomic/互斥锁做热路径累加（串行化 + 缓存行乒乓），应使用每线程私有副本 + 末尾归约（如 reduction(+:)）。

• 错误理解内存序与编译器优化边界：OoO 硬件重排的是单线程内的指令，多线程之间的可见性由内存序（memory ordering） 与同步原语决定——写一个 volatile 变量不构成同步，也不能替代 acquire/release 或锁。另一方面，-O3 -ffast-math 会让编译器重结合浮点运算（可能自动把你精心构造的串行链变成并行链，或反之改变结果），做性能实验或要求逐位可复现时必须显式关闭它。

7. 思考题（带答案）

思考题 1：判断延迟界与吞吐界

某机器的循环体如下（每轮 4 条指令），执行端口配置为：1 个整数端口（cmp、bne 各占 1 周期）、1 个乘法端口（mul 占 2 周期）、1 个 FMA 端口（fma 占 1 周期发射、4 周期延迟）：

loop:
  fma   f0, f2, f4, f0     // acc = acc + w * x   (延迟 4 周期, 依赖上一轮的 f0)
  addi  r3, r3, 4          // 指针推进
  cmp   r3, r1             // 边界比较
  bne   loop

问：(a) 延迟界是多少周期/迭代？(b) 吞吐界是多少周期/迭代？(c) 实际性能约为多少，IPC 是多少？(d) 如果程序需要跑 10⁶ 次迭代，在 3.0 GHz 下大约耗时多久？

【答案】

(a) 延迟界：跨迭代的真依赖只有 fma 链（f0 依赖上一轮的 f0），addi/cmp/bne 的链长都是 1 周期且远短于 FMA 链。所以关键路径 = 4 周期/迭代。

(b) 吞吐界：把每类操作的需求量除以对应端口的服务能力：

• FMA 端口：1 条 fma / 1 周期 = 1 周期
• 乘法端口：本轮没有 mul = 0 周期

• 整数端口：addi + cmp + bne = 3 条整数操作，端口 1 条/周期 = 3 周期

  吞吐界 = max(1, 0, 3) = 3 周期/迭代。

(c) 实际性能 ≈ max(延迟界, 吞吐界) = max(4, 3) = 4 周期/迭代，即 延迟受限。IPC = 4 条指令 / 4 周期 = 1.0。

(d) 10⁶ 迭代 × 4 周期 = 4×10⁶ 周期；在 3.0 GHz 下 = 4×10⁶ / 3×10⁹ s ≈ 1.33 ms。

追问：如果给这台机器再加一个整数端口（整数吞吐变成 2 条/周期），会变快吗？不会——吞吐界变成 max(1, 0, 1.5) = 1.5 周期，仍小于延迟界 4 周期，程序依旧是延迟受限，性能不变。只有缩短 FMA 依赖链（例如用 2 个累加器交替累加、循环结束后合并）才能提速：2 个累加器把 FMA 链变成 2 周期/迭代，此时瓶颈切换到吞吐界的 3 周期/迭代，性能从 4 → 3 周期/迭代，提升 1.33×；再用 4 个累加器则 FMA 链 1 周期/迭代 < 3 周期，彻底变成吞吐受限，无论如何加速比都止步于 4/3 ≈ 1.33×。这就是”延迟界与吞吐界在优化过程中会互相转换”的典型例证。

思考题 2：为什么单核 OoO 掩盖不了 DRAM 延迟？

某处理器：发射宽度 W = 4 条指令/周期，ROB 可容纳 256 条指令，一次 DRAM 访问延迟 248 周期（@4 GHz），程序在两次访存之间有约 20 条相互独立的指令。

问：(a) 用 Little 定律计算，要维持 IPC = 4 需要多少条指令在途？(b) 该机器能提供多少？(c) 如果你是架构师，有哪三种手段补上这个缺口，各自代价是什么？

【答案】

(a) Little 定律：在途指令数 = 延迟 × 目标吞吐 = 248 周期 × 4 条/周期 = 992 条指令。

(b) 该机器只有 256 条 ROB 条目，仅能支撑 992 条的约 26%。等效地，可持续的吞吐 ≈ 256 / 248 ≈ 1.03 条/周期，即 IPC 掉到约 1——发射宽度 4 的硬件在这里只发挥了 1/4。

(c) 三种手段：

1. 硬件多线程（SMT / interleaved multithreading）：在同一核上放 2–8 个执行上下文，A 线程等 DRAM 时发射 B 线程的指令。缺口 992 条需要约 992/256 ≈ 4 个线程（或按”每次访存携带 20 条独立指令”的模型：⌈(20+248)/20⌉ = 14 个线程才达 100% 利用率——这正是 GPU 一个 SM 放 64 个 warp 的原因）。代价：每个上下文的寄存器/存储开销，芯片面积与功耗；单线程的完成时间变长（吞吐导向的权衡）。
2. 增加 ROB 深度 / 重命名寄存器数：把窗口从 256 扩到 1024。代价：面积与功耗按超线性增长，且调度复杂度与唤醒逻辑（wakeup/select）本身成为关键路径，频率会被拖低——讲义明确指出”动态调度开销显著”。
3. 提高缓存命中率 / 软件预取：把 248 周期的 DRAM 延迟换成 L2 的 12 周期，缺口立刻变成 12×4 = 48 条，256 条的 ROB 绰绰有余。代价：需要程序员或编译器做分块（tiling）/ 预取 / 提高数据复用，改动算法结构；且缓存不命中的最坏情形仍存在。

补充结论：手段 3 是唯一不依赖硬件的，也是本课程反复强调的”利用局部性”。硬件手段 1 和 2 都直接消耗面积/功耗，而片上的功耗预算有限——这正是”ILP 撞墙、转向多核”的经济学根源。

思考题 3：一个 ILP 优化为什么在双核上几乎没加速？

程序 A：对一个 512 MB 的数组做 out[i] = f(in[i])，f 是 20 次浮点运算，in 和 out 都是 double。 某同学做了两项优化：（i）把 f 内部原本串行的表达式重排，使关键路径从 20 次 FMA 降到 5 次；（ii）用 OpenMP 把数组分给 2 个线程。 机器：2 核 × 8 宽 SIMD × 2（FMA）× 3.0 GHz（峰值 96 GFLOP/s 单精度；double 视为一半 = 48 GFLOP/s），DRAM 带宽 20 GB/s。

问：(a) 计算这个内核的算术强度。(b) 分别计算”带宽下限时间”与”双核计算下限时间”（元素数按 512 MB / 8 B = 6.4×10⁷）。(c) 预测优化 (i) 和 (ii) 各自的实际收益，并解释为什么”关键路径砍到 1/4”几乎没有帮助。

【答案】

(a) 算术强度：每个元素 20 FLOP，访存 8 B 读 + 8 B 写 = 16 B。

   AI = 20 FLOP / 16 B = 1.25 FLOP/byte

机器平衡点 = 48 GFLOP/s ÷ 20 GB/s = 2.4 FLOP/byte。1.25 < 2.4 ⇒ 带宽受限。

(b) 元素数 N = 512 MB / 8 B = 6.4×10⁷。

  带宽下限时间 = 总字节 / 带宽 = (6.4e7 × 16 B) / 20e9 B/s = 1.024e9 / 20e9 = 51.2 ms
  计算下限时间(2 核)  = 总 FLOP / 峰值 = (6.4e7 × 20) / 48e9 = 1.28e9 / 48e9 = 26.7 ms
  计算下限时间(1 核)  = 53.3 ms

带宽下限 51.2 ms 大于双核计算下限 26.7 ms ⇒ 用 2 个核时，程序卡在 51.2 ms 附近。

(c) 预测：

• 优化 (ii)（双核）：串行版受限于 1 核计算下限 53.3 ms（略大于带宽下限 51.2 ms），所以理论上限约 53.3/51.2 ≈ 1.04×……但由于单核实际很难达到理论峰值（延迟界、发射宽度、SIMD 利用率），串行版实测大概率在 70–90 ms，双核能压到约 51 ms 的带宽墙，实测约 1.4–1.7×，而非 2×。
• 优化 (i)（关键路径从 20 降到 5）：几乎没有帮助。原因是该内核的瓶颈是带宽（AI = 1.25 < 2.4），算术运算早就”藏在”访存后面了；而且 20 次 FMA 分布在 8 宽 SIMD 上只需要约 2.5 条向量指令，关键路径缩短带来的 ILP 收益根本无法越过 51.2 ms 的带宽地板。

诊断方法论：拿到任何内核，先算 AI 与 ridge point：

• AI < ridge ⇒ 先做带宽优化：数据复用（分块/融合循环）、减小数据宽度（float 代替 double、必要时量化）、避免多余的写-读往返（例如 a = a + b 就地运算，而不是 c = a + b 再拷贝）、提高访存连续性以吃满 DRAM 行缓冲。
• AI > ridge ⇒ 才轮到计算优化：缩短关键路径（抬升延迟界）、增加并行度（抬升吞吐界）、扩大 SIMD 宽度。

本讲（ILP/OoO）提供的全部是第二类工具；用错类别的优化，收益为零，这正是第 6 节”常见陷阱”中最贵的一条。

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;
}