本书的主要内容是使用连网工作站和并行计算机并行编程的技术及应用。书中介绍了流水线、分治、同步、工作池等并行技术以及经典的排序、矩阵相乘、线性方程组求解、图像处理、搜索和优化算法的并行实现，并提供了大量的PVM和MPI伪代码及例程。
本书是计算机专业本科生、研究生并行程序设计课程的较好教材。

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

本书的目的是介绍并行编程技术。并行编程使用多计算机或多处理机的计算机来求解问题，它比使用单台计算机的计算速度要快得多。它也为求解更大规模的问题提供了机会，这些问题需要更多的计算步骤或更大存储容量需求，之所以能满足后一要求是因为多计算机和多处理机系统通常比单计算机有更大的总存储容量。在本书中，我们讨论的重点是使用多计算机进行并行编程，它们之间的通信是通过发送消息来完成的，从而出现了消息传递并行编程的术语。我们所使用的计算机可以是不同的类型(PC，SUN，SGI等)，但它们必须由网络进行互连，此外还必须有一个软件环境以在计算机间进行消息传递。适当连网的计算机可广泛地作为学生的基本计算平台，以便可以避免使用特殊设计的多处理机系统。为实现消息传递并行编程，可使用几种软件工具，其中包括PVM和几个MPI的实现方案，它们均可免费得到。这些软件也可在特殊设计的多处理机系统上使用，如果这些系统可以使用的话。就实用这一点而言，我们所讨论的技术和应用是独立于系统的。
本书分为两个部分。在第一部分中，将讨论并行编程的基本技术。第一部分中的各章涉及了所有的基本方面，通过简单问题的求解来说明技术，但是这些技术本身可在许多场合用来求解问题。通常我们先给出顺序的示例代码，然后再给出实际的并行伪代码。一般来讲，基本算法在本质上已经是并行的，而顺序版本不自然地使用循环将其串行化。当然某些算法为了高效地进行并行求解必须进行重构，而这种重构可能不是立即出现的。第一部分中第8章所介绍的并行编程类型并不是围绕消息传递多计算机的，而是围绕专门设计的共享存储多处理机系统的。在这一章内，叙述如何使用Pthreads，这是一个IEEE的多处理机标准系统，已广泛流传并可在单计算机上使用。
学习第一部分所需的准备是有关顺序编程的知识，如C语言的使用和相关数据结构的知识，在掌握了基本的顺序编程后可立即进行第一部分的学习。第一部分中许多指定的作业甚至无需专门的数学知识就可尝试求解。如果需要使用MPI或PVM，则可用具有消息传递库调用的C语言编写程序。在本书的附录中对如何进行具体的库调用做了说明。
许多并行计算问题具有一些专门开发的算法，第二部分中所研究的专用算法涉及非数值和数值范畴。在学习第二部分时，将需要一些数学概念，如矩阵。在第二部分中涉及的主题包括排序、矩阵乘法、线性方程组、偏微分方程、图像处理以及搜索和优化。图像处理特别适合于并行化，因此第二部分中将其作为饶有兴趣的一个应用，专门用一章加以介绍，这种应用对于多种项目具有重要的潜力。在图像处理这一章中，还讨论了所涉及的快速傅里叶变换，这一重要变换还应用在许多其他领域中，包括信号处理和语音识别。
在每章的末尾列出了许多“现实生活”习题，其中绝大部分源自实际生活。这些习题的求解无需专门的数学知识，因而是本书的特色之一；这些习题有助于开发使用并行编程技术的技巧，而不是简单地学习如何去求解像数的排序或矩阵相乘那样的专门问题。
第一部分中的主题宜作为一般顺序编程课程的补充。在北卡罗来纳夏洛特分校，我们以这种方式指导一年级学生进行并行编程。在这种环境下，本书便是对顺序编程教科书的补充。我们设想所使用的顺序编程语言为C或C++。第一部分和第二部分合在一起适合作为高年级并行编程/并行计算课程，在UNCC我们以这种方式使用本书。
有关UNCC环境的全部细节以及具体网站的细节可以从http://www.cs.uncc.edu/par_prog中找到。在该网站中还有许多Web页面帮助学生如何对并行程序进行编译和运行，网站上还提供了一些示例程序，指导教师还可得到有关的教师指导手册。我们教授并行编程的工作是与北卡罗来纳州立大学的并行处理地区培训中心(Regional Training Center for Parallel Processing)所进行的培训工作相关联的，有关这个培训中心的更多情况可以从网站http://renoir.csc.ncsu. edu/RTCPP上找到。
本书是美国国家科学基金会对作者在北卡罗来纳大学夏洛特分校为一年级学生介绍并行编程技术项目(美国国家科学基金项目“将并行编程技术引入一年级课程”，项目编号DUE 9554975)进行资助的直接结果。我们极其感谢国家科学基金会的计划主任M. Mulder博士对我们项目的支持，没有他的帮助，我们不可能去追求在教科书中提出的那些想法。我们也要感谢参与本项目的研究生和本科生。这个学生小组帮助开发了有关素材和作业习题。还要感谢计算机科学系的系统管理员James Robinson，他建成了我们的本地工作站集群，没有该集群我们不可能完成这一著作。
我们还要感谢UNCC的许多学生，他们在过去的几年中帮助我们改进了教材素材，特别是那些“远程课程”，在这些课程中，本书的材料成为以独特方式实验的课堂。这些远程课程除了UNCC外还向几所北卡罗来纳州立大学做了传播，其中包括北卡罗来纳大学阿什维尔分校，北卡罗来纳大学格林斯伯勒分校、北卡罗来纳大学威尔明顿分校和北卡罗来纳州立大学。我们还要向许多人致谢，其中特别要提及的是北卡罗来纳大学阿什维尔分校的Wayne Lang教授和北卡罗来纳州立大学的Mladen Vouk教授。Lang教授投身于课堂的教案开发，而Vouk教授除了以客座专家身份授课外，还设计了一个给人深刻印象的Web页面，其中包括了我们课程的“实音”和“自动翻转”的幻灯片。(这些授课情况可在http://renoir.csc.ncsu.edu/CSC495A上看到。)杜克大学的John Board教授以及北卡罗来纳大学查珀尔希尔分校的Jan Prins教授也欣然做了客座专家讲演。承蒙Raul Gallard教授的邀请，我们还在阿根廷的圣路易斯国立大学讲授了基于本书素材的并行编程课程—所有这一切活动均有益于我们编写本书。我们要向Prentice Hall出版社的Alan Apt和Laura Steele致谢，他们接受了我们编写书的提议并自始至终支持我们。我们还要向所有评阅人致谢，感谢他们非常有益的指点。
最后我们恳请读者对本书提出宝贵意见并不吝指正，并通过下列电子邮件地址传给我们：abw@uncc.edu(Barry Wilkinson)或cma@uncc.edu(Michael Allen)。

Barry Wilkinson
Michael Allen
于北卡罗来纳大学夏洛特分校

陆鑫达 等：陆鑫达: 1938年9月生，上海市人。1961年和1964年分别获哈尔滨工业大学计算机专业学士和硕士学位。现为上海交通大学计算机科学与工程系教授，博士生导师，高性能计算研究室主任。1964-1978年在哈尔滨工业大学计算机系任教。1979-1981年为英国纽卡舍尔大学计算机系访问学者，主要从事高度并行计算技术、VLSI芯片设计技术、和处理机互连等技术研究。1981年1月随英国代表团访问美国西海岸的UC Berkeley 分校、Stanford大学、UCLA分校的计算机系以及 Xerox Palo Alto计算机研究中心等，并参加在加州哩工学院(CIT)举行的VLSI学术会议。1984年7月起任教于上海交通大学计算机系。1987-1990年为德国GMD-FIRST 柏林计算机研究所和柏林工业大学（TUB）的客座首席科学家，主要从事新型数据结构高性能计算系统研究，并负责国家自然科学基金会重大项目中的中德国际合作项目。2000年3月曾在美国纽约州立大学新珀斯分校计算机系讲学。2000年7月被聘为贵州大学兼职教授。
开设课程包括：计算机组成、计算机系统结构、计算机网络、数字电路、计算机仿真技术、高级计算机系统结构、网络计算及编程环境、VLSI设计导论、并行计算等。 著作和翻译了多本教材，包括：担任《中国大百科全书》“自动控制和系统工程”卷中“信息处理”分卷副主编； 主编《计算机系统结构》（高等教育出版社，1996年3月）；翻译《可扩展并行计算：技术、结构与编程》，《并行程序设计》等。 承担和主持多项科研项目，包括：国家自然科学基金会重大项目1项（1987-1992），面上项目4项（1987-1992，1992-1994，1997-1999，1998-2000），863项目1项，以及电科院等项目。目前承担国家自然科学基金会面上项目1项：“校园级自适应元计算系统中关键技术研究”（2002-2004）。九五期间所承担的211工程“高速信息网工程”中的子项目“高速计算技术实验室”已经完成。
获奖情况：1964年国家工业新产品二等奖（高速磁芯存储器）、1992年国家自然科学基金重大项目“优秀”、1998年上海高校优秀教材二等奖，1998年申银万国奖、2000年教育部科技进步三等奖，诺基亚奖教金一等奖，联想集团奖教金特等奖。
担任的社会职务有：中国计算机学会体系结构专委会副主任，中国计算机学会开放系统专委会高级委员。
目前的主要研究方向：高性能计算及应用、异构计算及元计算（包括Grid计算）、网络计算及其编程环境，机群计算（包括体系结构及中间件）、遗传和进化算法在映射和调度中的应用，分布计算及移动计算，智能代理等。

本书是有关使用连网计算机来进行并行计算的一本很实用的教科书。本书是Barry Wilkinson和Michael Allen两位教授多年教学和科研的结晶。作者用此教材指导美国大学一年级学生进行并行编程实践，具有超前意识，为此获得美国国家科学基金会的资助，使此书得以出版。我们翻译此书的宗旨是想促使并行/分布计算，特别是使用连网计算机的并行/分布计算，在中国的普及和发展，尤其是在高等院校中的普及和发展。
本书介绍了常用的算法范例，包括分治、流水线、同步计算、主从方式及工作池等内容，并介绍了常用的经典算法，如排序、矩阵相乘、线性方程组求解、图像处理中的预处理和相应的变换、搜索和优化(包括遗传算法)等，这是本书的一大特色。读者掌握了这些算法范例和经典算法后就可为并行编程打下良好基础。书中每一章后面均附有习题，除了与每章内容有关的习题之外，还有不少习题源自现实生活，既富有启发性，又具有趣味性，应该说这是本书的另一特色。
本书的翻译工作由陆鑫达负责和组织，并翻译目录、前言、第1~3章，以及第11、12章， 汤勇平翻译第4章，曾志勇翻译第5章，支小莉翻译第6章，张建翻译第7章，钟嵘翻译第8章，吴欣翻译第9章，徐蔚文翻译第10章。译稿全文由陆鑫达做了校对。
由于翻译时间仓促，再加上有的术语国内没有统一的译法，故翻译中的错误或不妥之处在所难免，恳请广大读者不吝指正。

陆鑫达
上海交通大学计算机科学与工程系
2001年6月8日

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