本书全面介绍并行计算的各个方面，包括体系结构、编程范型、算法和标准等，涉及并行计算中的新技术，也覆盖了较传统的算法，如排序、搜索、图和动态编程等。本书尽可能采用与底层平台无关的体系结构并且针对抽象模型来设计算法。书中选择MPI、POSIX线程和OpenMP作为编程模型，并在不同例子中反映了并行计算的不断变化的应用组合。
本书论述清晰，示例生动，并附有大量习题。适合作为高等院校计算机及相关专业本科生和研究生的教材或参考书。
无
自1994年本书第1版问世以来，并行计算领域发生了巨大的变化。十多年前，紧耦合可扩展的信息传递平台是并行计算的主流模式，而今，主导地位则由大量成本较低的工作站、多处理机工作站以及服务器构成的机群式计算平台所占据。在此期间，这些平台的程序设计模型也得以发展。尽管十多年前绝大部分的机器还依赖于特定的应用程序编程接口（API）来实现信息交换与基于循环的并行，而现在的模型已在不同平台上将API标准化。一些程序设计模型已被接受为标准，比如消息传递库PVM和MPI、POSIX线程库、基于指令的OpenMP等，并被移植到多种平台上。
十年前，流体力学、结构力学和信号处理等是并行计算应用的主要领域，并且这些应用仍对当前并行计算平台构成挑战。但是，今天许多新的应用也正变得越来越重要，其中包括事务处理、信息检索、数据挖掘与分析和多媒体服务等数据密集型应用。新兴应用领域，如计算生物学与纳米技术，对并行算法和系统开发也提出了巨大的挑战。在并行体系结构、程序设计模型与应用上的变化，也伴随着如何使用户以基于网格服务的形式利用并行计算平台方面的改变。
以上发展对并行算法的设计、分析与实现过程产生了深刻的影响。十年前，并行算法设计主要强调的是如何将任务精确地映射到如格网和超立方体这样的特定拓扑结构上，而今天却是从算法设计与实现的角度来强调可编程性与可移植性。为此，本书尽可能采用与底层平台无关的体系结构，并针对抽象模型来设计算法。关于程序设计模型，本书选择消息传递接口（Message-Passing Interface, MPI）、POISX线程和OpenMP。对于涉及并行计算的应用组合，也反映在本书的各种例子中。
本书构成一门专注于并行计算的课程的基础，也可分为两部分讲授。以下是对按两部分讲授的建议：
1）并行计算导论：第1～6章。这个课程提供并行算法设计和并行编程的基础。
2）并行算法设计与分析：第2、3章以及第8～12章。这个课程对各种并行算法的设计与分析进行深入的探讨。
本书材料曾在明尼苏达大学和普度大学的并行算法与并行计算课程中试用过。这些课程是为计算机科学专业低年级研究生与高年级本科生开设的。另外，对学习计算密集型问题的科学与工程专业的研究生，在他们选修的与科学计算相关的课程中也试用过这些材料。
本书多数章包括：1）例子与图解；2）教材的补充习题，用于测试学生对所学内容的理解程度；3）书目评注，用于帮助有兴趣的学生和研究人员了解相关的和更高级的课题。本书的索引帮助读者快速查找到感兴趣的术语。术语所在的页号使用黑体排印。内容相对比较复杂的节上加了“*”号。此外，从出版商（http://www.booksites.net/kumar）那里可以获得更多支持信息。
与本书前一版一样，我们认为本书也在不断发展之中。要感谢那些对我们第1版书提出批评、建议、问题和提供代码或者其他信息的读者，并真诚地希望围绕着这本新版书，我们之间还能继续这种交流。我们鼓励读者通过电子邮件 book-vk@cs.umn.edu 与我们交流。所有相关的读者反馈将在征得同意后加到http://www.cs.umn.edu/~parbook下的归档信息中。该网站还维护着本书的在线勘误表。我们相信，在像并行计算这个高度动态变化的领域，以这种健全的方式进行思想和资料的交流将使我们受益良多。
致 谢
首先要感谢我们各自的妻子Joanna、Rinku、Krista和Renu，如果没有她们的包容与理解，这项工作是不可能如期完成的。我们也要感谢我们各自的父母及其他家庭成员，Akash、Avi、Chethan、Eleni、Larry、Mary-Jo、Naina、Petros、Samir、Subhasish、Varun、Vibhav和Vipasha，感谢他们在本书写作期间给予作者的热情支持与鼓励。
我们各自所属的机构，普度大学计算机科学与计算研究所（CRI）、明尼苏达大学计算机科学与工程系、美国陆军高性能计算研究中心（AHPCRC）和数字技术中心（DTC），以及位于Yorktown Heights的IBM T. J. Watson研究中心，所具备的计算资源和活跃的学术氛围为我们提供了极大帮助。
本项目源于我们的第1版书，因此要感谢所有在两个版本书的写作期间帮助过我们的人们。许多人以不同方式为这个项目做出了贡献。我们要感谢Ahmed Sameh一如既往的支持与鼓励，Dan Challou、Michael Heath、Dinesh Mehta、Tom Nurkkala、Paul Saylor和Shang-Hua Teng为本书的各个版本提供了有价值的输入工作。感谢明尼苏达大学与普度大学中选修了并行计算导论课程的学生们，他们找出了本书早期手稿中的各种错误。特别要提到的是Jim Diehl和Rasit Eskicioglu，他们极其耐心地为本书的手稿勘正了大量的错误。Ramesh Agarwal、David Bailey、Rupak Biswas、Jim Bottum、Thomas Downar、Rudolf Eigenmann、Sonia Fahmy、Greg Frederickson、John Gunnels、Fred Gustavson、Susanne Hambrusch、Bruce Hendrickson、Christoph Hoffmann、Kai Hwang、Ioannis Ioannidis、Chandrika Kamath、David Keyes、Mehmet Koyuturk、Piyush Mehrotra、Zhiyuan Li、Jens Palsberg、Voicu Popescu、Alex Pothen、Viktor Prasanna、Sanjay Ranka、Naren Ramakrishnan、Elisha Sacks、Vineet Singh、Sartaj Sahni、Vivek Sarin、Wojciech Szpankowski、Srikanth Thirumalai、JanVitek和David Yau为本书提供了宝贵的技术资料。与有合作精神和乐于助人的Pearson Education出版社的员工们一起工作是件非常愉快的事。特别地，我们要感谢Keith Mansfield与Mary Lince对本书的出版所进行的专业运作。
美国陆军研究实验室（The Army Research Laboratory，ARL）、陆军研究局（Army Research Office, ARO）、能源部（Department of Energy，DoE）、国家宇航局（National Aeronautics and Space Administration, NASA）、国家科学基金会（The National Science Foundation, NSF）为作者Ananth Grama、George Karypis与Vipin Kumar提供了并行计算研究的支持。我们还要特别感谢Kamal Abdali、Michael Coyle、Jagdish Chandra、Frederica Darema、Stephen Davis、Wm Randolph Franklin、Richard Hirsch、Charles Koelbel、Raju Namburu、N. Radhakrishnan、John Van Rosendale、Subhash Saini与Xiaodong Zhang在并行计算领域为我们的研究项目所提供的支持。感谢IBM公司的Andrew Conn、Brenda Dietrich、John Forrest、David Jensen与Bill Pulleyblank多年来对作者Anshul Gupta研究工作的一贯支持。
我很高兴《并行计算导论》一书终于有了它的中文译本。在此，恭贺并感谢上海大学计算机学院张武教授承担了这项巨大的工程，以将此书呈献给了广大的中国读者。
并行计算是一个充满活力的领域，经过几十年的发展，这一领域的研究成果已在科学与技术的众多领域随处可见。现在，超级并行计算机在大规模科学与工程计算、电子商务、网络搜索、数据挖掘等领域都得到了广泛的应用。同时，利用现有的软硬件和网络技术制造机群式超级计算机也已变得越来越方便。此外，所有的超级计算机供应商都可为客户提供专用的超级并行计算机。重要的问题是如何充分利用这些超级并行计算机，这需要发展有效的并行算法和以适当的程序范例实施这些算法，这就是本书所讨论的重点。
我衷心希望本书能为读者在学习和应用并行计算这一重要的和不断发展着的最新技术的过程中提供有益的帮助。
Vipin Kumar
美国明尼苏达大学计算机科学与工程系教授
美国陆军高性能计算研究中心主任
Email: kumar@cs.umn.edu
URL: http://www.cs.umn.edu/~kumar
Ananth Grama, Anshul Gupta, George Karypis, Vipin Kumar：Ananth Grama: Ananth Grama普度大学计算机科学系的副教授，研究领域是并行和分布式系统和应用的不同方面。
Anshul Gupta: IBM T．J．Watson Research Center的研究人员，研究领域是并行算法和科学计算。
George Karypis: 明尼苏达大学计算机科学和工程系的副教授，研究领域是并行算法设计、数据挖掘和生物信息学等。
Vipin Kumar: 明尼苏达大学计算机科学和工程系的教授和军用高性能计算研究中心的主管．研究领域是高性能计算。用子科学计算问题和数据挖掘的并行算法。
张武 毛国勇 程海英 等：暂无简介
当代科学、技术和社会经济的发展对大规模科学与工程计算的需求是无止境的，诸如核反应模拟、数值天气预报、基因工程、城市交通、电子商务和网络搜索等问题都对计算提出了巨大的挑战。随着超级并行计算机的飞速发展，尤其是机群式超级计算机提供越来越方便的并行计算资源，如何充分利用这些并行计算机资源，已对并行计算及其应用构成严峻的考验。
《并行计算导论》的作者Vipin Kumar 教授等是国际知名的并行计算专家，他们在并行算法设计与分析、并行计算应用等方面有很深的造诣。自本书第1版1994年出版到2003年出版第2版以来，已在世界范围内被广泛地采用为高等院校本科生和研究生的并行计算教材或参考书。本书系统介绍涉及并行计算的体系结构、编程范例、算法与应用和标准等。本书结构合理，可读性强，加之每章精心设计的习题集，形成了本书的主要特色。相信本书对培养国内急需的并行计算人才和推动并行计算课程建设与改革必将发挥积极的作用。
本书的前言、第1、8、9、13章由张武翻译，第2、10、11、12章由毛国勇翻译，第6、7章由程海英翻译，第3章由宋安平翻译，第4章由付朝江翻译，第5章由张衡翻译。全书由张武统稿。
本书主要作者Vipin Kumar 教授应邀为本书中文版写了序，张武教授在美国伊利诺理工学院（IIT）计算机系工作期间，曾与Kumar 教授有过交流与合作。美国IIT计算机系孙贤和教授、上海大学童维勤教授、支小莉博士和夏骄雄讲师等在本书的翻译过程中给予了帮助。
本书翻译期间正值全国抗击SARS，上海大学于2003年10月接受国家教育部“本科教学水平”评估。因此，翻译时间非常仓促。虽然在翻译过程中力求尊重原意和翻译准确，但由于水平有限及新术语的不断出现，不当和疏漏之处在所难免，敬请读者提出宝贵意见。
译 者
上海大学计算机学院
2004年1月
第1章 并行计算介绍 1
1.1 推动并行化 1
1.1.1 计算能力因素—从晶体管到浮点运算速度 1
1.1.2 内存及磁盘速度的因素 2
1.1.3 数据通信因素 2
1.2 并行计算适用范围 3
1.2.1 在工程及设计中的应用 3
1.2.2 科学计算中的应用 3
1.2.3 商业应用 4
1.2.4 计算机系统中的应用 4
1.3 本书的组织及内容 4
1.4 书目评注 6
习题 6
第2章 并行编程平台 9
2.1 隐式并行:微处理器体系结构的发展趋势* 9
2.1.1 流水线与超标量执行 9
2.1.2 超长指令字处理器 12
2.2 内存系统性能的局限* 12
2.2.1 使用高速缓存改善有效内存延迟 13
2.2.2 内存带宽的影响 14
2.2.3 躲避内存延迟的其他方法 16
2.2.4 多线程与预取间的权衡 17
2.3 并行计算平台剖析 18
2.3.1 并行平台的控制结构 18
2.3.2 并行平台的通信模型 20
2.4 并行平台的物理组织 22
2.4.1 理想并行计算机的体系结构 22
2.4.2 并行计算机互连网络 23
2.4.3 网络拓扑结构 24
2.4.4 静态互连网络评价 31
2.4.5 动态互连网络评价 33
2.4.6 多处理器系统中的高速缓存一致性 34
2.5 并行计算机的通信成本 39
2.5.1 并行计算机的消息传递成本 39
2.5.2 共享地址空间计算机的通信成本 44
2.6 互连网络的路由选择机制 46
2.7 进程-处理器映射的影响和映射技术 47
2.7.1 图的映射技术 48
2.7.2 成本-性能平衡 53
2.8 书目评注 54
习题 55
第3章 并行算法设计原则 63
3.1 预备知识 63
3.1.1 分解、任务与依赖图 63
3.1.2 粒度、并发性与任务交互 65
3.1.3 进程和映射 69
3.1.4 进程与处理器 69
3.2 分解技术 70
3.2.1 递归分解 70
3.2.2 数据分解 72
3.2.3 探测性分解 77
3.2.4 推测性分解 79
3.2.5 混合分解 80
3.3 任务和交互的特点 81
3.3.1 任务特性 81
3.3.2 任务间交互的特征 82
3.4 负载平衡的映射技术 84
3.4.1 静态映射方案 85
3.4.2 动态映射方案 95
3.5 包含交互开销的方法 96
3.5.1 最大化数据本地性 97
3.5.2 最小化争用与热点 98
3.5.3 使计算与交互重叠 98
3.5.4 复制数据或计算 99
3.5.5 使用最优聚合交互操作 100
3.5.6 一些交互与另一些交互的重叠 100
3.6 并行算法模型 101
3.6.1 数据并行模型 101
3.6.2 任务图模型 101
3.6.3 工作池模型 102
3.6.4 主-从模型 102
3.6.5 流水线模型或生产者-消费者模型 103
3.6.6 混合模型 103
3.7 书目评注 103
习题 103
第4章 基本通信操作 107
4.1 一对多广播以及多对一归约 108
4.1.1 环或线性阵列 108
4.1.2 格网 110
4.1.3 超立方体 111
4.1.4 平衡二叉树 111
4.1.5 算法细节 112
4.1.6 成本分析 114
4.2 多对多广播和归约 114
4.2.1 线性阵列和环 115
4.2.2 格网 117
4.2.3 超立方体 117
4.2.4 成本分析 120
4.3 全归约与前缀和操作 121
4.4 散发和收集 123
4.5 多对多私自通信 125
4.5.1 环 126
4.5.2 格网 128
4.5.3 超立方体 128
4.6 循环移位 131
4.6.1 格网 131
4.6.2 超立方体 133
4.7 提高某些通信操作的速度 135
4.7.1 消息分裂和路由选择 135
4.7.2 全端口通信 136
4.8 小结 137
4.9 书目评注 138
习题 139
第5章 并行程序的解析建模 143
5.1 并行程序中的开销来源 143
5.2 并行系统的性能度量 144
5.2.1 执行时间 144
5.2.2 总并行开销 144
5.2.3 加速比 144
5.2.4 效率 147
5.2.5 成本 149
5.3 粒度对性能的影响 149
5.4 并行系统的可扩展性 152
5.4.1 并行程序的扩展特性 153
5.4.2 可扩展性的等效率度量 155
5.4.3 成本最优性和等效率函数 158
5.4.4 等效率函数的下界 159
5.4.5 并发度和等效率函数 159
5.5 最小执行时间和最小成本最优执行时间 159
5.6 并行程序渐近分析 162
5.7 其他可扩展性的度量 162
5.8 书目评注 165
习题 166
第6章 使用消息传递模式编程 171
6.1 消息传递编程的原理 171
6.2 操作构件：发送和接收操作 172
6.2.1 阻塞式消息传递操作 172
6.2.2 无阻塞式消息传递操作 175
6.3 MPI：消息传递接口 176
6.3.1 启动和终止MPI库 177
6.3.2 通信器 177
6.3.3 获取信息 178
6.3.4 发送和接收消息 178
6.3.5 实例：奇偶排序 182
6.4 拓扑结构与嵌入 184
6.4.1 创建和使用笛卡儿拓扑结构 184
6.4.2 实例：Cannon的矩阵与矩阵相乘 185
6.5 计算与通信重叠 187
6.6 聚合的通信和计算操作 191
6.6.1 障碍 191
6.6.2 广播 191
6.6.3 归约 191
6.6.4 前缀 193
6.6.5 收集 193
6.6.6 散发 194
6.6.7 多对多 195
6.6.8 实例：一维矩阵与向量相乘 195
6.6.9 实例：单源最短路径 197
6.6.10 实例：样本排序 199
6.7 进程组和通信器 200
6.8 书目评注 203
习题 204
第7章 共享地址空间平台的编程 205
7.1 线程基础 205
7.2 为什么要用线程 206
7.3 POSIX 线程API 207
7.4 线程基础：创建和终止 207
7.5 Pthreads中的同步原语 210
7.5.1 共享变量的互斥 210
7.5.2 用于同步的条件变量 216
7.6 控制线程及同步的属性 219
7.6.1 线程的属性对象 219
7.6.2 互斥锁的属性对象 220
7.7 线程注销 221
7.8 复合同步结构 221
7.8.1 读-写锁 222
7.8.2 障碍 225
7.9 设计异步程序的技巧 228
7.10 OpenMP：基于命令的并行编程标准 229
7.10.1 OpenMP编程模型 229
7.10.2 在OpenMP中指定并发任务 232
7.10.3 OpenMP中的同步结构 237
7.10.4 OpenMP中的数据处理 240
7.10.5 OpenMP库函数 241
7.10.6 OpenMP中的环境变量 242
7.10.7 显式线程与基于OpenMP编程的比较 243
7.11 书目评注 243
习题 244
第8章 稠密矩阵算法 247
8.1 矩阵向量乘法 247
8.1.1 一维行划分 247
8.1.2 二维划分 250
8.2 矩阵与矩阵的乘法 253
8.2.1 简单的并行算法 254
8.2.2 Cannon算法 254
8.2.3 DNS算法 256
8.3 线性方程组求解 258
8.3.1 简单高斯消元算法 259
8.3.2 带部分主元选择的高斯消元算法 269
8.3.3 求解三角系统：回代法 271
8.3.4 求解线性方程组时的数值因素 272
8.4 书目评注 272
习题 273
第9章 排序 279
9.1 并行计算机中的排序问题 279
9.1.1 输入输出序列的存放位置 279
9.1.2 如何进行比较 280
9.2 排序网络 281
9.2.1 双调排序 282
9.2.2 将双调排序映射到超立方体和格网 285
9.3 冒泡排序及其变体 290
9.3.1 奇偶转换 290
9.3.2 希尔排序 293
9.4 快速排序 294
9.4.1 并行快速排序 295
9.4.2 用于CRCW PRAM的并行形式 296
9.4.3 用于实际体系结构的并行形式 298
9.4.4 主元选择 302
9.5 桶和样本排序 303
9.6 其他排序算法 305
9.6.1 枚举排序 305
9.6.2 基数排序 306
9.7 书目评注 307
习题 308
第10章 图算法 315
10.1 定义和表示 315
10.2 最小生成树：Prim 算法 317
10.3 单源最短路径：Dijkstra算法 321
10.4 全部顶点对间的最短路径 321
10.4.1 Dijkstra算法 322
10.4.2 Floyd算法 323
10.4.3 性能比较 327
10.5 传递闭包 327
10.6 连通分量 328
10.7 稀疏图算法 331
10.7.1 查找最大独立集 332
10.7.2 单源最短路径 334
10.8 书目评注 340
习题 341
第11章 离散优化问题的搜索算法 345
11.1 定义与实例 345
11.2 顺序搜索算法 349
11.2.1 深度优先搜索算法 349
11.2.2 最佳优先搜索算法 351
11.3 搜索开销因子 353
11.4 并行深度优先搜索 353
11.4.1 并行DFS的重要参数 355
11.4.2 并行DFS分析的一般框架 357
11.4.3 负载平衡方案分析 359
11.4.4 终止检测 360
11.4.5 试验结果 362
11.4.6 深度优先分支定界搜索的并行形式 364
11.4.7 IDA*的并行形式 365
11.5 并行最佳优先搜索 365
11.6 并行搜索算法的加速比异常 368
11.7 书目评注 371
习题 374
第12章 动态规划 379
12.1 动态规划概述 379
12.2 串行一元DP形式 381
12.2.1 最短路径问题 381
12.2.2 0/1背包问题 382
12.3 非串行一元DP形式 384
12.4 串行多元DP形式 387
12.5 非串行多元DP形式 387
12.6 综述与讨论 390
12.7 书目评注 391
习题 391
第13章 快速傅里叶变换 395
13.1 串行算法 395
13.2 二进制交换算法 398
13.2.1 全带宽网络 399
13.2.2 有限带宽网络 404
13.2.3 并行快速傅里叶变换中的额外计算 405
13.3 转置算法 407
13.3.1 二维转置算法 407
13.3.2 转置算法的推广 410
13.4 书目评注 413
习题 414
附录A 函数的复杂度与阶次分析 417
索引 419
