MPI与OpenMP并行程序设计C语言版 (2008 年度畅销榜NO.2427 )

本书是美国Oregon州立大学的Michael J.Quinn教授在多年讲授“并行程序设计”课程的基础上编写而成的，主要介绍用C语言，并结合使用MPI和OpenMP进行并行程序设计，内容包括并行体系结构、并行算法设计、消息传递编程、Eratosthenes 筛法、Floyd 算法、性能分析、矩阵向量乘法、文档分类、蒙特卡洛法、矩阵乘法、线性方程组求解、有限差分方法、排序、快速傅立叶变换、组合搜索、共享存储编程、融合OpenMP和MPI以及5个附录。
本书按授课方式安排章节，通过划分、通信、集聚和映射等四步的并行程序设计方法，来解决各种实际的并行性问题，使读者掌握系统化的并行程序设计方法，开发出高效的并行程序。
本书不仅是一本优秀的并行程序设计教材，对广大的相关专业人员也很有参考价值。

第1章动机和历史
1.1概述
1.2现代科学方法
1.3超级计算的进化
1.4现代并行计算机
1.4.1CosmicCube并行计算机
1.4.2商品化的并行计算机
1.4.3Beowulf系统
1.4.4先进战略计算计划
1.5寻找并行性
1.5.1数据相关图
1.5.2数据并行性
1.5.3功能并行性
1.5.4流水线
1.5.5计算规模的考虑因素
1.6数据聚类
1.7为并行计算机编程
1.7.1扩展编译器
1.7.2扩展串行编程语言
1.7.3增加并行编程层
1.7.4创造一个并行语言
1.7.5现状
1.8本章小结
1.9主要术语
1.10参考文献
1.11练习题
第2章并行体系结构
2.1概述
2.2互连网络
2.2.1共享介质与开关介质
2.2.2开关网络的拓扑结构
2.2.3二维网格形网络
2.2.4二叉树形网络
2.2.5超树形网络
2.2.6蝶形网络
2.2.7超立方体网络
2.2.8混洗-交换网络
2.2.9小结
2.3阵列处理机
2.3.1体系结构与数据并行
2.3.2阵列处理机的性能
2.3.3处理器互连网络
2.3.4处理器的启动与阻塞
2.3.5其他体系结构特点
2.3.6阵列处理机的缺点
2.4多处理器
2.4.1集中式多处理器
2.4.2分布式多处理器
2.5多计算机
2.5.1非对称多计算机
2.5.2对称多计算机
2.5.3怎样的模型对商用集群来说是最佳的
2.5.4集群与工作站网络之间的差异
2.6弗林分类法
2.6.1SISD
2.6.2SIMD
2.6.3MISD
2.6.4MIMD
2.7本章小结
2.8主要术语
2.9参考文献
2.10练习题
第3章并行算法设计
3.1概述
3.2任务／通道模型
3.3Foster的设计方法论
3.3.1划分
3.3.2通信
3.3.3聚集
3.3.4映射
3.4边界值问题
3.4.1简介
3.4.2划分
3.4.3通信
3.4.4聚集与映射
3.4.5分析
3.5找出最大值
3.5.1简介
3.5.2划分
3.5.3通信
3.5.4聚集与映射
3.5.5分析
3.6n-body问题
3.6.1简介
3.6.2划分
3.6.3通信
3.6.4聚集与映射
3.6.5分析
3.7增加数据输入
3.7.1简介
3.7.2通信
3.7.3分析
3.8本章小结
3.9主要术语
3.10参考文献
3.11练习题
第4章消息传递编程
4.1概述
4.2消息传递模型
4.3MPI接口
4.4电路可满足性问题
4.4.1MPIInit函数
4.4.2MPICommrank和
MPICommsize函数
4.4.3MPIFinalize函数
4.4.4编译MPI程序
4.4.5运行MPI程序
4.5聚合通信简介
MPIReduce函数
4.6检测并行性能
4.6.1MPIWtime~MPIWtick
函数
4.6.2MPIBarrier函数
4.7本章小结
4.8主要术语
4.9参考文献
4.10练习题
第5章Eratosthenes筛法
5.1概述
5.2串行算法
5.3并行性的来源
5.4数据分解方法
5.4.1交叉数据分解
5.4.2按块数据分解
5.4.3用于按块分解的宏
5.4.4局部下标还是全局下标
5.4.5块分解的结果
5.5开发并行算法
函数MPIBcast
5.6并行筛法算法的分析
5.7并行程序的说明
5.8测试
5.9改进
5.9.1删赊偶数
5.9.2消除广播
5.9.3循环的重新组织
5.9.4测试
5.10本章小结
5.11主要术语
5.12参考文献
5.13练习题
第6章Floyd算法
6.1概述
6.2全点对最短路径问题
6.3运行时创建数组
6.4设计并行算法
6.4.1划分
6.4.2通信
6.4.3聚合和映射
6.4.4矩阵的输入／输出
6.5点对点通信
6.5.1函数MPISend
6.5.2函数MPIRecv
6.5.3死锁
6.6并行程序的说明
6.7分析和测试
6.8本章小结
6.9主要术语
6.10参考文献
6.11练习题
第7章性能分析
7.1概述
7.2加速比和效率
7.3Amdahl定律
7.3.1Amdahl定律的局限
7.3.2Amdahl效应
7.4Gustafson-Barsis定律
7.5Karp-Flatt量度
7.6等效指标
7.7本章小结
7.8主要术语
7.9参考文献
7.10练习题
第8章矩阵向量乘法
8.1概述
8.2串行算法
8.3数据分解方式
8.4矩阵按行分解
8.4.1设计与分析
8.4.2复制分块的向量
8.4.3函数MPI_Allgatherv
8.4.4被复制向量的输入／输出
8.4.5编写并行程序
8.4.6测试
8.5矩阵按列分解
8.5.1设计与分析
8.5.2读取按列分解的矩阵
8.5.3函数MPIScaUew
8.5.4打印输出按列分块矩阵
8.5.5函数MPIGaOew
8.5.6分发中间结果
8.5.7函数MPIAlltoallv
8.5.8编写并行程序
8.5.9坝C试
8.6棋盘式分解
8.6.1设计与分析
8.6.2创建通信域
8.6.3函数MPIDimscreate
8.6.4函数MPICartcreate
8.6.5读取棋盘式矩阵
8.6.6函数MPICadrank
8.6.7函数MPICartcoords
8.6.8函数MPI_Comm_split
8.6.9测试
8.7本章小结
8.8主要术语
8.9参考文献
8.10练习题
第9章文档分类
9.1概述
9.2并行算法设计
9.2.1划分与通信
9.2.2聚集和映射
9.2.3管理者／工人模式
9.2.4管理进程
9.2.5MPIAbort函数
9.2.635人进程
9.2.7建立一个只有工人的
通信域
9.3非阻塞通信
9.3.1管理进程的通信
9.3.2MPIIrecv函数
9.3.3MPIWait函数
9.3.432人的通信
9.3.5MPIIsend函数
9.3.6MPIProbe函数
9.3.7MPIGetcount函数
9.4文档分类的并行程序
9.5算法改进
9.5.1按组分配文档
9.5.2流水线处理
9.5.3MPITestsome函数
9.6本章小结
9.7主要术语
9.8参考文献
9.9练习题
第10章蒙特卡洛法
10.1概述
10.1.1为什么蒙特卡洛法
能奏效
10.1.2蒙特卡洛法与并行计算
10.2串行随机数生成器
10.2.1线性同余法
10.2.2滞后形斐波那契生成器
10.3并行随机数产生器
10.3.1管理者-32人方法
10.3.2蛙跳方法
10.3.3序列分割
10.3.4参数化
10.4其他的随机数分布
10.4.1逆分布累积分布
函数变换
10.4.2Box-Muller变换
10.4.3拒绝法
10.5应用示例
10.5.1中子输运
10.5.2维板上一个点的
温度
10.5.3维易辛模型
10.5.4房间分配问题
10.5.5车库停车问题
10.5.6交通环路
10.6本章小结
10.7主要术语
10.8参考文献
10.9练习题
第11章矩阵乘法
11.1概述
11.2矩阵相乘的串行算法
11.2.1基于行的迭代算法
11.2.2基于块的递归算法
11.3行块分解并行算法
11.3.1确定原始任务
11.3.2聚合
11.3.3通信和进一步的聚合
11.3.4分析
11.4Cannon算法
11.4.1组合
11.4.2通信
11.4.3分析
11.5本章小结
11.6主要术语
11.7参考文献
11.8练习题
第12章线性方程组求解
12.1概述
12.2基本术语
12.3回代法
12.3.1串行算法
12.3.2面向行的并行算法
12.3.3面向列的并行算法
12.3.4对比
12.4高斯消去法
12.4.1串行算法
12.4.2并行算法
12.4.3面向行的算法
12.4.4面向列的算法
12.4.5对比
12.4.6面向行的流水线算法
12.5迭代法
12.6共轭梯度法
12.6.1串行算法
12.6.2并行算法
12.7本章小结
12.8主要术语
12.9参考文献
12.10练习题
第13章有限差分方法
13.1概述
13.2偏微分等式
13.2.1偏微分方程的分类
13.2.2差分商
13.3弦振荡问题
13.3.1导出方程
13.3.2串行程序
13.3.3并行程序设计
13.3.4等效分析
13.3.5冗余计算
13.4稳定状态热量分布问题
13.4.1方程的导出
13.4.2串行程序导出
13.4.3并行程序设计
13.4.4等效分析
13.4.5实现细节
13.5本章小结
13.6主要术语
13.7参考文献
13.8练习题
第14章排序
14.1概述
14.2快速排序
14.3并行快速排序算法
14.3.1排序完毕的定义
14.3.2算法开发
14.3.3分析
14.4超级快速排序
14.4.1算法描述
14.4.2等效分析
14.5规则取样并行排序
14.5.1算法描述
14.5.2等效分析
14.6本章小结
14.7主要术语
14.8参考文献
14.9练习题
第15章快速傅立叶变换
15.1概述
15.2傅立叶分析
15.3离散傅立叶变换
15.3.1离散傅立叶逆变换
15.3.2应用示例：多项式乘法
15.4快速傅立叶变换
15.5并行程序设计
15.5.1分割与通信
15.5.2聚合与映射
15.5.3等效分析
15.6本章小结
15.7主要术语
15.8参考文献
15.9练习题
第16章组合搜索
16.1概述
16.2回溯搜索
16.2.1示例
16.2.2时间和空间复杂性
16.3并行回溯算法
16.4分布式终止检测
16.5分支定界法
16.5.1示例
16.5.2串行算法
16.5.3分析
16.6并行分支定界法
16.6.1存储和共享待解的
子问题
16.6.2效率
16.6.3停机条件
16.7搜索博弈树
16.7.1最大最小算法
16.7.2Alpha-Beta剪枝
16.7.3A1pha-Beta剪枝法
的改进
16.8并行Alpha-Beta搜索
16.8.1并行渴望搜索
16.8.2并行子树估值
16.8.3分布式树搜索
16.9本章小结
16.10主要术语
16.11参考文献
16.12练习题
第17章共享存储编程
17.1概述
17.2共享存储模型
17.3对for循环的并行化
17.3.1parallelfor编译
指导语句
17.3.2omp_get_num~mcs
函数
17.3.3ompsetnumthreads
函数
17.4声明私有变量
17.4.1private子句
17.4.2firstprivate子句
17.4.3las中rivate子句
17.51临界区
critical编译指导语句
17.6归约操作
17.7性能改善
17.7.1循环转化
17.7.2条件执行循环
17.7.3循环调度
17.8更普遍的数据并行
17.8.1parallel编译指导语句
17.8.2omp_get_thread_num
函数
17.8.3omp_get_num_threads
函数
17.8.4编译指导语句fo广
17.8.5single编译指导语句
17.8.6nowait子句
17.9功能并行
17.9.1parallelsections编译
指导语句
17.9.2section编译指导语句
17.9.3sections编译指导语句
17.10本章小结
17.11主要术语
17.12参考文献
17.13练习题
第18章融合OpenMP和MPI
18.1·概述
18.2共轭梯度算法
18.2.1MPI程序
18.2.2函数级程序轮廓刻画
18.2.3对函数matrixvector
product进行并行化
18.2.4测试程序
18.3Jacobi方法
18.3.1MPI程序轮廓刻画
18.3.2对函数findsteadystate
并行化
18.3.3测试程序
18.4本章小结
18.5练习题
附录AMn函数
附录B工具函数
B.1MyMPI.h头文件
B.2MyMPI.c源文件
附录C调试MPI程序
C.1概述
C.2MPI程序常见错误
C.2.1死锁错误
C.2.2导致不准确结果的错误
C.2.3组通信的优点
C.3实用调试策略
附录D复数回顾
附录EOpenMP函数
参考文献

并行处理是解决人类重大挑战问题的关键技术。随着集群技术和SMP系统的发展，并行处理在科学研究、工程计算以及商业计算等领域得到了越来越多的应用。并行程序设计一直是并行处理技术中的核心问题，人们也进行了非常多的尝试，提出了多种并行程序开发方法和并行程序设计语言。近年来，MPI和OpenMP逐渐成为了并行程序设计的主流方式。 本书是介绍使用MPI和OpenMP进行并行程序设计的教材，作者是美国俄勒冈州立大学的MiachaelJ.Quinn教授。我们觉得此书具有下面几个特点： 作为一本程序设计教材，本书没有简单地罗列所涉及的语句和函数，而是为每个 语句和函数的“出场”都精心设计了实际问题，让读者能够在实际的上下文中了 解这些语句和函数的目的和作用，以及在实际程序中的使用方式。这无疑将对读 者理解相关的概念带来极大的帮助。 全书中贯穿使用了Foster提出的并行程序设计方法，即划分、通信、聚集和映射 四步法。掌握系统化的并行程序设计方法，有助于读者养成良好的习惯，做出正 确的设计决策，开发出高效率的并行程序。 并行程序的性能是非常重要的，一个低效的并行程序可能还没有串行程序速度 快。本书专门介绍了并行程序性能量度模型和性能分析技术，并在多个章节中进 行了实例分析，对并行程序的性能问题给予了足够的重视。 内容较新。尽管目前已经有较多讲授MPI(消息传递接口)并行程序设计的教材， 但本书不仅包括了MPI并行程序设计，还包括了OpenMP程序设计的内容。这是 目前许多并行程序设计教材所不具备的。本书还介绍了MPI／OpenMP混合编程模 式，该模式对于现有的SMP(对称多处理器)集群系统具有重要意义。此外，处 理器在未来一段时间内的发展趋势是在一个芯片上集成多个核心，研究 MPI／OpenMP混合编程模式对采用多内核处理器构造的并行系统的适用性也是一 个重要的研究课题。 本书由于篇幅所限，并未在所有有关问题上都进行详细的展开讲解，但每一章最后的参考文献为希望更加深入学习的读者提供了进一步阅读的建议。 因此我们认为，本书是一本很优秀的并行程序设计教材，适合学习并行程序设计的学生和计算机专业人士阅读。我们希望本书中文版的出版，能够将本书介绍给更多的中国读者，并为大家的阅读带来方便。同时，由于本书所涉及的领域相当广泛，译者水平有限，翻译中可能还存在不妥之处，敬请广大读者批评指正。 感谢清华大学计算机系的周立柱教授，将本书介绍给我们。·感谢清华大学出版社的龙敏铭编辑，为本书的中文版的出版所付出的耐心和努力。 全书由陈文光、武永卫、陈永健、李建江、薛瑞尼、齐琳等译。清华大学计算机系都志辉进行了审读。 译 者