世界著名计算机教材精选 MPI与OpenMP并行程序设计 C语言版
作者：（美）Michael J.Quinn著 陈文光，武永卫等译
出版时间： 2004年版
丛编项： 世界著名计算机教材精选
内容简介
本书是美国Oregon州立大学的MichaelJ.Quinn教授在多年讲授“并行程序设计”课程的基础上编写而成的，主要介绍用C语言，并结合使用MPI和OpenMP进行并行程序设计，内容包括并行体系结构、并行算法设计、消息传递编程、Eratosthenes筛法、Floyd算法、性能分析、矩阵向量乘法、文档分类、蒙特卡洛法、矩阵乘法、线性方程组求解、有限差分方法、排序、快速傅立叶变换、组合搜索、共享存储编程、融合OpenMP和MPI以及5个附录。本书按授课方式安排章节，通过划分、通信、集聚和映射等四步的并行程序设计方法，来解决各种实际的并行性问题，使读者掌握系统化的并行程序设计方法，开发出高效的并行程序。本书不仅是一本优秀的并行程序设计教材，对广大的相关专业人员也很有参考价值。
目录
第1章 动机和历史
1.1 概述
1.2 现代科学方法
1.3 超级计算的进化
1.4 现代并行计算机
1.4.1 Cosmic Cube并行计算机
1.4.2 商品化的并行计算机
1.4.3 Beowulf系统
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.1 SISD
2.6.2 SIMD
2.6.3 MISD
2.6.4 MIMD
2.7 本章小结
2.8 主要术语
2.9 参考文献
2.10 练习题
第3章 并行算法设计
3.1 概述
3.2 任务/通道模型
3.3 Foster的设计方法论
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.6 n-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.3 MPI接口
4.4 电路可满足性问题
4.4.1 MPI_Init函数
4.4.2 MPI_Comm rank和MPI Comm_size函数
4.4.3 MPI Fimlize函数
4.4.4 编译MPI程序
4.4.5 运行MPI程序
4.5 聚合通信简介
MPI Reduce函数
4.6 检测并行性能
4.6.1 MPI_Wtime和MPI_Wtick函数
4.6.2 MPI_Barrier函数
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 开发并行算法
函数MPI Bcast
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 函数MPI_Send
6.5.2 函数MPI_Recv
6.5.3 死锁
6.6 并行程序的说明
6.7 分析和测试
6.8 本章小结
6.9 主要术语
6.10 参考文献
6.11 练习题
第7章 性能分析
7.1 概述
7.2 加速比和效率
7.3 Amdahl定律
7.3.1 Amdahl定律的局限
7.3.2 Amdahl效应
7.4 Gustafson-Barsis定律
7.5 Karp-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 函数MPI_Scatterv
8.5.4 打印输出按列分块矩阵
8.5.5 函数MPI_Gatherv
8.5.6 分发中间结果
8.5.7 函数MPI_Alltoallv
8.5.8 编写并行程序
8.5.9 测试
8.6 棋盘式分解
8.6.1 设计与分析
8.6.2 创建通信域
8.6.3 函数MPI_Dims_create
8.6.4 函数MPI_Cart_create
8.6.5 读取棋盘式矩阵
8.6.6 函数MPI_Cart_rank
8.6.7 函数MPI_Cart_coords
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.5 MPI_Abort函数
9.2.6 工人进程
9.2.7 建立一个只有工人的通信域
9.3 非阻塞通信
9.3.1 管理进程的通信
9.3.2 MPI_Irecv函数
9.3.3 MPI_Wait函数
9.3.4 工人的通信
9.3.5 MPI_Isend函数
9.3.6 MPI_Probe函数
9.3.7 MPI_Get_count函数
9.4 文档分类的并行程序
9.5 算法改进
9.5.1 按组分配文档
9.5.2 流水线处理
9.5.3 MPI_Testsome函数
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 管理者-工人方法
10.3.2 蛙跳方法
10.3.3 序列分割
10.3.4 参数化
10.4 其他的随机数分布
10.4.1 逆分布累积分布函数变换
10.4.2 Box-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.4 Cannon算法
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.2 Alpha-Beta剪枝
16.7.3 Alpha-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.1 parallel for编译指导语句
17.3.2 omp_get_num_procs函数
17.3.3 omp_set_num_theads函数
17.4 声明私有变量
17.4.1 private子句
17.4.2 firstprivate子句
17.4.3 lastprivate子句
17.5 临界区
critical编译指导语句
17.6 归约操作
17.7 性能改善
17.7.1 循环转化
17.7.2 条件执行循环
17.7.3 循环调度
17.8 更普遍的数据并行
17.8.1 parallel编译指导语句
17.8.2 omp_get_thread num函数
17.8.3 omp_get_num_threads函数
17.8.4 编译指导语句for
17.8.5 single编译指导语句
17.8.6 nowait子句
17.9 功能并行
17.9.1 parallel sections编译指导语句
17.9.2 section编译指导语句
17.9.3 sections编译指导语句
17.10 本章小结
17.1l 主要术语
17.12 参考文献
17.13 练习题
第18章 融合OpenMP和MPI
18.1概述
18.2 共轭梯度算法
18.2.1 MPI程序
18.2.2 函数级程序轮廓刻画
18.2.3 对函数matrix_vector_pmduct进行并行化
18.2.4 测试程序
18.3 Jacobi方法
18.3.1 MPI程序轮廓刻画
18.3.2 对函数find_steadv_state并行化
18.3.3 测试程序
18.4 本章小结
18.5 练习题
附录A MPI函数
附录B 工具函数
B.1 MyMPI.h头文件
B.2 MyMPI.c源文件
附录C 调试MPI程序
C.1 概述
C.2 MPI程序常见错误
C.2.1 死锁错误
C.2.2 导致不准确结果的错误
C.2.3 组通信的优点
C.3 实用调试策略
附录D 复数回顾
附录E OpenMP函数
参考文献
