并行算法实践

上篇 并行程序设计导论
单元i 并行程序设计基础 .

第一章 并行计算机系统与结构模型 (5)

1.1 典型并行计算机系统简介 (5)

1.1.1 阵列处理机 (5)

1.1.2 向量处理机 (7)

1.1.3 共享存储多处理机 (9)

1.1.4 分布存储多计算机 (10)

1.1.5 分布共享存储多处理机 (12)

1.2 当代并行计算机体系结构 (14)

1.2.1 并行计算机体系结构模型 (14)

1.2.2 并行计算机存储结构模型 (17)

1.2.3 分布式高速缓存与主存体系结构 (19)

1.3 小结 (22)

参考文献 (23)

第二章 pc机群的搭建 (24)

2.1 机群系统概述 (24)

2.1.1 机群系统原理与技术 (24)

2.1.2 典型机群系统简介 (26)

2.2 硬件的选择与安装 (27)

.2.2.1 节点构建 (28)

2.2.2 系统构建 (31)

2.2.3 机群系统示例 (33)

2.3 软件的选择与安装 (33)

2.3.1 os的选择 (33)

2.3.2 ssi的构建 (35)

2.3.3 编程环境的选择 (38)

2.3.4 作业管理系统的选择 (42)

2.4 机群系统性能评测 (49)

2.4.1 基准测试程序 (49)

2.4.2 性能分析工具 (53)

2.5 小结 (56)

参考文献 (56)

第三章 并行程序设计简介 (58)

3.1 并行程序开发方法 (58)

3.1.1 并行层次与代码粒度 (58)

3.1.2 并行程序开发策略 (59)

3.1.3 并行编程模式 (61)

3.1.4 并行应用编程过程 (63)

3.2 并行程序设计模型 (68)

3.2.1 计算π样本程序 (68)

3.2.2 数据并行模型 (69)

3.2.3 消息传递模型 (71)

3.2.4 共享变量模型 (72)

3.3 并行编程语言和环境概述 (73)

3.3.1 早期并行编程语言 (74)

3.3.2 近代并行编程语言与环境 (75)

3.3.3 并行说明性语言环境 (78)

3.4 循环程序并行化的一般方法 (78)

3.4.1 数据相关分析 (78)

3.4.2 数据划分与处理器指派 (80)

3.4.3 循环重构 (87)

3.5 小结 (96)

参考文献 (96)

单元i习题 (98)

单元ii 并行程序编程指南

第四章 mpi编程指南 (105)
4.1 引言 (105)

4.1.1 mpi的产生 (105)

4.1.2 mpi的语言绑定 (106)

4.1.3 mpi的实现 (107)

4.2 6个基本函数组成的mpi子集 (107)

4.3 mpi消息 (109)

4.3.1 消息数据类型 (110)

4.3.2 消息标签 (113)

4.3.3 通信域 (115)

4.3.4 消息状态 (117)

4.4 点对点通信 (117)

4.4.1 mpi通信模式 (118)

4.4.2 阻塞和非阻塞通信 (119)

4.4.3 通信和计算的重叠 (119)

4.5 群集通信 (121)

4.5.1 群集通信的通信功能 (122)

4.5.2 群集通信的同步功能 (125)

4.5.3 群集通信的聚合功能 (125)

4.5.4 群集通信例程的共同特点 (126)

4.5.5 计算π的mpi程序 (127)

4.6 mpi扩展 (127)

4.6.1 动态进程 (128)

4.6.2 远程存储访问 (129)

4.6.3 并行i/o (131)

4.7 小结 (132)

参考文献 (132)

第五章 pvm编程指南 (133)

5.1 引言 (133)

5.1.1 开发历史 (133)

5.1.2 pvm的特点 (134)

5.1.3 与mpi的比较 (134)

5.2 pvm的启动和命令 (135)

5.3 一个简单的pvm程序 (136)

5.3.1 程序介绍 (136)

5.3.2 编译和运行 (138)

5.4 pvm任务 (139)

5.4.1 任务派生 (139)

5.4.2 任务组 (140)

5.4.3 任务标识符 (141)

5.4.4 任务管理 (141)

5.5 pvm通信 (142)

5.5.1 点对点通信 (142)

5.5.2 群集通信 (142)

5.5.3 消息的打包/解包 (143)

5.5.4 通信函数 (144)

5.5.5 计算π的pvm程序 (145)

5.6 pvm虚拟机结构 (146)

5.6.1 结构分析 (147)

5.6.2 动态配置 (147)

5.6.3 pvm虚拟机的构建过程 (148)

5.7 小结 (149)

参考文献 (149)

第六章 hpf编程指南 (150)

6.1 hpf概述 (151)

6.1.1 引言 (151)

6.1.2 hpf的语言特点 (152)

6.1.3 hpf的语言模型 (153)

6.2 hpf编程简介 (154)

6.2.1 一个简单的hpf程序实例 (154)

6.2.2 hpf的基本特性 (155)

6.3 数据映射 (159)

6.3.1 数据映射说明语句 (159)

6.3.2 一个数据映射的hpf程序段分析 (164)

6.4 数据并行结构 (165)

6.4.1 数组运算 (165)

6.4.2 forall语句和forall结构 (167)

6.4.3 independent指示 (169)

6.5 hpf语言的过程 (171)

6.5.1 hpf语言的一般函数和子程序 (171)

6.5.2 hpf语言内部函数 (172)

6.5.3 hpf语言的库函数 (174)

6.6 hpf实例分析：2d fft (176)

6.7 hpf语言其他特性 (178)

6.7.1 hpf对fortran 90语言的限制 (178)

6.7.2 hpf 1.1子集 (179)

6.7.3 hpf 2.0与hpf 1.1的不同点 (180)

6.8 小结 (180)

参考文献 (181)

附录一 hpf指令语法 (182)

附录二 一般的内部函数及库函数 (184)

附录三 hpf网络资源 (187)

第七章 openmp编程指南(189)

7.1 openmp概述 (189)

7.1.1 什么是openmp (190)

7.1.2 openmp的历史 (191)

7.1.3 openmp的目标 (191)

7.2 openmp编程风格 (191)

7.2.1 openmp并行编程模型 (191)

7.2.2 openmp程序结构 (192)

7.3 openmp编程简介 (193)

7.3.1 一个简单的openmp程序实例 (194)

7.3.2 编译制导 (195)

7.3.3 并行域结构 (196)

7.3.4 共享任务结构 (197)

7.3.5 组合的并行共享任务结构 (201)

7.3.6 同步结构 (202)

7.3.7 threadprivate编译制导语句 (205)

7.3.8 数据域属性子句 (206)

7.3.9 子句/编译制导语句总结 (208)

7.3.10 语句的绑定和嵌套规则 (209)

7.4 运行库例程与环境变量 (210)

7.5 openmp计算实例 (210)

7.6 小结 (213)

参考文献 (214)

附录 运行库例程 (215)

单元ii习题 (217)

单元iii 并行程序开发方法

第八章 可视化并行程序设计环境 (223)

8.1 引言 (223)

8.1.1 并行软件工程 (223)

8.1.2 并行程序开发环境的要求 (224)

8.1.3 工具集成 (225)

8.2 sepp/hpcti简介 (225)

8.2.1 sepp/hpcti方法 (225)

8.2.2 sepp/hpcti组成 (226)

8.3 可视化并行语言的分类 (228)

8.3.1 通用编程模型 (229)

8.3.2 进程模型 (232)

8.3.3 进程交互 (233)

8.3.4 正则并行结构 (234)

8.3.5 分层设计和代码复用 (235)

8.4 可视化环境实例 (236)

8.4.1 frameworks系统 (236)

8.4.2 enterprise并行编程系统 (237)

8.4.3 code 2.0语言 (238)

8.4.4 hence编程环境 (239)

8.4.5 trapper编程环境 (240)

8.4.6 meander环境 (241)

8.5 小结 (243)

参考文献 (244)

第九章 并行程序的调试 (245)

9.1 并行调试的方法与步骤 (245)

9.1.1 并行调试的困难 (245)

9.1.2 并行调试的方法 (246)

9.1.3 并行调试的步骤 (247)

9.2 并行调试器的设计与实现 (254)

9.2.1 前期设计 (254)

9.2.2 初步实现 (256)

9.2.3 功能开发 (258)

9.2.4 维护 (260)

9.3 高级并行调试技术简介 (260)

9.3.1 全局断点 (261)

9.3.2 渐增检查点 (261)

9.3.3 事件分析 (261)

9.3.4 静态分析 (262)

9.4 并行程序的性能调试 (262)

9.4.1 性能调试的一般步骤 (262)

9.4.2 性能分析工具举例：vampir和guideview (263)

9.5 小结 (267)

参考文献 (267)

第十章 并行程序的性能分析 (269)

10.1 并行程序性能监控 (269)

10.1.1 监控的应用和分类 (269)

10.1.2 并行跟踪的实现 (271)

10.1.3 侵扰的模型和补偿处理 (273)

10.1.4 并行监控和操作系统的结合与交互 (275)

10.2 并行程序性能预测 (275)

10.2.1 并行系统中的性能预测 (275)

10.2.2 并行系统建模 (278)

10.2.3 并行系统模拟仿真 (281)

10.3 性能可视化 .. (282)

10.3.1 可视化的概念 (283)

10.3.2 数据生成 (284)

10.3.3 数据显示 (285)

10.3.4 数据分析和用户交互 (289)

10.3.5 用户界面 (291)

10.4 小结 (291)

参考文献 (292)

第十一章 并行程序的性能优化 (294)

11.1 引言 (294)

11.1.1 调度问题的一般模型 (294)

11.1.2 并行计算中的任务调度 (295)

11.1.3 并行计算中任务调度的分类 (297)

11.1.4 并行计算中任务调度的模型 (299)

11.2 静态任务调度的np完全性及其最优算法 (302)

11.2.1 静态任务调度的np完全性 (302)

11.2.2 静态任务调度的最优算法 (304)

11.3 静态任务调度的启发式算法 (305)

11.3.1 贪心算法 (305)

11.3.2 随机算法 (306)

11.3.3 聚簇策略 (307)

11.4 动态负载平衡 (308)

11.4.1 基本概念 (308)

11.4.2 负载信息收集 (309)

11.4.3 负载迁移决策 (310)

11.4.4 负载迁移执行 (315)

11.5 小结 (317)

参考文献 (318)

第十二章 图形化并行程序集成开发环境grade简介 (320)

12.1 grade并行程序集成开发环境(320)

12.1.1 grade的组成 (321)

12.1.2 在grade环境中开发并行程序的步骤 (321)

12.2 可视化并行程序设计 (323)

12.2.1 可视化并行程序设计语言grapnel (323)

12.2.2 图形编辑器gred (328)

12.3 映射和调度以及负载平衡工具 (330)

12.3.1 dsm&s和dlb与grade环境的集成 (330)
12.3.2 调度和映射工具 (331)

12.3.3 动态负载平衡系统 (332)

12.4 并行分布式程序调试器 (333)

12.4.1 ddbg与grade的集成 (334)

12.4.2 ddbg的体系结构与接口库 (334)

12.4.3 gred与ddbg的集成 (336)

12.5 tape/pvm监控器和prove可视化工具 (337)

12.5.1 源代码插桩 (337)

12.5.2 数据获取和跟踪分析 (339)

12.5.3 可视化 (340)

12.6 小结 (341)

参考文献 (341)

单元iii习题 (343)

下篇 并行算法编程实现

单元iv 非数值并行算法mpi编程实现

第十三章 排序 (351)

13.1 枚举排序 (351)

13.1.1 枚举排序及其串行算法 (351)

13.1.2 枚举排序的并行算法 (352)

13.2 快速排序 (353)

13.2.1 快速排序及其串行算法 (353)

13.2.2 快速排序的并行算法 (354)

13.3 并行正则采样排序psrs (356)

13.3.1 psrs算法原理 (356)

13.3.2 psrs算法形式化描述 (356)

13.4 小结 (357)

参考文献 (357)

附录 psrs算法mpi源程序 (358)

第十四章 串匹配 (364)

14.1 kmp串匹配算法 (364)

14.1.1 kmp串匹配及其串行算法 (364)

14.1.2 kmp串匹配的并行算法 (368)

14.2 随机串匹配算法 (372)

14.2.1 随机串匹配及其串行算法 (372)

14.2.2 随机串匹配的并行算法 (374)

14.3 近似串匹配算法 (375)

14.3.1 近似串匹配及其串行算法 (375)

14.3.2 近似串匹配的并行算法 (381)

14.4 小结 (383)

参考文献 (383)

附录 kmp串匹配并行算法的mpi源程序 (385)

第十五章 图论 (392)

15.1 传递闭包 (392)

15.1.1 传递闭包串行算法 (392)

15.1.2 传递闭包并行算法 (394)

15.2 连通分量 (396)

15.2.1 顶点倒塌法算法原理描述 (396)

15.2.2 连通分量并行算法 (396)

15.3 单源最短路径 (398)

15.3.1 最短路径串行算法 (398)

15.3.2 最短路径并行算法 (399)

15.4 最小生成树 (402)

15.4.1 最小生成树串行算法 (402)

15.4.2 最小生成树并行算法 (403)

15.5 小结 (406)

参考文献 (406)

附录 连通分量并行算法的mpi源程序 (407)

第十六章 组合优化 (411)

16.1 八皇后问题 (411)

16.1.1 八皇后问题及其串行算法 (411)

16.1.2 八皇后问题的并行算法 (412)

16.2 sat问题 (414)

16.2.1 sat问题及其串行算法 (414)

16.2.2 sat问题的并行算法 (415)

16.3 装箱问题 (418)

16.3.1 装箱问题及其串行算法 (418)

16.3.2 装箱问题的并行算法 (419)

16.4 背包问题 (420)

16.4.1 背包问题及其串行算法 (420)

16.4.2 背包问题的并行算法 (422)

16.5 tsp问题 (423)

16.5.1 tsp问题及其串行算法 (423)

16.5.2 tsp问题的并行算法 (423)

16.6 小结 (425)

参考文献 (426)

附录 八皇后问题并行算法的mpi源程序 (427)

第十七章 计算几何 (432)

17.1 包含问题 (432)

17.1.1 包含问题及其串行算法 (432)

17.1.2 包含问题并行算法 (433)

17.2 相交问题 (435)

17.2.1 两多边形相交问题及其串行算法 (435)
17.2.2 相交问题的并行算法 (436)

17.3 凸壳问题 (437)

17.3.1 凸壳问题及其串行算法 (438)

17.3.2 凸壳问题并行算法 (439)

17.4 小结 (440)

参考文献 (440)

附录 包含问题并行算法的mpi源程序 (441)

单元iv习题 (444)

单元v 数值并行算法mpi 编程实现

第十八章 矩阵运算(455)

18.1 矩阵转置 (455)

18.1.1 矩阵转置及其串行算法 (455)

18.1.2 矩阵转置并行算法 (456)

18.2 矩阵-向量乘法 (458)

18.2.1 矩阵-向量乘法及其串行算法 (458)

18.2.2 矩阵-向量乘法的并行算法 (458)

18.3 行列划分矩阵乘法 (459)

18.3.1 矩阵相乘及其串行算法 (459)

18.3.2 简单的矩阵并行分块乘法算法 (460)

18.4 cannon乘法 (462)

18.4.1 cannon乘法的原理 (462)

18.4.2 cannon乘法的并行算法 (462)

18.5 lu分解 (466)

18.5.1 矩阵的lu分解及其串行算法 (466)

18.5.2 矩阵lu分解的并行算法 (467)

18.6 qr分解 (469)

18.6.1 矩阵qr分解的串行算法 (469)

18.6.2 矩阵qr分解的并行算法 (471)

18.7 奇异值分解 (474)

18.7.1 矩阵奇异值分解的串行算法 (474)

18.7.2 矩阵奇异值分解的并行算法 (477)

18.8 cholesky分解 (480)

18.8.1 矩阵cholesky分解的串行算法 (480)

18.8.2 矩阵cholesky分解的并行算法 (481)

18.9 矩阵求逆 (483)

18.9.1 求矩阵的逆的串行算法 (483)

18.9.2 矩阵求逆的并行算法 (484)

18.10 小结 (486)

参考文献 (486)

附录一 cannon乘法并行算法的mpi源程序 (488)

附录二 矩阵lu分解并行算法的mpi源程序 (494)

附录三 矩阵求逆并行算法的mpi源程序 (498)

第十九章 线性方程组的直接解法 (504)

19.1 高斯消去法解线性方程组 (504)

19.1.1 高斯消去及其串行算法 (504)

19.1.2 并行高斯消去算法 (507)

19.2 约当消去法解线性方程组 (512)

19.2.1 约当消去及其串行算法 (512)

19.2.2 约当消去法的并行算法 (514)

19.3 小结 (517) 参考文献 (518)

附录 全主元高斯消去法并行算法的mpi源程序 (519)

第二十章 线性方程组的迭代解法 (524)

20.1 雅可比迭代 (524)

20.1.1 雅可比迭代及其串行算法 (524)

20.1.2 雅可比迭代并行算法 (526)

20.2 高斯-塞德尔迭代 (527)

20.2.1 高斯-塞德尔迭代及其串行算法 (527)
20.2.2 高斯-塞德尔迭代并行算法 (528)

20.3 松弛法 (531)

20.3.1 松弛法及其串行算法 (531)

20.3.2 松弛法并行算法 (532)

20.4 小结 (534)

参考文献 (534)

附录 高斯-塞德尔迭代并行算法的mpi源程序 (535)
第二十一章 矩阵特征值计算 (540)

21.1 求解矩阵最大特征值的乘幂法 (540)

21.1.1 乘幂法及其串行算法 (540)

21.1.2 乘幂法并行算法 (541)

21.2 求对称矩阵特征值的雅可比法 (543)

21.2.1 雅可比法求对称矩阵特征值的串行算法 (543)

21.2.2 雅可比法求对称矩阵特征值的并行算法 (546)

21.3 求对称矩阵特征值的单侧旋转法 (556)

21.3.1 单侧旋转法的算法描述 (556)

21.3.2 求对称矩阵特征值的单侧旋转法的并行计算 (5 59)

21.4 求一般矩阵全部特征值的qr方法 (562)

21.4.1 qr方法求一般矩阵全部特征值的串行算法 (562 )

21.4.2 qr方法求一般矩阵全部特征值的并行算法 (563 )

21.5 小结 (565)

参考文献 (566)

附录 求对称矩阵特征值的雅可比并行算法mpi源程序 (567)

第二十二章 快速傅氏变换和离散小波变换 (581)

22.1 快速傅里叶变换fft (581)

22.1.1 串行fft迭代算法 (581)

22.1.2 并行fft算法 (583)

22.2 离散小波变换dwt (585)

22.2.1 离散小波变换dwt及其串行算法 (585)
22.2.2 离散小波变换并行算法 (588)

22.3 小结 (590)

参考文献 (590)

附录 fft并行算法的mpi源程序 (591)

单元v习题 (598)

算法索引 (607)

mpi源程序清单 ... (609)

专业术语中英文对照及索引 (611)