《华章 并行编程模式》是软件开发人员学习并行编程的教程，其中并没有过多讲解理论知识，而是讨论并行程序员所面临的挑战及其解决方案，并结合当前并行API的用法给出一些示例。
　　书中引入了一种完整的、通俗易懂的模式语言，可以帮助任何有经验的开发人员编写高效的并行代码。

　　从网格、集群到下一代游戏平台，并行计算正在成为主流。IBM、Intel、Oracle公司的超线程技术、超传输技术和多核微处理器等技术创新正在加速推动并行计算的发展。万事俱备，只欠东风——满足并行软件飞速增长需求的程序员。
　　《华章并行编程模式》是软件开发人员学习并行编程的教程，其中并没有过多讲解理论知识，而是讨论并行程序员所面临的挑战及其解决方案，并结合当前并行API的用法给出一些示例。书中引入了一种完整的、通俗易懂的模式语言，可以帮助任何有经验的开发人员编写高效的并行代码。通过学习本书，读者将意识到模式是掌握并行编程的方式。本书不仅适用于高等院校计算机科学相关专业的学生，而且适用于各类软件开发人员。
　　本书主要内容包括：
　　理解并行计算和并行开发人员所面临的挑战。
　　找出软件设计中的并发问题并将其分解成并发任务。
　　管理不同任务间的数据使用。
　　生成一种可以有效利用已识别的并发性的算法结构。
　　将算法结构同需要实现的API相连接。
　　实现并行程序的特定软件结构。
　　与OpenMP、MPI和Java等当今主流的并行编程环境协同工作。

　　Timothy G. Mattson，加州大学圣克鲁兹分校化学博士，英特尔生命科学社区首席发言人。他主要研究对大多程序员来说简化的并行编程技术，重点是计算生物学方面。

　　Beverly A. Sanders，哈佛大学应用数学博士，佛罗里达大学计算机信息科学与工程系副教授。她主要研究如何帮助程序员构建高质量的、正确的程序，包括形式化方法、组件系统和设计模式。

　　Berna L. Massingill，加州理工学院计算机科学博士，三一大学副教授。她的研究领域为并行和分布式计算，以及设计模式和形式化方法。

Patterns for Parallel Programming
出版者的话
译者序
前言
作者简介
第1章　并行编程的模式语言
1.1 引言
1.2 并行编程
1.3 设计模式和模式语言
1.4 关于并行编程的模式语言
第2章　并行计算的背景和术语
2.1 并行程序中的并发性与操作系统中的并发性
2.2 并行体系结构简介
2.2.1　Flynn分类法
2.2.2 MIMD的进一步分类
2.2.3　小结
2.3 并行编程环境
2.4 并行编程术语
2.5 并行计算的度量
2.6 通信
2.6.1 延迟和带宽
2.6.2 重叠通信和计算以及延迟隐藏
2.7 本章小结
第3章　"寻找并发性"设计空间
3.1 关于设计空间
3.1.1 概述
3.1.2 使用分解模式
3.1.3 示例的背景知识
3.2 任务分解模式
3.3 数据分解模式
3.4 分组任务模式
3.5 排序任务模式
3.6　数据共享模式
3.7 设计评估模式
3.8 本章小结
第4章　"算法结构"设计空间
4.1 引言
4.2 选择一种算法结构设计模式
4.2.1 目标平台
4.2.2 主要组织原则
4.2.3 算法结构决策树
4.2.4 重新评估
4.3 示例
4.3.1 医学成像
4.3.2 分子动力学
4.4 任务并行模式
4.5 分治模式
4.6 几何分解模式
4.7 递归数据模式
4.8 流水线模式
4.9 基于事件的协作模式
第5章　"支持结构"设计空间
5.1 引言
5.1.1 程序结构模式
5.1.2 数据结构模式
5.2 面临的问题
5.3 模式选择
5.4 SPMD模式
5.5 主/从模式
5.6 循环并行模式
5.7 派生/聚合模式
5.8 共享数据模式
5.9 共享队列模式
5.10 分布式数组模式
5.11 其他支持结构
5.11.1 SIMD
5.11.2 MPMD
5.11.3 客户端-服务器计算
5.11.4 使用声明语言的并发编程
5.11.5 问题求解环境
第6章　"实现机制"设计空间
6.1 引言
6.2 UE管理
6.2.1 线程的创建/销毁
6.2.2 进程的创建/销毁
6.3 同步
6.3.1 内存同步和围栅
6.3.2 栅栏
6.3.3 互斥
6.4 通信
6.4.1 消息传递
6.4.2 集合通信
6.4.3 其他通信构造
附录A　OpenMP简介
附录B　MPI简介
附录C　Java并发编程简介
术语表
参考文献
索引

　　第1章
　　Patterns for Parallel Programming
　　并行编程的模式语言
　　1.1 引言
　　计算机被广泛用于模拟自然科学、医学和工程学等领域中的真实物理系统，包括天气预报模拟系统、震撼电影的场景模拟系统，并且可以使用任意的计算能力来完成更加精细的模拟。无论是顾客购物模式，还是来自于宇宙的遥测数据或者DNA序列，它们需要分析的数据量都十分巨大。为了提供这种计算能力，设计者将多个处理单元融入一个较大的系统中。这就是所谓的并行计算机，它能够同时运行多个任务，在更短的时间内解决规模更大的问题。
　　过去，并行计算机仅用于解决一些最重要的问题，但是从20世纪90年代中期开始，随着微处理器内部开始支持多线程技术，并且在单个硅片上可容纳多个处理器内核，这种情况已经发生了根本性变化。现在，并行计算机随处可见，几乎每所大学计算机系都至少有一台并行计算机。几乎所有的石油公司、汽车制造商、药品开发公司和特效工作室都已经使用了并行计算。
　　例如，计算机动画的生成过程是将动画文件的信息（如光、纹理和阴影）应用于3D模型以生成2D图像，再用这些2D图像组成电影的帧。为较长的电影生成所需的帧时（每秒24帧），并行计算是非常必要的。1995年，由Pixar公司发行的《玩具总动员》是第一个完全通过计算机软件制作的电影，该电影由一台包括100个双处理器机器的名为“renderfarm” [PS00]的机器处理。Pixar公司在1999年制作《玩具总动员2》时利用了一台具有1400个处理器的系统。由于提高了处理能力，影片的效果（包括纹理、服饰和艺术效果）有大幅度提升。Monsters公司2001年使用了一个拥有250个企业级服务器。（每个服务器包含14个处理器，共3500个处理器）的系统。然而利用更高的计算性能，包括处理器数目以及单个处理器计算性能，来提升动画效果，因此生成一幅帧需要的时间仍保持不变。
　　生物科学在能够从多种生物体（包括人）中获得DNA序列信息后实现了跨越式的发展。由Celera公司提出并成功使用的一种称为基因组鸟枪的排序算法，可将基因组划分为多个子段，首先通过实验确定每个子段的DNA序列，然后利用计算机通过重构子段间的重叠区域来重组整个序列。Celera公司排序人类基因组时使用的计算机包括150台四路服务器以及一台具有16个处理器和64GB内存的服务器，实际计算包括5兆亿次基对基比较[Ein00]。
　　项目[SET，ACK+02]的目的是寻找地外智能存在的证据，它是另一个展示并行计算能力的实例。该项目利用位于波多黎各的世界上最大的阿雷卡纳特无线望远镜搜索外太空，分析收集到的数据，搜索智能信号源。该项目的计算需求超过了世界上最大超级计算机的性能，因此只能利用公共计算资源满足性能需求，即将通过Internet互联的世界范围内的PC整合为一台并行计算机。项目将收集的数据划分为一些子任务，并将子任务通过Internet发送到每个客户端计算机上，利用这些分布的个人计算机的空闲时间进行计算。每个客户端定期连接到服务器，下载数据并执行分析计算，最后将结果发送回服务器。客户端程序被设计为一个屏幕保护程序，仅当计算机处于空闲状态时才将CPU贡献给SETI问题执行计算任务。目前，一个工作子任务平均需要一台计算机7～8个小时的CPU时间，从项目启动到现在已有2.05亿个工作单元得以处理。最近，也出现了一批利用公共计算资源的新项目，并且一些大公司也利用其内部个人计算机的空闲计时解决从新药筛选到芯片设计验证等问题。
　　尽管通过并行计算可以以更短的时间解决一些串行无法完成的问题，但实现并行也需要付出一些代价。编写并行计算软件是十分困难的，因此只有少量程序员具备丰富的并行编程经验。如果要利用并行计算机带来的并行性潜能，大部分程序员都需要学习如何编写并行
　　程序。
　　本书将为有串行程序设计经验的程序员介绍编写并行程序的设计方法。虽然已经有一些优秀的书籍介绍过特殊的并行编程环境，但本书不同之处在于，我们主要介绍并行算法的构造和设计思路。因此，我们将使用模式语言的概念，在面向对象社区中已经大量使用了这种包含专家设计经验的高度结构化表示。
　　本书前两章将介绍基础知识，其中第l章概述理解和使用模式语言所必需的并行计算相关概念及其背景，第2章将更深入地讨论并行程序员所使用的基本概念和术语，其余章节介绍具体的模式语言。
　　1.2 并行编程
　　并行计算的关键是可挖掘的并发性。如果一个计算问题能够被分解成多个子问题，并且所有子问题可在相同时间内同时、安全地解决，则该问题就存在并发性。必须分析问题并发性并在代码中显示开发性，使得子问题能够并行执行，也就是说，问题解决方案必须具备并发性。
　　大部分大规模计算问题具备一定的并发性。程序员通过建立并行算法并在并行编程环境中实现来挖掘问题的并发性。这样，当并行程序在多处理器系统上运行时，才能在更短的时间内完成计算。此外，相对于单处理器系统，多处理器系统能处理规模更大的问题。
　　例如，假设计算包括求一个大型数据集的和时，串行计算将所有的值按顺序相加；如果使用多处理器，则需划分数据集，并在不同处理器上计算每个子集的和，同时完成计算，最后求所有子集之和。这样利用多处理器并行计算能更快地完成任务。若每个处理器都有私有内存，将数据分布到多个处理器上即可处理更大规模的问题。
　　上述简单示例展示了并行计算的本质。并行计算的目标是利用多处理器在更短时间内解决问题，以及处理规模更大的问题（与单处理所能处理的问题规模相比）。程序员需要鉴别出问题的并发性，并设计并行算法来挖掘问题中的并发性，然后在合适的并行编程环境中编写并行代码，最后在并行系统上运行。
　　并行编程也面临一些挑战。通常，问题所包含的并发任务间具有一定依赖性，这些子计算以不同顺序完成可能会影响程序的运行结果。例如，在上述并行求和示例中，某一子集求和计算完成后，才能与其他子集的和相加。该算法对所有任务强加了一种偏序顺序（即所有子任务完成后才能够被组合在一起计算最终结果）。此外，由于浮点运算具有非结合性和非交换性，因此当求和运算顺序不同时，计算结果可能会有微小的数值差。设计安全的并行程序需要付出大量努力，优秀并行程序员必须非常谨慎以保证这些不确定性不会影响最终计算
　　结果。
　　即使一个并行程序是“正确”的，它也可能无法通过挖掘并发性来实现性能提高。必须确保挖掘并发性而导致的额外开销不会严重影响程序运行时间，并且在其他问题中实现负载平衡通常不像求和问题那样简单。并行算法效率依赖于它与底层硬件体系结构间的映射关系，一个并行体系结构上执行效率非常高的并行算法在另一个体系结构上执行的性能可能很差。
　　第2章将更为量化地介绍并行计算并重新讨论这个问题。
　　1.3 设计模式和模式语言
　　设计模式描述在特定上下文中类似问题的有效解决方法。模式具有预定的格式，包括模式名称、上下文的描述、目标和限制以及相应的解决方案。其理念是记录专家经验，供他人遇到类似问题时参考借鉴。除了解决方法本身外，模式名称也是非常重要的，它构成了领域专用词汇的基础，有效加强同一领域设计者之间的交流。
　　设计模式最早由Christopher Alexander提出，其应用的领域是城市规划和建筑学[AIS77]。Beck和Cunningham[BC87]最早将设计模式概念引入软件工程社区，随着Gamma、Helm、Johnson和Vlissides[GHJV95]的名为GoF（Gang of Four的缩写）的书籍的出版，这一概念在面向对象编程中占据了重要地位。该书收集了大量面向对象编程的设计模式。例如，Visitor模式描述了一种组织类的方式，能独立实现不同数据结构的代码与遍历它的代码，因此遍历仅仅依赖于每个节点的类型和实现该遍历的类。这能够在不改变数据结构类的情况下灵活地添加新功能，为数据结构的不同遍历方法实现提供了便利。GoF书中介绍的设计模式已经进入了面向对象编程词典，并已在学术文章、商业出版物和系统文档中广泛应用，这些设计模式已成为软件工程师所必需的知识。
　　一个组建于1993年的名为Hillside Group[Hil]的非盈利性教育组织促进了模式和模式语言的使用，更进一步地说，它鼓励人们编写通用的编程和设计实践方面的规范，因此促进了人们在计算机领域的交流。为了设计新的模式并帮助模式编写者提高技能，Hillside Group每年举办一次编程模式语言研讨会（Pattern Languages of Programs，PLoP），并在其他地方举办了分会，例如ChiliPLoP（在美国西部）、KoalaPLoP（在澳大利亚）、EuroPLoP（在欧洲）和Mensore PLOP（在日本）。这些研讨会的论文集[Pat]包含大量模式资源，覆盖了大多数软件应用领域，并成为几本书的[CS95、VCK96、MRB97、HFR99]主要素材。
　　Alexander最初研究模式时，不仅提出了一个模式分类方法，还提出了一种模式语言，从而引入了一种新的设计方法。在模式语言中，所有模式组织为一个特殊结构，用户遍历模式集，并选择具体模式来设计复杂系统。设计者在每个决策点上选择一个适合的模式，该模式可以导出其他多个模式，最终通过一个模式网络完成设计。因此，模式语言包括了一种设计方法学，并向应用程序开发人员提供了特定领域建议（尽管都称为语言，但模式语言并不是一种编程语言）。
　　1.4 关于并行编程的模式语言
　　本书给出了用于并行编程的模式语言，它具有许多优势。最直接的好处是它可以通过提供重要问题解决方法目录、扩展的词汇表和方法学来传播专家经验。我们希望在并行程序开发的全过程中提供指导来降低并行编程的难度。程序员首先应深入理解要解决的实际问题，然后利用模式语言，最终得到详细的并行设计或代码。我们的长期目标是希望模式语言成为定性评估不同编程模型、促进并行编程工具开发的基础。
　　模式语言由4个设计空间组成，包括寻找并发性、算法结构、支持结构和实现机制，如图1-1所示，4个空间构成一个线性层次，其中寻找并发性位于顶部，而实现机制位于底部。
　　寻找并发性设计空间的目标是重组问题以揭示其可开发的并发性。设计者在这个层次中主要面对高层次算法问题，并揭示问题的潜在并发性。算法结构设计空间利用潜在并发性构造算法，设计者在这个层次上考虑如何利用寻找并发性模式中的并发性。算法结构模式描述开发并发性的整体策略。支持结构设计空间为算法结构设计空间和实现机制设计空间提供了一个中间层。支持结构设计空间有两组重要的模式，一组程序构造方法的模式，另一组是通用共享数据结构模式。实现机制设计空间将上层空间的模式映射到特定的编程环境中。它描述进程/线程管理（例如，创建或销毁进程/线程）和进程/线程间交互（例如信号量、栅栏或消息传递）的通用机制。实现机制设计空间中的条目直接被映射到特定并行编程环境中的元素，因此不表示为模式。但它们都包含在模式语言中，以便提供从问题描述到最终编码的完整解决方案。

　　“如果建好了它，他们就会到来。”
　　我们已建成了多处理器工作站、大规模并行超级计算机和集群，但利用这些机器编程的程序员却还没有出现。少数乐于迎接挑战的程序员已经证明，大多数问题可以利用并行计算机快速求解，但普通程序员，特别是那些生活安逸的职业程序员，却忽略了并行计算机。
　　他们这样做十分不明智，因为并行计算机即将成为主流。多线程微处理器、多核CPU、多处理器PC、集群、并行游戏控制台等并行计算机正在逐步占领整个计算市场，在计算机行业中，市场上到处是这样的硬件，这些硬件唯有借助并行程序才能全速运行。但谁将编写并行程序呢？
　　这是一个老生常谈的问题，甚至在20世纪80年代早期“killer micros”开始取代传统向量机时，我们就十分担心如何吸引普通程序员编写并行程序。我们尝试了能想到的所有方法，包括高级硬件抽象、隐式并行编程语言、并行语言扩展和可移植消息传递库。但是经过多年的努力之后，“他们”并没有出现，绝大多数程序员并没有致力于编写并行软件。
　　一个常见的观点是，你不能将新技巧告诉老程序员，因此直到老程序员逐渐退出、新一代程序员逐渐成长后，并行编程问题才能够得到解决。
　　但我们不认同这种悲观主义态度。多年来，程序员一直在采用新的软件技术方面表现出非凡能力，许多使用Fortran的老程序员现在正在编写完美的Java面向对象程序。因此问题并非在于老程序员，而在于并行计算专家如何培养并行程序员。
　　这正是本书的目标，我们希望把握优秀并行程序员思考并行算法本质的过程，并以一种职业程序员易于掌握的方式讲解。为此，我们利用模式语言来介绍并行编程。之所以这样选择，不是因为要利用设计模式解决新领域中的问题，而是因为模式已经被证明适用于并行编程。例如，模式在面向对象设计领域非常有效，它们提供了一种用于讨论设计元素的通用语言，并且能够有效地帮助程序员掌握面向对象的设计方法。
　　本书包含并行编程的模式语言。前两章将介绍并行计算的一些基础知识，包括并行计算的概念和术语，而不是详尽介绍整个领域。
　　后4章介绍了模式语言，对应于创建一个并行程序的4个阶段。
　　寻找并发性。识别可用的并发性，并用于算法设计中。
　　算法结构。用一种高级结构组织一个并行算法。
　　支持结构。将算法转化为源代码，考虑如何组织并行程序以及如何管理共享数据。
　　实现机制。寻找特定的软件构造，实现并行程序。
　　这些模式紧密相关，构成了4个设计空间。从顶部（寻找并发性）开始，依次经历每一种模式，到达底部（实现机制）时，就可以得到并行程序的一个详细设计。
　　如果目标是一个并行程序，那么所需要的除了一个并行算法之外，还包括编程环境和用于表示程序源代码中并发性的方法。程序员过去需要面对大量不同的并行编程环境。幸运的是，随着时间的推移，并行编程社区目前主要使用三种编程环境。
　　OpenMP：扩展了C、C++和Fortran，主要用来在共享内存计算机上编写并行程序。
　　MPI：用于集群和其他分布式存储计算机的一种消息传递库。
　　Java：一种面向对象的编程语言，支持共享内存计算机上的并行编程，并支持分布式计算的标准类库。
　　很多读者可能熟悉其中的一种或几种编程语言，但为了方便那些并行计算的初学者，附录简要介绍了这几种编程环境。
　　我们研究模式语言多年，现在将其总结为一本书以便使用。但是这并非此项工作的终点。我们期望读者有自己的新想法，并设计更好的并行编程新模式。我们可能遗漏了模式语言的某些重要特征，希望并行计算社区能推广这种模式语言。我们将继续更新并改进这种模式语言，直到它成为并行计算社区的统一观点。我们将开展一些实际的工作，例如，使用模式语言来创建更好的并行编程环境，帮助人们使用这些模式来编写并行软件。我们将一直努力，直到并行软件全面代替串行软件的那一天。
　　致谢
　　我们从1998年开始研究模式语言，从如何设计并行算法的一个模糊概念开始到完成本书，已经走过了一段漫长而崎岖的道路。如果没有以下人员的帮助，我们不可能完成这项
　　任务。
　　Mani Chandy将Tim介绍给Berverly和Berna，并坚信我们能成为一个优秀团队。美国国家科学基金、英特尔公司、三一大学多年来一直支持本项目的研究。每年夏天在伊利诺伊举办的PLoP会议参与者为本书的具体并行编程模式提供了大量帮助。该会议的组织和审稿过程十分具有挑战性，但没有这些经验我们无法完成模式语言的研究。同时感谢仔细阅读本书并指出大量错误的审稿专家。
　　最后，还要感谢我们的家人。感谢Beverly的家人（Daniel和Steve），Tim的家人（Noah、August和Martha），以及Berna的家人（Billie），感谢他们的支持和付出。
　　Tim Mattson
　　Beverly Sanders
　　Berna Massingill