本书内容新颖，涉及现代并行硬件和软件技术，包括多核体系结构及其并行程序设计技术。本书侧重论述并行程序设计的原理，并论述了并行程序设计中一些深层次问题，如可扩展性、可移植性以及并行程序设计应遵循的方法学等。
并行程序设计原理
Principles of Parallel
Programming
(美) Calvin Lin得克萨斯大学奥斯汀分校 Lawrence Snyder华盛顿大学西雅图分校 著 陆鑫达 林新华 译
多核体系结构的出现使得并行程序设计技术对软件工程师和计算机系统设计师变得日益重要。本书着重论述并行计算的基本原理，解释各种现象，并分析为何这些现象是成功进行并行程序设计的机遇或阻碍。
本书是高等院校计算机专业高年级本科生或低年级研究生的理想教科书，同时也是专业程序员从事并行程序设计的理想入门书。
本书特色
以原理第一的原则重点阐述并行计算的基本原理，而不是指导读者“如何”去管理当前商品化的并行计算机。
以原理为背景讨论流行的程序设计语言并论述当代并行计算机编程所使用的工具。
使用注释框对书中所提及的内容进行饶有兴趣的扩展。
使用定义框对书中关键词和概念进行定义。
每章附有习题，便于读者掌握所论述的概念。
第10章着重论述可能影响该研究领域未来的当前进展。
第11章为读者构造实际的并行程序提供第一手的实践经验。
对于那些因多核芯片出现而激发起学习并行程序热情的读者来说，你找对了地方。本书
是为并行计算机无处不在的这个世界而编写的，这种并行计算机涉及广泛，从具有两核芯片
的膝上计算机，到超级计算机，再到用于搜索因特网的巨大数据中心机群。
本书侧重可扩展并行，即并行程序具有在任何数目处理器上运行良好的能力。这一概念
是非常关键的，原因有二：（1）创建可扩展并行计算所需的大多数技术与在多核芯片上生成
高效求解的技术是相同的；（2）目前的多核芯片具有适中数目的处理器，通常是2～8个，在
未来几年内每个芯片上的核数肯定会急剧增加，这就使得可扩展并行概念与之直接相关。因
而，尽管今天的多核芯片为核间低时延通信提供了机遇，但这种特性很可能只能在短期内得
益，因为当芯片上的核数增长时，芯片内不同部分的片内延迟将明显增加。所以，我们不会
侧重开发这种短期得益的方法，而是侧重那些能在现在和将来都能很好工作的方法。当然，
多核芯片还面临着自身的挑战，特别是它们有限的片外存储器带宽，以及有限的片上总的
cache容量。本书也将讨论这些问题。
首先，我们讨论构成实用和高效并行程序的原理。为了获取如程序设计那样复杂的能力，
学习原理是至关重要的。当然，对于并行程序设计来讲，原理也许更加重要，因为最新技术
水平的变化很快。如果训练过于紧密地捆绑于某个特定的计算机系统或一种语言，将不具有
跟上技术发展步伐的支撑力。可是原理（应用于任何并行计算系统的概念以及开发这些特征
的观念）对人们深入理解和掌握相关知识将提供深远的影响。
但我们并不会止步于对抽象概念的讨论，还会将那些原理应用到日常的计算中，这将使
本书非常实用。我们将介绍几个并行程序设计系统，还将描述在程序设计系统中如何应用这
些原理。我们期望读者在读完本书后能编写并行程序。在最后一章我们将专门讨论并行程序
设计技术，以及介绍如何开发一个有关并行程序设计的结课课程设计，这个设计可能需要历
时一个学期。
读者对象
读者对象可以是任何人，大学生或专业人员，只要他能用C或类似语言成功进行编程，以
及自认为是程序员的人。如果具有计算机执行顺序程序的概念，包括取指/执行周期以及高速
缓存基础的知识，则就更易理解本书的内容。本书最初的定位是计算机科学专业的高年级学
生以及具有计算机科学学士学位的一年级研究生，现在本书仍然适合这一程度。然而，作为
本书的宗旨，我们减少了对预备知识的要求，而强调对知识的传授，如果读者已经掌握某些
解释所涉及的知识，只需跳过这些知识。
本书结构
因为并行程序设计并不是读者所熟悉的顺序程序设计的直接扩展，所以我们将本书分为
四部分：
基础：第1～3章
并行抽象：第4～5章
并行程序设计语言：第6～9章
展望：第10～11章
为使读者能明智地从中选择感兴趣的部分，我们下面说明各部分的目的和内容。
基础在第1章中，我们通过实现一个计算说明并行程序员必须处理的许多问题是多么困
难，而在为顺序计算机编写同样的程序时则非常简单。该例子将我们的注意力集中到一些贯
穿于全书与我们相关的论题, 但它也强调了解并行计算机是如何操作的重要性。第2章介绍5种
不同类型的并行计算机，描述了其体系结构中的少量细节，以及它们扩展到更大规模的能力。
在这一章中得出了两个关键的结论：第一，不像顺序计算，并行计算机没有一个标准的体系
结构。第二，为了能适应这种体系结构的多样性，我们需要一个抽象的机器模型以指导我们
的程序设计。我们给出了一个抽象模型。在留意体系结构的基础上，第3章的内容涉及并发性
（包括线程和进程）、时延、带宽、加速比等基本概念，侧重叙述与性能相关的问题。第一部
分这些基础内容为第二部分讲解算法和抽象做好了准备。
并行抽象为支持并行算法的设计和讨论，第4章为编写独立于语言的并行程序引入了一
个非正式的伪代码符号。该符号具有跨各种程序设计模型和方法的许多特性，允许我们在讨
论算法时不会偏向任何具体的语言或机器。为了引导读者考虑并行算法，第5章介绍了一系列
的基本算法技术。在阅读完第二部分后，读者将掌握以并行方式求解问题的方法，从而可使
我们进入最后一个问题，即以一个具体的并行程序设计语言来编码算法。
并行程序设计语言还没有一种并行程序设计语言，能够如C或Java在顺序程序设计中所
起的作用那样，为大家所熟知和接受，并作为编码算法的基本手段。为此，第三部分介绍了
三种并行程序设计语言：基于线程的语言（第6章），消息传递语言（第7章）和高级语言（第
8章）。我们所论及的每种语言的内容，足以使读者能编写小的练习；但编写重大的问题将需
要更完整的语言介绍，这可通过在线资源获得。除了介绍一种语言，每一章还包含一个有关
语言的简短综述，这些语言在并行程序设计社团中有一批追随者。第9章简单地比较和对比了
所有已论述的语言，指明它们的优缺点。能通读这三章最好，但是我们知道许多读者将只会
定格在一种方法上，因此这三章是相互独立的。
展望第四部分是展望未来。第10章涉及一系列新的、有前途的并行技术，它们无疑将
影响未来的研究和实践。我们的观点是，这些技术还未为它们的“全盛时期做好准备”，但它
们是重要的，且值得我们去熟悉它们，即使在它们还未被完全部署之前。最后，第11章侧重
论述并行机程序设计的第一手实践技术。该章的前两节应在研究并行程序设计之前阅读，也
许与第4章和第5章的抽象一起学习更好。但该章的主要目的是帮助读者编写作为结课课程设
计内容的一个真实程序。
本书使用方法
虽然本书的内容以逻辑顺序排列，但也不必从头到尾阅读本书。的确，作为一个学期的
课程，在学完所有论题之前就开始程序设计的练习，这可能是一个明智的选择。请看如下的
一个明智的学习计划：
第1章和第2章
11.1节，3.4节；开始程序设计练习
第4章和第5章
第6～8章（关于程序设计语言）之一
完成第3章和第11章，然后开始学期课程设计
依次完成以下各章：关于语言的各章，第9章和第10章
当然，从头到尾阅读本书并无坏处，但上述方法的优点是阅读和程序设计可并行进行。
致谢
要真诚地感谢E Christopher Lewis 和Robert van de Geijn两位对本书初稿的评论。也要对
以下评阅人的宝贵反馈意见和建议表示感谢：
David Bader, 佐治亚技术学院
Purushotham Bangalore, 亚拉巴马大学伯明翰分校
John Cavazos, 特拉华大学
Sandhya Dwarkadas, 罗切斯特大学
John Gilbert, 加州大学圣巴巴拉分校
Robert Henry, Cray公司
E Christopher Lewis, VMWare
Kai Li, 普林斯顿大学
Glenn Reinman, UCLA
W. g
W&H g
75h
J@Hh
75 h
J@H h
7@he
@@he
@@he
@@he
@@he
@@he
3@he
N@L h
31 h
N@Lh
31h
V'L g
V/ g
加州大学洛杉矶分校
/Xhg
N)X hf
31 hf
N@Lhf
31hf
N@L he
@1 he
@@ he
@@ he
@@ he
@@ he
@@ he
@5 he
J@H he
75hf
J@Hhf
75 hf
J(Y hf
.Yhg
Darko Stefanovic, 新墨西哥大学
我们感谢Karthik Murthy和Brandon Plost两位在编写和运行并行程序中的帮助, 以及帮助
发现正文中的瑕疵，我们还要感谢Bobby Blumofe, 他与我们在多线程程序设计课程中的早期
合作在本书的许多地方都可看到。我们赞赏和感谢华盛顿大学2006年秋季学期并行程序设计
环境讨论班（CSE590o）的学生们对本教科书的贡献，他们是：Ivan Beschastnikh，Alex
Colburn，Roxana Geambasu，Sangyun Hahn，Ethan Katz Bassett, Nathan Kuchta, Harsha
Madhyastha, Marianne Shaw, Brian Van Essen, Benjamin Ylvisaker。Sonja Keserovic, Kate
Moore, Brad Chamberlain，Steven Deitz, Dan Grossman, Jeff Diamond, Don Fussell, Bill Mark
和David Mohr。
我们要向编辑Matt Goldstein以及Addison Wesley出版社团队成员Sarah Milmore、Marilyn
Lloyd、Barbara Atkinson、Joyce Wells和Chris Kelly表示感谢。谢谢Gillian Hall 对我们愚钝行
为的特别容忍。
最后，我们要感谢我们的家人在撰写本书期间对我们的容忍。
Calvin Lin
Lawrence Snyder
2008年2月
计算机科学及应用
多核体系结构的出现使得并行程序设计技术对软件工程师和计算机系统设计师变得日益重要。本书着重论述并行计算的基本原理，解释各种现象，并分析为何这些现象是成功进行并行程序设计的机遇或阻碍。
本书是高等院校计算机专业高年级本科生或低年级研究生的理想教科书，同时也是专业程序员从事并行程序设计的理想入门书。
本书特点
以原理第一的原则重点阐述并行计算的基本原理，而不是指导读者“如何”去管理当前商品化的并行计算机。
以原理为背景讨论流行的程序设计语言并论述当代并行计算机编程所使用的工具。
使用注释框对书中所提及的内容进行饶有兴趣的扩展。
使用定义框对书中关键词和概念进行定义。
每章附有习题，便于读者掌握所论述的概念。
第10章着重论述可能影响该研究领域未来的当前进展。
第11章为读者构造实际的并行程序提供第一手的实践经验。
陆鑫达：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计算）、网络计算及其编程环境，机群计算（包括体系结构及中间件）、遗传和进化算法在映射和调度中的应用，分布计算及移动计算，智能代理等。
随着多核体系结构的出现和快速发展，使得并行计算科学的硬件基础设施发生了很大变化，如果把并行硬件基础设施看成是“经济基础”，则其相应的上层并行软件就可以视为“上层建筑”。由于“经济基础”的变化，作为其中重要的“上层建筑”之一的并行程序设计技术，必须进行相应的变化以适应新的“经济基础”。因此如何在多核体系结构上进行高效的并行程序设计以充分利用多核所提供的硬件并行性，从而大幅度地提升并行计算性能指标就显得非常重要。本书的主要论题之一便是环绕这一问题展开的。
并行程序设计比顺序程序设计要困难得多，一是因为并行程序设计的平台不是唯一的，存在多种不同的并行体系结构，而顺序程序设计只有唯一的冯·诺依曼体系结构；二是因为并行程序有多个进程或线程在同时运行，它们之间往往需要进行通信和同步，这就使并行程序设计变得复杂，特别是在要获得线性加速比时尤为如此；三是因为并行程序设计没有顺序程序设计中如C及Java那样通用和普及的并行程序设计语言，因此只能针对不同的体系结构选择使用不同的并行语言或例程库，例如对于共享地址空间的体系结构就必须选择如OpenMP、Java Threads或POSIX Threads那样的语言，而对于分布地址空间的体系结构就不得不选择如MPI或PVM那样的例程库语言。此外若要开发数据并行性，则就需要选用高性能的如Fortran（HPF）那样的语言。本书另一个主要论题便是环绕这一问题展开的。
本书侧重论述并行程序设计的基本原理，解释各种现象，并分析为何这些现象意味着成功进行并行程序设计的机遇或是阻碍。并行的硬件基础设施和并行的软件设计环境随着时间的变迁会不断发生变化，但原理则永远不会过时。以原理作为第一要素进行论述是本书的特色之一。
本书的另一个特色是，它侧重可扩展性和可移植性，即所设计的并行程序具有在任何数目处理器系统上和在任何并行体系结构平台上运行良好的能力。这一概念在多核时代是非常关键的，这是因为：首先，使得并行计算具有可扩展能力的大多数技术与在多核芯片上生成高效求解的技术是相同的；其次，虽然目前的多核芯片所具有的处理器数目还比较小，通常是2～8个，但今后每个芯片上的核数将会急剧增加，这就使得可扩展并行概念与之直接相关；最后，显然我们应该侧重研究和开发那些在现在和将来都能很好工作的方法。
内容非常实用是本书的又一特色。这是因为本书在介绍并行程序设计系统的同时，还叙述如何在这些系统中应用并行程序的设计原理。作者通过自身丰富的实践经验为读者介绍了在从事并行程序设计时应遵循的方法学。译者认为从事并行程序设计者应注重对并行程序设计方法学的了解、掌握，以及有关素质的培养，唯此才能开发出性能良好以及生命力持久的并行程序，并提高编制并行程序的能力和生产率。
翻译本书的原因有两个：一是本书的内容相当新，涉及现代的并行硬件和软件技术，包括多核体系结构及其并行程序设计技术；二是本书论述了并行程序设计中的一些深层次问题，如可扩展性、可移植性以及并行程序设计应遵循的方法学等。本书的不足之处在于对一些性能问题的定量分析不够充实，此外所介绍的并行机抽象模型也不够全面，只有一个CTA模型。
但这些瑕疵并不会影响本书的阅读价值。
本书是计算机科学专业本科高年级学生或一年级硕士生的理想教科书，对专业程序员来讲则是从事并行程序设计的一本理想入门书。本书对软件工程师和计算机系统设计师也是非常值得一读的参考书。
本书的翻译工作由陆鑫达教授负责和组织。陆鑫达教授翻译了目录、前言、第1~4章以及第10~11 章，林新华老师翻译了第5~9章。译稿全文由陆鑫达教授统稿审校。原书只分章不分节，为方便读者阅读，我们统一进行了分节。值此中译本出版之际，译者特向机械工业出版社华章分社的策划和编辑人员表示深切的谢意。
书中的术语翻译，我们尽量采用已公布的计算机科学技术名词（第二版），对于一些未公布的术语（包括一些新出现的术语）我们尽量采用流行的译法。由于时间较为仓促，翻译中的错误或不妥之处在所难免，敬请广大读者不吝指正。
致谢
在本书行将付梓之前，承蒙Sun公司高性能计算及云计算技术中心主任兼首席科学家Simon See博士拨冗为本译著撰写了推荐序，在此仅表深切的谢意！
上海交通大学计算机科学与工程系
陆鑫达林新华
2009年6月10日
早在1842年，意大利数学家Luigi Menabrea 就在其?
??
?
?
?
?
?
?W&?W&e?
?75?75e?
J@HJ@He?
75?75?e?
?J@HJ@H?e?
?75?75f?
J@HJ@Hf?
75?75?f?
?J@HJ@H?f?
?'@W&@L?f?
?V'@R'1?f?
N@LN@Lf?
?31?31f?
?N@LN@L?e?
31?31?e?
N@LN@Le?
?31?31e?
?V'?V'e?
??
?
??
?
?
?
查尔斯·巴贝奇的分析引擎》
（《Sketch of the Analytical Engine Invented by Charles Babbage》）一文中阐述了并行的理念。
他的这篇文章涉及计算机系统结构和程序设计的诸多方面。到了1958年，S.Gill针对并行程序
设计进行了探讨，而IBM的John Cocke和Daniel Slotnick则针对并行数值计算进行了探讨。然
而直到1962年，第一台多处理计算机才藉由Burroughs公司的D825而面世。此后，为数众多的
公司提出并推出了不同系统结构的多处理器系统。
曾几何时，工业界和学术界进行了无数次的尝试，力图将并行程序设计置于主流程序设
计的核心地位，但由于种种原因，这些尝试最终都未能取得成功。最主要的原因在于我们既
然有能力将处理器的主频每12～18个月就增加一倍，因此除了那些依赖于大规模并行系统来
加速其模拟运算的科学社团外，其他人就几乎找不到任何理由来编写并行程序。
然而近来，半导体工业界与微处理器供应商却遭遇到了屏障，即虽然我们依然能增加芯
片的密度，但却再也无法增加主频。有鉴于此，多核处理器开始登场，比如Sun的Niagara系
列，IBM的Power系列，AMD的Opteron，以及Intel的Xeon。事实上，供应商们未来将会提供
时钟速度更低但核数更多的处理器，如Intel的Nehalem以及AMD的Istanbul。此外，其他形式
的加速器也纷纷登场，例如GPGPU（如Nvidia的Tesla，AMD的Firestream，Intel的Larabee），
Cell处理器，以及FPGA。
这就意味着，为了能充分利用多核处理器，我们必须寻找应用内在的并行性，必须要编
写具有并行线程的代码。我们已然预见到串行程序会“逐渐减速”，以此观之，似乎并行程序
设计的概念终将成为未来主流程序员所必须掌握的重要概念。
《并行程序设计原理》一书对学生以及初学者将颇有裨益。两位作者Calvin Lin和
Lawrence Snyder非常细致地将各种原则与当前的并行硬件和软件场景联系了起来，使得本书
既能扎根于计算机科学的基础，又能与时俱进。这本全新的可实践且实用的书，必将使得阅
读引人入胜且充满趣味。
本书着力介绍一系列不同类型的程序设计工具：如在共享存储器程序设计中介绍了
Pthread、Java Threads以及OpenMP；而在消息传递程序设计中将MPI作为局部视图语言的代
表，并提及了UPC等PGAS语言，而将ZPL作为全局视图语言的典范；此外还提及了3个最新
的并行程序设计语言，即Sun的Fortress，IBM的X10，以及Cray的Chapel。
本书还探讨了一些高级内容：比如“理想”的并行程序设计语言所应遵循的基本原则；
并行软件开发的方法学和方式，如在敏捷软件开发中最常用的增量式开发。
本书无论对于积极进取的HPC业内人士来说，还是通用程序员而言，都是一本极具价值
的参考书。总之，这本可靠而翔实的书探讨了整个社团所将面临的有关并行化的挑战与问题。
Simon See博士
Sun高性能计算及云计算技术中心主任兼首席科学家
新加坡南洋理工大学兼职副教授
2009年6月
出版者的话
推荐序
译者序
前言
第一部分 基 础
第1章 导论 2
1.1 并行的威力和潜能 2
1.1.1 并行，一个熟悉的概念 2
1.1.2 计算机程序中的并行 2
1.1.3 多核计算机，一个机遇 3
1.1.4 使用并行硬件的更多机遇 4
1.1.5 并行计算和分布式计算的比较 4
1.1.6 系统级并行 5
1.1.7 并行抽象的便利 5
1.2 考察顺序程序和并行程序 6
1.2.1 并行化编译器 6
1.2.2 范例求解的变化 7
1.2.3 并行前缀求和 8
1.3 使用多指令流实现并行 9
1.3.1 线程概念 9
1.3.2 统计3的个数的多线程求解方法 10
1.4 目标：可扩展性和性能可移植性 17
1.4.1 可扩展性 17
1.4.2 性能可移植性 18
1.4.3 原理第一 18
1.5 小结 19
历史回顾 19
习题 19
第2章 认识并行计算机 21
2.1 用可移植性衡量机器特征 21
2.2 6种并行机介绍 21
2.2.1 芯片多处理器 21
2.2.2 对称多处理器体系结构 23
2.2.3 异构芯片设计 26
2.2.4 机群 27
2.2.5 超级计算机 27
2.2.6 对6种并行计算机的评论 30
2.3 顺序计算机的抽象 30
2.3.1 应用RAM模型 31
2.3.2 评估RAM模型 31
2.4 PRAM：一种并行计算机模型 32
2.5 CTA：一种实际的并行计算机模型 32
2.5.1 CTA模型 33
2.5.2 通信时延 36
2.5.3 CTA的性质 36
2.6 存储器访问机制 37
2.6.1 共享存储器 37
2.6.2 单边通信 37
2.6.3 消息传递 38
2.6.4 存储器一致性模型 38
2.6.5 程序设计模型 39
2.7 进一步研究通信 40
2.8 CTA模型的应用 40
2.9 小结 41
历史回顾 41
习题 41
第3章 性能分析 43
3.1 动机和基本概念 43
3.1.1 并行和性能 43
3.1.2 线程和进程 43
3.1.3 时延和吞吐率 44
3.2 性能损失的原因 45
3.2.1 开销 45
3.2.2 不可并行代码 46
3.2.3 竞争 47
3.2.4 空闲时间 47
3.3 并行结构 48
3.3.1 相关性 48
3.3.2 相关性限制并行性 49
3.3.3 粒度 50
3.3.4 局部性 51
3.4 性能协调 51
3.4.1 通信和计算 52
3.4.2 存储器和并行性 52
3.4.3 开销与并行 52
3.5 性能度量 53
3.5.1 执行时间 54
3.5.2 加速比 54
3.5.3 超线性加速比 55
3.5.4 效率 55
3.5.5 加速比问题 55
3.5.6 可扩展加速比和固定加速比 56
3.6 可扩展性能 56
3.6.1 难于达到的可扩展性能 57
3.6.2 硬件问题 57
3.6.3 软件问题 58
3.6.4 问题规模的扩展 58
3.7 小结 59
历史回顾 59
习题 59
第二部分 并行抽象
第4章 并行程序设计起步 62
4.1 数据和任务并行 62
4.1.1 定义 62
4.1.2 数据和任务并行的说明 62
4.2 Peril-L记号 63
4.2.1 扩展C语言 63
4.2.2 并行线程 63
4.2.3 同步和协同 64
4.2.4 存储器模型 64
4.2.5 同步存储器 66
4.2.6 归约和扫描 67
4.2.7 归约的抽象 68
4.3 统计3的个数程序实例 68
4.4 并行性的表示 68
4.4.1 固定并行性 68
4.4.2 无限并行性 69
4.4.3 可扩展并行性 70
4.5 按字母顺序排序实例 71
4.5.1 无限并行性 71
4.5.2 固定并行性 72
4.5.3 可扩展并行性 73
4.6 三种求解方法的比较 77
4.7 小结 78
历史回顾 78
习题 78
第5章 可扩展算法技术 80
5.1 独立计算块 80
5.2 Schwartz算法 80
5.3 归约和扫描抽象 82
5.3.1 通用归约和扫描举例 83
5.3.2 基本结构 84
5.3.3 通用归约结构 86
5.3.4 通用扫描组件举例 87
5.3.5 应用通用扫描 88
5.3.6 通用向量操作 89
5.4 静态为进程分配工作 89
5.4.1 块分配 90
5.4.2 重叠区域 91
5.4.3 循环分配和块循环分配 92
5.4.4 不规则分配 94
5.5 动态为进程分配工作 95
5.5.1 工作队列 95
5.5.2 工作队列的变体 97
5.5.3 案例研究：并发存储器分配 97
5.6 树 99
5.6.1 按子树分配 99
5.6.2 动态分配 100
5.7 小结 100
历史回顾 100
习题 101
第三部分 并行程序设计语言
第6章 线程程序设计 104
6.1 POSIX Threads 104
6.1.1 线程的创建和销毁 104
6.1.2 互斥 108
6.1.3 同步 110
6.1.4 安全性问题 117
6.1.5 性能问题 120
6.1.6 案例研究1：连续过度松弛 124
6.1.7 案例研究2：重叠同步与计算 129
6.1.8 案例研究3：多核芯片上的流计算 134
6.2 Java Threads 134
6.2.1 同步方法 135
6.2.2 同步语句 136
6.2.3 统计3的个数程序实例 136
6.2.4 易变存储器 138
6.2.5 原子对象 138
6.2.6 锁对象 138
6.2.7 执行器 138
6.2.8 并发集合 138
6.3 OpenMP 138
6.3.1 统计3的个数程序实例 139
6.3.2 parallel for的语义局限 141
6.3.3 归约 141
6.3.4 线程的行为和交互 142
6.3.5 段 142
6.3.6 OpenMP总结 143
6.4 小结 143
历史回顾 143
习题 143
第7章 MPI和其他局部视图语言 145
7.1 MPI：消息传递接口 145
7.1.1 统计3的个数程序实例 145
7.1.2 组和通信子 152
7.1.3 点对点通信 152
7.1.4 集合通信 154
7.1.5 举例：连续过度松弛 157
7.1.6 性能问题 159
7.1.7 安全性问题 164
7.2 分区的全局地址空间语言 164
7.2.1 Co-Array Fortran 165
7.2.2 Unified Parallel C 166
7.2.3 Titanium 167
7.3 小结 167
历史回顾 168
习题 168
第8章 ZPL和其他全局视图语言 169
8.1 ZPL程序设计语言 169
8.2 ZPL基本概念 169
8.2.1 区域 170
8.2.2 数组计算 171
8.3 生命游戏实例 173
8.3.1 问题 173
8.3.2 解决方案 173
8.3.3 如何实现 174
8.3.4 生命游戏的哲学 175
8.4 与众不同的ZPL特征 175
8.4.1 区域 175
8.4.2 语句级索引 175
8.4.3 区域的限制 176
8.4.4 性能模型 176
8.4.5 用减法实现加法 177
8.5 操作不同秩的数组 177
8.5.1 部分归约 177
8.5.2 扩充 178
8.5.3 扩充的原理 179
8.5.4 数据操作举例 179
8.5.5 扩充区域 180
8.5.6 矩阵乘 181
8.6 用重映射操作重排数据 182
8.6.1 索引数组 183
8.6.2 重映射 183
8.6.3 排序举例 185
8.7 ZPL程序的并行执行 186
8.7.1 编译器的职责 186
8.7.2 指定进程数 187
8.7.3 为进程分配区域 187
8.7.4 数组分配 188
8.7.5 标量分配 188
8.7.6 工作分派 188
8.8 性能模型 189
8.8.1 应用实例1：生命游戏 190
8.8.2 应用实例2：SUMMA算法 190
8.8.3 性能模型总结 191
8.9 NESL并行语言 191
8.9.1 语言概念 191
8.9.2 用嵌套并行实现矩阵乘 192
8.9.3 NESL复杂性模型 192
8.10 小结 192
历史回顾 193
习题 193
第9章 对并行程序设计现状的评价 194
9.1 并行语言的四个重要性质 194
9.1.1 正确性 194
9.1.2 性能 195
9.1.3 可扩展性 196
9.1.4 可移植性 196
9.2 评估现有方法 196
9.2.1 POSIX Threads 196
9.2.2 Java Threads 197
9.2.3 OpenMP 197
9.2.4 MPI 197
9.2.5 PGAS语言 198
9.2.6 ZPL 198
9.2.7 NESL 199
9.3 可供将来借鉴的经验 199
9.3.1 隐藏并行 199
9.3.2 透明化性能 200
9.3.3 局部性 200
9.3.4 约束并行 200
9.3.5 隐式并行与显式并行 201
9.4 小结 201
历史回顾 201
习题 202
第四部分 展 望
第10章 并行程序设计的未来方向 204
10.1 附属处理器 204
10.1.1 图形处理部件 204
10.1.2 Cell处理器 207
10.1.3 附属处理器的总结 207
10.2 网格计算 208
10.3 事务存储器 209
10.3.1 与锁的比较 210
10.3.2 实现方法 210
10.3.3 未解决的问题 211
10.4 MapReduce 212
10.5 问题空间的提升 214
10.6 新出现的语言 214
10.6.1 Chapel 215
10.6.2 Fortress 215
10.6.3 X10 216
10.7 小结 218
历史回顾 218
习题 218
第11章 编写并行程序 219
11.1 起步 219
11.1.1 访问和软件 219
11.1.2 Hello, World 219
11.2 并行程序设计的建议 220
11.2.1 增量式开发 220
11.2.2 侧重并行结构 220
11.2.3 并行结构的测试 221
11.2.4 顺序程序设计 221
11.2.5 乐意写附加代码 222
11.2.6 测试时对参数的控制 222
11.2.7 功能性调试 223
11.3 对结课课程设计的设想 223
11.3.1 实现现有的并行算法 223
11.3.2 与标准的基准测试程序媲美 224
11.3.3 开发新的并行计算 224
11.4 性能度量 225
11.4.1 与顺序求解方法比较 226
11.4.2 维护一个公正的实验设置 226
11.5 了解并行性能 227
11.6 性能分析 227
11.7 实验方法学 228
11.8 可移植性和微调 229
11.9 小结 229
历史回顾 229
习题 229
术语表 230
参考文献 234
