第1章 并行计算基础（Fundamentals of Parallel Computing）

一、导读

1.1 本章学习目标

理解并行计算产生的历史背景和技术驱动力，包括摩尔定律放缓与功耗墙问题

掌握 Flynn 分类法（SISD/SIMD/MISD/MIMD）及其对并行体系结构的分类意义

能够准确陈述 Amdahl 定律和 Gustafson 定律的数学表达，并运用其分析并行系统的理论极限

理解并行计算中加速比、效率、吞吐量等核心性能指标的定义与计算方法

区分并行（Parallelism）与并发（Concurrency）的概念差异，理解其在系统设计中的不同含义

了解并行计算的主要应用领域，从科学计算到人工智能的演进历程

掌握并行计算的性能瓶颈分析方法，能够识别串行部分对整体性能的影响

建立对并行体系结构整体知识框架的认知，理解后续章节之间的逻辑关系

1.2 为什么本章如此重要

并行计算基础是理解整个并行计算机体系结构的基石。从2005年前后，Intel 和 AMD 相继放弃频率竞赛转向多核架构，这一历史性转折标志着单线程性能提升的时代基本结束。此后，无论是桌面处理器、服务器芯片还是移动 SoC，多核化成为唯一可行的性能提升路径。理解并行动机，就是理解过去二十年计算机体系结构演进的底层逻辑。

从应用角度看，几乎所有主流软件都在不同层面利用了并行性。现代浏览器使用多进程架构隔离标签页，数据库系统通过并行查询加速数据分析，深度学习框架依赖 GPU 的大规模并行计算能力。即便是日常使用的应用程序，其背后也可能涉及数十个并发线程的协作。不理解并行计算的基本原理，就无法真正理解现代计算机系统的工作方式。

从理论角度看，本章引入的 Amdahl 定律和 Gustafson 定律是并行性能分析的两大支柱。Amdahl 定律告诉我们并行化的理论上限取决于串行部分的比例，这一洞见至今仍然适用。Gustafson 定律则从另一个角度指出，当问题规模随处理器数量增长时，并行效率可以维持较高水平。这两个定律的辩证关系，构成了并行系统设计与分析的理论基础。

此外，本章建立的概念框架将贯穿全书。Flynn 分类法为后续章节的架构讨论提供了分类语言，性能评估指标为各章的性能分析提供了量化工具，而并行与并发的区分则帮助读者在后续章节中准确理解不同同步机制的设计目标。可以说，本章的学习质量直接决定了后续章节的理解深度。

1.3 核心问题引导

为什么单核处理器的频率无法无限提升？功耗墙（Power Wall）和内存墙（Memory Wall）是如何形成的？

Flynn 分类法中的四类系统各自对应什么样的实际硬件？MISD 为何在商业上几乎没有成功案例？

Amdahl 定律表明，如果程序中 10% 的代码无法并行化，即使使用无限多个处理器，最大加速比是多少？

Gustafson 定律与 Amdahl 定律的核心假设差异是什么？为什么两者看似矛盾却各有道理？

并行和并发有什么本质区别？一个并发程序一定能在多核系统上获得性能提升吗？

如何定义并行系统的效率指标？为什么效率随处理器数量增加而下降是普遍现象？

并行计算在人工智能领域（特别是深度学习）中扮演了什么角色？GPU 为何成为 AI 训练的核心硬件？

二、核心概念详解

2.1 并行动机：从频率竞赛到多核时代（约700字）

并行计算的兴起有着深刻的技术背景。在1970年代到2000年代初的三十年间，处理器性能的提升主要依靠两个途径：提高时钟频率和缩小晶体管尺寸。根据 Dennard 缩放比例定律（Dennard Scaling），当晶体管尺寸缩小时，其功耗也按比例下降，这使得在相同功耗预算下可以提高时钟频率。因此，处理器频率从 Intel 8086 的 4.79 MHz 一路攀升到 Pentium 4 的 3.8 GHz，几乎遵循着摩尔定律的节奏稳步增长。

然而，2004至2005年间，这一趋势遭遇了根本性的物理障碍。首先是功耗墙问题：当频率继续提升时，动态功耗以频率的三次方增长（P = C V^2 f，而电压 V 与频率 f 近似线性关系），导致芯片散热成为不可逾越的障碍。Intel 的 Pentium 4 Prescott 核心就是典型案例，其实际功耗远超设计预期，最终导致多代微架构的取消。其次是内存墙问题：处理器速度的增长远超内存速度的增长，导致处理器大量时间等待内存数据，频率提升带来的收益被内存延迟所吞噬。

面对这些物理限制，半导体工业选择了多核化路线。与其在一个芯片上制造一个高频核心，不如放置多个较低频的核心。这样在相同功耗预算下，总计算吞吐量可以显著提升。2005年，Intel 推出双核 Pentium D，AMD 推出双核 Opteron，标志着多核时代的正式开启。此后，核心数量持续增长，从双核到四核、八核，再到今天的数十核甚至上百核。AMD 的 EPYC 处理器已支持最多 128 个核心，而 NVIDIA 的 GPU 则拥有数千个计算核心。

这种转变对软件行业产生了深远影响。过去，程序员无需做任何特殊处理，只需等待下一代处理器就能获得性能提升。多核时代打破了这一"免费午餐"，软件必须显式地利用并行性才能从硬件进步中获益。这催生了并行编程模型、并行算法和并行体系结构的大量研究，也构成了本教材的核心主题。

2.2 Flynn 分类法与并行架构 taxonomy（约650字）

Michael Flynn 在1966年提出的分类法（Flynn's Taxonomy）是并行体系结构最经典的分类框架，它从指令流（Instruction Stream）和数据流（Data Stream）两个维度将计算机系统分为四类。

SISD（Single Instruction Stream, Single Data Stream）即传统的单处理器系统，每条指令操作一个数据元素。经典的 von Neumann 架构就是典型的 SISD 系统。虽然现代处理器通过流水线、超标量和乱序执行等技术实现了指令级并行，但从程序员的视角看，它仍然是单指令单数据的模型。

SIMD（Single Instruction Stream, Multiple Data Stream）是指一条指令同时操作多个数据元素的架构。Intel 的 SSE、AVX 指令集，ARM 的 NEON 指令集，以及 GPU 的流处理器都是 SIMD 的典型实现。SIMD 特别适合规则的数据并行任务，如图像处理、矩阵运算和信号处理。一条 256 位宽的 AVX2 指令可以同时处理 8 个 32 位浮点数，理论上能获得 8 倍的性能提升。

MISD（Multiple Instruction Stream, Single Data Stream）是多条指令操作同一数据流的架构。这一类别在理论上存在但在实践中几乎没有商业成功的案例。有时流水线结构被归入此类，但这种归类存在争议。少数容错系统通过让多个处理器执行不同的算法处理同一数据来实现冗余校验，勉强可以算作 MISD。

MIMD（Multiple Instruction Stream, Multiple Data Stream）是最通用的并行架构，多个处理器各自执行独立的指令流，操作各自的数据。现代多核处理器、SMP 系统和分布式计算集群都属于 MIMD 范畴。MIMD 系统可以进一步细分为共享内存和分布式内存两大类，这也是本教材后续章节的重点内容。

Flynn 分类法虽然简洁，但也有其局限性。它无法准确描述现代处理器中复杂的层次化并行结构，例如一个 MIMD 多核处理器中每个核心又包含 SIMD 单元。尽管如此，它仍然是理解并行架构多样性的有用起点。

2.3 Amdahl 定律与 Gustafson 定律（约750字）

Amdahl 定律由 Gene Amdahl 于1967年提出，是并行计算领域最重要的性能分析工具之一。其核心思想是：系统中不可并行化的串行部分限制了整体性能的提升上限。

设系统中可并行化的代码比例为 f（0 < f < 1），串行部分比例为 (1 - f)，使用 N 个处理器时，Amdahl 定律给出的加速比为：

S(N) = 1 / ((1 - f) + f / N)

当 N 趋于无穷大时，最大加速比趋近于 1 / (1 - f)。这意味着，即使只有 5% 的代码无法并行化（f = 0.95），最大加速比也只有 20 倍。这个结论对系统设计有深刻的启示：在追求大规模并行时，必须尽可能消除串行瓶颈。

然而，Amdahl 定律有一个关键假设：问题规模固定。当处理器数量增加时，每个处理器分到的工作量减少，但串行部分的工作量不变。这在实际应用中并不总是合理的。

Gustafson 定律（1988年）提出了不同的视角：当处理器数量增加时，我们通常会增大问题规模，使得每个处理器的工作量保持不变。在这种情况下，串行部分的比例随问题规模增大而减小。Gustafson 定律的加速比公式为：

S(N) = N - (N - 1) * s

其中 s 是串行部分在单处理器执行时间中的比例。与 Amdahl 定律不同，Gustafson 定律表明加速比可以近似线性增长，这为大规模并行系统提供了更乐观的理论依据。

两个定律并不矛盾，而是适用于不同的场景。Amdahl 定律适合固定规模的问题（如实时系统），Gustafson 定律适合可缩放的问题（如科学模拟）。在实际的并行系统设计中，需要同时考虑两个定律的约束，根据具体应用特性选择合适的并行策略。

2.4 并行性能评估指标体系（约600字）

科学地评估并行系统性能是设计和优化并行系统的基础。并行计算领域形成了一套成熟的性能指标体系，主要包括以下几个核心指标。

加速比（Speedup）是最基本的并行性能指标，定义为串行执行时间与并行执行时间的比值：S = T(1) / T(N)。理想情况下，使用 N 个处理器应获得 N 倍加速比（线性加速比）。实际中，由于通信开销、同步开销和串行部分的存在，加速比总是低于理想值。加速比又可分为强扩展（Strong Scaling，固定问题规模增加处理器数）和弱扩展（Weak Scaling，问题规模与处理器数等比例增长）。

效率（Efficiency）衡量处理器资源的利用程度，定义为 E = S / N。理想效率为1，实际效率总是小于1。效率的下降反映了并行开销的占比，是评估并行系统可扩展性的重要指标。

吞吐量（Throughput）定义为单位时间内系统完成的工作量，通常以任务数/秒或浮点运算次数/秒（FLOPS）衡量。吞吐量指标在批处理和数据密集型应用中尤为重要。

除了上述定量指标，还需要关注可扩展性（Scalability），即系统在增加处理器数量时维持效率的能力。一个可扩展的并行系统能够在处理器数量增长时，通过相应增大问题规模来维持较高的效率。

2.5 并行与并发的辨析（约500字）

并行（Parallelism）和并发（Concurrency）是两个密切相关但本质不同的概念，理解它们的区别对于正确设计并行系统至关重要。

并行是指多个计算任务在同一时刻真正地同时执行。这要求有多个物理处理单元同时工作。并行的核心目标是加速计算，通过将工作分配到多个处理器上来减少总执行时间。

并发是指系统在同一时间段内管理多个任务的执行，这些任务在逻辑上是独立的，但在物理上不一定同时执行。在单核系统上，通过时间片轮转可以实现并发：多个任务交替执行，从用户视角看似乎在同时进行。并发的核心目标是任务的管理和协调，包括响应性、资源利用和任务隔离。

一个经典的类比：并行是同时煮咖啡和烤面包（两个物理过程同时进行），并发是在煮咖啡的间隙去烤面包（一个处理器在多个任务间切换）。

在编程层面，并发程序的设计重点是正确性：如何避免竞态条件、死锁和数据不一致。并行程序的设计重点是性能：如何平衡负载、减少通信和最大化利用率。一个并发程序在单核上运行不会获得性能提升，只有当它在多核上真正并行执行时才能加速。

现代并行系统通常同时涉及并发和并行。例如，一个 Web 服务器可能并发处理数千个客户端连接，其中计算密集型的请求被分配到多个核心上并行执行。理解两者的区别有助于在不同层面选择合适的设计策略和工具。

三、深入分析与讨论

3.1 功耗墙与暗硅现象（约500字）

功耗墙（Power Wall）是推动并行计算发展的核心物理因素之一。CMOS 电路的动态功耗公式为 P = alpha C V^2 * f，其中 alpha 是活动因子，C 是负载电容，V 是供电电压，f 是时钟频率。当工艺节点缩小时，虽然单个晶体管的功耗降低，但芯片上集成的晶体管数量也在增加，导致总功耗持续攀升。

2011年，加州大学圣地亚哥分校的 Esmaeilzadeh 等人提出了"暗硅"（Dark Silicon）概念。他们指出，由于功耗限制，芯片上同时活跃的晶体管比例必须受到控制。随着工艺进步，越来越多的晶体管区域在任何时刻都必须保持断电状态，就像被"覆盖"了一层暗色。这意味着，即使芯片上集成了数十亿个晶体管，受功耗限制，能同时使用的比例可能只有20%到30%。

暗硅现象对并行计算有深远影响。一方面，它限制了通过增加核心数量来提升性能的传统路线，因为更多核心意味着更高的功耗。另一方面，它为异构计算提供了机遇：通过集成不同类型的专用加速器（如 GPU、NPU、DSP），在功耗预算内最大化计算效率。当某个加速器不工作时，可以将其区域关闭以节省功耗。

3.2 并行计算的 Amdahl 定律实践分析（约500字）

Amdahl 定律在实际系统设计中有着广泛的应用。以一个典型的科学计算程序为例，假设其计算过程分为初始化（5%）、并行计算（90%）和结果汇总（5%）三个阶段。根据 Amdahl 定律，串行部分占比为 10%，使用 100 个处理器时的加速比为：

S(100) = 1 / (0.1 + 0.9 / 100) = 1 / 0.109 = 9.17

尽管使用了 100 个处理器，加速比仅为 9.17 倍，效率不到 10%。这个例子清楚地说明了串行瓶颈的危害。

在实践中，串行部分往往比预想的更难消除。初始化阶段的内存分配、计算阶段的负载不均衡、结果汇总阶段的数据归约（Reduction）都可能成为隐性的串行瓶颈。特别是全局归约操作，如果使用不当，其时间复杂度可能随处理器数量线性增长，严重制约大规模并行的效果。

因此，并行系统设计的核心策略之一就是尽可能减少串行部分。这包括：将初始化延迟加载或并行化，使用局部归约替代全局归约，以及通过算法设计减少同步点的数量和持续时间。

3.3 并行计算的应用领域演进（约450字）

并行计算的应用领域经历了从科学计算到通用计算的演进过程。早期（1960-1990年代），并行计算主要服务于气象模拟、核物理仿真和流体力学计算等高性能科学计算领域，使用专门设计的超级计算机如 Cray 系列。

进入2000年代，随着多核处理器的普及，并行计算开始渗透到日常应用。数据库系统的并行查询、Web 服务器的并发处理、多媒体编解码的并行化成为常态。OpenMP 和 MPI 等标准化工具的出现降低了并行编程的门槛。

2010年代以来，深度学习的爆发将并行计算推向了新的高度。神经网络的训练涉及大规模矩阵运算，天然适合 GPU 的 SIMD 架构。NVIDIA 的 CUDA 生态系统使得研究者能够方便地利用 GPU 的数千个核心进行并行计算。从 AlexNet 到 GPT 系列模型，AI 模型规模的指数级增长完全依赖于并行计算能力的持续提升。今天，训练一个大型语言模型需要数千块 GPU 协同工作数周时间，这是并行计算最壮观的应用场景之一。

四、实践案例

4.1 案例一：多核处理器发展史中的并行化转型（约400字）

以 Intel 处理器的发展为例，可以清晰地看到从频率竞赛到多核并行的转型过程。2000年发布的 Pentium 4 采用了 NetBurst 微架构，设计目标是达到 10 GHz 的时钟频率。然而，到2004年的 Prescott 核心达到 3.8 GHz 时，功耗已高达 115W，散热问题使其无法继续提升频率。Intel 最终取消了后续的 Tejas 和 Jayhawk 核心。

2006年，Intel 推出 Core 微架构，转向多核路线。Core 2 Duo 在较低频率下实现了比 Pentium 4 更高的性能，同时功耗大幅降低。此后，核心数量持续增长：2017年推出 18 核的 Core i9，2023年的第14代酷睿采用大小核混合架构，最多 24 核。服务器端的 Xeon 系列更是达到了 60 核以上。

这一转型不仅是技术路线的改变，更深刻影响了软件生态。操作系统需要更好的线程调度器，应用程序需要支持多线程，编程模型需要从串行思维转向并行思维。这一案例生动说明了硬件变革如何驱动整个计算生态的演进。

4.2 案例二：Amdahl 定律在图像处理中的应用（约400字）

以一幅 4K 分辨率（3840 x 2160）图像的灰度转换为例。该算法对每个像素执行 Gray = 0.299 R + 0.587 G + 0.114 * B 的运算，总计约 830 万像素需要处理。

假设读取图像文件需要 10ms（串行），像素处理可以完全并行化，写入结果需要 5ms（串行）。在单核上总耗时为 100ms，其中串行部分为 15ms，占比 15%。

使用 8 核处理器时，像素处理部分耗时为 (100 - 15) / 8 = 10.625ms，总耗时为 15 + 10.625 = 25.625ms，加速比为 100 / 25.625 = 3.9。效率为 3.9 / 8 = 48.75%。

如果使用 64 核，像素处理部分耗时为 85 / 64 = 1.33ms，总耗时 16.33ms，加速比仅为 6.12。效率降至 9.56%。可以看到，即使像素处理完全可并行，15% 的串行 I/O 操作也将最大加速比限制在 100 / 15 = 6.67 倍。这说明在实际应用中，I/O 操作往往是并行化的重要瓶颈。

五、常见误区与注意事项

误区：核心越多性能越好。实际上，由于 Amdahl 定律的限制和并行开销的存在，核心数量增加带来的性能提升会逐渐饱和。超过某个临界点后，增加核心甚至可能因通信开销增大而导致性能下降。设计并行系统时需要根据应用的并行度选择合适的核心数量。

误区：并行程序一定能加速。并非所有程序都适合并行化。如果程序的串行部分占比过高，或者数据依赖关系复杂导致并行化困难，强行并行化可能因额外开销而变慢。在并行化之前，应先评估程序的并行潜力。

误区：Amdahl 定律否定了大规模并行的价值。Amdahl 定律假设固定问题规模，但实际中我们通常随处理器增加而增大问题规模。Gustafson 定律表明，在可缩放场景下，大规模并行仍然非常有效。两个定律需要结合使用。

误区：并发就是并行。并发是逻辑上的多任务管理，并行是物理上的同时执行。并发程序在单核上无法获得性能提升，只有并行执行才能加速。混淆两者会导致对程序性能的错误预期。

注意事项：性能评估必须考虑基准测试的代表性。不同的基准测试可能给出截然不同的性能结论。应使用与实际应用场景匹配的基准测试，避免仅依赖单一指标做出判断。

六、本章小结

本章系统介绍了并行计算的基础概念和理论框架。我们从并行动机出发，分析了摩尔定律放缓、功耗墙和内存墙如何推动计算机从单核向多核转型。Flynn 分类法为并行架构提供了经典的分类框架，将系统分为 SISD、SIMD、MISD 和 MIMD 四类。Amdahl 定律和 Gustafson 定律从不同角度揭示了并行化的理论极限，前者适用于固定规模问题，后者适用于可缩放问题。并行与并发的辨析帮助我们理解任务管理和计算加速的不同目标。性能评估指标体系为量化分析并行系统提供了工具。这些基础概念和理论将贯穿全书，为后续章节中具体架构和编程模型的讨论奠定基础。

七、思考题与练习

假设一个程序中 20% 的操作是串行的，使用 16 个处理器时，根据 Amdahl 定律计算加速比和效率。如果要将效率提升到 80% 以上，最多可以使用多少个处理器？

对比分析 Amdahl 定律和 Gustafson 定律的核心假设差异。在一个大规模气象模拟应用中，哪个定律更适合用来预测性能提升？为什么？

调研一款现代多核处理器（如 AMD EPYC 9654 或 Apple M2 Ultra），分析其核心配置、缓存层次和互连拓扑，说明其设计如何体现本章讨论的并行计算原理。

解释"暗硅"（Dark Silicon）现象对并行计算发展的影响。为什么单纯增加核心数量不再能持续提升性能？异构计算如何帮助解决暗硅问题？

选择一个你熟悉的应用程序（如 Web 浏览器、数据库系统或图像处理软件），分析其中可能存在的并行化机会和串行瓶颈，估算其可并行化比例。

设计一个实验方案，测量某个并行程序在不同处理器数量下的加速比和效率。如何判断该程序属于强扩展还是弱扩展？实验中需要注意哪些控制变量？

讨论 Flynn 分类法在现代计算系统中的适用性和局限性。现代 GPU 是否可以简单地归类为 SIMD？为什么一些学者提出了更细粒度的分类方案？

并行计算在深度学习训练中扮演了什么角色？分析模型训练中哪些部分可以并行化（数据并行、模型并行），哪些部分存在串行瓶颈（梯度同步、参数更新），并讨论其对训练效率的影响。