并行计算基础

并行计算是一门交叉学科，涵盖的内容非常广泛，包括并行机体系结构、编译系统、并行算法、并行编程、并行软件技术、并行性能优化与评价、并行应用等。从交叉学科的角度，并行计算可以定义为连接并行机系统和实际应用的桥梁。

并行计算（parallel computing）是指，在并行机上，将一个应用分解成多个子任务，分配给不同的处理器，各个处理器之间相互协同，并行地执行子任务，从而达到加速求解速度，或者求解应用问题规模的目的。

由此，为了成功开展并行计算，必须具备三个基本条件：

1、并行机。并行机至少包含两台或两台以上处理机，这些处理机通过互连网络相互连接，相互通信。

2、应用问题必须具有并行度。也就是说，应用可以分解为多个子任务，这些子任务可以并行地执行。将一个应用分解为多个子任务的过程，称为并行算法的设计。

3、并行编程。在并行机提供的并行编程环境上，具体实现并行算法，编制并行程序，并运行该程序，从而达到并行求解应用问题的目的。

并行计算技术的主要目的在于两个方面：

1、加速求解问题的速度。例如100台处理器的并行计算可比单处理器加速50倍。

2、提高求解问题的规模。例如100个处理器的并行计算可将问题求解规模线性地扩大100倍。

由并行计算的三个必备条件可知，并行计算的主要研究内容大致可分为四个方面：

1、并行机的高性能特征抽取。主要任务在于，充分理解和抽取当前并行机体系结构的高性能特征，提出实用的并行计算模型和并行性能评价方法，指导并行算法的设计和并行程序的实现。

2、并行算法设计与分析。针对应用领域专家求解各类应用问题的离散计算方法，设计高效率的并行算法，将应用问题分解为可并行计算的多个子任务，并具体分析这些算法的可行性和效果。

3、并行实现技术，主要包含并行程序设计和并行性能优化。基于并行机提供的并行编程环境，例如消息传递平台MPI或者共享存储平台OpenMP，具体实现并行算法，研制求解应用问题的并行程序。同时，结合并行机的高性能特征和实际应用的特点，不断优化并行程序的性能。

4、 并行应用。这是并行计算研究的最终目的。通过验证和确认并行程序的正确性和效率，进一步将程序发展为并行应用软件，应用于求解实际问题。同时，结合实际应 用出现的各种问题，不断地改进并行算法和并行程序。一个没有经过实际应用验证和确认的算法和程序，不能说是一个好的算法和程序。

并行计算不同于分布式计算（distributed computing）。后 者主要指，通过网络相互连接的两个以个的处理机相互协调，各自执行相互依赖的不同应用，从而达到协调资源访问，提高资源使用效率的目的。但是，它无法达到 并行计算所倡导的提高求解同一个应用的速度，或者提高求解同一个应用的问题规模的目的。对于一些复杂应用系统，分布式计算和并行计算通常相互配合，既要通 过分布式计算协调不同应用之间的关系，又要通过并行计算提高单个应用的能力。

从体系结构的角度，当前并行机的体系结构可分为如下三类：

1、机群（cluster）。它有三个明显的特征：

a、系统由商用结点构成，每个结点包含2～4个商用微处理器，结点内部共享存储。

b、采用商用机群交换机连接结点，结点间分布存储。

c、在各个结点上，采用机群Linux操作系统、GNU编译系统和作业管理系统。

2、星群（constellation）。它们也有三个明显的特征：

a、系统由结点构成，每个结点是一台共享存储或者分布共享存储的并行机子系统，包含数十、数百、乃至上千个微处理器，计算功能强大。

b、采用商用机群交换机连接结点，结点间分布存储。

c、在各个结点上，运行专用的结点操作系统、编译系统和作业管理系统。

3、大规模并行机系统（MPP：Massively Parallel Processing）。它们的主要特征为：

a、系统由结点构成，每个结点含10个左右处理器，共享存储。处理器采用专用或者商用CPU。

b、采用专用高性能网络互连，结点间分布存储。

c、系统运行专用操作系统、编译系统和作业管理系统。

此类系统是传统意义的大规模并行处理系统。它区别于其他两种体系结构的一个特征就是，它的处理器或者结点间的互连网络是针对应用需求而特殊定制的，在某种程度上，带有专用并行机的特点。

组成并行机的三个要素为：

1、结点（node）。每个结点由多个处理器构成，可以直接输入输出（I／O）。

2、互联网络（interconnect network）。所有结点通过互联网络相互连接相互通信。

3、内存（memory）。内存由多个存储模块组成，这些可以与结点对称地分布在互联网络的两侧，或者位于各个节点的内部。

结点是构成并行机的最基本单位。一个结点包含2个或2个以上微处理器（CPU），并行程序执行时，程序分派的各个进程将并行地运行在结点的各个微处理器上。每个微处理器拥有局部的二级高速缓存（L2 cache）。

在 结点内部，多个微处理器通过集线器（HUB）相互连接，并共享连接在集线器上的内存模块和I／O模块，以及路由器（router）。当处理器个数较少时， 例如8～16个以内，集线器一般采用高速全交互交叉开关，或者高带宽总线完成；如果处理器个数较多，例如数十个，则集线器就等同于并行机的互联网络。

互联网络是连接所有结点成并行机的高速网络。对于一般的并行机使用者，无须知道互联网络底层复杂的通信原理，而只需从拓扑结构的角度了解互联网络。

互联网络的拓扑结构可用无向图表示。其中，图中的结点唯一地代表并行机的各个结点，图中的边表示在两个端点代表的并行机结点之间，存在直接连接的物理通信通道。

互联网络拓扑结构的几个重要定义：

1、并行机规模：并行机包含的结点总数，或者包含的CPU总数。

2、结点的度：拓扑结构图中，以某个结点为端点的边的条数，称为该结点的度。结点的度表示，存在多少个结点，与该结点有直接的物理连接通道。

3、结点距离：两个结点之间跨越的图的边的最少条数。

4、网络直径：网络中任意两个结点之间的最长距离。

5、点对点带宽：图中边对应的两个结点之间相互连接的物理通道的通信带宽。

6、点对点延迟：图中任意两个结点之间的一个零长度消息传递必须花费的时间。延迟与结点间距离相关，其中所有结点之间的最小延迟称为网络的最小延迟，所有结点之间的最大延迟称为网络的最大延迟。

7、折半宽度（对分带宽）：对分图成相同规模的两个子图（它们的结点数相等，或者至多相差1）时，必须去掉的边的最少条数。或者，这些边对应的网络点对点带宽的最小总和。

8、总通信带宽：所有边对应的网络通信带宽之和。

显然，评价一个互联网络的基本准则应该为：固定并行机包含的结点个数，如果点对点带宽越高、折半宽度越大、或者网络直径越小、点对点延迟越小，则互联网络质量可以说越高。

按节点间连接的性质，拓扑结构可分为三类：

1、静态拓扑结构：

如 果结点之间存在固定的物理连接，且在程序的执行过程中，结点间的连接方式不变，则称该并行机的互联网络拓扑结构是静态的。拓扑结构中，如果两个结点之间存 在直接物理连接，则称之互为相邻结点。当前并行机采用的各类静态拓扑结构包括阵列（array）、环（ring）、网格（mesh）、网格环 （torus，也叫环面）、树（tree）、超立方体（hypercube）、蝶网（butterfly）、Benes网等。

2、动态拓扑结构：

结点之间无固定的物理连接，而是在连接路径的交叉点处用电子开关、路由器或仲裁器等提供动态连接，主要包含单一总线、多层总线、交叉开关、多级互联网络（MIN：Multistage Interconnection Network）等类型。

3、宽带互联网络：

随 着网络技术的成熟，商用宽带互联网络逐步成为连接微机而构成简易并行机的互联网络，并且，相继推出了专用于微机机群的宽带交换机。它们的出现，极大地丰富 了并行机的市场，简化了并行机的研制难度，大幅度降低了并行机的成本，使得微机机群成为科研经费较少的研究所和大学的可用并行机系统。当前除了专用MPP 系统采用静态的拓扑结构外，微机机群均采用宽带互联网络连接各个计算结点。几个典型的代表有：以太网（Ethernet）、商用交换机（switch）、 专用微机机群互联网络。

根据Moore定律，峰值运算速度每18个月翻一番。同时，内存模块的容量以每年几乎翻一番的速度发展。但是，内存的访问速度要比处理器执行速度慢很多，难以发挥微处理器的峰值速度，这就是所谓的内存墙（memory wall）性能瓶颈问题。为此，引入了多级存储体系结构。从上层往下依次为：CPU、寄存器、L1 Cache、L2 Cache、局部内存、以及远程内存（其它结点的局部内存模块）。

根据内存访问的性质，并行机的访存模型可以分为四类：

1、均匀访存模型。

内存模块与结点分离，分别位于互联网络的两侧，互联网络一般采用系统总线、交叉开关或多级网络，称之为紧耦合系统（tightly coupled system）。该模型具有如下典型特征：

a、物理存储器被所有结点共享；

b、所有结点访问任意存储单元的时间相同；

c、发生访存竞争时，仲裁策略平等对待每个结点，即每个结点机会均等；

d、各结点的CPU可带有局部私有高速缓存（cache）；

e、外围I／O设备也可以共享，且每个结点有平等的访问权利。

当前对称多处理共享存储并行机（SMP：Symmetric Multi-Processing）均采用这种模型。

2、非均匀访存模型。

内存模块局部在各个结点内部，所有局部内存模块构成并行机的全局内存模块。并行机的内存模块在物理上是分布的，但是，在逻辑上是全局共享的。非均匀访存模型也可称为分布共享访存模型。该模型具有如下典型特征：

a、物理存储器被所有结点共享，任意结点可以直接访问任意内存模块；

b、结点访问内存模块的速度不同：访问本地存储模块的速度一般是访问其他结点内存模块的3倍以上；

c、发生访存竞争时，仲裁策略对结点可能是不等价的；

d、各结点的CPU可带有局部私有高速缓存（cache）；

e、外围I／O设备也可以共享，但对各结点是不等价的。

非 均匀访存模型的典型例子为SGI Origin系列并行机，它们采用基于cache目录一致性的非均匀访存模型（CC-NUMA：Cache-Coherent Nonuniform Memory Access），设计了专门的硬件，保证在任意时刻，各结点cache中数据与全局内存数据的一致性。

3、分布访访存模型。

与 非均匀访存模型的物理分布相同。不同的是，各个结点的存储模块只能被局部CPU访问，对其它结点的内存访问只能通过消息传递程序设计来实现。一般地，每个 结点均是一台由处理器、存储器、I／O设备组成的计算机。当前的MPP并行机各个结点之间，或者微机机群各个结点之间，均是这种访存模型。

4、混合访存模型。

这是前3类访存模型的优化组合。典型的星群系统中，每个结点内部是均匀模型或者非均匀访存模型，结点之间是分布访存模型。当前MPP系统中，大多采用混合访存模型。

按经典的指令与数据流进行分类，并行机可以分为三类：

1、单指令多数据流（SIMD）：按同一条指令，并行机的各个不同的功能部件同时对不同的数据进行不同的处理。目前，这类并行机已经退出历史舞台。

2、多指令多数据流（MIMD）：不同的处理器可同时对不同的数据执行不同的指令，目前所有并行机均属于这一类。

3、多指令单数据流（MISD）：至今没有出现。

按内存访问模型、微处理器和互联网络的不同，当前流行的并行机可分为五类：

1、对称多处理共享存储并行机（SMP）：

内存模块和处理器对称地分布在互联网络的两侧，内存访问属典型的均匀访问模型。SMP并行机有如下主要特征：

a、对称共享存储：系统中任何处理器均可直接访问任何存储模块中的存储单元和I／O模块，且访问的延迟、带宽和访问成功的概率是一致的。所有内存单元统一编址。各个处理器之间的地位等价，不存在任何特权处理器。操作系统可在任意处理器上运行。

b、单一的操作系统映像：全系统只有一个操作系统驻留在共享存储器中，它根据各个处理器的负载情况，动态地分配各个进程到各个处理器，并保持各处理器间的负载平衡。

c、局部高速缓存cache及其数据一致性：每个处理器均配备局部cache，它们可以拥有独立的局部数据，但是这些数据必须与存储器中的数据保持一致。

d、低通信延迟：各个进程通过读／写操作系统提供的共享数据缓存区来完成处理器间的通信，其延迟通常小于网络通信的延迟。

e、共享总线带宽：所有处理器共享总线的带宽，完成对内存模块和I／O模块的访问。

f、支持消息传递、共享存储并行程序设计。

SMP并行机具有如下缺点：

a、欠可靠：总线、存储器或操作系统失效可导致系统崩溃。

b、可扩展性（scalability）较差：由于所有处理器共享总线带宽，而总线带宽每3年才增加2倍，跟不上处理器速度和内存容量的增加步伐，因此，SMP并行机的处理器个数一般少于32个，且只能提供每秒数百亿次的浮点运算性能。

2、分布共享存储并行机（DSM）：

内存模块局部在各个结点内部，并被所有结点共享。这样，可以较好地改善对称多处理器共享存储并行机的可扩展能力。DSM并行机具有如下主要特征：

a、并行机以结点为单位，每个结点包含一个或多个CPU，每个CPU拥有自己的局部cache，并共享局部存储器和I／O设备，所有结点通过高性能互联网络相互连接。

b、物理上分布存储：内存模块分布在各结点中，并通过高性能互联网相互连接，避免了SMP访存总线的带宽瓶颈，增强了并行机的可扩展能力。

c、单一的内存地址空间：尽管内存模块分布在各个结点，但是，所有这些内存模块都由硬件进行统一编址，并通过互联网络连接形成了并行机的共享存储器。各个结点既可以直接访问局部内存单元，又可以直接访问其他结点的局部内存单元。

d、非一致内存访问（NUMA）模式：由于远端访问必须通过高性能互联网络，而本地访问只需直接访问局部内存模块，因此，远端访问的延迟一般是本地访问延迟的3倍以上。

e、单一的操作系统映像：类似于SMP，在DSM并行机中，用户只看到一个操作系统，它可以根据各结点的负载情况，动态地分配进程。

f、基于cache的数据一致性：通常采用基于目录的cache一致性协议来保证各结点的局部cache数据与存储器中数据的一致性。同时，也称这种DSM并行机结构为CC-NUMA结构。

g、低通信延迟与高通信带宽：专用的高性能互联网络使得结点间的延迟很小，通信带宽可以扩展。

h、DSM并行机可扩展到数百个结点，能提供每秒千亿次的浮点运算性能。

i、支持消息传递、共享存储并行程序设计。

3、机群系统。

4、星群系统。

5、大规模并行机系统（MPP）：

典型的分布存储系统，其典型特征为：

a、 由数百个乃至数千个计算结点和I／O结点组成，每个结点相对独立，并拥有一个或多个微处理器。这些结点配备有局部cache，并通过局部总线或互联网与局 部内存模块和I／O设备相连接。通常地，这些微处理器针对应用特征，进行了某些定制，与商用的通用微处理器略有不同。

b、这些结点由局部高性能网卡（NIC）通过高性能互联网络相互连接。互联网络与机群互联网络不同，它一般采用由多种静态拓扑结构耦合而成的混合拓扑结构，其通信延迟和通信带宽均明显优于机群互联网络。

c、MPP的各个结点均拥有不同的操作系统映像。一般情况下，用户可以将作业提交给作业管理系统，由它负责调度当前最空闲、最有效的计算结点来执行该作业。但是，MPP也允许用户登录到某个特定的结点，或在某些特定的结点上运行作业。

d、各个结点间的内存模块相互独立，且不存在全局内存单元的统一硬件编址。一般情形下，各个结点只能直接访问自身的局部内存模块，如果要求直接访问其他结点的局部内存模块，则必须有操作系统的特殊软件支持。

e、仅支持消息传递或者高性能Fortran并行程序设计，不支持全局共享的OpenMP并行程序设计模式。

在当前并行机上，比较流行的并行编程环境可以分为三类：消息传递、共享存储和数据并行。下表给出它们各个特征的比较：

特征	消息传递	共享存储	数据并行
典型代表	MPI、PVM	OpenMP	HPF
可移植性	所有流行并行机	SMP、DSM	SMP、DSM、MPP
并行粒度	进程级大粒度	线程级细粒度	进程级细粒度
并行操作方式	异步	异步	松散同步
数据存储模式	分布式存储	共享存储	共享存储
数据分配方式	显式	隐式	半隐式
学习入门难度	较难	容易	偏易
可扩展性	好	较差	一般

由上表可看出：

1、共享存储并行编程基于线程级细粒度并行，仅被SMP和DSM并行机所支持，可移植性不如消息传递并行编程。但是，由于它们支持数据的共享存储，所以并行编程的难度较小，但一般情形下，当处理机个数较多时，其并行性能明显不如消息传递编程。

2、 消息传递并行编程基于大粒度的进程级并行，具有最好的可移植性，几乎被当前流行的各类并行机所支持，且具有很好的可扩展性。但是，消息传递并行编程只能支 持进程间的分布存储模式，即各个进程只能直接访问其局部内存空间，而对其它进行的局部内存空间的访问只能通过消息传递来实现。因此，学习和使用消息传递并 行编程的难度均大于共享存储和数据并行两种编程模式。

由于当前流行的种类SMP、DSM、MPP和微机机群等并行机均支持消息传递并行程序设计，因此，有必要对这些具体并行机的体系结构进行抽象，设计一个理想的消息传递并行机模型。基于该模型，用户可以在不考虑具体并行机体系结构的条件下，组织消息传递并行程序设计，从而简化并行程序设计，增强程序的可移植性。

P／M ｜	P／M ｜	……	P／M ｜
互联网络－－消息传递函数库
｜ P／M	｜ P／M	……	｜ P／M

上 图是一个理想的消息传递进程拓扑结构。其中，“P”表示MPI进程，“M”表示每个进程的局部内存空间，多个“P／M”进程／内存模块通过互联网相互连 接，构成一个分布式存储的进程拓扑结构。在该结构中，各个进程之间可以直接通信，但是各个进程只能直接访问自身的局部内存空间，对其他进程的局部内存空间 的访问只能调用消息传递函数，通过进程间通信才能实现。因此，该进程拓扑结构的核心是连接进程的互联网络，也就是消息传递标准函数库，而构成该函数库的所 有函数就构成了用户面对的消息传递并行编程环境。

如果把上图的每个P／M模块替换成处理器，且规定每个处理器只能分配用户程序的一个进程， 则所得的理想并行机模型就是消息传递并行机模型。不难看出，消息传递并行程序设计所依赖的并行机模型实际上属于典型的分布式存储并行机，且每台处理器只能 分配用户程序的一个进程。基于该并行机模型，用户可以自由地调用消息传递函数库中的函数来组织具体的并行程序设计，且程序研制成功后，便可以在任何支持该 并行机模型隐含的进程拓扑结构的所有具体并行机上运行。

这里，有必要说明的是，消息传递分布式存储并行机模型和具体并行机体系结构没有必然 的联系。无论将该模型映射到何种类型的并行机（SMP、DSM、cluster、constellation、MPP），用户面对的都是该模型隐含的进程 拓扑结构，只是各类具体并行机实现的消息传递函数库的方式不同，但用户无须知道这些细节。例如：在共享存储SMP、DSM并行机中，消息传递是通过共享数 据缓存区来实现的；在MPP并行机中，消息传递是通过网络通信来实现的；在机群和星群并行机中，消息传递在SMP、DSM并行机内部是通过共享数据缓存区 实现的，而在SMP、DSM并行机之间是通过网络通信来实现的。因此，无论哪种类型的具体并行机，呈现在消息传递并行程序设计用户面前的必然是上图所示的 分布式存储并行机模型。

1994年6月，全球工业、政府和科研应用部门联合推出消息传递并行编程环境的标准用户界面（MPI）， 它将消息传递并行编程环境分解为两个部分，第一是构成该环境的所有消息传递函数的标准接口说明，它们是根据并行应用程序对消息传递功能的不同要求而制定 的，不考虑该函数能否具体实现；第二是各并行机厂商提供的对这些函数的具体实现。这样，用户只需学习MPI库函数的标准接口，设计MPI并行程序，便可在 支持MPI并行编程环境的具体并行机上执行该程序。通常意义下所说的MPI系统就是指所有这些具有标准接口说明的消息传递函数所构成的函数库。

在 标准串行程序设计语言（C、Fortran、C++）的基础上，再加入实现进程间通信的MPI消息传递库函数，就构成了MPI并行程序设计所依赖的并行编 程环境。MPI吸收了众多消息传递系统的优点，例如P4、PVM、Express、PARMACS等，是目前国内外最流行的并行编程环境之一。

相对其他并行编程环境，MPI具有许多优点：

1、具有很好的可移植性，被当前所有并行环境支持；

2、具有很好的可扩展性，是目前高效率的大规模并行计算（数百个处理器）最可依赖的平台；

3、比其它消息传递系统好用；

4、有完备的异步通信功能；

5、有精确的定义，从而为并行软件的发展提供了必要的条件。

MPI 1.0版于1994年推出，并同时获得了各并行机产商的具体实现；MPI 2.0于1998年10月推出，它在1.0版的基础上，增加了如下的消息传递功能：

1、并行I／O：允许多个进程同时读／写同一个文件；

2、线程安全：允许MPI进程的多个线程执行，即支持与OpenMP的混合并行编程；

3、动态进程管理：允许并行应用程序在执行过程中，动态地增加和删除进程个数；

4、单边通信：允许某个进程对其他进程的局部内存单元直接执行读／写访问，而不需要对方进程的显式干预；

5、并行应用程序之间的动态互操作：允许各个MPI并行应用程序之间动态地建立和删除消息传递通信通道。

并行算法是适合在并行机上实现的算法，一个好的并行算法应该具备充分发挥并行机潜在性能的能力。

并行计算机的出现来源于实际应用程序中存在内在并行度这一基本事实，因此，应用问题中是否存在可挖掘的并行度是并行计算机应用的关键，而并行算法作为应用程序开发的基础，自然在并行计算机应用中具有举足轻重的地位。

根据运算基本对象的不同，并行算法可分为：

1、数值并行算法：

主要为数值计算方法而设计的并行算法；

2、非数值并行算法：

主要为符号运算而设计的并行算法，如图论算法、遗传算法等。

根据并行进程间相互执行顺序关系的不同可分为：

1、同步并行算法：

进程间由于去处执行顺序而必须相互等待的并行算法；

2、异步并行算法：

进程间执行相对独立，不需要相互等待的一种算法，根据最新消息决定进程的继续或终止；

3、独立并行算法：

进行间执行是完全独立的，计算的整个过程不需要任何通信。

根据各进程承担的计算任务粒度的不同，可分为：

1、细粒度并行算法：

通常指基于向量和循环级并行的算法；

2、中粒度并行算法：

通常指基于较大的循环级并行；

3、大粒度并行算法：

通常指基于子任务级并行的算法。

其实，并行算法的粒度是一个相对的概念。如果处理器的计算功能强大，则原来的粗粒度算法也可以被认为是细粒度算法。