并行程序设计(第2版)pdf

并行程序设计(第2版) 内容简介

本书系统介绍并行程序设计原理及应用。除介绍常用的一些算法范例，包括分治、流水、同步计算、主从及工作池，还介绍了一些常用的经典数值和非数值算法，如排序、矩阵相乘、线性方程组求解、图像处理中的预处理和相应的变换、搜索和优化等。第2版新增了机群计算等使用机群的内容，对如何打造专用和通用的机群以及设置相应的程序设计环境做了较为详尽的介绍。章后包含大量习题，其中现实生活习题非常实用，既可增强学习兴趣，又可提高并行程序设计技巧。

本书可作为高等院校计算机专业高年级本科生或研究生的教材，对从事高性能计算的科技工作者也是一本很有价值的参考书。

并行程序设计(第2版) 目录

前言

作者简介

第一部分 基本技术

第1章 并行计算机 2

1.1 对计算速度的需求 2

1.2 提高计算速度的潜力 4

1.2.1　加速系数 4

1.2.2 什么是最大的加速比 5

1.2.3 消息传递计算 9

1.3 并行计算机的类型 9

1.3.1 共享存储器多处理机系统 10

1.3.2 消息传递多计算机 11

1.3.3 分布式共享存储器 17

1.3.4　MIMD和SIMD的分类 17

1.4 机群计算 18

1.4.1 以互联计算机作为计算平台 18

1.4.2 机群的配置 23

1.4.3 打造“Beowulf风格”的专用机群 26

1.5 小结 27

推荐读物 27

参考文献 28

习题 30

第2章 消息传递计算 31

2.1 消息传递程序设计基础 31

2.1.1 编程的选择 31

2.1.2 进程的创建 31

2.1.3 消息传递例程 33

2.2 使用计算机机群 37

2.2.1 软件工具 37

2.2.2 MPI 37

2.2.3 伪代码构造 44

2.3 并行程序的评估 45

2.3.1 并行执行时间方程式 45

2.3.2 时间复杂性 48

2.3.3 对渐近分析的评注 50

2.3.4 广播/集中的通信时间 50

2.4 用经验方法进行并行程序的调试和评估 51

2.4.1 低层调试 52

2.4.2 可视化工具 52

2.4.3 调试策略 53

2.4.4 评估程序 53

2.4.5 对优化并行代码的评注 55

2.5 小结 55

推荐读物 55

参考文献 56

习题 57

第3章 易并行计算 59

3.1 理想的并行计算 59

3.2 易并行计算举例 60

3.2.1 图像的几何转换 60

3.2.2 曼德勃罗特集 64

3.2.3 蒙特卡罗法 69

3.3 小结 73

推荐读物 73

参考文献 73

习题 74

第4章 划分和分治策略 79

4.1 划分 79

4.1.1 划分策略 79

4.1.2 分治 82

4.1.3 M路分治 86

4.2 分治技术举例 87

4.2.1 使用桶排序法排序 87

4.2.2 数值积分 91

4.2.3 N体问题 93

4.3 小结 96

推荐读物 97

参考文献 97

习题 98

第5章 流水线计算 104

5.1 流水线技术 104

5.2 流水线应用的计算平台 107

5.3 流水线程序举例 107

5.3.1 数字相加 108

5.3.2 数的排序 110

5.3.3 生成质数 112

5.3.4 线性方程组求解—特殊个例 114

5.4 小结 117

推荐读物 117

参考文献 117

习题 117

第6章 同步计算 122

6.1 同步 122

6.1.1 障栅 122

6.1.2 计数器实现 123

6.1.3 树实现 124

6.1.4 蝶形障栅 125

6.1.5 局部同步 126

6.1.6 死锁 126

6.2 同步计算 127

6.2.1 数据并行计算 127

6.2.2 同步迭代 129

6.3 同步迭代程序举例 130

6.3.1 用迭代法解线性方程组 130

6.3.2 热分布问题 135

6.3.3 细胞自动机 142

6.4 部分同步方法 143

6.5 小结 144

推荐读物 144

参考文献 144

习题 145

第7章 负载平衡与终止检测 151

7.1 负载平衡 151

7.2 动态负载平衡 152

7.2.1 集中式动态负载平衡 152

7.2.2 分散式动态负载平衡 153

7.2.3 使用线形结构的负载平衡 155

7.3 分布式终止检测算法 157

7.3.1 终止条件 157

7.3.2 使用确认消息实现终止 158

7.3.3 环形终止算法 158

7.3.4 固定能量分布式终止算法 160

7.4 程序举例 160

7.4.1 最短路径问题 160

7.4.2 图的表示 161

7.4.3 图的搜索 162

7.5 小结 166

推荐读物 166

参考文献 167

习题 168

第8章 共享存储器程序设计 172

8.1 共享存储器多处理机 172

8.2 说明并行性的构造 173

8.2.1 创建并发进程 173

8.2.2 线程 175

8.3 共享数据 178

8.3.1 创建共享数据 179

8.3.2 访问共享数据 179

8.4 并行程序设计语言和构造 185

8.4.1 并行语言 185

8.4.2 并行语言构造 186

8.4.3 相关性分析 187

8.5 OpenMP 189

8.6 性能问题 193

8.6.1 共享数据的访问 193

8.6.2 共享存储器的同步 195

8.6.3 顺序一致性 196

8.7 程序举例 199

8.7.1 使用UNIX进程的举例 199

8.7.2 使用Pthread的举例 201

8.7.3 使用Java的举例 203

8.8 小结 204

推荐读物 205

参考文献 205

习题 206

第9章 分布式共享存储器系统及其程序设计 211

9.1 分布式共享存储器 211

9.2 分布式共享存储器的实现 212

9.2.1 软件DSM系统 212

9.2.2 DSM系统的硬件实现 213

9.2.3 对共享数据的管理 214

9.2.4 基于页面系统的多阅读器/单写入器策略 214

9.3 在DSM系统中实现一致性存储器 214

9.4 分布式共享存储器的程序设计原语 216

9.4.1 进程的创建 216

9.4.2 共享数据的创建 216

9.4.3 共享数据的访问 217

9.4.4 同步访问 217

9.4.5 改进性能的要点 217

9.5 分布式共享存储器的程序设计 219

9.6 实现一个简易的DSM系统 219

9.6.1 使用类和方法作为用户接口 220

9.6.2 基本的共享变量实现 220

9.6.3 数据组的重叠 222

9.7 小结 224

推荐读物 224

参考文献 224

习题 225

第二部分 算法和应用

第10章 排序算法 230

10.1 概述 230

10.1.1 排序 230

10.1.2 可能的加速比 230

10.2 比较和交换排序算法 231

10.2.1 比较和交换 231

10.2.2 冒泡排序与奇偶互换排序 233

10.2.3 归并排序 236

10.2.4 快速排序 237

10.2.5 奇偶归并排序 239

10.2.6 双调谐归并排序 240

10.3 在专用网络上排序 243

10.3.1 二维排序 243

10.3.2 在超立方体上进行快速排序 244

10.4 其他排序算法 247

10.4.1 秩排序 248

10.4.2 计数排序 249

10.4.3 基数排序 250

10.4.4 采样排序 252

10.4.5 在机群上实现排序算法 253

10.5 小结 253

推荐读物 254

参考文献 254

习题 255

第11章 数值算法 258

11.1 矩阵回顾 258

11.1.1 矩阵相加 258

11.1.2 矩阵相乘 258

11.1.3 矩阵-向量相乘 259

11.1.4 矩阵与线性方程组的关系 259

11.2 矩阵乘法的实现 259

11.2.1 算法 259

11.2.2 直接实现 260

11.2.3 递归实现 262

11.2.4 网格实现 263

11.2.5 其他矩阵相乘方法 266

11.3 求解线性方程组 266

11.3.1 线性方程组 266

11.3.2 高斯消去法 266

11.3.3 并行实现 267

11.4 迭代方法 269

11.4.1 雅可比迭代 269

11.4.2 快速收敛方法 272

11.5　小结 274

推荐读物 275

参考文献 275

习题 276

第12章 图像处理 279

12.1 低层图像处理 279

12.2 点处理 280

12.3 直方图 281

12.4 平滑、锐化和噪声消减 281

12.4.1 平均值 281

12.4.2 中值 283

12.4.3 加权掩码 284

12.5 边缘检测 285

12.5.1 梯度和幅度 285

12.5.2 边缘检测掩码 286

12.6 霍夫变换 288

12.7 向频域的变换 290

12.7.1 傅里叶级数 291

12.7.2 傅里叶变换 291

12.7.3 图像处理中的傅里叶变换 292

12.7.4 离散傅里叶变换算法的并行化 294

12.7.5 快速傅里叶变换 296

12.8 小结 300

推荐读物 300

参考文献 300

习题 302

第13章 搜索和优化 305

13.1 应用和技术 305

13.2 分支限界搜索 306

13.2.1 顺序分支限界 306

13.2.2 并行分支限界 307

13.3 遗传算法 308

13.3.1 进化算法和遗传算法 308

13.3.2 顺序遗传算法 310

13.3.3 初始种群 310

13.3.4 选择过程 312

13.3.5 后代的生成 312

13.3.6 变异 314

13.3.7 终止条件 314

13.3.8 并行遗传算法 314

13.4 连续求精 317

13.5 爬山法（hill climbing） 318

13.5.1 银行业务应用问题 319

13.5.2 爬山法在金融业务中的应用 320

13.5.3 并行化 321

13.6 小结 321

推荐读物 321

参考文献 322

习题 323

附录A 基本的MPI例程 329

附录B 基本的Pthread例程 335

附录C OpenMP命令、库函数以及

环境变量 339

索引 347