并行计算

大型超级计算机（如IBM的Blue Gene/P）在设计上极度依赖并行计算技术。

并行计算（英語：Parallel computing）是一种计算模式，指将多个计算任务或进程同时进行处理。 庞大复杂的问题通常可以被拆分为多个较小的部分，随后在同一时间内被并行求解。并行计算有几种不同的形式：位级并行、指令级并行、数据并行以及任务并行。并行计算长期以来一直被应用于高性能计算，但随着阻碍频率缩放的物理限制日益凸显，它如今获得了更为广泛的关注。 由于近年来计算机的功耗及发热问题日益严峻， 并行计算现已成为计算机架构的主导范式，这在多核处理器的普及上体现得尤为明显。

并行性与并发性的对比

在计算机科学中，并行性（英語：parallelism）和并发性（英語：concurrency）是两个截然不同的概念：并行程序利用多个CPU核心，每个核心独立且同时地执行一个任务。相比之下，并发性使得程序即使在单核CPU上也能处理多个任务：核心在多个任务（即线程）之间快速切换，无需等待上一个任务完全结束。一个程序可以兼具两者、两者皆无，或者是并行性与并发性特征的某种组合。

并行计算机可以根据硬件支持并行的级别进行大致分类。多核计算机与多处理器计算机在一台机器内部拥有多个处理单元；而计算机集群、大规模并行处理系统（MPP）和网格计算则调动多台计算机协同处理同一任务。有时，传统的处理器还会搭配专门的并行计算机架构使用，以加速特定任务的处理。

在某些情况下，并行性对程序员而言是透明的（例如位级并行或指令级并行）；但显式编写的并行算法（特别是那些利用了并发性的算法），往往比顺序算法更难开发， 这是因为并发性引入了多类潜在的新型软件缺陷，其中最常见的就是竞争条件。不同子任务之间的通信与同步，往往是实现并行程序最佳性能所面临的最大障碍。

单一程序通过并行化所能达到的理论加速比上界，由阿姆达尔定律给出。该定律指出，程序的加速比受限于其能够被并行化的那部分时间比例。

背景

传统上，计算机软件通常是为串行计算而编写的。为了解决某个问题，人们会构建一个算法，并将其实现为一串线性的指令流。这些指令在同一台计算机上的一个中央处理器中执行。在任何特定时刻，只能有一条指令在执行——待该指令执行完毕后，才会接着执行下一条。

相比之下，并行计算同时使用多个处理单元来解决问题。它的实现方式是将大问题拆分为相互独立的小分块，使得每个处理单元都能与其它单元同时执行其负责的算法部分。处理单元的形式多种多样，包括配备多处理器的单台计算机、多台联网的计算机、专用硬件，或者是上述方式的任意组合。 历史上，并行计算主要用于科学计算及自然现象的模拟，特别是在自然科学和工程科学领域，如气象学。这一需求推动了并行硬件、软件系统以及高性能计算的设计与发展。

从20世纪80年代中期直到2004年，频率缩放一直是提升计算机性能的主要驱动力。程序运行的运行时等于指令数乘以每条指令的平均执行时间。在保持其他条件不变的情况下，提高时钟频率会减少执行单条指令所需的平均时间。因此，频率的提升能够直观地降低所有计算密集型程序的运行时间。 然而，芯片消耗的功率（$P$）由公式 $P=C\times V^{2}\times F$ 决定，其中 $C$ 是每个时钟周期发生开关操作的电容（与状态发生改变的晶体管数量成正比），$V$ 是电压，$F$ 是处理器频率（每秒周期数）。 频率的增加会直接导致处理器功耗的急剧攀升。过高的功耗最终导致了英特尔在2004年5月8日取消了其Tejas和Jayhawk处理器的研发计划，这通常被视作频率缩放作为主导计算机架构范式终结的标志。

为了解决功耗和过热问题，各大主要的中央处理器制造商开始生产具备多核心且功耗效率更高的处理器。核心是处理器的计算单元，在多核处理器中，每个核心都是独立的，并且可以并发地访问同一内存。多核处理器将并行计算引入了日常的台式计算机。由此，串行程序的并行化成为了一项主流的编程任务。到了2012年，四核处理器已成为台式计算机的标配，而服务器则普遍拥有10核以上的处理器。摩尔定律曾预测每个处理器的核心数量每18到24个月将翻一番。 截至2023年，一些处理器已拥有超过一百个核心。受限于散热和设计约束，有些设计甚至混合了性能核心与能效核心（例如ARM的big.LITTLE设计）。

操作系统能够确保不同的任务和用户程序在可用的核心上并行运行。然而，为了让串行软件程序充分利用多核架构，程序员需要对代码进行重构和并行化处理。应用软件运行时间的缩短将不再仅仅依赖于硬件频率的提升；相反，程序员必须并行化他们的软件代码，以充分发挥多核架构日益强大的计算潜力。

相关定律

阿姆达尔定律的图形化表示。该定律展示了整个系统的理论最大加速比以及收益递减的概念。如果恰好有50%的工作可以并行化，那么最佳可能的加速比为2倍。如果95%的工作可以并行化，最佳加速比则为20倍。根据这一定律，即使拥有无限多的处理器，整体的加速也会受到不可并行部分的严格制约。

假设一个任务由两个独立的部分 $A$ 和 $B$ 组成。部分 $B$ 大约占据整个计算时间的25%。通过极大的努力，人们或许能将这部分的速度提升5倍，但这只能让整体计算时间缩短一小点。相反，人们可能只需要付出较少的努力就能将部分 $A$ 的速度提升一倍。虽然从比例上看，部分 $B$ 的加速比更大（5倍对比2倍），但优化部分 $A$ 却能让整体计算变得快得多。

主条目：阿姆达尔定律

理想情况下，并行化带来的加速比应当是线性的——处理单元数量翻倍应使运行时间减半，再次翻倍则运行时间应再次减半。然而，极少数并行算法能达到如此完美的加速效果。它们中的大多数在处理单元较少时能表现出近乎线性的加速比，但当处理单元数量庞大时，加速比就会逐渐趋于平缓，最终变为一个常数。

整体系统潜在的最大加速比可以通过阿姆达尔定律来计算。 阿姆达尔定律表明，要想实现最优的性能提升，必须在增强任务的并行部分与非并行部分之间取得平衡。此外，它揭示了单纯增加处理器数量会导致收益递减的现象，一旦越过某个临界点，能够获得的加速收益将微乎其微。

阿姆达尔定律也有其局限性，它预设了工作负载是固定的，并且忽略了进程间通信与同步的开销。它主要只聚焦于计算层面，而对外部因素（如数据持久化、I/O操作和内存访问延迟）缺乏考量。

古斯塔夫森定律与通用可扩展性定律对并行性能给出了更为现实的评估。

古斯塔夫森定律的图形化表示

依赖关系

理解数据依赖对于实现并行算法至关重要。程序的执行速度不可能超过其中最长的那条相互依赖的计算链（通常被称为关键路径），因为链条中后续的计算必须等待前置计算产生结果后，才能按顺序执行。然而，绝大多数算法并非仅仅由单一且漫长的依赖链构成；往往存在大量的机会来并行执行那些互不依赖的计算。

假设 $P_{i}$ 和 $P_{j}$ 是两个程序段。伯恩斯坦条件（Bernstein's conditions）描述了这两段程序在什么情况下是互不依赖且可以并行执行的。对于 $P_{i}$，设 $I_{i}$ 为其所有输入变量的集合，$O_{i}$ 为其输出变量的集合，对 $P_{j}$ 亦然。当且仅当它们满足以下条件时，$P_{i}$ 和 $P_{j}$ 才是独立的：

$I_{j}\cap O_{i}=\varnothing ,$

$I_{i}\cap O_{j}=\varnothing ,$

$O_{i}\cap O_{j}=\varnothing .$

如果违反了第一个条件，就会产生“流依赖”（flow dependency），即第一段程序产生的结果被第二段程序当作输入使用。第二个条件代表了“反依赖”（anti-dependency），即第二段程序产生的结果覆盖了第一段程序所需读取的变量。第三个也是最后一个条件代表“输出依赖”：当两段程序都要向同一个位置写入数据时，最终保存在那里的结果必须来自于逻辑上最后执行的那段程序。

请看以下几个函数，它们展示了各种依赖关系：

 1: function Dep(a, b)
 2: c := a * b
 3: d := 3 * c
 4: end function

在这个例子中，指令3不能在指令2之前（甚至也不能与指令2并行）执行，因为指令3使用了指令2的结果。它违反了条件1，因此引入了流依赖。

 1: function NoDep(a, b)
 2: c := a * b
 3: d := 3 * b
 4: e := a + b
 5: end function

在这个例子中，指令之间不存在任何依赖关系，因此它们可以全部并行运行。

伯恩斯坦条件默认不同进程之间不会共享内存。如果需要共享内存，就必须使用某种手段来强制规范访问顺序，例如使用信号量、屏障或是其他同步方法。

竞争条件、互斥、同步与并行减速

并行程序中的子任务通常被称为线程。一些并行计算机架构使用更小、更轻量级的线程版本，称为纤程，而另一些则使用更大的版本，即进程。不过，“线程”一词现已被普遍接受作为子任务的统称。 线程往往需要以同步的方式访问某个对象或其他资源，例如当它们必须更新一个共享的变量时。如果没有同步机制，两个线程之间的指令可能会以任何随机顺序交错执行。例如，考虑以下程序：

线程 A	线程 B
1A: 读取变量 V	1B: 读取变量 V
2A: 将变量 V 加 1	2B: 将变量 V 加 1
3A: 写回变量 V	3B: 写回变量 V

如果指令 1B 在 1A 和 3A 之间执行，或者指令 1A 在 1B 和 3B 之间执行，程序将会产生错误的数据。这被称为竞争条件。程序员必须使用锁来提供互斥。锁是一种编程语言结构，允许一个线程获取变量的控制权，并在该变量被解锁前，阻止其它线程读取或写入它。持有锁的线程可以自由地执行其临界区（程序中需要独占访问某个变量的代码段），并在完成后解锁数据。因此，为了保证程序的正确执行，可以将上述程序改写为使用锁的形式：

线程 A	线程 B
1A: 锁定变量 V	1B: 锁定变量 V
2A: 读取变量 V	2B: 读取变量 V
3A: 将变量 V 加 1	3B: 将变量 V 加 1
4A: 写回变量 V	4B: 写回变量 V
5A: 解锁变量 V	5B: 解锁变量 V

其中一个线程将成功锁定变量 V，而另一个线程将被锁定在外——在 V 再次被解锁前无法继续执行。这确保了程序的正确运行。当线程必须排队（串行化）访问资源时，使用锁也许是保证程序正确性的必要手段，但这会极大拖慢程序的执行速度，并可能影响其可靠性。

使用非原子性锁来锁定多个变量可能会引入程序死锁的风险。原子锁会一次性锁定所有需要的变量。如果它不能同时锁定所有变量，它就不会锁定其中的任何一个。如果两个线程都需要使用非原子锁去锁定相同的两个变量，很可能发生的情况是：一个线程锁定了其中一个变量，而第二个线程锁定了另一个变量。在这种情况下，任何一个线程都无法继续推进，从而导致死锁。

许多并行程序要求其子任务同步执行。这就需要用到屏障。屏障通常通过锁或信号量来实现。 有一类被统称为无锁与无等待算法的算法，能够完全避免使用锁和屏障。然而，这种方法往往难以实现，并且需要对数据结构进行极为精巧的设计。

并非所有的并行化都能带来加速效果。通常情况下，随着任务被分割成越来越多的线程，这些线程将把越来越大比例的时间花在相互通信或者等待资源访问上。 一旦资源争用或通信带来的开销超过了实际计算所花费的时间，进一步的并行化（即把工作负载分配给更多的线程）反而会增加而不是减少完成任务的时间。这一问题被称为并行减速， 但在某些情况下，它可以通过软件层面的分析与重新设计来得到改善。

细粒度、粗粒度与极其并行

应用程序经常根据其子任务需要彼此同步或通信的频率来进行分类。如果一个应用程序的子任务每秒必须通信许多次，那么它表现出的就是细粒度并行（fine-grained parallelism）；如果它们每秒不需要通信太多次，则表现为粗粒度并行（coarse-grained parallelism）；如果它们很少或者根本不需要通信，那么它就具备极其并行（embarrassing parallelism，也译作易并行）特性。极其并行的应用程序通常被认为是最容易实现并行化的。

弗林分类法

主条目：弗林分类法

迈克尔·弗林为并行（及顺序）计算机与程序创建了最早的分类系统之一，如今被称为弗林分类法。弗林根据指令流是单一还是多重，以及这些指令操作的数据流是单一还是多重，对程序和计算机进行了分类。

单指令流单数据流（SISD）分类相当于一个完全顺序执行的程序。单指令流多数据流（SIMD）分类类似于对庞大的数据集反复执行相同的操作，这在信号处理应用中非常常见。多指令流单数据流（MISD）是一个较少使用的分类。尽管曾经设计过应对这一分类的计算机架构（如脉动阵列），但符合该类别的实际应用却寥寥无几。多指令流多数据流（MIMD）程序则是迄今为止最为常见的并行程序类型。

正如大卫·帕特森和约翰·轩尼诗所言：“当然，有些机器是这些分类的混合体，但这种经典模型之所以能留存至今，是因为它简单、易于理解，并且能够提供一个很好的初步近似评估。也许正因为其通俗易懂，它也是应用最广泛的分类方案。”

缺点

在实践中，并行计算可能会引入显著的额外开销，这主要是因为需要将来自多个进程的数据进行同步与合并。具体而言，与在单个线程上处理相同数据相比，进程间通信和同步所导致的开销要大得多——通常要高出两个甚至更多数量级。 因此，应当仔细评估并行化带来的整体性能提升是否物有所值。

粒度

位级并行

主条目：位级并行

台湾的台湾杉三号（Taiwania 3），一台参与了COVID-19研究的并行超级计算设备

从20世纪70年代超大规模集成电路（VLSI）计算机芯片制造技术问世，一直到大约1986年，计算机架构运算速度的提升主要依赖于计算机字长（处理器每个周期能够处理的信息量）的翻倍。 增加字长减少了处理器为了对尺寸大于字长的变量执行运算而必须执行的指令数量。例如，当一个8位处理器必须对两个16位整数整数执行加法运算时，处理器必须首先使用标准的加法指令将两个整数的8个低位比特相加，然后使用带进位加法指令加上刚才低位加法产生的进位位与两个整数的8个高位比特。因此，8位处理器需要两条指令来完成单次运算，而16位处理器只需一条指令即可完成。

历史上，4位微处理器被8位取代，随后是16位、32位。随着32位处理器的普及，这一趋势在通用计算领域停滞了长达二十年之久，32位成为了标准。直到2000年代初，随着x86-64架构的出现，64位处理器才开始变得普遍。

指令级并行

主条目：指令级并行

一个没有流水线的规范处理器。它需要五个时钟周期才能完成一条指令，因此该处理器的发射性能低于标量水平（$IPC<1$）。

本质上，计算机程序是由处理器执行的一连串指令流。如果没有指令级并行，处理器只能在每个时钟周期发射不到一条指令（$IPC<1$）。这类处理器被称为“亚标量”（subscalar）处理器。通过将这些指令重新排序并组合成组，使其能够在不改变程序最终结果的前提下被并行执行，这就是所谓的指令级并行。从20世纪80年代中期到90年代中期，指令级并行技术的进步主导了计算机架构的发展。

一个具备五个流水线阶段的规范处理器。在最佳情况下，它只需要一个时钟周期就能完成一条指令，因此具有标量性能（$IPC=1$）。

所有现代处理器都具备多级指令流水线。流水线中的每一个阶段对应于处理器在这一阶段对指令执行的不同操作；一个拥有 $N$ 级流水线的处理器可以同时处理多达 $N$ 条处于不同完成阶段的指令，因此每个时钟周期能够发射一条指令（$IPC=1$）。这类处理器被称为“标量”（scalar）处理器。经典流水线处理器的一个代表是具有五个阶段的RISC处理器：取指（IF）、译码（ID）、执行（EX）、访存（MEM）和写回（WB）。奔腾4处理器更是拥有高达35级的流水线。

一个具备双执行单元的规范五级流水线处理器。在最佳情况下，它每个时钟周期可以完成两条指令，因此具有超标量性能（$IPC=2>1$）。

大多数现代处理器也配备了多个执行单元。它们通常将此特性与流水线技术相结合，从而在每个时钟周期内能够发射多条指令（$IPC>1$）。这类处理器被称为“超标量”处理器。超标量处理器与多核处理器的区别在于，其内部的多个执行单元并非独立的完整处理器。只有当指令之间不存在数据依赖时，它们才能被组合在一起执行。记分板技术（Scoreboarding）和托马苏洛算法（类似于记分板但运用了寄存器重命名）是实现乱序执行与指令级并行的两种最常用技术。

任务并行

主条目：任务并行

任务并行是并行程序的一种特性，即“可以将完全不同的计算操作作用于相同或不同的数据集上”。 这与数据并行形成了对比，在数据并行中，是对相同或不同的数据集执行相同的计算。任务并行涉及将一个大任务分解为多个子任务，然后将每个子任务分配给各个处理器去执行。这些处理器随后将并发地、且通常是协作地执行这些子任务。任务并行的规模通常不会随着问题规模的扩大而自动扩展。

超字级并行

超字级并行（Superword level parallelism）是一种基于循环展开和基本块向量化的自动向量化技术。它与循环向量化算法的不同之处在于，它可以利用内联代码的并行性，例如处理坐标、颜色通道或是手动展开的循环。

硬件

内存与通信

并行计算机中的主存要么是共享内存（在单一的地址空间内被所有处理单元共享），要么是分布式内存（每个处理单元拥有各自局部的地址空间）。 分布式内存意味着内存不仅在逻辑上是分布的，往往在物理上也是分开的。分布式共享内存和内存虚拟化结合了这两种方法的优势：处理单元既拥有属于自己的本地内存，也可以访问非本地处理器上的内存。访问本地内存的速度通常比访问非本地内存快得多。在超级计算机上，可以使用诸如分区全局地址空间（PGAS）等编程模型来实现分布式共享内存空间。这种模型允许一个计算节点上的进程透明地访问另一节点的远程内存。所有的计算节点还会通过高速互连网络（如InfiniBand）连接到一个外部的共享内存系统，这个系统被称为突发缓冲区，通常由物理分布在多个I/O节点上的非易失性存储器阵列构建而成。

非统一内存访问架构（NUMA）的逻辑视图。一个目录中的处理器访问本地目录内存的延迟，要比访问另一个目录内存的延迟更低。

能够以相同的延迟和带宽访问主存中每个存储单元的计算机架构，被称为统一内存访问（UMA）系统。通常只有内存非物理分布的共享内存系统才能实现这一点。不具备这一特性的系统则被称为非统一内存访问架构（NUMA）。分布式内存系统均属于非统一内存访问架构。

计算机系统利用CPU缓存（位于处理器附近的小型高速存储器）来存放内存值的临时副本（不仅在物理距离上更近，逻辑上也紧密配合）。在并行计算机系统中，如果同一个变量的值被缓存到多个不同的位置，可能会导致缓存数据不一致，进而引起程序执行错误。为了解决这个问题，这些计算机需要引入缓存一致性系统，该系统负责追踪被缓存的值并策略性地将其清除，从而保障程序的正确执行。总线嗅探是追踪哪些值正被访问（并应当被清理）的最常见方法之一。设计大型、高性能的缓存一致性系统是计算机架构中一个非常棘手的难题。正因为如此，共享内存架构的扩展性远不如分布式内存系统。

处理器与处理器之间、处理器与内存之间的通信可以在硬件层面上通过多种方式实现，包括使用共享内存（无论是多端口还是多路复用内存）、交叉开关矩阵、共享总线或各种拓扑结构的互连网络，例如星型、环型、树型、超立方体、胖超立方体（每个节点上有多个处理器的超立方体）或是N维网格。

基于互连网络的并行计算机需要配备一定的路由机制，以实现在没有直接连接的节点间传递消息。在大型多处理器机器中，处理器间通信所使用的媒介通常呈现出层次化的结构特征。

并行计算机的分类

并行计算机可以根据硬件支持并行的级别进行大致分类。这种分类方式很大程度上与基础计算节点之间的物理或逻辑距离相对应。这些分类并非互不相容的；例如，由对称多处理器组成的集群就非常普遍。

多核计算

主条目：多核处理器

多核处理器是指在同一个芯片上集成了多个处理单元（称为“核心”）的处理器。它有别于超标量处理器：超标量处理器包含多个执行单元，可以在每个时钟周期内从同一个指令流（线程）中发射多条指令；相反，多核处理器则能在每个时钟周期内从多个独立的指令流中发射多条指令。专为索尼PlayStation 3游戏机设计的IBMCell微处理器就是一款极其出色的多核处理器。多核处理器中的每个核心甚至可能同时也是超标量的——也就是说，在每个时钟周期内，每个核心不仅独立运作，还能从各自的一个线程中发射多条指令。

同步多线程（其中以英特尔的超线程技术最为人熟知）是早期的一种伪多核形式。能够支持并发多线程的处理器在其处理单元内包含了多个执行单元（即具备超标量架构），并且能在每个时钟周期内从“多个”线程中发射指令。与此不同，时间多线程在处理单元内仅包含一个执行单元，每次只能从“多个”线程中的某一个发射一条指令。

对称多处理

主条目：对称多处理

对称多处理器（SMP）是一种由多个相同的处理器构成的计算机系统，这些处理器共享内存并通过总线相互连接。 然而，总线竞争限制了总线架构的扩展能力。因此，SMP系统的处理器数量一般不会超过32个。 由于处理器的尺寸日益缩小，加之大容量缓存大幅降低了对总线带宽的需求，只要能保证充足的内存带宽，这种对称多处理器系统在性价比上极具吸引力。

分布式计算

主条目：分布式计算

分布式计算机（也被称为分布式内存多处理器系统）是指处理单元通过网络互相连接的分布式内存计算机系统。分布式计算机具有极高的可扩展性。术语“并发计算”、“并行计算”和“分布式计算”之间有很大的重叠，彼此间并没有明确的界限。 同一个系统往往可以同时被称为“并行的”与“分布式的”；在一个典型的分布式系统中，各个处理器实际上也是在并发地并行运行。

集群计算

主条目：计算机集群

一个贝奥武夫集群

集群是由一组松散耦合的计算机组成的群体，它们紧密协作，在很多方面可以被视作一台独立的计算机。 集群由多台通过网络互连的独立机器组成。尽管集群中的机器不必完全对称，但如果它们硬件存在差异，实现负载均衡就会变得更为困难。最常见的一种集群是贝奥武夫集群，它是由多台完全相同的商用现货计算机构建的，这些计算机通过基于TCP/IP的以太网局域网相连。 贝奥武夫技术最早由托马斯·斯特林和唐纳德·贝克开发。全球TOP500超级计算机榜单中，有87%的系统都属于集群架构。 剩下的部分则是大规模并行处理器（下文将介绍）。

因为网格计算系统（下文将详细描述）可以轻松处理极其并行的问题，所以现代集群通常被设计用于解决更为复杂的计算难题——这些问题要求节点之间更频繁地共享中间计算结果。这需要互连网络不仅具备高带宽，更重要的是具备低延迟。许多历史上以及现役的超级计算机都采用了专门为集群计算量身定制的定制化高性能网络硬件，例如克雷（Cray）的 Gemini 网络。 截至2014年，大多数现有的超级计算机都在使用某些标准的现成网络硬件，最常见的是Myrinet、InfiniBand或千兆以太网。

大规模并行计算

主条目：大规模并行处理系统

IBM Blue Gene/L 大规模并行超级计算机的一个机柜

大规模并行处理器（MPP）是一台包含了成百上千甚至更多联网处理器的单一计算机。MPP在很多特征上与集群相似，但MPP采用的是专用的互连网络（而集群多采用商用现货硬件进行网络连接）。此外，MPP的规模通常远大于一般集群，其处理器数量通常“远超”100个。 在一台MPP系统中，“每个CPU都配备了自己的内存、操作系统副本以及应用程序。各个子系统通过高速互连网络与其它部分进行通信。”

IBM的Blue Gene/L正是这样一台MPP，它曾在2009年6月的TOP500榜单中位列世界第五快超级计算机。

网格计算

主条目：网格计算

网格计算是并行计算分布最为广泛的一种形式。它通过互联网（Internet）将分布各地的计算机联系起来，共同处理某个特定问题。受限于互联网相对较低的带宽和极高的延迟，这种分布式计算方式通常只适合处理极其并行的问题。

大多数网格计算应用都依赖于中间件（一种介于操作系统和应用程序之间的软件层，专门负责管理网络资源及标准化软件接口）。最广为人知的网格计算中间件当属伯克利开放式网络计算平台（BOINC）。很多志愿计算软件就是利用了计算机在空闲时的“剩余周期”来执行后台计算。

云计算

主条目：云计算

互联网的普及和高带宽网络的发展催生了云计算，这是一种将大规模并行资源作为服务对外提供的模式。该范式将底层硬件进行了抽象，使得用户无需亲自动手管理物理基础设施，就能利用虚拟化的集群来处理可动态扩展的计算工作负载。

分布式账本技术

主条目：分布式账本

现代分布式账本协议巧妙地应用了并行计算原理，旨在突破传统区块链存在的串行瓶颈。通过将状态空间进行分片（sharding），新型的共识架构实现了“大规模并行的交易处理”。在这种模型下（例如Cerberus等协议所采用的方式），独立的交易被视为并行任务，并被分配到不同的节点上同时执行，而不是像过去那样在单一的全局区块中进行串行排队处理。

专用并行计算机

在并行计算的广阔天地中，存在一些专用并行设备，它们始终是属于特定领域的利基设备。虽然它们未必是针对某种特定领域语言设计的，但往往只能应用于少数几类并行计算问题。

结合FPGA的可重构计算

可重构计算涉及将现场可编程逻辑门阵列（FPGA）作为通用计算机的协处理器来使用。本质上，FPGA是一种能够根据特定任务的需要，在物理层面上重新改变自身线路连接的计算机芯片。

人们可以使用诸如VHDL或Verilog等硬件描述语言为FPGA编写程序。目前已有几家供应商推出了C转HDL语言的编译器，试图模拟大多数程序员所熟悉的C语言的语法和语义。比较著名的C转HDL语言包括Mitrion-C、Impulse C以及Handel-C。基于C++的部分SystemC子集也可以用于此目的。

AMD向第三方供应商开放其HyperTransport总线技术的决定，成为了推动高性能可重构计算发展的关键赋能技术。 据DRC电脑公司首席运营官迈克尔·R·达穆尔（Michael R. D'Amour）透露：“当我们最初走进AMD大门时，他们戏称我们是‘插槽窃贼’。而现在，他们将我们视作亲密的合作伙伴。”

图形处理器通用计算（GPGPU）

主条目：图形处理器通用计算

Nvidia的Nvidia Tesla GPGPU运算卡

在图形处理器上进行通用计算（GPGPU）是计算机工程研究中一个相对较新的趋势。GPU原本是专门为计算机图形学处理而进行了高度优化的协处理器。 而计算机图形处理领域恰恰由海量的数据并行操作所主导——尤其是线性代数中的矩阵运算。

在早期，GPGPU程序必须借道普通的图形API来执行计算任务。然而如今，业界已经构建了多种全新的编程语言和平台，旨在直接利用GPU进行通用计算，Nvidia和AMD分别推出了包含CUDA和Stream SDK的专属开发环境。其他涉及GPU编程的语言和平台还包括BrookGPU、PeakStream以及RapidMind。Nvidia甚至还在其Tesla系列中推出了专为科学计算打造的计算卡产品。技术联盟Khronos Group发布了OpenCL规范，这是一个旨在编写能够跨CPU和GPU等异构平台执行的程序的框架。目前，AMD、苹果公司、英特尔、Nvidia等多家巨头均已宣布支持OpenCL。

专用集成电路（ASIC）

主条目：专用集成电路

工程师们已经设计出了几种基于专用集成电路（ASIC）的方法来应对高度特定的并行应用。

顾名思义，ASIC是为特定应用量身定制的，因此它可以为该应用进行毫不妥协的全方位优化。这就使得对于给定的计算任务而言，ASIC往往能够击败任何通用的计算机架构。然而，ASIC必须通过紫外光刻工艺制造，这一过程需要制作掩模，成本极其昂贵。一套掩模的成本可能高达上百万美元。 （芯片所需的晶体管越小，掩模的成本就越发惊人。）与此同时，通用计算机性能的随时间演进（正如摩尔定律所描述的那样）往往会在一两代芯片之后，就将ASIC原本的性能优势蚕食殆尽。 高昂的初期成本，加上极易被遵循摩尔定律发展的通用计算硬件赶超，使得ASIC对于大多数并行计算应用而言都不够经济。不过，仍有一些特殊的ASIC被制造了出来。一个著名的例子就是计算能力达到PFLOPS级别的理化学研究所MDGRAPE-3机器，它专门使用定制的ASIC来进行分子动力学的模拟。

向量处理器

主条目：向量处理器

Cray-1 是一台经典的向量处理器。

向量处理器是一种能够对大规模数据集执行同一条指令的CPU或计算机系统。这类处理器具备针对数字或向量的一维线性数组进行操作的高级运算功能。一个经典的向量运算例子是 $A=B\times C$，其中 $A$、$B$ 和 $C$ 都是包含了64个64位浮点数字的向量。 它们与弗林分类法中的SIMD类别有着极为紧密的渊源。

在20世纪70年代和80年代，克雷公司凭借其向量处理计算机在业界名声大噪。然而，作为独立的CPU或完整的计算机系统，向量处理器如今基本上已经淡出了历史舞台。不过，现代处理器的指令集中确实融入了许多用于处理向量的指令，例如飞思卡尔半导体的AltiVec技术和英特尔的单指令流多数据流扩展（SSE）。

软件

并行编程语言

主条目：并发与并行编程语言列表

为了在并行计算机上进行编程，人们开发出了各种并发编程语言、程序库、API以及并行编程模型（例如算法骨架）。这些工具大致可以根据它们对底层内存架构的假设来划分：针对共享内存、针对分布式内存，或是针对分布式共享内存。编写共享内存语言的程序通过操作共享的内存变量进行通信；而分布式内存系统则主要依赖于消息传递。POSIX线程（Pthreads）和OpenMP是两种最被广泛使用的共享内存API；而消息传递接口（MPI）则是分布式内存中应用最广的消息传递API。 在并行编程的诸多概念中，Future与Promise被经常使用：程序的某个部分做出一个承诺（Promise），保证会在未来的某个时刻向程序的另一部分交付某个所需的数据（Future）。

目前，业界也在致力于推行并行编程标准的统一，比如针对混合多核计算的开放标准OpenHMPP。这是一种基于指令（directive）的编程模型，它提供了一套语法，通过远程过程调用（RPC），能将计算任务高效卸载到硬件加速器上，并优化与硬件内存之间的数据移动。

消费级GPU的崛起极大地推动了业界对计算内核的支持，不论是在图形API中（通常被称为计算着色器）、专用的计算API中（如OpenCL），还是在其他语言的扩展包中。

自动并行化

主条目：自动并行化

借助编译器实现串行程序的自动并行化，一直被视作并行计算领域孜孜以求的“圣杯”，在处理器时钟频率遇到瓶颈的今天，这一诉求显得尤为迫切。尽管编译器研究人员付出了几十年的努力，但自动并行化目前取得的成功仍相当有限。

主流的并行编程语言要么仍然需要程序员进行显式并行编程，要么最好也只是做到部分隐式并行——即程序员通过向编译器发送编译指令来协助其完成并行化操作。目前存在极少数能够实现完全隐式并行的编程语言，包括SISAL、Parallel Haskell、SequenceL、以及专门用于FPGA的SystemC、Mitrion-C、VHDL和Verilog。

应用程序检查点

主条目：应用程序检查点

随着计算机系统复杂度的增加，其平均故障间隔时间通常会变得越来越短。应用程序检查点是一种容错技术，系统会给应用程序打个“快照”——即记录下所有当前的资源分配状态以及变量值，类似于进行一次核心转储；倘若计算机发生崩溃，这份记录就可以用来恢复程序的运行。使用应用程序检查点意味着，程序只需从它最近一次记录的检查点重新启动即可，而无需从头再来。尽管检查点技术在许多场合下都能发挥作用，但它对那些被用于高性能计算、包含大量处理器且高度并行的系统来说，尤为不可或缺。

算法方法

随着并行计算机变得愈发庞大与快速，我们现在已经能够解决过去因为计算时间过长而无法触及的难题。从生物信息学（用于蛋白质折叠和序列分析）到经济学，形形色色的领域都已从并行计算中获益。在并行计算的应用中，常见的求解问题类型包括：

• 稠密线性代数
• 稀疏线性代数
• 谱方法（例如库利-图基快速傅里叶变换算法）
• N体问题（例如Barnes-Hut模拟）
• 结构化网格问题（例如格子玻尔兹曼方法）
• 非结构化网格问题（例如在有限元分析中所见的问题）
• 蒙特卡罗方法
• 组合逻辑（例如暴力密码分析技术）
• 图遍历（例如排序算法）
• 动态规划
• 分支定界法
• 概率图模型（例如检测隐马尔可夫模型以及构建贝叶斯网络）
• HBJ模型，一种简洁的消息传递模型
• 有限状态机模拟
• 优化问题（例如遗传算法与模拟退火）
• 粒子方法（例如网格质点法与平滑粒子流体动力学）
• 约束满足问题
• 数据挖掘与模式识别
• 机器学习与深度学习的训练
• 光线追踪与渲染
• 时间序列分析
• 流数据分析

容错机制

更多信息：容错计算机系统

并行计算的理念同样可以被应用到容错计算机系统的设计中去，最典型的便是通过锁步系统让多个组件并行执行完全相同的操作。一旦某个组件发生故障，这便能提供热备用的冗余；如果多次计算的结果出现分歧，系统还能借此进行自动的错误检测甚至错误纠正。这些方法常被用来防止由瞬态错误引起的单事件翻转效应。 尽管在嵌入式系统或高度专用的系统中有时还需要辅以额外的措施，但就商用现货系统而言，这种方法提供了一种实现N模冗余（N-modular redundancy）的极具成本效益的途径。

历史

有关此主题的更广泛信息，请参见：计算史。

ILLIAC IV，一台被称为“最声名狼藉的超级计算机”的机器

真正意义上的（MIMD）并行计算的根源，可以追溯到路易吉·费德里科·梅纳布雷亚以及他的著作《关于由查尔斯·巴贝奇发明的分析机的草图》。

1957年，布尔机器公司宣布推出了世界上第一款专门为并行性设计的计算机架构——Gamma 60。 它采用了一种Fork-Join模型，并利用一个“程序分发器”（Program Distributor）在中央存储器与各个独立的处理单元之间分发和收集数据。

1958年4月，斯坦利·吉尔（来自费兰蒂公司）探讨了并行编程以及引入分支（branching）与等待（waiting）机制的必要性。 同样在1958年，IBM的研究员约翰·科克与丹尼尔·斯洛特尼克首次在数值计算领域探讨了并行性思想的运用。 宝来公司于1962年推出了D825，这是一款配备了四个处理器的计算机，通过交叉开关矩阵能够访问多达16个内存模块。 1967年，在一次美国信息处理学会联合会的会议上，阿姆达尔与斯洛特尼克针对并行处理的可行性展开了激烈的辩论。 正是在这场辩论的背景下，后人熟知的阿姆达尔定律被提了出来，用以界定由并行化所能带来的加速极限。

1969年，霍尼韦尔推出了首款基于Multics的系统，这是一个能够并行运行多达八个处理器的对称多处理器系统。 诞生于20世纪70年代的C.mmp是卡内基梅隆大学发起的一个多处理器项目，它是首批处理器数量超过寥寥几个的多处理器系统之一。而1984年的 Synapse N+1 则是首台具备窥探缓存（snooping caches）并基于总线连接的多处理器计算机。

SIMD并行计算机的历史同样可以追溯到20世纪70年代。设计早期SIMD计算机的初衷，是为了将处理器控制单元的门电路传播延迟分摊到多条指令上去。 早在1964年，斯洛特尼克就曾提议为劳伦斯利弗莫尔国家实验室建造一台大规模并行计算机。 他的这项设计后来获得了美国空军的资助，这便是最早投入实际研发的SIMD并行计算工程——ILLIAC IV。 其设计的核心在于极高的并行度，规划了多达256个处理器，允许机器对巨量的数据集执行操作，这种思想后来演变成了人们所熟知的向量处理。然而，ILLIAC IV却被贴上了“最声名狼藉的超级计算机”的标签，因为该项目耗时11年，开销几乎飙升至最初预算的四倍，而最终只完成了原计划规模的四分之一。 当它在1976年终于准备好运行第一个真正的应用程序时，它的性能反而被当时已经上市的商用超级计算机（如Cray-1）抛在了身后。

作为大规模并行计算机的生物大脑

早在20世纪70年代初，在麻省理工学院计算机科学与人工智能实验室，马文·明斯基和西摩·派普特就开始构思他们的《心智社会》理论，该理论将生物的大脑视作一台大规模并行计算机器。1986年，明斯基出版了《心智社会》一书，他在书中提出“心智是由众多微小的智能体（agent）组成的，而这些智能体本身是没有智能的”。 该理论试图解释我们称之为“智能”的现象，是如何通过那些不具备智能的微小部件相互作用而涌现出来的。明斯基坦言，触发该理论灵感的最主要来源是他试图创造一种能够操纵机器臂、摄像机以及计算机去搭积木的机器人的研究工作。

类似的模型（同样将生物大脑视为一台大规模并行计算机，即认为大脑由一群独立的或半独立的智能体组成）也被以下学者或著作提出过：

• 托马斯·R·布莱克斯利（Thomas R. Blakeslee），
• 迈克尔·加扎尼加，
• 罗伯特·奥恩斯坦，
• 欧内斯特·希尔加德，
• 加来道雄，
• 乔治·葛吉夫，
• 神经集群大脑模型（Neurocluster Brain Model）。

参见

• 计算机多任务处理
• 并发 (计算机科学)
• 内容可寻址并行处理器
• 分布式计算学术会议列表
• 循环级并行
• 曼彻斯特数据流机器
• 众核
• 并行通信
• 并行编程模型
• 并行化契约
• 可串行化
• 同步编程
• Transputer
• 向量处理

延伸阅读

• Rodriguez, C.; Villagra, M.; Baran, B. Asynchronous team algorithms for Boolean Satisfiability. 2007 2nd Bio-Inspired Models of Network, Information and Computing Systems. 29 August 2008: 66–69. S2CID 15185219. doi:10.1109/BIMNICS.2007.4610083. 
• Sechin, A.; Parallel Computing in Photogrammetry. GIM International. #1, 2016, pp. 21–23.

外部链接

• Lawrence Livermore National Laboratory: Introduction to Parallel Computing
• Designing and Building Parallel Programs, by Ian Foster
• Internet Parallel Computing Archive