图85 MPI ACCUMULATE操作图示 274 图86 MPI WIN FENCE的同步方式 276 图87窗口握手同步方式图示 图8通过加锁与开锁实现对同 窗口的互斥访问 图89 MPI FILE READ AT图示 .287 图0MPIFⅡE WRITE AT图示. 288 图0，两步非阳寒组调用图示 201 图92文件与视口的关系图示 293 图3视口与基本类型、文件类型和文件的关系图示 .29 图94不同的数据表示和效率与移植性的关系 .29 图5当前文件视口位置图示 .297 图96相对于视口的偏移和相对于文件的绝对位置关系图示 298 图97一维块分布 311 图8一维循环分布 3 图99一维循环块分布 31 XVI
XVI 图 85 MPI_ACCUMULATE操作图示....................................................................................................274 图 86 MPI_WIN_FENCE的同步方式....................................................................................................276 图 87 窗口握手同步方式图示.................................................................................................................276 图 88 通过加锁与开锁实现对同一窗口的互斥访问............................................................................279 图 89 MPI_FILE_READ_AT图示...........................................................................................................287 图 90 MPI_FILE_WRITE_AT图示 .........................................................................................................288 图 91 两步非阻塞组调用图示.................................................................................................................291 图 92 文件与视口的关系图示.................................................................................................................293 图 93 视口与基本类型 文件类型和文件的关系图示........................................................................294 图 94 不同的数据表示和效率与移植性的关系....................................................................................295 图 95 当前文件视口位置图示.................................................................................................................297 图 96 相对于视口的偏移和相对于文件的绝对位置关系图示...........................................................298 图 97 一维块分布......................................................................................................................................311 图 98 一维循环分布..................................................................................................................................311 图 99 一维循环块分布..............................................................................................................................311
表格列表 表格】数据并行与消息传递并行编程模型 表格2MPI的 一些克 表格3MPI预定义数据类型与FORTR4N77数据类型的对应关系 表格4PI预定义数据类型与C数据类型的对应关系 .29 表格5附加的MP1数据类型 30 表格6P1的通信模式， 60 表格7非阻塞MPI通信模式。 表格8非阻塞通信的完成与检测 表格9PI预定义的归约操作 .141 表格I0C或FORTR4N类型与MPI类型的对应 .141 表格川归约操作与相应类型的对应关系 1d1 表格12MP1定义的Form语言的值对类型 152 表格13MPI定义的C语言的值对类型 表格14归的操作MP_MAXLOC的结果 表格5通信域分 .193 表格16箭卡儿拓执和图拓林调用的简单对比 .199 表格17结点、度数、边的对应关系 206 表格8图拓扑的定义参数 206 表格19错误类列表 表格20各种并行文件/0调用. 28 表格2引文件打开方式 283 表格22不同文件位置参照点的含义 296 XVII
XVII 表格列表 表格 1 数据并行与消息传递并行编程模型 ..............................................................................................7 表格 2 MPI的一些实现................................................................................................................................15 表格 3 MPI预定义数据类型与FORTRAN77数据类型的对应关系.......................................................29 表格 4 MPI预定义数据类型与C数据类型的对应关系...........................................................................29 表格 5 附加的MPI数据类型......................................................................................................................30 表格 6 MPI的通信模式................................................................................................................................69 表格 7 非阻塞MPI通信模式......................................................................................................................98 表格 8 非阻塞通信的完成与检测.............................................................................................................99 表格 9 MPI预定义的归约操作.................................................................................................................141 表格 10 C或FORTRAN类型与MPI类型的对应...................................................................................141 表格 11 归约操作与相应类型的对应关系.............................................................................................141 表格 12 MPI定义的Fortran语言的值对类型......................................................................................152 表格 13 MPI定义的C语言的值对类型.................................................................................................152 表格 14 归约操作MPI_MAXLOC的结果 ...............................................................................................153 表格 15 通信域分裂..................................................................................................................................193 表格 16 笛卡儿拓扑和图拓扑调用的简单对比....................................................................................199 表格 17 结点 度数 边的对应关系.....................................................................................................206 表格 18 图拓扑的定义参数.....................................................................................................................206 表格 19 错误类列表..................................................................................................................................215 表格 20 各种并行文件I/O调用................................................................................................................282 表格 21 文件打开方式..............................................................................................................................283 表格 22 不同文件位置参照点的含义.....................................................................................................296
第一部分并行程序设计基础 本部分包括如下内容：并行计算机、并行编程模型与并行语言、并行算法。 通过本部分的介绍，使读者对并行计算和并行程序设计有一个基本的概念，为后续几章 具体讲解MP并行程序设计方法提供基础知识
1 第一部分 并行程序设计基础 本部分包括如下内容 并行计算机 并行编程模型与并行语言 并行算法 通过本部分的介绍 使读者对并行计算和并行程序设计有一个基本的概念 为后续几章 具体讲解MPI并行程序设计方法提供基础知识
第1章并行计算机 本章给出了并行计算机的基本划分方法和与之相关的体系结构，是宏观的总体的论述而 不是具体的细节，这主要是考虑到读者是并行程序设计人员而不是并行机的设计与开发人 员。对并行机有一个总体上的了解可以帮助编程者设计出更高效的并行程序 本章还给出了 个物理问题如何一步步在并行机上得到解决的，以及并行程序设计在这 一过程中所起的作用。 1.1并行计算机的分类 为什么要采用并行计算？这是因为：1它可以加快速度，即在更短的时间内解决相同的 问题或在相同的时间内解决更多更复杂的问题，特别是对一些新出现的巨大挑战问题，不使 用并行计算是根本无法解决的；2节省投入，并行计算可以以较低的投入完成串行计算才能 够完成的任务： 3物理极限的约束，光速是不可逾越的速度极限，设各和材料也不可能做得 无限小，只有通过并行才能够不断提高速度。 并行计算机即能在同一时间内执行多条指令（或处理多个数据）的计算机，并行计算机 是并行计算的物理载体。通过下面对并行计算机的不同分类方式，可以对它有一个总体上的 了解，为并行程序设计莫定基础。 1.1.1指令与数据 根据一个并行计算机能够同时执行的指令与处理数据的多少，可以把并行计算机分为 SIMD(Single--Instruction Multiple-Data)单指令多数据并行计算机和MlMD(Multiple- Instruction Multiple-Data)多指令多数据并行计算机（图1）。 SMD计算机同时用相同的指令对不同的数据进行操作，比如对于数组赋值运算 在SMD并行机上可以用加法指令同时对数组A的所有元素实现加1。即数组（或向量）运算 特别适合在SMD并行计算机上执行，SMD并行机可以对这种运算形式进行直接地支持，高 效地实现。 MMD计算机同时有多条指令对不同的数据进行操作，比如对于算术表达式 A-B+C+D-E+F*G 可以转换为 A=(B+CH(D-E+F◆G) 加法(B+C),减法(D-E),乘法(F*G)如果有相应的直接执行部件，则这三个不同的计 算可以同时进行。 SIMD和MMD汶种表达方法吊然至今环在广一泛伸用，但是，随若新的并行计算机组织 方式的产生，比照上面的划分方法，人们按同时执行的程序和数据的不同， 又提出了SPMD (Single--Program Multuple--Data）单程序多数据并行计算机和MPMD(Multiple-Program Multiple-Data)多程序多数据并行计算机（图I)的概念。这种划分方式依据的执行单位不 是指令而是程序，显然其划分粒度要大得多。 如果一个程序的功能就是为一个矩形网格内的不同面片涂上相同的颜色，则对于一个划
2 第1章 并行计算机 本章给出了并行计算机的基本划分方法和与之相关的体系结构 是宏观的总体的论述而 不是具体的细节 这主要是考虑到读者是并行程序设计人员而不是并行机的设计与开发人 员 对并行机有一个总体上的了解可以帮助编程者设计出更高效的并行程序 本章还给出了一个物理问题如何一步步在并行机上得到解决的 以及并行程序设计在这 一过程中所起的作用 1.1 并行计算机的分类 为什么要采用并行计算 这是因为 1 它可以加快速度 即在更短的时间内解决相同的 问题或在相同的时间内解决更多更复杂的问题 特别是对一些新出现的巨大挑战问题 不使 用并行计算是根本无法解决的 2 节省投入 并行计算可以以较低的投入完成串行计算才能 够完成的任务 3 物理极限的约束 光速是不可逾越的速度极限 设备和材料也不可能做得 无限小 只有通过并行才能够不断提高速度 并行计算机即能在同一时间内执行多条指令 或处理多个数据 的计算机 并行计算机 是并行计算的物理载体 通过下面对并行计算机的不同分类方式 可以对它有一个总体上的 了解 为并行程序设计奠定基础 1.1.1 指令与数据 根据一个并行计算机能够同时执行的指令与处理数据的多少 可以把并行计算机分为 SIMD Single-Instruction Multiple-Data 单指令多数据并行计算机和MIMD MultipleInstruction Multiple-Data 多指令多数据并行计算机 图 1 SIMD计算机同时用相同的指令对不同的数据进行操作 比如对于数组赋值运算 A=A+1 在SIMD并行机上可以用加法指令同时对数组A的所有元素实现加1 即数组 或向量 运算 特别适合在SIMD并行计算机上执行 SIMD并行机可以对这种运算形式进行直接地支持 高 效地实现 MIMD计算机同时有多条指令对不同的数据进行操作 比如对于算术表达式 A=B+C+D-E+F*G 可以转换为 A=(B+C)+(D-E)+(F*G) 加法 B+C 减法 D-E 乘法 F*G 如果有相应的直接执行部件 则这三个不同的计 算可以同时进行 SIMD和MIMD这种表达方法虽然至今还在广泛使用 但是 随着新的并行计算机组织 方式的产生 比照上面的划分方法 人们按同时执行的程序和数据的不同 又提出了SPMD Single-Program Multuple-Data 单程序多数据并行计算机和MPMD Multiple-Program Multiple-Data 多程序多数据并行计算机 图 1 的概念 这种划分方式依据的执行单位不 是指令而是程序 显然其划分粒度要大得多 如果一个程序的功能就是为一个矩形网格内的不同面片涂上相同的颜色 则对于一个划
分得很细的特大矩形面片，可以将它划分为互不交叉的几个部分，每一部分都用相同的程序 讲行若色。SPMD并行计算机可以很自然地实现类似的计算。一般地，SPD并行计算机是 由多个地位相同的计算机或处理器组成的，而MPMD并行计算机内计算机或处理器的地位 是不同的，根据分工的不同，它们长完成的工作也不同，因此，可以根据需要将不同的程 序（任务）放到MPMD并行计算机上执行，使得这些程序协调一致地完成给定的工作。 数据个数D 数据个数D MSIMD MIMD SPMD MPMD 并行计算机 SISD MISD PSD MPSD M指令个 M程序个 图1按指令（程序）数据的个数对并行计算机进行分类 1.1.2存储方式 从物理划分上，共享内存和分布式内存是两种基本的并行计算机存储方式，除此之外 分布式共享内存也是一种越来越重要的并行计算机存储方式（图2） p口 生 共享内存 互连网络 网 555 pOO 共享内存并行计算机分布式内存并行计算机 分布式共享内存并行计算机 不具有局部存储的处理单元 共享存储的局部处理单元 具有局部存储的处理单元 图2按存储方式对并行计算机进行分类
3 分得很细的特大矩形面片 可以将它划分为互不交叉的几个部分 每一部分都用相同的程序 进行着色 SPMD并行计算机可以很自然地实现类似的计算 一般地 SPMD并行计算机是 由多个地位相同的计算机或处理器组成的 而MPMD并行计算机内计算机或处理器的地位 是不同的 根据分工的不同 它们擅长完成的工作也不同 因此 可以根据需要将不同的程 序 任务 放到MPMD并行计算机上执行 使得这些程序协调一致地完成给定的工作 数据个数D 数据个数D M SIMD MIMD M SPMD MPMD 并行计算机 S SISD MISD S SPSD MPSD S M 指令个数I S M 程序个数P 图 1 按指令 程序 数据的个数对并行计算机进行分类 1.1.2 存储方式 从物理划分上 共享内存和分布式内存是两种基本的并行计算机存储方式 除此之外 分布式共享内存也是一种越来越重要的并行计算机存储方式 图 2 互 连 共享内存 互连网络 网 络 共享内存并行计算机 分布式内存并行计算机 分布式共享内存并行计算机 不具有局部存储的处理单元 共享存储的局部处理单元 具有局部存储的处理单元 图 2 按存储方式对并行计算机进行分类