BLOG

并行计算

并行计算是一种同时执行许多计算或过程的计算类型。大问题往往可以分解为小问题，然后同时解决。

并行计算有几种不同的形式：位级并行、指令级并行、数据并行和任务并行。并行性长期以来一直被用于高性能计算，但由于物理限制阻碍了频率扩展，它引起了更广泛的兴趣。近年来，随着计算机的功耗（以及由此产生的热量）成为人们关注的问题，并行计算已成为计算机体系结构的主导范例，主要以多核处理器的形式出现。

并行计算与并发计算密切相关--它们经常被一起使用，也经常被混为一谈，尽管两者是截然不同的：有并行却没有并发，有并发却没有并行（如在单核 CPU 上通过分时进行多任务处理）。在并行计算中，一个计算任务通常会被分解成几个（通常是很多个）非常相似的子任务，这些子任务可以独立处理，并在完成后将其结果合并。相比之下，在并发计算中，各个进程通常不会处理相关的任务；当它们处理相关任务时（如分布式计算中的典型情况），独立的任务可能具有不同的性质，在执行过程中通常需要进行一些进程间通信。

并行计算机可以根据硬件支持并行性的级别大致分类，多核和多处理器计算机在单个机器内具有多个处理单元，而集群、 MPP和网格则使用多台计算机在同一台计算机上工作任务。专门的并行计算机架构有时与传统处理器一起使用，以加速特定任务。

在某些情况下，并行对程序员来说是透明的，如位级或指令级并行，但明确的并行算法，特别是那些使用并发的算法，比顺序算法更难编写，因为并发引入了几类新的潜在软件错误，其中竞赛条件是最常见的。不同子任务之间的通信和同步通常是获得最佳并行程序性能的最大障碍。

Amdahl （阿姆达尔）定律给出了并行化后单个程序速度提升的理论上限，该定律指出，速度提升受限于可利用并行化的部分时间。

背景

传统上，计算机软件是为串行计算而编写的。为了解决一个问题，算法是以串行指令流的形式构建和实现的。这些指令在一台计算机的中央处理单元上执行。每次只能执行一条指令，该指令执行完毕后，下一条指令开始执行。

而并行计算则是同时使用多个处理元件来解决问题。具体做法是将问题分解成独立的部分，使每个处理元件都能与其他处理元件同时执行算法中的自己部分。处理元素可以是多种多样的，包括带有多个处理器的单台计算机、多台联网计算机、专用硬件等资源，或上述资源的任意组合。并行计算历来用于科学计算和科学问题的模拟，尤其是在气象学等自然科学和工程科学领域。这导致了并行硬件和软件以及高性能计算的设计。

从 20 世纪 80 年代中期到 2004 年，频率扩展是计算机性能提高的主要原因。程序的运行时间等于指令数乘以每条指令的平均时间。在其他条件不变的情况下，提高时钟频率会减少执行一条指令所需的平均时间。因此，频率的增加会减少所有计算型程序的运行时间。然而，芯片的功耗 P 是由公式 P = C × V 2 × F 得出的，其中 C 是每个时钟周期切换的电容（与输入变化的晶体管数量成正比），V 是电压，F 是处理器频率（每秒周期数）。频率的提高会增加处理器的功耗。处理器功耗的增加最终导致英特尔公司于 2004 年 5 月 8 日取消了 Tejas 和 Jayhawk 处理器，这被普遍认为是频率扩展作为主流计算机架构模式的终结。

为了解决功耗和过热问题，主要的中央处理器（CPU 或处理器）制造商开始生产具有多个内核的高能效处理器。内核是处理器的计算单元，在多核处理器中，每个内核都是独立的，可以同时访问相同的内存。多核处理器为台式电脑带来了并行计算。因此，串行程序的并行化已成为主流编程任务。2012 年，四核处理器成为台式电脑的标准配置，而服务器则拥有 10 核以上的处理器。根据摩尔定律可以预测，每个处理器的内核数量将每 18-24 个月翻一番。这可能意味着 2020 年后，一个典型的处理器将拥有数十或数百个内核，但实际上，标准内核大约在 4 到 16 个之间，由于散热和设计上的限制，有些设计混合了性能和效率内核（如 ARM 的 big.LITTLE 设计）。

操作系统可确保不同任务和用户程序在可用内核上并行运行。然而，要使串行软件程序充分利用多核架构，程序员需要对代码进行重组和并行化。应用软件运行时间的加速将不再通过频率扩展来实现，程序员需要对软件代码进行并行化处理，以利用多核架构不断增强的计算能力。

Amdahl's law and Gustafson's 定律

最理想的情况是，并行化带来的速度提升是线性的--处理元素数量增加一倍，运行时间减半，再增加一倍，运行时间再次减半。然而，很少有并行算法能达到最佳速度。大多数并行算法在处理元素数量较少的情况下速度接近线性，而在处理元素数量较多的情况下，速度会趋于平缓，变成一个恒定值。

算法在并行计算平台上的潜在加速度由阿姆达尔定律给出

其中

• Slatency 是执行整个任务的潜在加速延迟；
• s 是任务可并行化部分执行延迟的加速度；
• p 是并行化前整个任务可并行化部分执行时间的百分比。

由于 Slatency < 1/(1-p)，它表明程序中不能并行化的一小部分将限制并行化带来的整体速度提升。一个解决大型数学或工程问题的程序通常由几个可并行化的部分和几个不可并行化（串行）的部分组成。如果程序中不可并行的部分占运行时间的 10% (p = 0.9)，那么无论增加多少处理器，我们的速度都不会超过 10 倍。这就为增加并行执行单元的效用设置了上限。"当任务因顺序限制而无法分割时，增加工作量对进度没有任何影响。无论分配多少妇女，生一个孩子都需要 9 个月的时间"。

阿姆达尔定律只适用于问题规模固定的情况。实际上，随着计算资源的增多，它们往往会被用于处理更大的问题（更大的数据集），可并行化部分所花费时间的增长速度往往比固有的串行工作快得多。在这种情况下，古斯塔夫森定律对并行性能的评估就不那么悲观，而是更切合实际：

阿姆达尔定律和古斯塔夫森定律都假设程序串行部分的运行时间与处理器数量无关。阿姆达尔定律假定整个问题的大小是固定的，因此并行处理的总工作量也与处理器数量无关，而古斯塔夫森定律假定并行处理的总工作量与处理器数量呈线性变化。

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

并行程序中的子任务通常称为线程。一些并行计算机体系结构使用较小的轻量级线程，称为 "纤维"，而另一些则使用较大的线程，称为 "进程"。不过，"线程 "通常被接受为子任务的通用术语。线程通常需要同步访问对象或其他资源，例如，当它们必须更新它们之间共享的变量时。如果没有同步，两个线程之间的指令可以任意顺序交错执行。

使用非原子锁锁定多个变量可能会导致程序死锁。原子锁会同时锁定多个变量。如果不能锁定所有变量，就不会锁定任何变量。如果两个线程分别需要使用非原子锁锁定相同的两个变量，那么可能会出现一个线程锁定其中一个变量，而第二个线程锁定第二个变量的情况。在这种情况下，两个线程都无法完成，从而导致死锁。

许多并行程序要求其子任务同步运行。这就需要使用障碍。障碍通常使用锁或信号来实现。有一类算法，即所谓的无锁算法和无等待算法，可以完全避免使用锁和障碍。不过，这种方法一般很难实现，需要正确设计数据结构。

并不是所有的并行化都能提高速度。一般来说，当一个任务被分割成越来越多的线程时，这些线程会花费越来越多的时间相互通信或等待对方访问资源。一旦资源争用或通信所产生的开销超过了其他计算所花费的时间，进一步并行化（即把工作负载分割给更多线程）就会增加而不是减少完成任务所需的时间。这个问题被称为并行减速，在某些情况下可以通过软件分析和重新设计来改善。

细粒度、粗粒度、尴尬并行

应用程序通常根据其子任务需要同步或相互通信的频率进行分类。如果应用程序的子任务每秒必须多次通信，则表现出细粒度并行性；如果子任务每秒不多次通信，则表现出粗粒度并行性；如果子任务很少或从不通信，则表现出令人尴尬的并行性。令人尴尬的并行应用被认为是最容易并行化的。

Flynn分类法

迈克尔-J-弗林（Michael J. Flynn）创建了最早的并行（和顺序）计算机和程序分类系统之一，即现在的弗林分类法。弗林根据程序和计算机是使用单组指令还是多组指令运行，以及这些指令是使用单组数据还是多组数据进行分类。

Flynn 定义的四种初始分类基于架构中可用的并发指令（或控制）流和数据流的数量。 Flynn 于 1972 年定义了 SIMD 的三个附加子类别。

• 单指令流、单数据流（SISD）

  顺序计算机在指令或数据流中不利用并行性。单个控制单元 (CU) 从内存中获取单个指令流 (IS)。然后CU生成适当的控制信号以指导单个处理元件(PE)对单个数据流(DS)进行操作，即一次一个操作。

  SISD 架构的示例是传统的单处理器机器，例如老式个人计算机(PC)（到 2010 年，许多 PC 具有多个内核）和大型计算机。

• 单指令流、多数据流（SIMD）

  单个指令同时应用于多个不同的数据流。指令可以例如通过流水线顺序执行，或者由多个功能单元并行执行。 Flynn 1972 年的论文将 SIMD 进一步细分为三个类别：

  • 阵列处理器（Array processor）– 这些处理器接收一条（相同）指令，但每个并行处理单元都有自己独立且不同的内存和寄存器文件。
  • 流水线处理器（Pipelined processor）——它们接收一条（相同的）指令，然后从中央资源读取数据，每个处理器处理该数据的片段，然后将结果写回到同一中央资源。在 Flynn 1972 年论文的图 5 中，资源是主内存：对于现代 CPU，该资源现在更典型的是寄存器文件。
  • 关联处理器（Associative processor）– 这些处理器接收一条（相同）指令，但在每个并行处理单元中，根据单元本地数据做出独立决策，决定是否执行执行或是否跳过执行。在现代术语中，这称为“谓词”（屏蔽）SIMD。

  阵列处理器

  阵列处理器的现代术语是“单指令、多线程”(SIMT)。这是 Flynn 1972 年分类法中的一个独特分类，作为 SIMD 的一个子类别。它可以通过具有自己独立的寄存器文件和存储器（高速缓存和数据存储器）的并行子元件来识别。 Flynn 的原始论文引用了 SIMT 处理器的两个历史示例： SOLOMON和ILLIAC IV 。

  Nvidia 通常在其营销材料和技术文档中使用该术语，以证明其架构的新颖性。 SOLOMON 比 Nvidia 早 60 多年。

  Aspex 微电子关联字符串处理器 (ASP) 在其营销材料中将自己归类为“大规模宽 SIMD”，但具有位级ALU 和位级预测（Flynn 的分类法：关联处理），并且每个 4096 处理器都有自己的寄存器和内存（弗林的分类法：数组处理）。 2010 年发布的 Linedancer 包含 4096 个 2 位谓词 SIMD ALU，每个都有自己的内容可寻址存储器，每秒能够处理 8000 亿条指令。 Aspex 的 ASP 关联阵列 SIMT 处理器比 NVIDIA 早 20 年。

  流水线处理器

  Flynn 在 1972 年撰写论文时，许多系统都使用主内存作为管道读写的资源。当所有“管道”读取和写入的资源是寄存器文件而不是主存储器时，就会产生 SIMD 的现代变体。示例包括Altivec 、 NEON和AVX 。

  这种类型的基于寄存器的 SIMD 的另一个名称是“打包 SIMD”，另一个名称是寄存器内的 SIMD (SWAR) 。当应用谓词时，就变成了联想处理（下）

  关联处理器

  关联处理器的现代术语是“谓词”（或屏蔽）SIMD。示例包括AVX-512 。

  一些现代设计（特别是GPU ）采用了多个子类别的特征：当今的 GPU 是 SIMT，但也是关联的，即 SIMT 阵列中的每个处理元素也是可预测的。

• 多指令流、单数据流（MISD）

  多条指令对一个数据流进行操作。这是一种不常见的架构，通常用于容错。异构系统在相同的数据流上运行，并且必须就结果达成一致。例子包括航天飞机飞行控制计算机。

• 多指令流、多数据流（MIMD）

  多个自主处理器同时对不同数据执行不同指令。 MIMD 架构包括多核超标量处理器和分布式系统，使用一个共享内存空间或分布式内存空间。

  有些人将 MIMD 类别进一步划分为以下两类，有时甚至考虑进一步细分。

  单程序、多数据流（SPMD）

  多个自治处理器同时对不同的数据执行相同的程序（但在独立的点上，而不是按照 SIMD 规定的锁步）。也称为单进程、多数据- 使用 SPMD 这一术语在技术上是不正确的，因为 SPMD 是并行执行模型，并假设多个协作处理器执行程序。 SPMD 是最常见的显式并行编程风格。 SPMD模型和术语是由RP3团队的Frederica Darema提出的。

  • 程序的同一部分（"单程序"）会被划分成多个部分，每个部分在不同的处理器上运行，但每个处理器都用不同的输入数据执行同样的操作。任务在每个处理器上并行执行，计算结果会在合适的时机进行汇合（同步）。
  • 每个处理器开始时执行相同的程序，但通过同步指令（如锁、条件判断等）使得各个处理器可以选择性地处理不同的任务或数据。

  多程序、多数据流（MPMD）

  多个自主处理器同时运行至少两个独立程序。在 HPC 环境中，此类系统通常选择一个节点作为“主机”（“显式主机/节点编程模型”）或“管理器”（“管理器/工作器”策略），该节点运行一个程序，将数据分包给所有其他节点都运行第二个程序。然后，其他节点将其结果直接返回给管理器。

  MPMD 在非 HPC 环境中很常见。例如，除了 make 可执行文件本身之外， make构建系统还可以使用依赖于目标的程序来并行构建多个依赖项。 MPMD 也经常采用管道的形式。一个简单的 Unix shell 命令，如ls | grep “A”| more启动三个进程，并行运行单独的程序，其中一个进程的输出用作下一个程序的输入。

  它们都与 HPC 中使用的显式并行编程不同，因为各个程序是通用构建块，而不是实现特定并行算法的一部分。在流水线方法中，可用并行量不会随着数据集大小的增加而增加。

并行粒度

Bit-level parallelism

从 20 世纪 70 年代超大规模集成（VLSI）计算机芯片制造技术问世到 1986 年左右，计算机体系结构的提速主要是通过将计算机字长（即处理器每个周期可处理的信息量）增加一倍来实现的。字长的增加减少了处理器在对大小大于字长的变量进行操作时必须执行的指令数量。例如，如果 8 位处理器必须将两个 16 位整数相加，处理器必须首先使用标准加法指令将每个整数的 8 个低阶位相加，然后使用带进位的加法指令和低阶加法的进位将 8 个高阶位相加；因此，8 位处理器需要执行两条指令才能完成一次操作，而 16 位处理器只需执行一条指令即可完成操作。

从历史上看，4 位微处理器先后被 8 位、16 位和 32 位微处理器取代。随着 32 位处理器的问世，这一趋势总体上告一段落，20 年来，32 位处理器一直是通用计算的标准。直到 2000 年代初，随着 x86-64 架构的出现，64 位处理器才开始普及

Instruction-level parallelism

计算机程序实质上是由处理器执行的指令流。如果没有指令级并行，处理器每个时钟周期只能发出少于一条指令（IPC < 1）。这些处理器被称为亚标量处理器。这些指令可以重新排序并组合成指令组，然后在不改变程序结果的情况下并行执行。这就是所谓的指令级并行。从 20 世纪 80 年代中期到 20 世纪 90 年代中期，指令级并行技术的进步一直主导着计算机体系结构的发展

所有现代处理器都有多级指令流水线。流水线中的每个阶段都对应着处理器对该阶段中的指令执行的不同操作；一个拥有 N 级流水线的处理器在不同的完成阶段可以有多达 N 条不同的指令，因此每个时钟周期可以发出一条指令（IPC = 1）。这些处理器被称为标量处理器。流水线处理器的典型例子是 RISC 处理器，有五个阶段：指令获取 (IF)、指令解码 (ID)、执行 (EX)、内存访问 (MEM) 和寄存器回写 (WB)。奔腾 4 处理器拥有 35 级流水线。

大多数现代处理器还具有多个执行单元。它们通常将这一特性与流水线技术相结合，因此每个时钟周期可发出一条以上的指令（IPC > 1）。这些处理器被称为超标量处理器。超标量处理器与多核处理器的不同之处在于，多个执行单元并不是整个处理器（即处理单元）。只有当指令之间不存在数据依赖关系时，才能将它们组合在一起。记分卡和 Tomasulo 算法（与记分卡类似，但使用寄存器重命名）是实现超阶执行和指令级并行的两种最常用技术

编译器和处理器设计人员的目标是尽可能多地识别和利用 ILP。普通程序通常是在顺序执行模型下编写的，其中指令一条接一条地执行，并按照程序员指定的顺序执行。ILP 允许编译器和处理器重叠执行多条指令，甚至可以改变指令执行的顺序。

程序中存在多少 ILP 是非常特定于应用程序的。在某些领域，例如图形和科学计算，数量可能非常大。然而，密码学等工作负载可能表现出更少的并行性。

用于利用 ILP 的微架构技术包括：

• 多条指令的执行可以部分重叠的指令流水线。
• 超标量VLIW显式并行指令计算执行单元执行、和密切相关的概念，其中多个用于并行执行多条指令。
• 乱序执行，其中指令以不违反数据依赖性的任何顺序执行。请注意，此技术独立于流水线和超标量执行。当前动态乱序执行的实现（即，当程序正在执行并且没有编译器的任何帮助时）从普通程序中提取 ILP。另一种方法是在编译时提取这种并行性，并以某种方式将此信息传递给硬件。由于缩放乱序执行技术的复杂性，业界重新检查了指令集，这些指令集明确编码每条指令的多个独立操作。
• 寄存器重命名指的是一种技术，用于避免因这些操作重用寄存器而强加的不必要的程序操作序列化，用于实现乱序执行。
• 推测执行，允许在确定是否应该执行之前执行完整指令或部分指令。推测执行的常用形式是控制流推测，其中在控制流指令的目标被确定之前执行通过控制流指令（例如，分支）的指令。已经提出并正在使用其他几种推测执行形式，包括由值预测、内存依赖预测和缓存延迟预测驱动的推测执行。
• 分支预测，用于避免拖延以解决控制依赖性。分支预测与推测执行一起使用。

众所周知，编译器和硬件支持都利用了 ILP，但编译器还通过编译时优化为硬件提供了程序中固有和隐式的 ILP。用于在程序中提取可用 ILP 的一些优化技术包括指令调度、寄存器分配/重命名和内存访问优化。

数据流架构是另一类明确指定 ILP 的架构，有关最近的示例，请参阅TRIPS 架构。

近年来，尽管处理器工作频率和内存访问时间之间的差异越来越大（早期的 ILP 设计，例如 IBM System/360 Model 91使用 ILP 技术来克服相对较小的寄存器文件带来的限制）。目前，对主存储器的高速缓存未命中惩罚会花费数百个 CPU 周期。虽然原则上可以使用 ILP 来容忍这种内存延迟，但相关的资源和功耗成本是不成比例的。此外，底层硬件结构的复杂性和延迟通常会导致操作频率降低，从而进一步减少任何好处。因此，上述技术证明不足以防止 CPU 因片外数据而停止。相反，该行业正朝着开发更高级别的并行性的方向发展，这些并行性可以通过多处理和多线程等技术加以利用。[4]

Task parallelism

任务并行性（也称为函数并行性和控制并行性）是并行计算环境中跨多个处理器的计算机代码并行化的一种形式。任务并行性侧重于在不同处理器之间分配任务（由进程或线程同时执行）。与涉及在不同数据组件上运行相同任务的数据并行性相比，任务并行性的特点是在同一数据上同时运行许多不同的任务。[1]一种常见的任务并行类型是流水线，它包括通过一系列单独的任务移动一组数据，其中每个任务都可以独立于其他任务执行。

线程级并行性( TLP ) 是同时运行多个线程的应用程序中固有的并行性。这种类型的并行性主要出现在为商业服务器（如数据库）编写的应用程序中。通过一次运行多个线程，这些应用程序能够承受其工作负载可能产生的大量 I/O 和内存系统延迟 - 当一个线程延迟等待内存或磁盘访问时，其他线程可以执行有用的工作。

随着多核微处理器的出现，线程级并行性的开发也开始进入桌面市场。发生这种情况是因为，出于各种原因，提高单核的时钟速度或每个时钟的指令变得越来越不切实际。如果这种趋势继续下去，新的应用程序将不得不设计为利用多线程，以便从潜在计算能力的增加中获益。这与之前的微处理器创新形成鲜明对比，在这些创新中，现有代码通过在更新/更快的计算机上运行而自动加速。

任务并行是指并行程序具有 "可对相同或不同的数据集进行完全不同的计算 "的特性。这与数据并行不同，数据并行是指在相同或不同的数据集上执行相同的计算。任务并行涉及将任务分解为子任务，然后将每个子任务分配给一个处理器执行。然后，处理器将并发执行这些子任务，通常是合作执行。任务并行通常不会随着问题的大小而扩展

内存级并行（MLP）

内存级并行( MLP ) 是计算机体系结构中的一个术语，指的是同时 处理多个内存操作的能力，特别是高速缓存未命中或转换后备缓冲区(TLB) 未命中。

在单个处理器中，MLP 可被视为指令级并行(ILP) 的一种形式。然而，ILP 通常与超标量混为一谈，即同时执行多条指令的能力，例如英特尔奔腾 Pro等处理器是五路超标量，能够在给定周期内开始执行五个不同的微指令，但它可以随时处理多达 20 条不同的加载微指令的四种不同的缓存未命中。

有可能拥有一台不是超标量但仍然具有高 MLP 的机器。

可以说，一台没有 ILP 的机器，它不是超标量的，它以非流水线方式一次执行一条指令，但它执行硬件预取（不是软件指令级预取）表现出 MLP（由于多个预取未完成）但是不是 ILP。这是因为有多个内存操作未完成，但不是指令。指令通常与操作混为一谈。

此外，多处理器和多线程计算机系统可以说由于并行性而表现出 MLP 和 ILP——但不是线程内、单进程、ILP 和 MLP。然而，我们通常将术语 MLP 和 ILP 限制为指从看似非并行的单线程代码中提取此类并行性。

数据并行性（DLP）

数据并行性是并行计算环境中跨多个处理器的并行化。它侧重于将数据分布在不同的节点上，这些节点对数据进行并行操作。通过并行处理每个元素，它可以应用于数组和矩阵等常规数据结构。它与作为另一种形式的并行性的任务并行性形成对比。

数据并行与任务并行

数据并行与模型并行

当今有多种数据并行编程环境可用，其中使用最广泛的是：

1. 消息传递接口：它是用于并行计算机的跨平台消息传递编程接口。它定义了库函数的语义，允许用户用 C、C++ 和 Fortran 编写可移植的消息传递程序。
2. Open Multi Processing [8]（Open MP）：它是一个应用程序编程接口（API），支持在多处理器系统的多个平台上共享内存编程模型。
3. CUDA和OpenACC：CUDA 和 OpenACC（分别）是并行计算 API 平台，旨在允许软件工程师利用 GPU 的计算单元进行通用处理。
4. Threading Building Blocks和RaftLib：这两种开源编程环境都支持跨异构资源在 C/C++ 环境中实现混合数据/任务并行。

模型并行是指将模型分布在多个设备或机器上。这使得模型太大而无法放入单个设备的内存中。在这种情况下，模型的不同部分运行在不同的设备上，设备之间的通信是执行前向和后向传递所必需的。

Hardware

Memory and communication

并行计算机中的主存储器要么是共享存储器（在单个地址空间中的所有处理元件之间共享），要么是分布式存储器（其中每个处理元件都有其自己的本地地址空间）。分布式内存指的是内存在逻辑上是分布的，但通常意味着它在物理上也是分布的。分布式共享内存和内存虚拟化结合了这两种方法，其中处理元件拥有自己的本地内存并可以访问非本地处理器上的内存。对本地存储器的访问通常比对非本地存储器的访问更快。在超级计算机上，可以使用PGAS等编程模型来实现分布式共享内存空间。该模型允许一个计算节点上的进程透明地访问另一计算节点的远程内存。所有计算节点还通过高速互连连接到外部共享内存系统，例如Infiniband ，这种外部共享内存系统称为突发缓冲区，通常由物理分布在多个I/上的非易失性内存阵列构建。 O 节点。

非均匀内存访问(NUMA) 架构的逻辑视图。一个目录中的处理器访问该目录内存的延迟比访问另一目录内存中的内存的延迟要短。

可以以相同的延迟和带宽访问主存储器的每个元素的计算机体系结构被称为统一存储器访问（UMA）系统。通常，这只能通过共享内存系统来实现，其中内存不是物理分布的。不具有此属性的系统称为非均匀内存访问(NUMA) 体系结构。分布式内存系统具有非统一的内存访问。

计算机系统利用高速缓存——靠近处理器的小而快速的存储器，用于存储存储器值的临时副本（在物理和逻辑意义上都在附近）。并行计算机系统在高速缓存方面存在困难，因为高速缓存可能在多个位置存储相同的值，并且可能会导致程序执行不正确。这些计算机需要缓存一致性系统，该系统可以跟踪缓存的值并有策略地清除它们，从而确保正确的程序执行。总线监听是跟踪正在访问哪些值（因此应该清除）的最常见方法之一。设计大型、高性能的缓存一致性系统是计算机体系结构中的一个非常困难的问题。因此，共享内存计算机架构的扩展性不如分布式内存系统。

处理器-处理器和处理器-内存通信可以通过多种方式在硬件中实现，包括通过共享（多端口或多路复用）内存、交叉开关、共享总线或各种拓扑（包括星形、环形、树形）的互连网络、 hypercube 、 fat hypercube （在一个节点上具有多个处理器的超立方体）或n 维网格。

基于互连网络的并行计算机需要具有某种路由，以便能够在不直接连接的节点之间传递消息。在大型多处理器机器中，用于处理器之间通信的介质可能是分层的。

parallel computers 分类

并行计算机可根据硬件支持并行性的程度进行粗略分类。这种分类大致类似于基本计算节点之间的距离。这些分类并不相互排斥；例如，对称多处理器集群就比较常见

• Multi-core computing(Multi-core processor)

  多核处理器是在同一芯片上包含多个处理单元（称为“核心”）的处理器。该处理器与超标量处理器不同，超标量处理器包括多个执行单元，并且可以在每个时钟周期从一个指令流（线程）发出多条指令；相反，多核处理器可以在每个时钟周期从多个指令流发出多个指令。 IBM的Cell 微处理器专为索尼PlayStation 3使用而设计，是一款出色的多核处理器。多核处理器中的每个核心也可能是超标量的，也就是说，在每个时钟周期，每个核心都可以从一个线程发出多条指令。

  同步多线程（其中最著名的是英特尔的超线程）是伪多核的早期形式。能够并发多线程的处理器在同一处理单元中包含多个执行单元，即具有超标量架构，并且可以在每个时钟周期从多个线程发出多条指令。另一方面，临时多线程在同一处理单元中包括单个执行单元，并且可以从多个线程一次发出一条指令。

• Symmetric multiprocessing（对称多处理器SMP）(Symmetric multiprocessing)

  对称多处理器 (SMP) 是一种具有多个相同处理器的计算机系统，这些处理器共享内存并通过总线连接。总线争用会阻碍总线架构的扩展。因此，SMP 通常不包含超过 32 个处理器。由于处理器尺寸较小，并且通过大型高速缓存可显着降低对总线带宽的要求，因此只要存在足够的内存带宽，这种对称多处理器就极具成本效益。

• Distributed computing（分布式计算）(Distributed computing)

  分布式计算机（也称为分布式内存多处理器）是其中处理元件通过网络连接的分布式内存计算机系统。分布式计算机具有高度可扩展性。 “并发计算”、“并行计算”和“分布式计算”等术语有很多重叠，并且它们之间不存在明确的区别。同一系统可以同时具有“并行”和“分布式”的特征；典型分布式系统中的处理器同时并行运行

• Cluster computing（集群计算）(Computer cluster)

  集群是一组紧密协作的松散耦合的计算机，因此在某些方面它们可以被视为一台计算机。集群由通过网络连接的多台独立机器组成。虽然集群中的机器不必是对称的，但如果不对称，负载平衡就会更加困难。最常见的集群类型是Beowulf 集群，它是在通过TCP/IP以太网局域网连接的多台相同的商用现成计算机上实现的集群。 Beowulf 技术最初由Thomas Sterling和Donald Becker开发。 Top500超级计算机中 87% 是集群。其余的是大规模并行处理器，如下所述。

  由于网格计算系统（如下所述）可以轻松处理令人尴尬的并行问题，因此现代集群通常被设计为处理更困难的问题，即需要节点更频繁地彼此共享中间结果的问题。这需要高带宽，更重要的是低延迟的互连网络。许多历史上和现在的超级计算机都使用专门为集群计算设计的定制高性能网络硬件，例如 Cray Gemini 网络。截至 2014 年，当前大多数超级计算机都使用一些现成的标准网络硬件，通常是Myrinet 、 InfiniBand或千兆位以太网。

• Massively parallel computing（大规模并行计算）(Massively parallel (computing))

  大规模并行处理器 (MPP) 是具有许多联网处理器的单个计算机。 MPP 具有许多与集群相同的特征，但 MPP 具有专门的互连网络（而集群使用商用硬件进行联网）。 MPP 也往往比集群更大，通常拥有“远远超过”100 个处理器。在 MPP 中，“每个 CPU 都包含自己的内存以及操作系统和应用程序的副本。每个子系统通过高速互连与其他子系统进行通信。”

  根据 2009 年 6 月的TOP500排名， IBM的Blue Gene/L是世界上第五快的超级计算机，它是一台 MPP。

• Grid computing（网格计算）(Grid computing)

  网格计算是并行计算的最分布式形式。它利用通过互联网进行通信的计算机来解决给定的问题。由于互联网上的低带宽和极高的延迟，分布式计算通常只能处理令人尴尬的并行问题。

  大多数网格计算应用程序都使用中间件（位于操作系统和应用程序之间的软件，用于管理网络资源并标准化软件接口）。最常见的网格计算中间件是伯克利网络计算开放基础设施（BOINC）。通常，志愿计算软件会利用“空闲周期”，在计算机空闲时执行计算。

• 云计算

  互联网的普及带来了大规模云计算的可能性。

• Specialized parallel computers（专用并行计算机）

  在并行计算中，有一些专门的并行设备仍然是人们感兴趣的小众领域。虽然不是特定于领域的，但它们往往仅适用于几类并行问题。

• Reconfigurable computing with field-programmable gate arrays（利用现场可编程门阵列实现可重构计算）

  可重构计算是使用现场可编程门阵列（FPGA）作为通用计算机的协处理器。 FPGA 本质上是一种可以为给定任务重新布线的计算机芯片。

  FPGA 可以使用VHDL或Verilog等硬件描述语言进行编程。一些供应商已经创建了C 到 HDL语言，试图模拟大多数程序员所熟悉的C 编程语言的语法和语义。最著名的 C 到 HDL 语言是Mitrion-C 、 Impulse C和Handel-C 。基于 C++ 的SystemC的特定子集也可以用于此目的。

  AMD决定向第三方供应商开放其HyperTransport技术，这已成为高性能可重构计算的支持技术。 DRC 计算机公司首席运营官 Michael R. D'Amour 表示，“当我们第一次走进 AMD 时，他们称我们为‘套接字窃取者’。现在他们称我们为他们的合作伙伴。”

• General-purpose computing on graphics processing units (GPGPU)(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 。

• Application-specific integrated circuits（专用集成电路）(Application-specific integrated circuit)

  已经设计了几种专用集成电路（ASIC）方法来处理并行应用。

  由于 ASIC（根据定义）特定于给定应用，因此可以针对该应用进行全面优化。因此，对于给定的应用，ASIC 的性能往往优于通用计算机。然而，ASIC 是通过紫外光刻技术创建的。此过程需要掩模组，这可能非常昂贵。一套面具的售价可能超过一百万美元。 （芯片所需的晶体管越小，掩模就越昂贵。）同时，随着时间的推移，通用计算的性能提高（如摩尔定律所述）往往会在一两代芯片内消除这些增益。高昂的初始成本以及被摩尔定律驱动的通用计算所取代的趋势，使得 ASIC 无法用于大多数并行计算应用。不过，有些已经建成。 PFLOPS RIKEN MDGRAPE-3机器就是一个例子，它使用定制 ASIC 进行分子动力学模拟。

• Vector processors（向量式处理器）(Vector processor)

  矢量处理器是可以对大量数据执行相同指令的 CPU 或计算机系统。矢量处理器具有适用于数字或矢量线性数组的高级操作。向量运算的示例为A = B × C ，其中A 、 B和C均为 64 位浮点数的 64 元素向量。它们与 Flynn 的 SIMD 分类密切相关。

  Cray计算机在 20 世纪 70 年代和 80 年代因其矢量处理计算机而闻名。然而，矢量处理器（无论是 CPU 还是完整的计算机系统）通常已经消失。现代处理器指令集确实包含一些矢量处理指令，例如飞思卡尔半导体的AltiVec和英特尔的Streaming SIMD Extensions (SSE)。

Software

Parallel programming languages

(List of concurrent and parallel programming languages)

并发编程语言、库、 API和并行编程模型（例如算法骨架）已被创建用于对并行计算机进行编程。通常可以根据对底层内存架构（共享内存、分布式内存或共享分布式内存）所做的假设将其分为几类。共享内存编程语言通过操作共享内存变量进行通信。分布式内存使用消息传递。 POSIX 线程和OpenMP是两个最广泛使用的共享内存 API，而消息传递接口(MPI) 是最广泛使用的消息传递系统 API。并行程序编程中使用的一个概念是未来概念，其中程序的一部分承诺在未来的某个时间向程序的另一部分传递所需的数据。

标准化并行编程的努力包括一个名为OpenHMPP的开放标准，用于混合多核并行编程。基于 OpenHMPP 指令的编程模型提供了一种语法，可以有效卸载硬件加速器上的计算，并使用远程过程调用优化与硬件内存之间的数据移动。

消费级 GPU 的兴起导致了对计算内核的支持，无论是在图形 API（称为计算着色器）、专用 API（例如OpenCL ）还是其他语言扩展中。

Automatic parallelization（自动并行化）

编译器对顺序程序的自动并行化是并行计算的“圣杯”，特别是在前面提到的处理器频率限制的情况下。尽管编译器研究人员进行了数十年的工作，但自动并行化仅取得了有限的成功。

主流并行编程语言要么保持显式并行，要么（最多）部分隐式并行，其中程序员向编译器提供并行化指令。存在一些完全隐式并行编程语言 - SISAL 、Parallel Haskell 、 SequenceL 、 System C （用于FPGA ）、 Mitrion-C 、 VHDL和Verilog

应用程序检查点

（Application checkpointing）

随着计算机系统复杂性的增加，平均故障间隔时间通常会缩短。应用程序检查点是一种技术，计算机系统通过该技术拍摄应用程序的“快照”——所有当前资源分配和变量状态的记录，类似于核心转储——；如果计算机出现故障，此信息可用于恢复程序。应用程序检查点意味着程序必须仅从最后一个检查点而不是开头重新启动。虽然检查点在各种情况下都具有优势，但它在高性能计算中使用大量处理器的高度并行系统中尤其有用。

Algorithmic methods

随着并行计算机的规模越来越大、速度越来越快，我们现在能够解决以前运行时间太长的问题。生物信息学（用于蛋白质折叠和序列分析）和经济学（用于数学金融）等不同领域都利用了并行计算。并行计算应用中常见的问题类型包括

• Dense linear algebra
• Sparse linear algebra
• Spectral methods (such as Cooley–Tukey fast Fourier transform)
• Nbody problems (such as Barnes–Hut simulation)
• Structured grid problems (such as Lattice Boltzmann methods)
• Unstructured grid problems (such as found in finite element analysis)
• Monte Carlo method
• Combinational logic (such as brute-force cryptographic techniques)
• Graph traversal (such as sorting algorithms)
• Dynamic programming
• Branch and bound methods
• Graphical models (such as detecting hidden Markov models and constructing Bayesian networks)
• HBJ model, a concise message-passing model
• Finite-state machine simulation

容错能力

并行计算还可以应用于容错计算机系统的设计，特别是通过并行执行相同操作的锁步系统。这可以在一个组件发生故障时提供冗余，并且如果结果不同，还可以进行自动错误检测和纠错。这些方法可用于帮助防止瞬态错误引起的单事件干扰。尽管在嵌入式或专用系统中可能需要额外的措施，但该方法可以提供一种经济有效的方法来在商业现成系统中实现 n 模块冗余。

See also

• Computer multitasking
• Concurrency (computer science)
• Content Addressable Parallel Processor
• List of distributed computing conferences
• Manchester dataflow machine
• Manycore
• Parallel programming model
• Serializability
• Synchronous programming
• Transputer
• Vector processing

External links

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

并行编程模型

在计算领域，并行编程模型是并行计算机体系结构的一种抽象概念，利用它可以方便地在程序中表达算法及其组成。一个编程模型的价值可根据其通用性来判断：在各种不同的体系结构下，一系列不同问题的表达效果如何；以及其性能：编译后的程序执行效率如何。并行编程模型的实现形式可以是从顺序语言中调用的库，也可以是对现有语言的扩展，还可以是一种全新的语言。

围绕特定编程模型达成共识非常重要，因为这将导致不同的并行计算机在构建时支持该模型，从而促进软件的可移植性。从这个意义上讲，编程模型被称为硬件和软件之间的桥梁。

并行编程模型的分类

并行编程模型的分类可以大致分为两个方面：进程交互和问题分解

进程交互

进程交互涉及并行进程能够相互通信的机制。最常见的交互形式是共享内存和消息传递，但交互也可以是隐式的（对程序员不可见）

Shared memory（Shared memory (interprocess communication)）

共享内存是一种在进程之间传递数据的有效方式。在共享内存模型中，并行进程共享它们异步读写的全局地址空间。异步并发访问会导致竞争条件，可以使用锁、信号量和监视器等机制来避免这些情况。传统的多核处理器直接支持共享内存，许多并行编程语言和库（例如Cilk、OpenMP和Threading Building Blocks）旨在利用共享内存。

Message passing（Message passing）

在消息传递模型中，并行进程通过相互传递消息来交换数据。这些通信可以是异步的，消息可以在接收者准备好之前发送，也可以是同步的，接收者必须准备好。消息传递的通信顺序进程(CSP) 形式化使用同步通信通道连接进程，并催生了Occam、Limbo和Go等重要语言。相比之下，actor 模型使用异步消息传递，并已被用于D、Scala和 SALSA 等语言的设计中。

Partitioned global address space（分区全局地址空间）（Partitioned global address space）

分区全局地址空间 (PGAS) 模型提供了共享内存和消息传递之间的中间地带。PGAS 提供了一个逻辑分区的全局内存地址空间抽象，其中一部分对于每个进程都是本地的。并行进程通过在全局地址空间上异步执行操作（例如读取和写入）进行通信，其方式让人联想到共享内存模型。然而，通过在语义上将全局地址空间划分为与特定进程具有亲和力的部分，它们允许程序员利用引用的局部性并在分布式内存并行计算机上实现高效实现。PGAS 由许多并行编程语言和库提供，例如Fortran 2008，Chapel、UPC++和SHMEM。

Implicit interaction（隐式互动）（Implicit parallelism）

分区全局地址空间 (PGAS) 模型提供了共享内存和消息传递之间的中间地带。PGAS 提供了一个逻辑分区的全局内存地址空间抽象，其中一部分对于每个进程都是本地的。并行进程通过在全局地址空间上异步执行操作（例如读取和写入）进行通信，其方式让人联想到共享内存模型。然而，通过在语义上将全局地址空间划分为与特定进程具有亲和力的部分，它们允许程序员利用引用的局部性并在分布式内存并行计算机上实现高效实现。PGAS 由许多并行编程语言和库提供，例如Fortran 2008，Chapel、UPC++和SHMEM。

问题分解

并行程序由同时执行的进程组成。问题分解与制定组成过程的方式有关

Task parallelism Task parallelism

任务并行模型侧重于进程或执行线程。这些过程通常在行为上是不同的，这强调了沟通的必要性。任务并行是表达消息传递通信的一种自然方式。在Flynn 的分类法中，任务并行性通常被归类为MIMD / MPMD或MISD。

Data parallelism Data parallelism

数据并行模型的重点是对数据集（通常是规则结构的数组）执行操作。一组任务将对这些数据进行操作，但独立地对不相连的分区进行操作。在 Flynn 的分类法中，数据并行通常分为 MIMD/SPMD 或 SIMD。

Stream Parallelism

流并行也称流水线并行，主要是将计算分成一系列阶段，每个阶段处理一部分输入数据。每个阶段独立并发运行，一个阶段的输出作为下一阶段的输入。流并行尤其适用于具有连续数据流或流水线计算的应用。

Implicit parallelism

与隐式进程交互一样，隐式并行模型不会向程序员透露任何内容，因为编译器、运行时或硬件负责。例如，在编译器中，自动并行化是将顺序代码转换为并行代码的过程，而在计算机体系结构中，超标量执行是一种利用指令级并行性来并行执行操作的机制。

术语

并行计算模型是计算模型的一大范畴，包括：细胞自动机、PRAM机、LogP机、佩特里网、进程网（英语：Kahn process networks）和交互网（英语：Interaction nets）等。计算模型是用来分析计算进程代价的一种抽象化，利用它分析并行算法（英语：Analysis of parallel algorithms）性能，可以不取决于特定实现和技术所特有的各种变化，并行算法一般而言是针对特定计算模型而编写的，为PRAM机编写的伪码通常会采用某种For循环形式的并发编程构造。

编程模型（英语：Programming model）指称一种编程样式，即通过看起来像库调用的方式引发执行。例子包括POSIX的Pthreads库和Apache Hadoop中的MapReduce。在这二者情况下，执行模型（英语：Execution model）都符合这个库所用语言的语法却不能按照其语义来理解。不同于计算模型，编程模型特别暗含着对硬件或软件实现的实际考虑。

在并行计算中，执行模型经常必须暴露硬件特征来达成高性能。并行硬件有大量的变种导致了同时需要类似数量的并行执行模型。对每个执行模型都建立一门新语言是不实际的，因此常见的实践都是通过某个API来引发并行执行模型的行为。并行编程语言可以基于一种或一个组合的编程模型。例如，高性能Fortran基于共享内存交互和数据并行问题分解，而Go提供共享内存交互和消息传递交互。

并行编程模型

这里列出的编程模型是可称为桥接模型（英语：Bridging model）的计算机的抽象模型，它提供了在一个机器的物理实现和编程者可获得的这个机器的抽象概念之间的桥梁；换句话说，它意图在硬件和软件工程师之间提供共同的理解层面。成功的编程模型可以在现实中有效的实现并被编程者有效的作为目标；特别是应当有可能用典型的高级语言编译器生成良好的代码。从编程者的角度来看，这种桥接并行编程模型一般典型的位于Pthreads、IPC、MPI等之上，而在OpenMP、OpenACC等之下。

OpenCL将计算系统视为组成自一组“计算设备”，它们可以是CPU或是附加的“加速器”比如GPU。它定义了一种类C语言（英语：List of C-family programming languages）用来写程序。在OpenCL设备上执行的函数叫做“内核”:17。一个单一的计算设备典型的组成自一些“计算单元”，它们依次又包含很多“处理元素”（PE）。一个单一的内核执行可以在所有或多个PE上并行运行。OpenCL定义了API，允许运行于主机上的程序，启动在计算设备上的内核，并管理设备内存，它至少在概念上分离于主机内存。用OpenCL语言写的程序预期会被即时编译，所以使用OpenCL的应用程序在针对各种设备的实现之间是可移植的。

FPGA可以被用来解决任何可计算的问题，这通过用FPGA能实现软微处理器（英语：Soft microprocessor）的事实就可轻易的证明。它们的好处在于对某些应用它们明显的要更快速，因为它们有着并行本质和在对用在特定处理上的逻辑门的数目方面的优化（英语：Logic optimization）。近年来开始兴起使用OpenCL编程来利用FPGA提供的性能和能耗效率。OpenCL允许编程者用C语言编码并把FPGA组合函数作为使用OpenCL构造的OpenCL计算内核的目标。

MapReduce是通过并行、分布式算法在集群上处理和生成键/值对形式的大数据集的编程模型和有关实现 ，Apache Hadoop中将它与HDFS分立实现。MapReduce受到了在函数式编程范型中常用的map和reduce函数的启发，但是它们在MapReduce框架中的用途不同于它们在起初形式中那样。

并行编程模型还有很多，比如：马里兰大学学院市分校依据PRAM计算模型，建立了指令级并行显式多线程（英语：Explicit multi-threading）的多处理器计算机和编程语言XMTC（英语：XMTC]]），实现了Spawn-Join范型。

See also

• Automatic parallelization
• Bridging model
• Concurrency
• Degree of parallelism
• Explicit parallelism
• List of concurrent and parallel programming languages
• Optical Multi-Tree with Shuffle Exchange
• Parallel external memory (Model)
• 并发计算
• 异构计算
• 高性能计算
• 集群计算
• 分布式计算
• 并发及并行编程语言列表（英语：List of concurrent and parallel programming languages）
• 远程直接内存访问
• 并行外部内存（英语：Parallel external memory）

Further reading

• Blaise Barney, Introduction to Parallel Computing, Lawrence Livermore National Laboratory, archived from the original on 2013-06-10, retrieved 2015-11-22
• Murray I. Cole., Algorithmic Skeletons: Structured Management of Parallel Computation (PDF), University of Glasgow
• J. Darlinton; M. Ghanem; H. W. To (1993). "Structured parallel programming". Proceedings of Workshop on Programming Models for Massively Parallel Computers. In Programming Models for Massively Parallel Computers. IEEE Computer Society Press. pp. 160–169. doi:10.1109/PMMP.1993.315543. ISBN 0-8186-4900-3. S2CID 15265646.
• Ian Foster, Designing and Building Parallel Programs, Argonne National Laboratory