并行是大势所趋
串行性能受物理限制（光速、功耗密度），并行是唯一出路。从手机到超级计算机，并行无处不在。
CS267 · 第 1 课 · Aydin Buluc
什么是并行计算机？为什么并行计算是现代科学计算的基石？本课程从"速度"与"内存"两大需求出发，带你走进高性能计算的世界。
并行计算的核心动机可以归结为两点：
许多科学问题的计算量远超单个处理器的能力。通过将工作分配给多个处理器并行执行，我们可以将问题求解时间从数年缩短到数小时。
示例：分解 10 亿个数的质因数。若有 100 万个处理器，每个只需处理约 1000 个数。
某些科学问题的内存需求超过 100 TB。单个节点无法容纳如此庞大的数据集，必须将数据分布在多个节点的内存中。
示例：气候模拟、基因组分析、天体物理模拟等。
以加法归约为例，利用加法的结合律：
Serial: O(n) — 逐一相加
Parallel: O(log n) — 成对相加，逐层归约使用 n 个处理器，可以在对数时间内完成求和。这是并行算法设计中最基本的模式之一。
并行计算机主要有三种架构：
| 架构 | 特征 | 典型代表 |
|---|---|---|
| 共享内存 (SMP/Multicore) | 多个处理器共享同一内存空间，通过读写共享变量通信 | 多核 CPU、SMP 服务器 |
| 分布式内存 (HPC/Cluster) | 每个处理器拥有独立内存，通过高速网络通信 | 集群、超级计算机 |
| 单指令多数据 (SIMD) | 多个处理单元同时执行相同操作，处理不同数据 | GPU、向量处理器 |
并发 (Concurrency)：多个任务在逻辑上同时活跃（可能交替执行）。
并行 (Parallelism)：多个任务在物理上同时执行。
并发是并行的必要条件，但不是充分条件。
| 单位 | FLOPS | 字节 |
|---|---|---|
| Kilo | 10³ flop/sec | ~2¹⁰ bytes (KiB) |
| Mega | 10⁶ flop/sec | ~2²⁰ bytes (MiB) |
| Giga | 10⁹ flop/sec | ~2³⁰ bytes (GiB) |
| Tera | 10¹² flop/sec | ~2⁴⁰ bytes (TiB) |
| Peta | 10¹⁵ flop/sec | ~2⁵⁰ bytes (PiB) |
| Exa | 10¹⁸ flop/sec | ~2⁶⁰ bytes (EiB) |
TOP500 每半年（6 月 ISC、11 月 SC）更新一次全球最快的 500 台计算机系统。基准测试使用 Linpack（求解稠密线性方程组 Ax=b），其性能主要由稠密矩阵乘法决定。
| 排名 | 系统 | 国家 | Rmax (Pflops) | 核心数 |
|---|---|---|---|---|
| 1 | El Capitan | USA | 1,742 | 11,039,616 |
| 2 | Frontier | USA | 1,353 | 9,066,176 |
| 3 | Aurora | USA | 1,012 | 9,264,128 |
| 4 | Eagle | USA | 561.2 | 2,073,600 |
| 5 | HPC6 | Italy | 309.1 | 2,069,760 |
| 6 | Fugaku | Japan | 442.0 | 7,630,848 |
高性能计算（HPC）是科学的"第三支柱"，与理论和实验并列：
高性能模拟用于理解以下现象：
随着实验设备（探测器、测序仪、望远镜）产生的数据量呈指数级增长，高性能数据分析（HPDA）成为科学发现的"第四范式"。
从 2011 年（AlexNet）到 2018 年（AlphaGo Zero），AI 计算量增长了 30 万倍。分布式深度学习已成为 HPC 的重要驱动力。
Phil Colella 提出的 7 个科学计算"dwarfs"（后扩展为 Berkeley 13 个 motifs）：
| Motif | 描述 | 典型应用 |
|---|---|---|
| Dense Linear Algebra | 稠密线性代数 | 矩阵乘法、LU 分解 |
| Sparse Linear Algebra | 稀疏线性代数 | SpMV、迭代求解器 |
| Spectral Methods (FFT) | 谱方法 | 信号处理、PDE 求解 |
| Particle Methods | 粒子方法 | N-body、分子动力学 |
| Structured Grids | 结构网格 | 有限差分、有限体积 |
| Unstructured Grids | 非结构网格 | 有限元分析 |
| Monte Carlo | 蒙特卡洛方法 | 金融模拟、辐射传输 |
Gordon Moore 在 1965 年预测晶体管密度每 18 个月翻一番。虽然摩尔定律仍在延续，但形式已发生变化：
当晶体管尺寸缩小时：
结论：无法继续通过提升时钟频率来获得性能，必须转向并行架构。
假设程序中有 \(s\) 的比例是串行的，\((1-s)\) 可以并行化，使用 \(P\) 个处理器：
\[\text{Speedup}(P) = \frac{1}{s + \frac{1-s}{P}} \leq \frac{1}{s}\]
示例：若 1/10 的运行时间是串行的，即使使用 Cori 的 65K 核，最大加速比也仅为 10x。
考虑 1 Tflop/s、1 Tbyte 的串行机器：
结论：串行性能有物理上限，必须走并行之路。
| 主题 | 编程模型 | 语言/库 |
|---|---|---|
| 共享内存 | Shared Memory | OpenMP (pThreads) |
| 分布式内存 | Distributed Memory | MPI |
| 分区全局地址空间 | PGAS | UPC++ |
| 数据并行 | Data Parallel | CUDA, Spark |
Q1：以下哪项不是并行计算机的架构？
Q2：根据 Amdahl 定律，若程序 20% 是串行的，使用无限多个处理器的最大加速比是多少？
Q3：TOP500 排行榜使用什么基准测试？
Q4：为什么 Dennard Scaling 的终结意味着必须转向并行计算？
Q5：Berkeley 的 13 个计算 motifs 中，不包括以下哪项？
串行性能受物理限制（光速、功耗密度），并行是唯一出路。从手机到超级计算机，并行无处不在。
Bill Dally（NVIDIA）的名言：Performance = Parallelism，Efficiency = Locality。
串行部分决定了加速比的上限。优化并行部分之前，先优化串行部分。
掌握 Dense/Sparse Linear Algebra、FFT、Particle Methods 等核心算法模式，即可覆盖绝大多数 HPC 应用。