本书循序渐进地展示了如何利用MPI、PThread 和OpenMP开发高效的并行程序，教给读者如何开发、调试分布式内存和共享式内存的程序，以及对程序进行性能评估。

并行程序设计导论
An Introduction to Parallel Programming
（美）Peter S. Pacheco 著　 邓倩妮 等译
毫无疑问，随着多核处理器和云计算系统的广泛应用，并行计算不再是计算世界中被束之高阁的偏门领域。并行性已经成为有效利用资源的首要因素，Peter Pacheco撰写的这本新教材对于初学者了解并行计算的艺术和实践很有帮助。
　　　　　　　　　　　　　　 —— Duncan Buell，南卡罗来纳大学计算机科学与工程系
本书阐述了两个越来越重要的领域：使用Pthreads和OpenMP进行共享内存编程，以及使用MPI进行分布式内存编程。更重要的是，通过指出可能出现的性能错误，强调好的编程实现的重要性。这些主题包含在计算机科学、物理学和数学等多个学科中。各章包含了大量不同难易程度的编程习题。对于希望学习并行编程技巧、更新知识面的学生或专业人士来说，本书是一本理想的参考书。
　　　　　　　　　　 —— Leigh Little，纽约州立大学布罗科波特学院计算机科学系
并行编程已不仅仅是面向专业技术人员的一门学科。如果想要全面开发集群和多核处理器的计算能力，那么学习分布式内存和共享内存的并行编程技术是不可或缺的。本书是一本精心撰写的、全面介绍并行计算的书籍。作者循序渐进地展示了如何利用MPI、Pthreads 和OpenMP开发高效的并行程序，教给那些专业知识有限、没有并行化经验的读者如何开发、调试分布式内存和共享内存的程序，以及对程序进行性能评估。
本书特色
采用教程形式，从简短的编程实例起步，一步步编写更有挑战性的程序。
重点介绍分布式内存和共享内存的程序设计、调试和性能评估。
使用MPI、Pthreads 和OpenMP等编程模型，强调实际动手开发并行程序。
作者简介
Peter S. Pacheco　拥有佛罗里达州立大学数学专业博士学位。曾担任旧金山大学计算机系主任，目前是旧金山大学数学系主任。近20年来，一直为本科生和研究生讲授并行计算课程。

并行硬件已经普及了一段时间。现在已经很难找到一台没有多核处理器的笔记本、台式机或者服务器。在20世纪90年代还是高性能工作站的Beowulf集群，而今已经达到普及程度。与此同时，云计算的出现使得分布式内存系统与台式机一样便于访问。尽管如此，大多数计算机专业的学生在毕业时拥有很少甚至几乎没有任何并行编程经验。虽然许多学院或大学为高年级学生提供并行计算选修课程，但因为计算机科学专业有过多的必修课要求，很多人在毕业时甚至没有写过一个多线程或者多进程的程序。
　　毫无疑问，这样的现状是需要改变的。虽然许多程序在单核上获得了较满意的性能，但是计算机科学家们必须意识到：并行化有潜力使性能得到巨大提升。当需求提升时，他们应该具备开发这种潜力的能力。
　　本书旨在部分地解决该问题。它介绍如何使用MPI、Pthreads和OpenMP编写并行程序。MPI、Pthreads和OpenMP是三个广泛应用在并行编程中的应用程序编程接口（Application Programming Interface，API）。本书的预期读者是需要编写并行程序的学生和专业人员。阅读本书仅需要很少的预备知识：大专程度的数学知识和使用C语言编写串行程序的能力。前导知识要求少，因为我们认为学生应该尽快具备编写并行系统的能力。
　　在旧金山大学，计算机科学专业的学生可以通过学习以本书为教材的课程来达到专业课的要求。“计算机科学导论”是大多数新生在第一个学期学习的课程，本书介绍的课程可以安排为它的后续课程。我们将这门课程作为并行计算的相关课程已经有6年时间。根据我们的经验，学生完全不需要从中、高年级才开始编写并行程序。相反，这门课程十分受欢迎。通过学习这门导论课，学生可以很轻松地将并行性应用于其他课程。
　　第二学期的新生可以通过课堂学习编写并行程序，而带着目的进行学习的计算机专业人员可以自学并行编程。我们希望本书对于他们是有用的资源。
关于本书
　　正如前面所说的，本书的主要目的是：让那些对计算机科学只有有限背景知识、没有并行性经验的读者学习使用MPI、Pthreads和OpenMP进行并行编程。为了让本书使用起来更灵活，我们尽量让那些对API没有兴趣的读者花费较少的时间就能很容易地阅读剩下的部分。因此，针对这三个API的章节是相互独立的：可以按任意顺序阅读它们，甚至可以跳过一两个章节。但是，这种独立性有一定代价：有些内容会在这些章节中重复提到。当然，重复的内容可以简单浏览或者直接跳过。
没有并行计算经验的读者应该先阅读第1章。第1章尝试用相关的非技术性的语言解释为什么并行系统已经在计算机领域中占有重要地位。这一章还为并行系统和并行编程提供了一个简短的介绍。
　　第2章介绍计算机硬件和软件的一些技术背景。在API章节开始之前，许多关于硬件的材料可以先粗略浏览。第3章、第4章、第5章分别介绍使用MPI、Pthreads、OpenMP进行编程。
　　在第6章中，我们开发了两个更长的程序：并行n体问题求解和并行树搜索。这两个程序都使用上述的三个API。第7章提供一个简单的列表，给出并行计算各个方面的补充信息。
　　我们使用C语言来开发程序，因为这三个API都使用C语言接口，同时也因为C语言是相对简单易学的语言，尤其是对于C++和Java程序员来说，他们已经对C的控制结构非常熟悉。
课堂使用
　　本书来源于旧金山大学低年级本科生的课程。这门课满足了计算机科学的专业课要求，同时也是本科生操作系统课程的先修课。本课程唯一的要求是在第一学期的“计算机科学导论”课程中获得B及以上成绩，或在第二学期的“计算机科学导论”课程中获得C及以上成绩。课程的前四个星期介绍C语言编程。由于大部分学生已经编写过Java程序，因此课程主要集中在C语言中如何使用指针上
　　有趣的是，很多学生认为C语言中的指针比MPI编程更困难。 。课程剩下的部分介绍使用MPI、Pthreads、OpenMP编程。
　　上述的大部分内容集中在本书第1章、第3章、第4章、第5章中，并在第2章和第6章中有少量提及。当需求提高时，第2章的背景知识应该介绍。比如，在讨论OpenMP（第5章）缓存一致性问题前，应该先介绍第2章中缓存的知识。
　　本课程的作业包括每周作业、5个编程作业、两次期中考试和一次期末考试。作业中经常涉及编写一个简短的程序或者对现有的程序进行一些小的改进。这些作业的目的是保证学生能够跟上课程，并且根据课堂上的想法得到实际操作经验。这些作业的布置是本课程成功的重要原因。课本中大多数习题与这些简短的作业是相适应的。
　　编程作业中需要编写更大的程序，但我们一般会为学生提供非常多的指导：我们经常在作业中提供伪代码，并在课堂上讨论较难的部分。这些额外的指导是非常有效的：那些需要花费学生大量时间完成的编程作业变得不再难以提交。期中和期末考试的结果，以及讲授操作系统课程的教师的报告都表明，这门课程对于教授学生如何编写并行程序是非常成功的。
　　对于其他高级并行计算课程，本书和它的在线辅助材料可以作为补充，许多关于这三个API语法和语义的信息都可以作为课外阅读资料。本书也可以作为工程方面的课程或者与计算机科学无关但涉及并行计算的课程的补充材料。
辅助材料
　　关于本书的勘误表和一些相关材料，请访问本书出版社的网站（http://www.elsevierdirect.com/），那里还可以下载完整的课件、图表、习题答案和编程作业。所有的用户都可以下载课本中讨论过的较长程序。
　　我们非常感谢读者提出任何发现的错误。如果你发现错误，请发送邮件至peter@usfca.edu。

随着多核处理器和云计算系统的广泛应用，毫无疑问，并行计算不再是计算世界中被束之高阁的偏门领域。并行性已经成为有效利用资源的首要因素。由Peter Pacheco（彼得·帕切克）撰写的这本新教材，对于刚开始学术生涯的学生掌握并行计算的艺术和实践很有帮助。
　　　　Duncan Buell
　　　　南卡罗来纳州大学计算机科学与工程系
　　本书阐述了两个越来越重要的领域：使用Pthreads和OpenMP进行共享内存编程，以及使用MPI进行分布式内存编程的基本方法。更重要的是，通过指出可能出现的性能错误，强调好的编程实践的重要性。这些主题包含在计算机科学、物理学和数学等多个学科中。各章包含了大量不同难易程度的编程习题。对希望学习并行编程技巧、更新知识面的学生或专业人士来说，本书是一本理想的参考书。
　　　　Leigh Little
　　　　纽约州立大学布罗科波特学院计算机科学系
　　本书是一本精心撰写的、全面介绍并行计算的书籍。学生以及相关领域从业人员会从本书的相关最新信息中获益匪浅。Peter Pacheco通俗易懂的写作手法，结合各种有趣的实例，使本书引人入胜。在并行计算这个瞬息万变、不断发展的领域里，本书深入浅出、全面地介绍了并行软件和并行硬件的方方面面。
　　　　Kathy JLiszka
　　　　阿克伦大学计算机科学系
　　并行计算就是未来！ 本书通过实用而有益的例子，介绍了这门复杂的学科。
　　　　Andrew N.Sloss,FBCS
　　　　ARM公司顾问工程师，《ARM System Developers Guide》作者

计算机科学及应用

毫无疑问，随着多核处理器和云计算系统的广泛应用，并行计算不再是计算世界中被束之高阁的偏门领域。并行性已经成为有效利用资源的首要因素，Peter Pacheco撰写的这本新教材对于初学者了解并行计算的艺术和实践很有帮助。
　　　　　　　　　　　　　　 Duncan Buell，南卡罗来纳大学计算机科学与工程系
本书阐述了两个越来越重要的领域：使用Pthreads和OpenMP进行共享内存编程，以及使用MPI进行分布式内存编程。更重要的是，通过指出可能出现的性能错误，强调好的编程实现的重要性。这些主题包含在计算机科学、物理学和数学等多个学科中。各章包含了大量不同难易程度的编程习题。对于希望学习并行编程技巧、更新知识面的学生或专业人士来说，本书是一本理想的参考书。
　　　　　　　　　　 Leigh Little，纽约州立大学布罗科波特学院计算机科学系
本书是一本精心撰写的、全面介绍并行计算的书籍。学生以及相关领域从业人员会从书的相关最新信息中获益匪浅。Peter Pacheco以通俗易懂的写作手法，结合各种有趣的实例，使本书引人入胜。在并行计算这个瞬息万变、不断发展的领域里，本书深入浅出、全面地介绍了并行软件和硬件的方方面面。
　　　　　　　　　　　　　　　　　　Kathy J. Liszka，阿克伦大学计算机科学系
并行计算就是未来！本书通过实用而有益的例子，介绍了这门复杂的学科。
　Andrew N. Sloss ，FBCS，ARM公司顾问工程师，《ARM System Developer's Guide》作者
并行编程已不仅仅是面向专业技术人员的一门学科。如果想要全面开发集群和多核处理器的计算能力，那么学习分布式内存和共享内存的并行编程技术是不可或缺的。本书循序渐进地展示了如何利用MPI、Pthreads 和OpenMP开发高效的并行程序，教给那些对计算机科学只有有限背景知识、没有并行化经验的读者如何开发、调试分布式内存和共享内存的程序，以及对程序进行性能评估。

本书特色
 采用教程形式，从简短的编程实例起步，一步步编写更有挑战性的程序。
 重点介绍分布式内存和共享内存的程序设计、调试和性能评估。
 使用MPI、Pthreads 和OpenMP等编程模型，强调实际动手开发并行程序。

(美）Peter S.Pacheco 著：Peter Pacheco 拥有佛罗里达州立大学数学专业博士学位。曾担任旧金山大学计算机系主任，目前是旧金山大学数学系主任。近20年来，一直为本科和研究生讲授并行计算课程。他的研究方向主要是并行科学计算。他参与了电路仿真的并行软件开发、语音识别、模拟大规模神经元网络等。

邓倩妮 等译：暂无简介

本书在对并行硬件和并行软件进行知识总结之后，着重介绍如何利用MPI、Pthreads和OpenMP开发高效的并行程序。本书的特点在于：
　　1） 文字流畅，易于理解。本书内容通俗易懂，简洁实用。清晰的概念解释，配以丰富的实例和易懂的代码，对帮助初学者理解并行程序设计的基本手段非常重要，可以帮助读者很快掌握设计并行程序的基本方法。
　　2） 循序渐进，由浅及深。本书分别介绍了如何利用MPI、Pthreads和OpenMP进行并行程序设计。每一章都从最基本的实例开始示范，再介绍一些常见问题不同的实现方法，最后分析和比较不同实现方法的性能。这不仅能帮助初学者快速掌握并行编程方法，还能让读者进一步学习开发高效并行程序设计的方法。
　　3） 重实践，重开发。各章包含了详细介绍的编程实例，以及不同难易程度的编程习题。
　　本书不仅适合作为计算机专业并行程序设计的课程教材，对需要通过并行程序设计提高计算性能的其他学科（如物理、机械、生物医药等专业）的技术人员，也可以作为参考手册。
　　本书由上海交通大学邓倩妮副教授主持翻译定稿。此外，冯叶、曾卫、黄鑫、黄叶伟、戴云晶、王强和吕品也参加了本书部分翻译工作，黄鑫还参与了本书的校对工作，对他们的支持和帮助，在此表示衷心的感谢。
　　由于时间和水平有限，翻译中难免存在不准确，敬请读者指正。
译者
2012年6月

出版者的话
译者序
本书赞誉
前言
致谢
第1章为什么要并行计算
11为什么需要不断提升的性能
12为什么需要构建并行系统
13为什么需要编写并行程序
14怎样编写并行程序
15我们将做什么
16并发、并行、分布式
17本书的其余部分
18警告
19字体约定
110小结
111习题
第2章并行硬件和并行软件
21背景知识
211冯·诺依曼结构
212进程、多任务及线程
22对冯·诺依曼模型的改进
221Cache基础知识
222Cache映射
223Cache和程序: 一个实例
224虚拟存储器
225指令级并行
226硬件多线程
23并行硬件
231SIMD系统
232MIMD系统
233互连网络
234Cache一致性
235共享内存与分布式内存
24并行软件
241注意事项
242进程或线程的协调
243共享内存
244分布式内存
245混合系统编程
25输入和输出
26性能
261加速比和效率
262阿姆达尔定律
263可扩展性
264计时
27并行程序设计
28编写和运行并行程序
29假设
210小结
2101串行系统
2102并行硬件
2103并行软件
2104输入和输出
2105性能
2106并行程序设计
2107假设
211习题
第3章用MPI进行分布式内存编程
31预备知识
311编译与执行
312MPI程序
313MPI_Init和MPI_Finalize
314通信子、MPI_Comm_size和MPI_Comm_rank
315SPMD程序
316通信
317MPI_Send
318MPI_Recv
319消息匹配
3110status_p参数
3111MPI_Send和MPI_Recv的语义
3112潜在的陷阱
32用MPI来实现梯形积分法
321梯形积分法
322并行化梯形积分法
33I/O处理
331输出
332输入
34集合通信
341树形结构通信
342MPI_Reduce
343集合通信与点对点通信
344MPI_Allreduce
345广播
346数据分发
347散射
348聚集
349全局聚集
35MPI的派生数据类型
36MPI程序的性能评估
361计时
362结果
363加速比和效率
364可扩展性
37并行排序算法
371简单的串行排序算法
372并行奇偶交换排序
373MPI程序的安全性
374并行奇偶交换排序算法的重要内容
38小结
39习题
310编程作业
第4章用Pthreads进行共享内存编程
41进程、线程和Pthreads
42“Hello，World”程序
421执行
422准备工作
423启动线程
424运行线程
425停止线程
426错误检查
427启动线程的其他方法
43矩阵-向量乘法
44临界区
45忙等待
46互斥量
47生产者-消费者同步和信号量
48路障和条件变量
481忙等待和互斥量
482信号量
483条件变量
484Pthreads路障
49读写锁
491链表函数
492多线程链表
493Pthreads读写锁
494不同实现方案的性能
495实现读写锁
410缓存、缓存一致性和伪共享
411线程安全性
412小结
413习题
414编程作业
第5章用OpenMP进行共享内存编程
51预备知识
511编译和运行OpenMP程序
512程序
513错误检查
52梯形积分法
53变量的作用域
54归约子句
55parallel for指令
551警告
552数据依赖性
553寻找循环依赖
554π值估计
555关于作用域的更多问题
56更多关于OpenMP的循环：排序
561冒泡排序
562奇偶变换排序
57循环调度
571schedule子句
572static调度类型
573dynamic和guided调度类型
574runtime调度类型
575调度选择
58生产者和消费者问题
581队列
582消息传递
583发送消息
584接收消息
585终止检测
586启动
587atomic指令
588临界区和锁
589在消息传递程序中使用锁
5810critical指令、atomic指令、锁的比较
5811经验
59缓存、缓存一致性、伪共享
510线程安全性
511小结
512习题
513编程作业
第6章并行程序开发
61n体问题的两种解决方法
611问题
612两个串行程序
613并行化n体算法
614关于I/O
615用OpenMP并行化基本算法
616用OpenMP并行化简化算法
617评估OpenMP程序
618用Pthreads并行化算法
619用MPI并行化基本算法
6110用MPI并行化简化算法
6111MPI程序的性能
62树形搜索
621递归的深度优先搜索
622非递归的深度优先搜索
623串行实现所用的数据结构
624串行实现的性能
625树形搜索的并行化
626采用Pthreads实现的静态并行化树搜索
627采用Pthreads实现的动态并行化树搜索
628Pthreads树搜索程序的评估
629采用OpenMp实现的并行化树搜索程序
6210OpenMp实现的性能
6211采用MPI和静态划分来实现树搜索
6212采用MPI和动态划分来实现树搜索
63忠告
64选择哪个API
65小结
651Pthreads和OpenMP
652MPI
66习题
67编程作业
第7章接下来的学习方向
参考文献
索引