并行程序设计

　　本书讲解如何在并行和分布式操作系统下设计高效率、低开销的程序，内容既包括并行程序设计的技术也包括实现程序的工具。全书分为三个部分13章。第一部分是前4章，介绍并行计算和程序设计的概念。第二部分介绍了并行程序设计的语言和函数库，包括C++、FortranM、HPF和MPI等进行编程工具。第三部分给出了并行程序的几类算法和常用的资源。本书适合作为高等学院校计算机专业并行程序设计课程的教材，也适合具有相应水平的读者自学。

　　BarryWilkinson是北卡卡罗来纳大学夏洛特分校计算机科学系教授。在此之前他曾在英格兰布赖顿大学（1984-1987）、纽约州立大学纽帕尔兹学院（1983-1984）、威尔士加的夫大学学院（1976-1983）以及英格兰阿斯顿大学（1973-1976）任职。从1969到1970年，他曾在Ferranti有限公司从事过程控制计算机系统工作。他是《ComputerPeripherals》（同D.Horrocks，Hodder和Stoughton合作，1980，1987年第2版）、《DigitalSystemDesign》（PrenticeHall，1987，第2版1992年）、《ComputerArchitectureDesignandPerformance》（PrenticeHall，1991，第2版1996年）和《TheEssenceofDigitalDesign》（PrenticeHall，1997年）的作者。除了上述的著作之外，他在主要的计算机刊物上发表了许多论文。1969年他在英格兰索尔福德大学获得电气工程学士学位（优等成绩），1971和1974年在英格兰的曼彻斯特大学（计算机科学系）分别获得硕士和博士学位。自1983年起，他一直是IEEE的资深会员。MichaelAllen是北卡罗来纳大学夏洛特分校计算机科学系教授。在此之前他曾是北卡罗来纳大学夏洛特分校电气工程系的副教授和教授（1974-1985），并曾是纽约州大学布法罗分校的讲师和助理教授。在1985到1987年他离开了北卡罗来纳大学夏洛特分校，在DataSpan公司任董事长。其他的工业界经历还包括在EastmanKodak，slyvaniaElectronics，宾夕法尼亚的Bell，WachoviaBank以及许多其他公司中从事电子设计和软件系统开发工作。他于1964和1965年分别在卡纳基-梅隆大学获得电气工程的学士和硕士学位，并于1968年在纽约州立大学布法罗分校获得博士学位。陆鑫达，现为上海交通大学计算机科学与工程系教授、博士生导师、高性能计算研究室主任，中国计算机学会体系结构委会副主任，中国计算机学会开放系统专委会高级委员，贵州大学兼职教授。1961年和1964年分别获哈尔滨大学计算机专业学士。1979-1981年为英国纽卡舍尔大学计算机系统访问学者，主要从事高度并行计算技术、VLSI芯片设计技术和处理机互连等技术研究。1987-1990年为德国GMD-FIRST柏林计算机研究所和柏林工业大学（TUB）的客座首席科学家，主要从事新型数据结构高性能计算机系统研究，并负责国家自然科学基金会重大项目中的中德国际合作项目。曾任《中国大百科全书》“自动控制和系统工程”卷“信息处理”分卷副主编。主编教材《计算机系统结构。（高等教育出版社，1996年3月）。教材译著：《可扩展并行计算：技术、结构与编程》（机械工业出版社，2000年5月）。目前主要研究方向为高性能计算及应用、异构及元计算（包括Grid计算）、网络计算及其编程环境、机群计算（包括体系结构及中国件）、遗传和进化算法在映射和调度中的应用、分布计算及移动计算、智能代理等。

专家指导委员会
译者序
译者简介
前言
作者简介
第一部分   基本技术
第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