什么是并行计算
并行计算（parallel computing）是指，在并行机上，将一个应用分解成多个子任务，分配给不同的处理器，各个处理器之间相互协同，并行地执行子任务，从而达到加速求解速度，或者增大求解应用问题规模的目的。
由此，为了成功开展并行计算，必须具备三个基本条件：
(1) 并行机。并行机至少包含两台或两台以上处理机，这些处理机通过互连网络相互连接，相互通信。
(2) 应用问题必须具有并行度。也就是说，应用可以分解为多个子任务，这些子任务可以并行地执行。将一个应用分解为多个子任务的过程，称为并行算法的设计。
(3) 并行编程。在并行机提供的并行编程环境上，具体实现并行算法，编制并行程序，并运行该程序，从而达到并行求解应用问题的目的。
并行计算的主要研究目标和内容
对于具体的应用问题，采用并行计算技术的主要目的在于两个方面：
(1) 加速求解问题的速度。
(2) 提高求解问题的规模。
组成并行机的三个要素为：
•结点（node）。每个结点由多个处理器构成，可以直接输入输出（I/O）。•互联网络（interconnect network）。所有结点通过互联网络相互连接相互通
信。
•内存（memory）。内存由多个存储模块组成，这些模块可以与结点对称地分布在互联网络的两侧，或者位于各个结点的内部。
并行编程模型
1.共享内存模型
a)在共享编程模型中，任务间共享统一的可以异步读写的地址空间。
b)共享内存的访问控制机制可能使用锁或信号量。
c)这个模型的优点是对于程序员来说数据没有身份的区分，不需要特别清楚任务间的单数据通信。程序开发也相应的得以简化。
d)在性能上有个很突出的缺点是很难理解和管理数据的本地性问题。
2.线程模型
在并行编程的线程模型中，单个处理器可以有多个并行的执行路径。
3.消息传递模型
消息传递模型有以下三个特征：
1）计算时任务集可以用他们自己的内存。多任务可以在相同的物理处理器上，同时可以访问任意数量的处理器。
2）任务之间通过接收和发送消息来进行数据通信。
3）数据传输通常需要每个处理器协调操作来完成。例如，发送操作有一个接受操作来配合。
4.数据并行模型
数据并行模型有以下特性：
并行工作主要是操纵数据集。数据集一般都是像数组一样典型的通用的数据结构。
任务集都使用相同的数据结构，但是，每个任务都有自己的数据。
每个任务的工作都是相同的，例如，给每个数组元素加4。
在共享内存体系结构上，所有的任务都是在全局存储空间中访问数据。在分布式存储体系结构上数据都是从任务的本地存储空间中分离出来的。
基于消息传递的并行计算环境
在当前并行机上，比较流行的并行编程环境可以分为三类：消息传递、共享存储和数据并行，它们的典型代表、可移植性、并行粒度、并行操作方式、数据存储模式、数据分配方式、学习难度、可扩展性等方面的比较如下：
(1) 共享存储并行编程基于线程级细粒度并行，仅被SMP 和DSM并行机所支持，可移植性不如消息传递并行编程。但是，由于它们支持数据的共享存储，所以并行编程的难度较小，但一般情形下，当处理机个数较多时，其并行性能明显不如消息传递编程。
(2) 消息传递并行编程基于大粒度的进程级并行，具有最好的可移植性，几乎被当前流行的各类并行机所支持，且具有很好的可扩展性。但是，消息传递并行编程只能支持进程间的分布存储模式，即各个进程只能直接访问其局部内存空间，而对其他进程的局部内存空间的访问只能通过消息传递来实现。因此，学习和使用消息传递并行编程的难度均大于共享存储和数据并行两种编程模式。
三种并行编程环境主要特征一览表
特征消息传递共享存储数据并行
典型代表MPI、PVM OpenMP HPF
可移植性所有流行并行
机SMP﹑DSM SMP﹑DSM﹑
MPP
并行粒度进程级大粒度线程级细粒
度
进程级细粒度并行操作方
式
异步异步松散同步
数据存储模
式
分布式存储共享存储共享存储
数据分配方
式
显式隐式半隐式
学习入门难
度
较难容易偏易
可扩展性好较差一般本书的主要目的是全面介绍消息传递并行编程环境MPI，因此，在以后的篇幅中，将不再讨论共享存储和数据并行编程环境。
1.消息传递并行机模型
由于当前流行的各类SMP、DSM、MPP 和微机机群等并行机均支持消息传递并行程序设计，因此，有必要对这些具体并行机的体系结构进行抽象，设计一个理想的消息传递并行机模型。基于该模型，用户可以在不考虑具体并行机体系结构的条件下，组织消息传递并行程序设计，从而简化并行程序设计，增强程序的可移植性。
图1.1给出了一个理想的消息传递进程拓扑结构。其中，“P”表示MPI 进程，“M”表示每个进程的局部内存空间，多个“P/M”进程/内存模块通过互联网络相互连接，构成一个分布式存储的进程拓扑结构。在该结构中，各个进
程之间可以直接通信，但是各个进程只能直接访问自身的局部内存空间，对其他进程的局部内存空间的访问只能调用消息传递函数，通过进程间通信才能实现。因此，该进程拓扑结构的核心是连接进程的互联网络和消息传递标准函数库，构成该函数库的所有函数就构成了用户面对的消息传递并行编程环境。
图1.1 消息传递进程拓扑结构和并行机模型
如果将图1.1 的每个P/M 模块替换成处理器，且规定每个处理器只能分配用户程序的一个进程，则所得的理想并行机模型就是消息传递并行机模型。不难看出，消息传递并行程序设计所依赖的并行机模型实际上属于典型的分布式存储并行机，且每台处理器只能分配用户程序的一个进程。基于该并行机模型，用户可以自由地调用消息传递函数库中的函数来组织具体的并行程序设计，且程序研制成功后，便可以在任何支持该并行机模型隐含的进程拓扑结构的所有具体并行机上运行。
这里，有必要说明的是，消息传递分布式存储并行机模型和具体并行机体系结构没有必然的联系。无论将该模型映射到何种类型的并行机（SMP、DSM、cluster、constellation、MPP），用户面对的都是该模型隐含的进程拓扑结构，只是各类具体并行机实现的消息传递函数库的方式不同，但用户无须知道这些细节。例如，在共享存储SMP、DSM 并行机中，消息传递是通过共享数据缓存区来实现的；在MPP 并行机中，消息传递是通过网络通信来实现的；在机群和星群并行机中，消息传递在SMP、DSM 并行机内部是通过共享数据缓存区实现的，而在SMP、DSM 并行机之间是通过网络通信来实现的。因此，无论哪种类型的具体并行机，呈现在消息传递并行程序设计用户面前的必然是分布式存储并行机模型。
2.标准消息传递界面MPI
1994 年6 月，全球工业、政府和科研应用部门联合推出消息传递并行编程环境的标准用户界面（MPI），它将消息传递并行编程环境分解为两个部分，第
