并行程序设计

专家指导委员会

译者序

译者简介

前言

作者简介

第一部分 基本技术

第1章 并行计算机 2

1.1 对计算速度的需求 2

1.2 并行计算机的类型 4

1.2.1 共享存储器多处理机系统 4

1.2.2 消息传递多计算机系统 5

1.2.3 分布式共享存储器系统 6

1.2.4 MIMD和SIMD分类法 7

1.3 消息传递多计算机的体系结构特征 8

1.3.1 静态网络消息传递多计算机 8

1.3.2 嵌入 12

1.3.3 通信方法 15

1.3.4 输入/输出 17

1.4 用连网计算机作为多计算机平台 18

1.5 提高计算速度的潜力 21

1.6 小结 26

推荐读物 26

参考文献 27

习题 29

第2章 消息传递计算 31

2.1 消息传递编程基础 31

2.1.1 编程的选择 31

2.1.2 进程的创建 31

2.1.3 消息传递例程 33

2.2 使用工作站集群 38

2.2.1 软件工具 38

2.2.2 PVM 38

2.2.3 MPI 43

2.2.4 伪代码构造 49

2.3 并行程序的评估 50

2.3.1 并行执行时间 50

2.3.2 时间复杂性 52

2.3.3 对渐近分析的评注 55

2.3.4 广播/汇集的时间复杂性 55

2.4 并行程序的调试和评估 58

2.4.1 低层次调试 58

2.4.2 可视化工具 59

2.4.3 调试策略 60

2.4.4 用经验方法评估程序 60

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

2.5 小结 63

推荐读物 63

参考文献 63

习题 65

第3章 易并行计算 67

3.1 理想的并行计算 67

3.2 易并行计算举例 68

3.2.1 图像的几何变换 68

3.2.2 曼德勃罗特集 72

3.2.3 蒙特卡罗法 78

3.3 小结 82

推荐读物 82

参考文献 82

习题 83

第4章 划分和分治策略 88

4.1 划分 88

4.1.1 划分策略 88

4.1.2 分治 91

4.1.3 M路分治 95

4.2 分治技术举例 97

4.2.1 使用桶排序法排序 97

4.2.2 数值积分 100

4.2.3 N体问题 103

4.3 小结 107

推荐读物 107

参考文献 108

习题 109

第5章 流水线计算 114

5.1 流水线技术 114

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

5.3 流水线程序举例 118

5.3.1 数字相加 118

5.3.2 数的排序 120

5.3.3 生成质数 123

5.3.4 线性方程组求解—特殊案例 125

5.4 小结 127

推荐读物 128

参考文献 128

习题 128

第6章 同步计算 132

6.1 同步 132

6.1.1 路障 132

6.1.2 计数器实现 133

6.1.3 树实现 135

6.1.4 蝶形路障 136

6.1.5 局部同步 136

6.1.6 死锁 137

6.2 同步计算 137

6.2.1 数据并行计算 137

6.2.2 同步迭代 140

6.3 同步迭代程序举例 140

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

6.3.2 热分布问题 145

6.3.3 细胞自动机 152

6.4 小结 153

推荐读物 153

参考文献 154

习题 154

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

7.1 负载平衡 160

7.2 动态负载平衡 161

7.2.1 集中式动态负载平衡 162

7.2.2 分散式动态负载平衡 163

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

7.3 分布式终止检测算法 167

7.3.1 终止条件 167

7.3.2 使用应答消息实现终止 167

7.3.3 环形终止算法 168

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

7.4 程序举例 170

7.4.1 最短路径问题 170

7.4.2 图表示 171

7.4.3 图的搜索 172

7.5 小结 177

推荐读物 177

参考文献 178

习题 179

第8章 共享存储器编程 184

8.1 共享存储器多处理机 184

8.2 说明并行性的结构 186

8.2.1 创建并发进程 186

8.2.2 线程 187

8.3 共享数据 191

8.3.1 创建共享数据 191

8.3.2 访问共享数据 192

8.3.3 并行性的语言结构 198

8.3.4 相关性分析 199

8.3.5 具有高速缓存的系统中

的共享数据 201

8.4 程序举例 203

8.4.1 UNIX进程 204

8.4.2 Pthreads的例子 206

8.4.3 Java的例子 208

8.5 小结 209

推荐读物 210

参考文献 210

习题 211

第二部分 算法和应用

第9章 排序算法 216

9.1 概述 216

9.1.1 排序 216

9.1.2 可能的加速 216

9.1.3 秩排序 217

9.2 比较和交换排序算法 219

9.2.1 比较和交换 219

9.2.2 冒泡排序与奇偶互换排序 221

9.2.3 二维排序 224

9.2.4 归并排序 226

9.2.5 快速排序 228

9.2.6 超立方体上的快速排序 230

9.2.7 奇偶归并排序 234

9.2.8 双调谐归并排序 235

9.3 小结 238

推荐读物 239

参考文献 239

习题 240

第10章 数值算法 243

10.1 矩阵—回顾 243

10.1.1 矩阵相加 243

10.1.2 矩阵相乘 243

10.1.3 矩阵－向量相乘 244

10.1.4 矩阵与线性方程组的关系 244

10.2 矩阵乘法的实现 244

10.2.1 算法 244

10.2.2 直接实现 246

10.2.3 递归实现 248

10.2.4 网格实现 249

10.2.5 其他矩阵相乘方法 252

10.3 求解线性方程组 253

10.3.1 线性方程组 253

10.3.2 高斯消去法 253

10.3.3 并行实现 254

10.4 迭代方法 256

10.4.1 雅可比迭代 256

10.4.2 快速收敛方法 260

10.5 小结 263

推荐读物 263

参考文献 264

习题 265

第11章 图像处理 268

11.1 低层图像处理 268

11.2 点处理 269

11.3 直方图 270

11.4 平滑. 锐化和噪声消减 270

11.4.1 平均值 271

11.4.2 中值 272

11.4.3 加权掩码 274

11.5 边缘检测 275

11.5.1 梯度和幅度 275

11.5.2 边缘检测掩码 276

11.6 霍夫变换 279

11.7 向频域的变换 282

11.7.1 傅里叶级数 282

11.7.2 傅里叶变换 282

11.7.3 图像处理中的傅里叶变换 283

11.7.4 离散傅里叶变换算法的并行化 285

11.7.5 快速傅里叶变换 287

11.8 小结 293

推荐读物 293

参考文献 293

习题 295

第12章 搜索和优化 298

12.1 应用和技术 298

12.2 分枝限界搜索 299

12.2.1 顺序分枝限界 299

12.2.2 并行分枝限界 300

12.3 遗传算法 301

12.3.1 进化算法和遗传算法 301

12.3.2 顺序遗传算法 303

12.3.3 初始种群 303

12.3.4 选择过程 305

12.3.5 后代的生成 306

12.3.6 变异 307

12.3.7 终止条件 307

12.3.8 并行遗传算法 308

12.4 连续求精 311

12.5 爬山法 311

12.5.1 银行业务应用问题 312

12.5.2 爬山法在银行业务中的应用 314

12.5.3 并行化 315

12.6 小结 315

推荐读物 315

参考文献 315

习题 317

附 录

附录A 基本的PVM例程 323

附录B 基本的MPI例程 328

附录C 基本的Pthread例程 333

附录D 并行计算模型 337

索引 346