本教材的编写和出版得到了美国国家科学基金会的大力支持，并经过美国许多大学的授课检验。本书覆盖并行程序设计的众多技术，将重点放在使用免费获得的并行软件工具在联网计算机上执行的并行程序上，所涉及的应用是独立于系统的。从顺序程序设计开始进行自然扩充，介绍并行程序设计技术。拓展了消息传递并行程序设计的基本技术，并探究了在数值和非数值领域特定问题的算法。学习本书并不需要并行程序设计的任何预备知识，读者只需具有C程序设计知识。
本书特点
● 使用MPI伪代码描述算法，有助于在不同的程序设计工具上实现。
● 详细介绍共享存储器程序设计，包括Pthread和OpenMP，辅助学生完成共享存储器程序设计的课外作业。
● 每章末尾包含大量习题，其中“现实生活习题”非常有趣，既可增强学习兴趣又能提高并行程序设计技巧，并且这些习题的求解无需专门的数学知识。
● 配合一个综合的教师指导网站，其中包括：实例、课外作业以及使用MPI软件的辅导材料等，网址为：www.cs.uncc.edu/par_prog。
无
本教科书的目的是介绍并行程序设计技术。并行程序设计使用多计算机或多个内部处理器的计算机来求解问题，它比使用单台计算机的计算速度要快得多。它也为求解更大规模的问题提供了机会，这些问题需要更多的计算步或更大存储容量需求，之所以能满足后一要求, 是因为多计算机和多处理机系统通常比单计算机有更大的总存储容量。在本书中，我们讨论的重点是使用多计算机进行并行程序设计，它们之间的通信是通过发送消息来完成的，从而出现了消息传递并行程序设计的术语。我们所使用的计算机可以是不同的类型（PC、SUN、SGI等），但它们必须由网络进行互联，此外还必须有一个软件环境以在计算机间进行消息传递。适当联网的计算机（或者在网络中或者具有互联的能力的计算机）可广泛地作为学生的基本计算平台，以便避免使用特殊设计的多处理机系统。为实现消息传递并行程序设计，可使用几种软件工具，特别是几个MPI的实现方案，它们均可免费得到。这些软件也可在特殊设计的多处理机系统上使用，如果这些系统可以使用的话。我们所讨论的技术和应用是独立于系统的，因本书非常实用。
第2版 自从本书第1版出版后，使用互联的计算机作为高性能计算平台已很普遍，并用术语“机群计算”来描述这类计算。通常在机群中使用的计算机是“商品”计算机，即在家庭和办公室中使用的低价个人计算机。虽然本教科书的重点在于使用多计算机和多处理机作为高性能计算这一宗旨没有改变，但我们对第1章做了修订以反映这种商品机群的趋势，并远离专门设计的、自含的多处理机。在第1版中，我们叙述了PVM 和MPI，并为它们各提供了一个附录，但是一般在课堂上只使用其中一个。在第2版中，我们从教科书中删去了有关PVM的详尽细节，因为现在的MPI是一个被广泛接受的标准，并提供了更为强大的机制。如果读者愿意，仍可使用PVM，我们在网页中仍提供对它的支持。
消息传递程序设计有某些缺点，特别是要求程序员显式地说明消息传递应在程序的何处、何时出现以及要发送什么。数据不得不通过相当慢的消息发送给需要该数据的计算机。有些学者将这种类型的程序设计比作汇编语言的程序设计，即使用计算机内部语言编程，这是一种非常低级和麻烦的程序设计方法，除非在非常特殊的情况下，一般不采用这种方法来编程。另一种程序设计模型是共享存储器模型。 在第1版中，共享存储器程序设计适用于具有多个内部处理器和一个公共共享存储器的计算机。这种共享存储器多处理机现在已变得非常经济有效和普遍，特别是双处理器和四处理器系统。线程的程序设计是用Pthread描述的。在第2版中，保留了共享存储器的程序设计，并增加了许多新的内容，包括共享存储器的编程性能和OpenMP，OpenMP是比Pthread有更高层次的、基于线程的共享存储器程序设计的标准。任何实践并行程序设计的宽范围的课程将包括共享存储器的程序设计，因而具有OpenMP程序设计经验是非常合意的。在新的附录中，增加了OpenMP。对教育机构来讲，只需用低廉的价格就可获得OpenMP编译器。
使用机群是重点，因此增加了有关在机群上进行共享存储器程序设计的新的一章。使用合适的分布式共享存储器（DSM）软件就可在机群上实现共享存储器模型。分布式共享存储器程序设计试图获得机群可扩展性的优点和共享存储器的长处。提供DSM环境的软件可免费得到，而我们将展示学生能编写他们自己的DSM系统（已经有若干学生做到了这一点）。应该指出的是DSM系统存在一些性能方面的问题。不能期待软件DSM的性能会如同在一个共享存储器多处理机上真正的共享存储器程序设计那样好。但一个大型的、可扩展的共享存储器多处理机比起商品机群来要昂贵得多。
第2版中的其他变化是有关机群程序设计的。在第6章中增加了部分同步计算的内容，这在机群中是特别重要的，因为在机群中同步很花时间，因此应尽量避免。我们对第10章的排序算法内容作了修订和补充，包括适用于机群的其他排序算法。我们还在本书的第一部分增加了对算法的分析，包括计算/通信比，因为这对消息传递计算非常重要。此外，还增加了一些习题。为保持合理的篇幅，在附录中删去了并行计算模型。
曾将本教科书的第1版定位为主要用作大学本科生的并行程序设计课程的教科书。但我们发现某些单位也将它作为研究生课程的教科书。我们也已将它既作为高年级本科的也作为研究生课程的教科书，本书适合作为研究生的初级课程。作为研究生的课程，应包括更先进的内容，例如DSM的实现和快速傅里叶变换，并选择有更高要求的程序设计研究作业。
内容编排 如第1版一样，本教科书分为两部分。第一部分现在包括第1章到第9章，而第二部分现在包括第10章到第13章。在第一部分中，将讨论并行程序设计的基本技术。在第1章中，对并行计算机的概念现在更注重机群的介绍。第2章概述消息传递例程，特别是MPI软件。从理论和实践两方面讨论如何评估消息传递程序的性能。第3章叙述理想的并行化问题，即易并行计算，在这种计算中，问题可被分割成独立部分。事实上，许多重要应用都可以这种方式加以并行化。第4、5、6、7各章叙述了各种程序设计策略（分割和分治、流水线、同步计算、异步计算和负载平衡）。第一部分的这几章涉及了并行程序设计的所有基本内容，并通过对消息传递和对简单问题的求解来示范技术，而这些技术的本身可在许多场合用来求解问题。通常我们首先给出顺序的示范代码，然后再给出并行的伪代码。一般来讲，基本算法在本质上是并行的，而顺序版本“不自然”地使用循环将其串行化。当然，某些算法为了高效地进行并行求解必须进行重构，但这种重构并不是立即就能看清的。第8章叙述了共享存储器程序设计，其中包括了广泛采用的IEEE标准系统Pthread以及OpenMP。在该章中，还增加了有关定时和性能问题的全新的一节内容。新增的一章是有关分布式共享存储器程序设计的，它被放在共享存储器这一章之后，以此结束第一部分，在此之后的各章已重新编号。
许多并行计算问题具有一些专门开发的算法，在第二部分中所研究的专用算法涉及非数值和数值范畴。在学习第二部分时，将需要一些数学概念，如矩阵。在第二部分中涉及的主题包括排序（第10章），数值算法、矩阵乘法、线性方程组、偏微分方程（第11章），图像处理（第12章）以及搜索和优化（第13章）。图像处理特别适合于并行化，因此在第二部分中将其作为饶有兴趣的一个应用，专门用一章加以介绍，这种应用对许多研究项目有很大的潜在参考价值。在图像处理这一章中，还讨论了所涉及的快速傅里叶变换，这一重要变换还被用于许多其他领域中，包括信号处理和语音识别。
在每章的末尾列出了许多“现实生活”习题，其中绝大部分源自实际生活。这些习题的求解无需专门的数学知识，它是本书的特色之一；这些习题有助于开发使用并行程序设计技术的技巧，而不是简单地学习如何去求解像数的排序或矩阵相乘那样的专门问题。
预备知识 学习第一部分所需的准备是有关顺序程序设计的知识，这可通过使用C语言学到。教科书中的并行伪代码是用类似C的赋值语句和控制流语句编写的。但是，如果学生只有Java知识应不难理解伪代码，因为这些语句的语法与Java是类似的。在掌握了基本的顺序程序设计后可立即进行第一部分的学习。在第一部分中的许多作业无需专门的数学知识就可尝试求解。如果作业需使用MPI，则可用具有MPI消息传递库调用的C或C++语言来编写程序。在附录A中，对如何进行具体的库调用做了说明。也可以使用Java，虽然学生只具有Java知识，他们应没有任何困难用C/C++来完成程序设计作业。
在第二部分中，学习排序这一章时，假定学生已在学习数据结构或顺序程序设计课程时掌握了顺序排序的知识。学数值算法这一章时，学生应具有相应的数学背景，这些背景是高年级计算机科学或工程系的学生应该掌握的。
课程结构 教师可灵活地介绍本书的内容，没有必要包括所有内容。事实上，用一个学期是不可能讲完整本书的内容的。宜从第一部分中选择一部分主题作为一般顺序程序设计课程的补充。我们以这种方式指导一年级学生进行并行程序设计。在这种环境下，本书便是对顺序程序设计教科书的补充。整个第一部分及第二部分的一部分合在一起，可作为高年级本科生或研究生初期的并行程序设计/计算课程，我们以这种方式使用本书。
主页 为本书已开发了Web网站以帮助学生和教师。网址为www.cs.uncc.edu/par_prog。在该网站中还有许多Web页面帮助学生学习如何对并行程序进行编译和运行，网站上还提供了一些示范程序，作为简单的初期作业以检查软件环境。在准备本书第2版时，对整个网站做了重新设计，包括使用导航按钮对学生进行逐步指导，还提供了DSM程序设计的细节。对指导教师提供了新的教师手册，并给出了MPI的解答。最初的解答手册包含PVM的解答，仍可使用。可从作者处得到电子版的解答手册。从主页上还可得到大量的幻灯片。
致谢 本教科书的第1版是美国国家科学基金会资助作者在北卡罗来纳大学夏洛特分校的向一年级学生介绍并行程序设计的直接结果。 没有当时的国家科学基金会计划主任、已故的M.Mulder博士的支持，我们不可能去追求在教科书中所提及的那些想法。许多研究生参加了这一独创的研究项目。Uday Kamath先生创作了最初的习题解答手册。
我们要向部门的系统管理员James Robinson致谢，他建成了我们本地的工作站机群，如果没有该机群我们不可能完成这一著作。我们还要感谢UNC（北卡罗来纳大学）夏洛特分校的许多学生，多年来他们选了我们的课程并帮助我们改进了教材。其中包括了“远程课程”，在这些课程中，本书第1版的材料成为以独特方式实验的课堂。这些远程课程除了在UNC夏洛特分校外，还向几所北卡罗来纳大学得到了普及，其中包括北卡罗来纳大学阿什维尔分校、北卡罗来纳大学格林斯伯勒分校、北卡罗来纳大学威尔明顿分校和北卡罗来纳州立大学。北卡罗来纳州立大学的Mladen Vouk教授除了以客座专家身份授课外，还设计了一个给人印象深刻的Web页面，其中包括了我们讲课的“实况录音”和“自动翻页”的幻灯片。（这些授课情况可通过链接我们的主页看到。）杜克大学的John Board教授以及北卡罗来纳大学查珀尔希尔分校的Jan Prins教授也欣然做了客座专家的讲演，承蒙Raul Gallard教授的友好邀请，我们还在阿根廷的圣路易斯国立大学讲授了基于本书素材的并行程序设计课程。
是国家科学基金会继续支持我们对机群计算的研究工作使我们得以撰写本书的第2版。一项国家科学基金会的资助项目鼓励我们开发分布式共享存储器的工具和教学素材。 本书第9章分布式共享存储器程序设计叙述了这一研究工作。此后，国家科学基金会又资助我们一个项目，于2001年7月在UNC夏洛特分校组织一个三天的有关机群计算教学的专题学术讨论会， 这使我们进一步地精练了本书的素材。我们要向国家科学基金会计划主任Andrew Bernat博士对我们的继续支持表示感谢。是他提议在夏洛特分校举行机群计算的专题学术讨论会。参加这次专题学术讨论会的共有来自美国各地的18位教学人员。它导致了另一个三天的、于2001年12月在印度阿哈玛德巴德的Gujarat大学举行的有关机群计算教学的专题学术讨论会，这一次是受IEEE机群计算特别工作组（Task Force on Cluster Computing，TFCC）及印度IEEE计算机学会的邀请。这次专题学术讨论会约有40位教学人员参加。我们要衷心感谢潜心于该专题学术讨论会的人们，特别是Rajkumar Buyya先生，IEEE机群计算特别工作组的主席，是他提议召开这次专题学术讨论会。我们也非常感谢Prentice Hall出版社为每位出席代表免费提供了本教科书。
我们仍继续与在UNC夏洛特分校的和在别处的（包括波士顿的马萨诸塞大学，在休假离校时）学生一起检测本书素材。在编写第2版时，好几位UNC夏洛特分校的本科生与我们一起从事该项目。第2版的新Web页面是由Omar Lahbabi开发的，并由 Sari Ansari进一步改进，两位都是本科生。MPI的解答手册是由Thad Drum和Gabriel Medin完成的，他们两位也是UNC夏洛特分校的本科生。
我们特别感谢Prentice Hall出版社高级组稿编辑Petra Rector，他在出版本书第2版的整个过程中给予了我们支持。评阅人对我们提供了非常有用的指点，特别是一位匿名评阅人，是他直言不讳的评论使我们重审本书的许多方面，无疑地改进了本书的素材。
最后，我们要感谢许多与本书第1版有关的人们，他们向我们提供了修正和建议。我们保留了一份在线勘误表，这在本书再版时将非常有用。已在第2版中对所有在第1版中发现的错误做了修正。也将为第2版保留一份在线勘误表，它与我们的主页相连。我们将永远欢迎对本书进行评论和提供修改意见。请将你们的评论和修改意见通过下列电子邮件地址发给我们：wilkinson @ email.wcu.edu (Barry Wilkinson)或cma@uncc.edu ( Michael Allen)。
Barry Wilkinson
西卡罗来纳大学
Michael Allen
北卡罗来纳大学, 夏洛特分校
Barry Wilkinson, Michael Allen：Barry Wilkinson: 是北卡罗来纳大学夏洛特分校计算机科学系教授，并在西卡罗来纳大学任教。在此之前他曾在英格兰布赖顿大学（1984～1987）、纽约州立大学纽珀尔兹学院（1983～1984）、威尔士加的夫大学学院（1976～1983）以及英格兰阿斯顿大学（1973～1976）任职。从1969到1970年，他曾在Ferranti有限公司从事过程控制计算机系统的工作。他是《Computer Peripherals》（与D. Horrocks、Hodder和Stoughton合作,1980, 第2版1987年）、《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的资深会员，并在2001年由于从事IEEE机群计算特别工作组（TFCC）的教育计划工作而荣获IEEE计算机科学学会的感谢证书。
Michael Allen: 是北卡罗来纳大学夏洛特分校计算机科学系教授。在此之前他曾是北卡罗来纳大学夏洛特分校电气工程系的副教授和教授（1974～1985），并曾是纽约州立大学布法罗分校的讲师和助理教授（1968～1974）。在1985到1987年他离开了北卡罗来纳大学夏洛特分校，在DataSpan公司任董事长和主席。他还曾经在Eastman Kodak、Sylvania Electronics、宾夕法尼亚州的Bell、Wachovia Bank以及许多其他公司中从事电子设计和软件系统开发工作。他于1964年和1965年分别在卡内基-梅隆大学获得电气工程的学士和硕士学位，并于1968年在纽约州立大学布法罗分校获得博士学位。
陆鑫达 等：陆鑫达: 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计算）、网络计算及其编程环境，机群计算（包括体系结构及中间件）、遗传和进化算法在映射和调度中的应用，分布计算及移动计算，智能代理等。
自本书第1版出版以来，联网计算机，特别是以消息传递为基础的联网机群的程序设计技术有了长足的进步，机群计算技术已成为经济有效地获取高性能计算能力的主流技术，相应的MPI程序设计环境也已逐步成为主流的消息传递程序设计环境，而PVM程序设计环境则逐渐淡出。
共享存储器程序设计在经历了较长时间的发展后也终于有了像OpenMP那样为各界共同接受的共享存储器程序设计标准，它在以SMP作为基本结点的高性能并行机系统的并行程序设计中起着关键的作用。将消息传递程序设计和共享存储器程序设计两者有机结合的分布式共享存储器程序设计将是未来机群程序设计的发展方向。本书第2版的内容变动正是对这些发展趋势的及时反映。
长期以来，计算机体系结构课程缺少相应的实验素材，第2版新增了机群计算和使用计算机机群的内容，对如何打造专用和通用的计算机机群以及设置相应的程序设计环境做了较为详尽的介绍，译者相信这将为开设网络环境下的计算机体系结构实验课程打下良好的基础。
本书第1版的翻译工作由陆鑫达教授负责和组织，并翻译了目录、序、第1～3章，以及第11和12章，曾志勇翻译了第5章，张建翻译了第7章，支小莉翻译了第6章，徐蔚文翻译了第10章，钟嵘翻译了第8章，吴欣翻译了第9章，汤勇平翻译了第4章。译稿全文由陆鑫达教授作了校对。
第2版的翻译和审校由陆鑫达教授负责，翻译了新增的内容（1.2节提高计算速度的潜力，1.4节机群计算，2.2节使用计算机机群，6.4节部分同步方法，8.4节并行程序设计语言和构造，8.5节OpenMP，8.6节性能问题，第9章分布式共享存储器系统及其程序设计，10.3节在专用网络上排序，10.4节其他排序算法，以及附录C—OpenMP命令、库函数以及环境变量及各章新增的习题等），重译了各章中改写的内容，并仔细校对了删除的内容。
本书是有关使用联网计算机进行并行计算的一本很实用的教科书，是两位教授多年教学和科研工作的结晶。作者用此教材引导美国大学一年级学生进行并行程序设计实践，具有超前意识，为此获得美国国家科学基金会的资助，使此书得以出版。我们翻译此书的宗旨是想促使并行/分布计算，特别是使用联网计算机的并行/分布计算，在中国的普及和发展，尤其是在高等院校中的普及和发展。
本书除介绍了常用的一些算法范例，包括分治、流水、同步计算、主从及工作池等，还介绍了一些常用的经典数值和非数值算法，如排序、矩阵相乘、线性方程组求解、图像处理中的预处理和相应的变换、搜索和优化（包括遗传算法）等，这是本书的一大特色。读者掌握了这些算法范例和经典算法后就可为并行程序设计打下良好基础。书中每一章后面均附有习题，除与每章内容有关的习题之外，还有不少习题源自现实生活，既富有启发性，又具有趣味性，应该说这是本书的另一大特色。学习本书的唯一要求是具有C语言的程序设计知识，对并行程序设计知识没有要求。对算法的描述采用MPI伪代码，并允许使用不同的程序设计工具加以实现。
本书可作为计算机专业本科生高年级选修课程的教材，也可作为研究生的学位或非学位课程的教材，对在其他各个专业领域中从事高性能计算的科技工作者也是一本很有价值的参考书。
值本书第2版出版之际，译者谨向机械工业出版社华章分社的策划和编辑人员表示深切的谢意。
由于翻译时间较仓促，再加有的英语术语国内没有统一的译法，故翻译中的错误或不妥之处在所难免，敬请读者不吝指正。
第一部分 基本技术
第1章 并行计算机 2
1.1 对计算速度的需求 2
1.2 提高计算速度的潜力 4
1.2.1 加速系数 4
1.2.2 什么是最大的加速比 5
1.2.3 消息传递计算 9
1.3 并行计算机的类型 9
1.3.1 共享存储器多处理机系统 10
1.3.2 消息传递多计算机 11
1.3.3 分布式共享存储器 17
1.3.4 MIMD和SIMD的分类 17
1.4 机群计算 18
1.4.1 以互联计算机作为计算平台 18
1.4.2 机群的配置 23
1.4.3 打造“Beowulf风格”的专用机群 26
1.5 小结 27
推荐读物 27
参考文献 28
习题 30
第2章 消息传递计算 31
2.1 消息传递程序设计基础 31
2.1.1 编程的选择 31
2.1.2 进程的创建 31
2.1.3 消息传递例程 33
2.2 使用计算机机群 37
2.2.1 软件工具 37
2.2.2 MPI 37
2.2.3 伪代码构造 44
2.3 并行程序的评估 45
2.3.1 并行执行时间方程式 45
2.3.2 时间复杂性 48
2.3.3 对渐近分析的评注 50
2.3.4 广播/集中的通信时间 50
2.4 用经验方法进行并行程序的调试和评估 51
2.4.1 低层调试 52
2.4.2 可视化工具 52
2.4.3 调试策略 53
2.4.4 评估程序 53
2.4.5 对优化并行代码的评注 55
2.5 小结 55
推荐读物 55
参考文献 56
习题 57
第3章 易并行计算 59
3.1 理想的并行计算 59
3.2 易并行计算举例 60
3.2.1 图像的几何转换 60
3.2.2 曼德勃罗特集 64
3.2.3 蒙特卡罗法 69
3.3 小结 73
推荐读物 73
参考文献 73
习题 74
第4章 划分和分治策略 79
4.1 划分 79
4.1.1 划分策略 79
4.1.2 分治 82
4.1.3 M路分治 86
4.2 分治技术举例 87
4.2.1 使用桶排序法排序 87
4.2.2 数值积分 91
4.2.3 N体问题 93
4.3 小结 96
推荐读物 97
参考文献 97
习题 98
第5章 流水线计算 104
5.1 流水线技术 104
5.2 流水线应用的计算平台 107
5.3 流水线程序举例 107
5.3.1 数字相加 108
5.3.2 数的排序 110
5.3.3 生成质数 112
5.3.4 线性方程组求解—特殊个例 114
5.4 小结 117
推荐读物 117
参考文献 117
习题 117
第6章 同步计算 122
6.1 同步 122
6.1.1 障栅 122
6.1.2 计数器实现 123
6.1.3 树实现 124
6.1.4 蝶形障栅 125
6.1.5 局部同步 126
6.1.6 死锁 126
6.2 同步计算 127
6.2.1 数据并行计算 127
6.2.2 同步迭代 129
6.3 同步迭代程序举例 130
6.3.1 用迭代法解线性方程组 130
6.3.2 热分布问题 135
6.3.3 细胞自动机 142
6.4 部分同步方法 143
6.5 小结 144
推荐读物 144
参考文献 144
习题 145
第7章 负载平衡与终止检测 151
7.1 负载平衡 151
7.2 动态负载平衡 152
7.2.1 集中式动态负载平衡 152
7.2.2 分散式动态负载平衡 153
7.2.3 使用线形结构的负载平衡 155
7.3 分布式终止检测算法 157
7.3.1 终止条件 157
7.3.2 使用确认消息实现终止 158
7.3.3 环形终止算法 158
7.3.4 固定能量分布式终止算法 160
7.4 程序举例 160
7.4.1 最短路径问题 160
7.4.2 图的表示 161
7.4.3 图的搜索 162
7.5 小结 166
推荐读物 166
参考文献 167
习题 168
第8章 共享存储器程序设计 172
8.1 共享存储器多处理机 172
8.2 说明并行性的构造 173
8.2.1 创建并发进程 173
8.2.2 线程 175
8.3 共享数据 178
8.3.1 创建共享数据 179
8.3.2 访问共享数据 179
8.4 并行程序设计语言和构造 185
8.4.1 并行语言 185
8.4.2 并行语言构造 186
8.4.3 相关性分析 187
8.5 OpenMP 189
8.6 性能问题 193
8.6.1 共享数据的访问 193
8.6.2 共享存储器的同步 195
8.6.3 顺序一致性 196
8.7 程序举例 199
8.7.1 使用UNIX进程的举例 199
8.7.2 使用Pthread的举例 201
8.7.3 使用Java的举例 203
8.8 小结 204
推荐读物 205
参考文献 205
习题 206
第9章 分布式共享存储器系统及其程序设计 211
9.1 分布式共享存储器 211
9.2 分布式共享存储器的实现 212
9.2.1 软件DSM系统 212
9.2.2 DSM系统的硬件实现 213
9.2.3 对共享数据的管理 214
9.2.4 基于页面系统的多阅读器/单写入器策略 214
9.3 在DSM系统中实现一致性存储器 214
9.4 分布式共享存储器的程序设计原语 216
9.4.1 进程的创建 216
9.4.2 共享数据的创建 216
9.4.3 共享数据的访问 217
9.4.4 同步访问 217
9.4.5 改进性能的要点 217
9.5 分布式共享存储器的程序设计 219
9.6 实现一个简易的DSM系统 219
9.6.1 使用类和方法作为用户接口 220
9.6.2 基本的共享变量实现 220
9.6.3 数据组的重叠 222
9.7 小结 224
推荐读物 224
参考文献 224
习题 225
第二部分 算法和应用
第10章 排序算法 230
10.1 概述 230
10.1.1 排序 230
10.1.2 可能的加速比 230
10.2 比较和交换排序算法 231
10.2.1 比较和交换 231
10.2.2 冒泡排序与奇偶互换排序 233
10.2.3 归并排序 236
10.2.4 快速排序 237
10.2.5 奇偶归并排序 239
10.2.6 双调谐归并排序 240
10.3 在专用网络上排序 243
10.3.1 二维排序 243
10.3.2 在超立方体上进行快速排序 244
10.4 其他排序算法 247
10.4.1 秩排序 248
10.4.2 计数排序 249
10.4.3 基数排序 250
10.4.4 采样排序 252
10.4.5 在机群上实现排序算法 253
10.5 小结 253
推荐读物 254
参考文献 254
习题 255
第11章 数值算法 258
11.1 矩阵回顾 258
11.1.1 矩阵相加 258
11.1.2 矩阵相乘 258
11.1.3 矩阵-向量相乘 259
11.1.4 矩阵与线性方程组的关系 259
11.2 矩阵乘法的实现 259
11.2.1 算法 259
11.2.2 直接实现 260
11.2.3 递归实现 262
11.2.4 网格实现 263
11.2.5 其他矩阵相乘方法 266
11.3 求解线性方程组 266
11.3.1 线性方程组 266
11.3.2 高斯消去法 266
11.3.3 并行实现 267
11.4 迭代方法 269
11.4.1 雅可比迭代 269
11.4.2 快速收敛方法 272
11.5 小结 274
推荐读物 275
参考文献 275
习题 276
第12章 图像处理 279
12.1 低层图像处理 279
12.2 点处理 280
12.3 直方图 281
12.4 平滑、锐化和噪声消减 281
12.4.1 平均值 281
12.4.2 中值 283
12.4.3 加权掩码 284
12.5 边缘检测 285
12.5.1 梯度和幅度 285
12.5.2 边缘检测掩码 286
12.6 霍夫变换 288
12.7 向频域的变换 290
12.7.1 傅里叶级数 291
12.7.2 傅里叶变换 291
12.7.3 图像处理中的傅里叶变换 292
12.7.4 离散傅里叶变换算法的并行化 294
12.7.5 快速傅里叶变换 296
12.8 小结 300
推荐读物 300
参考文献 300
习题 302
第13章 搜索和优化 305
13.1 应用和技术 305
13.2 分支限界搜索 306
13.2.1 顺序分支限界 306
13.2.2 并行分支限界 307
13.3 遗传算法 308
13.3.1 进化算法和遗传算法 308
13.3.2 顺序遗传算法 310
13.3.3 初始种群 310
13.3.4 选择过程 312
13.3.5 后代的生成 312
13.3.6 变异 314
13.3.7 终止条件 314
13.3.8 并行遗传算法 314
13.4 连续求精 317
13.5 爬山法（hill climbing） 318
13.5.1 银行业务应用问题 319
13.5.2 爬山法在金融业务中的应用 320
13.5.3 并行化 321
13.6 小结 321
推荐读物 321
参考文献 322
习题 323
附录A 基本的MPI例程 329
附录B 基本的Pthread例程 335
附录C OpenMP命令、库函数以及
环境变量 339
索引 347
