CS149 并行计算工程课

01. Why Parallelism? Why Efficiency?

第一讲先拆掉一个直觉：程序变快并不只是等硬件升级。频率、功耗和单核指令级并行都遇到上限后，性能增长转向并行计算。并行计算带来的也不是免费加速，而是一整套关于串行部分、数据搬运和同步成本的账本。

1. 为什么单核继续加速变难

早期软件常常受益于处理器频率提升。同一段代码不改，下一代 CPU 也许就更快。但功耗密度、散热和电压缩放让这条路越来越窄。处理器还能做乱序执行、分支预测、流水线和向量化，但单线程里的可挖空间有限。

所以硬件把更多晶体管预算放到多核、SIMD lane、GPU SM 和专用加速器上。代价是软件必须显式或半显式地表达并行性。一个串行程序如果没有独立工作、没有合适的数据布局、没有可控同步，硬件资源会闲着。

2. speedup 的上限由串行部分决定

Amdahl's Law 是这门课的第一把尺。假设程序中比例为 s 的部分必须串行，剩余部分可以在 p 个处理单元上并行，那么理想加速近似是：

如果 10% 必须串行，即使给 100 个 core，理想加速也只有大约 9.17 倍。真实程序还会有调度、通信、cache miss 和负载不均，所以结果通常更低。这个公式的价值不在精确预测，而在逼你先问：串行部分到底在哪。

3. 对 AI 系统的含义

大模型训练和推理都喜欢用“多少 GPU”描述规模，但 GPU 数字只是表面。真正的问题是：前处理、调度、网络通信、KV cache 访问、kernel launch、同步点、后处理和日志写入里，哪一段无法并行或无法被隐藏。

Agent 系统尤其容易踩这个坑。你可能把模型调用并发度调高，却发现端到端任务没有明显变快，因为工具调用串行、状态存储排队、或者每一步都要等上一步输出。第一讲的判断力就是：先找不可并行的链路，再谈扩容。

02. A Modern Multi-Core Processor (Part I)

第二讲建立机器模型：现代处理器里同时存在多核、SIMD、硬件多线程和多级缓存。并行程序的性能不是“线程越多越好”，而是计算单元、数据路径和内存层级能否配合。

1. 多核、SIMD、硬件线程解决的问题不同

多核让不同 core 同时执行不同指令流，适合任务之间相对独立的场景。SIMD 是一条指令作用在多个数据 lane 上，适合同一个操作应用到一批数据。硬件多线程则用多个执行上下文隐藏等待，例如一个线程等内存时切到另一个线程。

这三者经常同时存在。一个 CPU 可以有多个 core，每个 core 有 SIMD 指令，每个 core 还可能支持多硬件线程。GPU 更进一步，把大量轻量线程组织成 warp，用 SIMT 的方式执行。

2. 并行效率常被内存限制

处理器算得很快，但主存访问很慢。cache 层级就是为了把常用数据放近一点：L1 小而快，L2/L3 更大但更慢，主存更远。程序如果访问模式混乱，cache miss 会让 core 等数据，算力就用不满。

3. 分支会伤 SIMD

SIMD lane 最喜欢所有元素走同一条路径。如果一半元素走 if 分支，一半走 else 分支，硬件可能要分两批执行，未参与当前路径的 lane 空转。源码里看起来只是普通分支，硬件上却变成有效吞吐下降。

这解释了很多高性能代码的写法：数据先重排，分支变成 mask，热路径单独处理，边界条件放到后面。代码可读性和硬件友好性之间有取舍。

03. Modern Multi-Core Architecture (Part II) + ISPC

第三讲用 ISPC 训练一种写法：代码看起来像标量程序，但执行时是一组 program instances 同步运行。它让你感受到抽象和硬件之间的距离，也让 SIMD 的成本变得可见。

1. latency 和 bandwidth 要分清

latency 是一次访问从发出到拿到结果要多久。bandwidth 是单位时间能搬多少数据。一个系统可能 latency 很高但 bandwidth 很大，也可能 latency 低但带宽很小。并行程序经常通过并发请求隐藏 latency，通过连续访问榨出 bandwidth。

矩阵乘法和流式数组处理的优化方式不同，就因为它们的 arithmetic intensity 不同。前者每搬一块数据能做很多乘加，后者可能只是读一个数、改一下、写回。

2. ISPC 的 mental model

ISPC 采用 SPMD 风格：你写的是“每个 program instance 做什么”，编译器把多个 instance 组成 gang，映射到 SIMD lane。它不像手写 intrinsics 那样直接操作向量寄存器，但底层仍然受 SIMD 限制。

foreach (i = 0 ... n) {
    y[i] = a * x[i] + y[i];
}

这段代码看起来像普通循环，但每个 instance 处理不同元素。只要访问连续、分支少、工作均匀，SIMD lane 就更容易满载。反过来，如果每个元素访问随机指针或走不同路径，抽象不会自动救性能。

3. 抽象层越高，越要保留机器直觉

Python、PyTorch、SQL、Spark、Triton 和 serving runtime 都会隐藏执行细节。隐藏细节可以提高开发速度，但性能出了问题时，你必须回到机器：数据是否连续，批次是否足够大，是否生成了过多 kernel，是否在做不必要同步。

ISPC 的价值正在这里。它让你看到“并行表达”和“硬件实际执行”不是同一件事。

04. Parallelizing Code: An Example Thought Process

第四讲不急着给 API，而是训练并行化的思考顺序。拿到一段串行代码，先找独立工作、依赖、共享状态和数据布局，再决定线程、任务、SIMD 或 GPU。

1. 先画依赖图

并行化的第一步是问：哪些计算必须等前一步，哪些可以同时做。循环不一定能并行，递归也不一定不能并行。你要看每次迭代读写的数据是否互相依赖，是否存在 reduction，是否有顺序语义。

一个简单的数组 map 基本天然并行。一个前缀和看似每个位置依赖前一个位置，但可以用树形算法改写。一个带共享 hash map 写入的循环，则要考虑冲突、锁或先分桶再合并。

2. 粒度太细会被调度成本吞掉

把每个元素丢给一个任务，听起来并行度很高，实际常常很慢。任务创建、入队、出队、同步和 cache 迁移都有成本。好的切分会让每个 worker 拿到足够大的 chunk，同时避免最后几个慢任务拖住全局。

3. reduction 是共享状态的常见解法

很多串行代码慢在一个共享变量上，例如计数、求和、最大值、直方图。直接加锁会让所有线程排队。更常见的做法是每个 worker 先算局部结果，最后再合并。这个模式牺牲一点额外内存，换来少得多的同步。

05. Program Optimization 1: Work Distribution and Scheduling

第五讲关注工作如何分给处理单元。并行程序经常不是算得慢，而是有人忙到最后，有人早早空等。调度策略决定这种空等能不能被减少。

1. 静态调度和动态调度

静态调度在开始时把任务分好，开销低，适合每个任务成本差不多的情况。动态调度在运行时分配任务，更能处理不均匀工作，但要付出队列、锁或原子操作成本。

没有一种调度方式永远最好。如果图像中每个 tile 成本相近，静态划分可能更快。如果某些 tile 很复杂、某些很空，动态调度能减少尾部等待。

2. work stealing 的思想

Cilk 这类系统常用 work stealing：每个 worker 有自己的双端队列，平时从本地拿任务；本地没活时，从其他 worker 偷任务。这样常见路径少竞争，只有空闲时才跨队列协调。

它适合 fork-join 和任务树。理论上，work 和 span 可以描述并行程序的下限：work 是总工作量，span 是最长依赖链。调度再聪明，也不能突破 span。

3. 在线推理里的同类问题

LLM serving 里的 continuous batching 也是调度问题。请求长度不同、输出长度不同、优先级不同，GPU 上的 batch 会不断变化。系统要在吞吐、首 token 延迟、尾延迟和公平性之间取舍。

06. Program Optimization 2: Locality and Communication

第六讲把性能问题从“算多少”转向“数据怎么移动”。数据越远，访问越贵；通信越频繁，并行收益越容易被吃掉。

1. 局部性有两种

时间局部性是同一数据短时间内反复使用。空间局部性是访问一个地址后，很快访问它旁边的地址。cache 主要靠这两点工作。高性能代码会通过 tiling、blocking、layout 改写，让数据进入 cache 后尽量多用几次。

矩阵乘法的 block 优化就是典型例子。一次搬入 tile 后，在寄存器或 cache 中做很多乘加，比每次都去主存拿单个元素更划算。

2. 通信可以减少，也可以隐藏

跨线程、跨进程、跨节点通信都比本地访问贵。优化有两条路：减少通信量，或者把通信和计算重叠。message passing、non-blocking send/recv、pipeline 都是围绕这个目标设计的。

3. AI kernel 的共同主题

FlashAttention、fused MLP、fused layernorm、paged KV cache 看起来分属不同系统，其实都在处理数据移动。很多优化没有改变数学结果，只是让中间 tensor 少写回 HBM，或者让 cache 中的数据复用更多。

07. GPU Architecture and CUDA Programming

第七讲进入 GPU。GPU 的强项是用大量线程跑高吞吐数据并行计算。它不是更快的 CPU；它牺牲了复杂控制流能力，换取更多计算单元和更高内存带宽。

1. CUDA 的层级

CUDA 程序用 grid、block、thread 描述工作。block 会被调度到 SM 上，thread 以 warp 为单位执行。warp 中的线程执行同一指令流，但每个线程有自己的寄存器和数据。

2. 影响 GPU kernel 的几个变量

• Occupancy：SM 上活跃 warp 是否足够多，用来隐藏内存延迟。
• Coalescing：相邻线程是否访问连续地址，以减少内存事务。
• Shared memory：block 内线程共享的快速内存，常用于 tile 复用。
• Warp divergence：同一 warp 内线程走不同分支，会降低有效吞吐。
• Atomics：解决并发写，但高冲突会让线程排队。

3. GPU 优化不能只看利用率

一个 kernel occupancy 高，仍可能慢，因为每个线程做的有用计算少，或者访存不连续。一个 kernel occupancy 不满，也可能很快，因为它受寄存器或 shared memory 限制，但 arithmetic intensity 高。你需要 profiler 指标，而不是单个“GPU usage”。

08. Data-Parallel Thinking

第八讲把 GPU 编程从硬件细节拉回算法原语。map、reduce、scan、scatter、gather、sort、groupByKey 是数据并行程序的常见积木。很多复杂任务都可以拆成这些原语的组合。

1. 三个基础原语

map 对每个元素独立执行同一函数。reduce 把很多元素合成一个值，前提通常是操作可结合。scan 为每个位置计算前缀结果，它比普通求和更能体现并行算法设计，因为每个位置都要输出。

2. 数据重排也是计算的一部分

并行程序常常先把数据整理成硬件喜欢的形状。groupByKey、sort、compact、partition 这些操作本身可能很贵，但它们能让后续计算少分支、少冲突、访问更连续。

这和训练/推理系统里的 batching 很像。请求进入模型前要按长度、模型、优先级或 cache 命中情况组织；组织本身有成本，但能换来更高吞吐。

3. prefix sum 的意义

prefix sum 常用于 stream compaction、radix sort、稀疏数据布局和动态分配。它把“每个元素输出位置取决于前面元素”的顺序依赖，改写成树形上扫和下扫。这个例子说明：并行算法的核心经常是重新表达依赖，而不是机械加线程。

09. Efficiently Evaluating DNNs on GPUs

第九讲连接 AI 和并行计算。神经网络推理看起来是模型问题，落到 GPU 上会变成矩阵乘法、访存、kernel 调度、融合和 batch 的问题。

1. DNN 层为什么常映射到 GEMM

全连接层天然是矩阵乘法。卷积可以通过 im2col 或直接卷积 kernel 变成类似矩阵乘法的计算。Transformer 的 attention 和 MLP 也包含大量矩阵乘。硬件厂商会为这类 dense linear algebra 做深度优化，例如 tensor core。

但“都是矩阵乘”不代表性能相同。矩阵形状、batch size、精度、layout、是否有小 batch、是否频繁启动小 kernel，都会改变实际速度。

2. fusion 的收益来自少搬数据

如果 layer A 输出一个大 tensor，再由 layer B 读取，中间结果要写回 HBM 再读出。fusion 把多个操作放到一个 kernel 或一个调度单元里，减少中间结果往返。LayerNorm、bias、activation、dropout、residual add 都常被融合。

3. LLM 推理的两类阶段

prefill 处理已知 prompt，矩阵更大，更像训练时的大批计算。decode 每次只生成一个 token，容易受权重读取和 KV cache 读取限制。CS149 的 DNN 推理章节和 CS336 的 inference 章节在这里接上。

10. Hardware Specialization

第十讲讨论专用硬件。GPU 已经比 CPU 专用，但 AI 加速器会进一步把硬件资源押在少数高频计算模式上，以换取能效和吞吐。

1. 专用化换来的是什么

通用处理器要支持复杂控制流、异常、系统调用和广泛指令。专用加速器可以减少这些通用能力，把面积和功耗放在矩阵乘、片上缓存、数据搬运和低精度计算上。systolic array、dataflow accelerator、NPU 都围绕这个思路。

收益是高能效。代价是灵活性下降：不支持的算子会走慢路径，动态 shape 可能麻烦，编程系统也更复杂。

2. 片上存储比峰值算力更实在

很多加速器设计的中心是数据复用。权重、activation 或 tile 能留在片上，就少走昂贵的片外内存。低精度也有双重收益：存储更小，带宽压力更低，专用乘加单元能塞更多。

3. 选硬件要看 workload

训练、大 batch 推理、小 batch 交互推理、端侧视觉、语音唤醒、推荐召回都不是同一个 workload。AI Infra 的硬件选择不能只看峰值 FLOPs，而要看模型 shape、精度、batch、内存、网络和软件栈。

11. Programming Systems for Specialized Hardware

第十一讲回答一个现实问题：有了加速器，为什么还需要编译器、DSL 和 runtime。硬件只有被正确映射，才能变成可用性能。

1. 算法和调度要分开

同一个矩阵乘、卷积或 attention，可以有很多实现方式：tile 多大、循环顺序如何、数据 layout 如何、是否展开、是否用 shared memory、是否融合后续操作。高层算法只说明算什么，调度说明怎么在硬件上算。

TVM、Halide、Triton、XLA、MLIR 等系统都在尝试保留足够的计算语义，同时暴露或搜索调度空间。程序员不用手写所有汇编，但仍能影响硬件映射。

2. 自动调优需要目标和验证

autotuning 会尝试不同 tile、block、vectorize、unroll、layout 等参数。它必须有 benchmark，也必须保证语义正确。否则搜索出的“最快版本”可能只是测量噪声，或者偷偷改变结果。

3. 抽象也会制造诊断困难

高层系统提速时很好用；出问题时，你要能看生成 kernel、profiling trace 和内存访问。编译器不是魔法，它只能优化它理解的结构。如果动态图、Python 控制流或不规则算子让结构不可见，编译器空间就会缩小。

12. Mapping AI Applications to the Datacenter Computer

第十二讲把单机扩展到数据中心。对 AI workload 来说，数据中心不是一堆独立服务器，而是一台由 GPU、CPU、内存、网络、存储、调度器和服务目标组成的大机器。

1. 机器边界会变大

单机上，“近”可能是 L1、L2、NUMA 远端内存。集群里，“近”可能是同 GPU、同节点、同机架、同集群。每跨一层，带宽和延迟都变化。分布式训练的 all-reduce、推理的 tensor parallel、KV cache 分布、数据加载都受这个层级影响。

2. serving 是排队系统

AI serving 要同时看吞吐和延迟。batching 能提高吞吐，但会增加等待。优先级能保护交互请求，但可能降低整体利用率。长输出请求会占用 decode slot，短请求可能被拖慢。系统需要调度策略，不只是模型 API。

3. 对 Agent 平台的提醒

Agent 平台还会把工具服务、状态存储、文件系统、浏览器环境和评测器放进链路。一个任务慢，可能是模型慢，也可能是工具沙箱启动慢、网络慢、锁竞争、队列积压、日志系统写入慢。CS149 让你把“慢”拆成可测部分。

13. Domain-Specific Programming Systems and AI-Driven Performance Optimization

第十三讲很贴近你的 Agent 背景：AI 能不能帮助优化高性能代码。答案取决于是否有可执行环境、正确性测试、性能指标和回滚机制。

1. 领域专用系统缩小问题空间

通用语言什么都能写，优化空间也杂。领域专用系统限制表达方式，让编译器或搜索器知道代码是矩阵、卷积、图计算、SQL 还是数据流。限制越合适，优化器越能做出强假设。

2. AI optimizer 需要闭环

一个代码 agent 可以提出 kernel 改写、tile 参数、循环重排或融合方案。但它必须编译、运行 correctness tests、跑 benchmark、记录结果、失败回滚。没有这个闭环，优化建议只是文本。

3. 防止 benchmark gaming

如果测试覆盖不足，agent 可能生成只对样例快的代码，或者改变语义。性能任务必须固定输入分布、正确性 oracle、计时方式和硬件环境。对隐藏测试、随机 seed、冷启动和热启动也要有规定。

14. Cache Coherence

第十四讲转向共享内存正确性。多核系统里，每个 core 有自己的 cache。同一个内存地址可能在多个 cache 中有副本，coherence 协议负责让这些副本看起来一致。

1. coherence 解决什么

如果 core A 写了变量 x，core B 后续读 x，B 应该看到合理的值。cache coherence 通过状态机和消息做到这一点。MSI/MESI 这类协议会为 cache line 维护 Modified、Shared、Invalid 等状态，写入时让其他副本失效或更新。

2. false sharing 为什么烦

coherence 的粒度通常是 cache line，不是语言里的变量。两个线程写不同变量，如果变量刚好在同一个 cache line 上，它们也会互相 invalidation。源码里没有共享变量，硬件里却共享了 cache line。

3. 性能和正确性绑在一起

coherence 让共享内存编程可用，但它也会把本地写变成全局通信。高频计数器、共享队列、状态表、引用计数都可能因为 cache line 抖动变慢。优化时常见做法是分片、padding、局部聚合或减少共享写。

15. Implementing Synchronization + Memory Consistency

第十五讲说明：加锁不是并发正确性的全部。硬件和编译器会重排内存操作，memory consistency 定义多线程程序能观察到哪些顺序。

1. 锁、原子和 fence

锁提供互斥：同一时间只有一个线程进入临界区。原子操作提供不可分割的读改写，例如 compare-and-swap。fence 或 memory barrier 用来约束重排，让某些读写在其他线程看来有必要顺序。

它们都不是免费操作。锁可能阻塞，原子在高冲突下会让 cache line 来回迁移，fence 会限制硬件优化空间。

2. consistency model 是程序员和机器的合同

顺序一致性最容易理解：所有操作像按某个全局顺序执行，并且每个线程内部顺序不变。但真实硬件常采用更弱模型，允许部分重排来提高性能。程序员需要用同步原语建立 happens-before 关系。

这类 release/acquire 配对告诉系统：看到 flag 后，也应该看到 flag 之前发布的数据。

3. volatile 不是同步

很多语言里的 volatile 主要约束编译器对单个访问的优化，不保证互斥，也不保证跨线程原子性和完整内存顺序。用它替代锁或原子，是并发 bug 的常见来源。

16. Fine-Grained Locking and Lock-Free Programming

第十六讲讨论更激进的同步优化。粗粒度锁简单，但会让线程排队；细粒度锁和 lock-free 能减少等待，却让正确性证明更难。

1. 锁粒度的取舍

一个全局锁保护整个数据结构，代码容易写，但所有操作互相阻塞。把锁拆到 bucket、node 或 range，可以提高并行度。但锁越多，越容易出现死锁、漏锁、锁顺序不一致和状态跨锁不一致。

2. lock-free 不是没有同步成本

lock-free 数据结构常用 CAS。CAS 会检查内存位置是否仍等于旧值，如果是就写新值。失败说明别人改过，需要重试。它避免了传统锁等待，但高竞争下可能不断重试，cache line 也会来回迁移。

3. ABA 和内存回收

ABA 问题是：一个位置从 A 变成 B，又变回 A。CAS 看到还是 A，以为没有变化，但对象身份或相关状态已经变了。无锁链表、栈、队列还要处理节点何时能释放，避免另一个线程还握着旧指针。

17. Transactional Memory (Part I)

第十七讲介绍事务内存。它想把一段共享内存操作包装成事务：要么提交成功，要么检测到冲突后回滚重试。目标是缓解锁的可组合性问题。

1. 为什么锁难组合

两个函数各自内部加锁，单独调用没问题；把它们组合成一个更大的原子操作时，锁顺序、死锁和中间状态就出现了。事务内存希望程序员声明一段 atomic block，由系统处理冲突。

2. 乐观并发控制

事务内存通常先让事务执行，记录读集和写集。提交时检查有没有其他线程修改了相关位置。如果没有冲突，写入生效；如果有冲突，事务回滚并重试。这是乐观策略：假设冲突少，冲突时再处理。

3. STM 和 HTM

软件事务内存用 runtime 维护元数据，更灵活但开销高。硬件事务内存用 cache coherence 等硬件机制跟踪读写集，常见路径更快，但受容量、I/O 和硬件实现限制。事务不是万能锁替代品。

18. Transactional Memory (Part II) + AMA

最后一讲收束整门课。事务内存继续展示“抽象、性能、正确性”三者的张力；AMA 和 wrapup 则把并行计算重新放回工程诊断流程。

1. 事务内存的边界

事务适合冲突少、读写集可跟踪、没有不可回滚副作用的内存操作。它不适合长事务、高冲突热点、复杂 I/O 或需要精细控制失败语义的场景。和锁一样，它是工具，不是并发问题的终点。

2. CS149 的诊断顺序

学完这门课，遇到慢系统时可以按下面顺序排查：

1. 任务是否有足够并行性，串行部分在哪里。
2. 并行划分是否造成负载不均或过细调度。
3. 数据布局是否有局部性，访存是否连续。
4. 同步、原子、coherence traffic 是否吞掉收益。
5. 硬件映射是否匹配 CPU、SIMD、GPU 或加速器。
6. 测量是否覆盖平均延迟、尾延迟、吞吐和资源占用。

3. 和 CS336、6.5940 的连接

CS336 关心语言模型从数据到训练到推理的链路。6.5940 关心如何让模型更小、更快、更适合目标设备。CS149 提供底层语言：并行性、局部性、通信、同步、调度和硬件映射。三门课合起来，能让你把 AI Infra 从“模型很大所以很贵”拆成更具体的问题。