对于共享内存的并行计算机，各个处理单元通过对共享内存的访问来交换信息、协调各 处理器对并行任务的处理。对这种共享内存的编程，实现起来相对简单，但共享内存往往成 为性能特别是扩展性的重要瓶颈 对于分布式内存的并行计算机，各个处理单元都拥有自己独立的局部存储器，由于不存 在公共可用的存储单元因此各个处理器之间通过消息传递来交换信息，协调和控制各个处 理器的执行。这是本书介绍的消息传递并行编程模型所面对的并行计算机的存储方式。不难 看出，通信对分布式内存并行计算机的性能有重要的影响，复杂的消息传递语句的编写成为 在这种并行计算机上进行并行程序设计的难点所在，但是，对于这种类型的并行计算机，由 于它有很好的扩展性和很高的性能，因此，它的应用非常) 分布式共享内存的并行计算机结合了前两者的特点，是当今新一代并行计算机的一种重 要发展方向。对于目前越来越流行的机群计算(Cluster Computing),大多采用这种形式的 结构。通过提高一个局部结点内的计算能力，使它成为所谓的“超结点”，不仅提高了整个 系统的计算能力，而且可以提高系统的模块性和扩展性，有利于快速构造超大型的计算系统。 1.2物理问题在并行机上的求解 并行机 映射 物理问题 抽象 抽象 并行计算模型 并行求解模型 入精确描述 精确描述 适合并行计算 模型的并行算法 求解算法 用思 并行程序设计 图3问题的并行求解过程 一个物理问题并行求解的最终目的是将该问趣映射到并行机上，这一物理上的映射是通 过不同层次上的抽象映射来实现的《图3》。 路并行知的非本质的细特征 ,可以得到该并行机的并行计算模型，在这一模型上 可以设计各种适合该模型的并行算法 这些算法精确描述了该并行模型能够实现的功能，而 这些算法是通过用特定的并行语言设计并行程序后得以实现的。对于现实世界的物理问题， 为了能够高效地并行求解，必须建立它的并行求解模型，一个串性的求解模型是很难在并行 机上取得满意的并行效果的。有了并行求解模型，就可以针对该模型设计高效的并行算法， 这样就可以对该问题的求解进行精确描述和定量分析，就可以对各种不同的算法进行性能上
4 对于共享内存的并行计算机 各个处理单元通过对共享内存的访问来交换信息 协调各 处理器对并行任务的处理 对这种共享内存的编程 实现起来相对简单 但共享内存往往成 为性能特别是扩展性的重要瓶颈 对于分布式内存的并行计算机 各个处理单元都拥有自己独立的局部存储器 由于不存 在公共可用的存储单元 因此各个处理器之间通过消息传递来交换信息 协调和控制各个处 理器的执行 这是本书介绍的消息传递并行编程模型所面对的并行计算机的存储方式 不难 看出 通信对分布式内存并行计算机的性能有重要的影响 复杂的消息传递语句的编写成为 在这种并行计算机上进行并行程序设计的难点所在 但是 对于这种类型的并行计算机 由 于它有很好的扩展性和很高的性能 因此 它的应用非常广泛 分布式共享内存的并行计算机结合了前两者的特点 是当今新一代并行计算机的一种重 要发展方向 对于目前越来越流行的机群计算 Cluster Computing 大多采用这种形式的 结构 通过提高一个局部结点内的计算能力 使它成为所谓的 超结点 不仅提高了整个 系统的计算能力 而且可以提高系统的模块性和扩展性 有利于快速构造超大型的计算系统 1.2 物理问题在并行机上的求解 并行机 映射 物理问题 抽象 抽象 并行计算模型 并行求解模型 精确描述 精确描述 适合并行计算 问题的并行 模型的并行算法 求解算法 实现 用并行语言进行 并行程序设计 图 3 问题的并行求解过程 一个物理问题并行求解的最终目的是将该问题映射到并行机上 这一物理上的映射是通 过不同层次上的抽象映射来实现的 图 3 忽略并行机的非本质的细节特征 可以得到该并行机的并行计算模型 在这一模型上 可以设计各种适合该模型的并行算法 这些算法精确描述了该并行模型能够实现的功能 而 这些算法是通过用特定的并行语言设计并行程序后得以实现的 对于现实世界的物理问题 为了能够高效地并行求解 必须建立它的并行求解模型 一个串性的求解模型是很难在并行 机上取得满意的并行效果的 有了并行求解模型 就可以针对该模型设计高效的并行算法 这样就可以对该问题的求解进行精确描述和定量分析 就可以对各种不同的算法进行性能上
的比较，最后通过并行程序设计，实现问题和并行机的结合。 并行程序设计，需要将问颗的并行求解算法转化为特定的话合并行计算檬型的并行算 法，为了达到这一目的，首先是问题的并行求解算法必须能够将问恩内在的并行特征充分体 现出来，否则并行求解算法将无法利用这些并行特征，从而使问题的高效并行求解成为不可 能；其次是并行求解模型要和并行计算模型尽量吻合，这样，就为问题向并行机上的高效解 决提供了前提。 1.3小结 本章对并行机和物理问题在并行机上的求解进行了简单地介绍，按照指令和数据的不同 对并行计算机讲行别分是一种经典的方法，至今仍在使用，而不同的编程模式和并行计算机 的存储方式有很大的关系，其实互连网络也是并行计算机的重要组成部分，但是对于并行 序员来说看不到这种不同，因此本章没有对它进行介绍。本书的目的是力求以最简单的方式 将最重要和最基本的内容介绍给读者
5 的比较 最后通过并行程序设计 实现问题和并行机的结合 并行程序设计 需要将问题的并行求解算法转化为特定的适合并行计算模型的并行算 法 为了达到这一目的 首先是问题的并行求解算法必须能够将问题内在的并行特征充分体 现出来 否则并行求解算法将无法利用这些并行特征 从而使问题的高效并行求解成为不可 能 其次是并行求解模型要和并行计算模型尽量吻合 这样 就为问题向并行机上的高效解 决提供了前提 1.3 小结 本章对并行机和物理问题在并行机上的求解进行了简单地介绍 按照指令和数据的不同 对并行计算机进行划分是一种经典的方法 至今仍在使用 而不同的编程模式和并行计算机 的存储方式有很大的关系 其实互连网络也是并行计算机的重要组成部分 但是对于并行程 序员来说看不到这种不同 因此本章没有对它进行介绍 本书的目的是力求以最简单的方式 将最重要和最基本的内容介绍给读者
第2章并行编程模型与并行语言 本章介绍最重要的两种并行编程模型数据并行和消息传递及它们之间的相互关系，讲 述了它们各自的优缺点和适用范围，给出了几种并行语言的产生方法和各自的特点。 2.1并行编程模型 目前两种最重要的并行编程模型是数据并行和消息传递，数据并行编程模型的编程级别 比较高，编程相对简单，但它仅适用于数据并行问题消息传递编程模型的编程级别相对较 低，但消息传递编程模型可以有更广泛的应用范围。 数据并行即将相同的操作同时作用于不同的数据，因此适合在SMD及SPMD并行计算 机上运行，在向量机上通过数据并行求解问题的实践也说明数据并行是可以高效地解决一大 举科学与丁程计算问颗的。 数据并行编 型是一种较高层次上的模型，它提供给编程着 一个全局的地址空间 般这种形式的语言本身就提供并行执行的语义，因此对于编程者来说，只需要简单地指明执 行什么样的并行操作和并行操作的对象，就实现了数据并行的编程，比如对于数组运算，使 得数组B和C的对应元素相加后送给A则通过语句 A=B+C(或其它的表达方式) 就能够实现上述功能，使并行机对B、C的对应元素并行相加 并将结果并行赋给A 。因此 数据并行的表达是相对简单和简洁的，它不需要编程者关心并行机是如何对该操作进行并行 执行 数据并行编程模型虽然可以解决一大类科学与工程计算问题，但是对于非数据并行类的 问题，如果通过数据并行的方式来解决，一般难以取得较高的效率，数据并行不容易表达甚 至无法表其它形式的并行特征 数据并行发展到现在，高效的编译实现成为它面临的一个主要问题，有了高效的编译器 数据并行程序就可以在共享内存和分布式内存的并行机上都取得高效率，这样可以提高并行 程序的开发效率，提高并行程序的可移植性，进一步推广并行程序设计。 消息传递即各个并行执行的部分之间通过传递消息来交换信息、协调步伐、控制执行。 消息传递一般是面向分布式内存的，但是它也可适用于共享内存的并行机。消息传递为编程 者提供了更灵活的控制手段和表达并行的方法 方法很难表达的并行算法 都可以用消息传递模型来实现，灵活性和控制手段的多样化，是消息传递并行程序能提供高 的执行效率的重要原因。 消息传递模型一方面为编程者提供了灵活性，另一方面，它也将各个并行执行部分之间 复杂的信息交换和协调、控制的任务交给了编程者，这在一定程度上增加了编程者的负担， 这也是消息传递编程模型编程级别低的主要原因。虽然如此消息传递的基本通信模式是简 单和清楚的，学习和掌握这些部分并不闲难，因此目前大量的并行程序设计仍然是消息传递 并行编程模式。 表格1是对数据并行和消息传递两种并行编程模式的简单对比
6 第2章 并行编程模型与并行语言 本章介绍最重要的两种并行编程模型—数据并行和消息传递及它们之间的相互关系 讲 述了它们各自的优缺点和适用范围 给出了几种并行语言的产生方法和各自的特点 2.1 并行编程模型 目前两种最重要的并行编程模型是数据并行和消息传递 数据并行编程模型的编程级别 比较高 编程相对简单 但它仅适用于数据并行问题 消息传递编程模型的编程级别相对较 低 但消息传递编程模型可以有更广泛的应用范围 数据并行即将相同的操作同时作用于不同的数据 因此适合在SIMD及SPMD并行计算 机上运行 在向量机上通过数据并行求解问题的实践也说明数据并行是可以高效地解决一大 类科学与工程计算问题的 数据并行编程模型是一种较高层次上的模型 它提供给编程者一个全局的地址空间 一 般这种形式的语言本身就提供并行执行的语义 因此对于编程者来说 只需要简单地指明执 行什么样的并行操作和并行操作的对象 就实现了数据并行的编程 比如对于数组运算 使 得数组B和C的对应元素相加后送给A 则通过语句 A=B+C 或其它的表达方式 就能够实现上述功能 使并行机对B C的对应元素并行相加 并将结果并行赋给A 因此 数据并行的表达是相对简单和简洁的 它不需要编程者关心并行机是如何对该操作进行并行 执行的 数据并行编程模型虽然可以解决一大类科学与工程计算问题 但是对于非数据并行类的 问题 如果通过数据并行的方式来解决 一般难以取得较高的效率 数据并行不容易表达甚 至无法表达其它形式的并行特征 数据并行发展到现在 高效的编译实现成为它面临的一个主要问题 有了高效的编译器 数据并行程序就可以在共享内存和分布式内存的并行机上都取得高效率 这样可以提高并行 程序的开发效率 提高并行程序的可移植性 进一步推广并行程序设计 消息传递即各个并行执行的部分之间通过传递消息来交换信息 协调步伐 控制执行 消息传递一般是面向分布式内存的 但是它也可适用于共享内存的并行机 消息传递为编程 者提供了更灵活的控制手段和表达并行的方法 一些用数据并行方法很难表达的并行算法 都可以用消息传递模型来实现 灵活性和控制手段的多样化 是消息传递并行程序能提供高 的执行效率的重要原因 消息传递模型一方面为编程者提供了灵活性 另一方面 它也将各个并行执行部分之间 复杂的信息交换和协调 控制的任务交给了编程者 这在一定程度上增加了编程者的负担 这也是消息传递编程模型编程级别低的主要原因 虽然如此 消息传递的基本通信模式是简 单和清楚的 学习和掌握这些部分并不困难 因此目前大量的并行程序设计仍然是消息传递 并行编程模式 表格 1是对数据并行和消息传递两种并行编程模式的简单对比
表格1数据并行与消息传递并行编程模型 对比内容 数据并行 消息传递 适用的 机类型 SIMD/SPMD SIMD/MIMD/SPMD/MPMD 依赖于编译器 通信的 分布式或共享内存 编译器负责 程序员负责 数据并行类题 数据并 任务并行 目前状 缺乏高效的编译器支持 用广 2.2并行语言 并行程序是通过并行语言来表达的， 并行语言的产生主要有三种方式：1设计全新的并 行语言；2扩展原来的串行语言的语法成分，使它支持并行特征：3不改变串行语言，仅为 串行语言提供可调用的并行库， 设计一种全新的并行语言的优点是可以完全摆脱串行语言的束缚，从语言成分上直接支 持并行，这样就可以使并行程序的书写更方便，更自然，相应的并行程序也更容易在并行机 上实现。但是， 由于并行计算至今还没有象串行计算那样统一的冯·诺伊曼模型可供遵循 因此并行机、并行模型、并行算法和并行语言的设计和开发千差万别，没有一个统一的标准 虽然有多种多样全新的并行语言出现但至今还没有任何一种新出现的并行语言，成为普遍 接受的标准，设计全新的并行语言，实现起来难度和工作量都很大，但各种各样并行语言的 出现、实践和研究，无疑都为并行语言和并行计算的发展作出了贡献。 一种重要的对串行语言的扩充方式就是标注，即将对串行语言的并行扩充作为原来串行 语言的注释，对于这样的并行程序，若用原来的串行编译器来编译，标注的并行扩充部分将 不起作用，仍将该程序作为一般的串行程序处理，若使用扩充后的并行编译器来编译，则该 并行编译器就会根据标注的要求，将原来串行执行的部分转化为并行执行。对串行语言的并 行扩充，相对于设计全新的并行语言，显然难度有所降低，但需要重新开发编译器，使它能 够支持扩充的并行部分，一般地，这种新的编译器往往和运行时支持的并行库相结合 仅仅提 供开仃库 是一种对原来的 行程 设计 动最小的并行 化方法。这样，原来的 串行编译器也能够使用，不需要任何修改编程者只需要在原来的串行程序中加入对并行库 的调用，就可以实现并行程序设计，本书所介绍的MPI讲行程序设计，就属于这种方式。 对于这三种并行语言的实现方法，目前最常使用的是第二种和第三种方法，特别是第三 种方法。 图4给出了并行语言的实现方式和实现难度之间的关系。 >
7 表格 1 数据并行与消息传递并行编程模型 对比内容 数据并行 消息传递 编程级别 高 低 适用的并行机类型 SIMD/SPMD SIMD/MIMD/SPMD/MPMD 执行效率 依赖于编译器 高 地址空间 单一 多个 存储类型 共享内存 分布式或共享内存 通信的实现 编译器负责 程序员负责 问题类 数据并行类问题 数据并行 任务并行 目前状况 缺乏高效的编译器支持 使用广泛 2.2 并行语言 并行程序是通过并行语言来表达的 并行语言的产生主要有三种方式 1 设计全新的并 行语言 2 扩展原来的串行语言的语法成分 使它支持并行特征 3 不改变串行语言 仅为 串行语言提供可调用的并行库 设计一种全新的并行语言的优点是可以完全摆脱串行语言的束缚 从语言成分上直接支 持并行 这样就可以使并行程序的书写更方便 更自然 相应的并行程序也更容易在并行机 上实现 但是 由于并行计算至今还没有象串行计算那样统一的冯·诺伊曼模型可供遵循 因此并行机 并行模型 并行算法和并行语言的设计和开发千差万别 没有一个统一的标准 虽然有多种多样全新的并行语言出现 但至今还没有任何一种新出现的并行语言 成为普遍 接受的标准 设计全新的并行语言 实现起来难度和工作量都很大 但各种各样并行语言的 出现 实践和研究 无疑都为并行语言和并行计算的发展作出了贡献 一种重要的对串行语言的扩充方式就是标注 即将对串行语言的并行扩充作为原来串行 语言的注释 对于这样的并行程序 若用原来的串行编译器来编译 标注的并行扩充部分将 不起作用 仍将该程序作为一般的串行程序处理 若使用扩充后的并行编译器来编译 则该 并行编译器就会根据标注的要求 将原来串行执行的部分转化为并行执行 对串行语言的并 行扩充 相对于设计全新的并行语言 显然难度有所降低 但需要重新开发编译器 使它能 够支持扩充的并行部分 一般地 这种新的编译器往往和运行时支持的并行库相结合 仅仅提供并行库 是一种对原来的串行程序设计改动最小的并行化方法 这样 原来的 串行编译器也能够使用 不需要任何修改 编程者只需要在原来的串行程序中加入对并行库 的调用 就可以实现并行程序设计 本书所介绍的MPI并行程序设计 就属于这种方式 对于这三种并行语言的实现方法 目前最常使用的是第二种和第三种方法 特别是第三 种方法 图 4 给出了并行语言的实现方式和实现难度之间的关系
实现难度个 @ ☆ 将 提供并行库 扩充语法成分 新语言→改动多少 图4并行语言的实现方法 2.3小结 并行编程模型除了数据并行和消息传递之外，还有共享变量模型、函数式模型等等，但 它们的应用都没有数据并行和消息传递那样普遍，因此本书不再介绍，况且只要知道了一两 种并行编程模型，再自学其它的模型也会比较容易些。 并行语言的发展其实十分迅速，并行语言的种类也非常多，但真正使用起来并被广为接 受的却寥寥无几，因此这里并没有介绍某一具体的并行语言，而只是给出了并行语言产生的 基本方法，对FORTRAN和C的扩充是最常见的并行语言产生方法MPI并行程序设计就是 和FORTRAN或C结合起来实现的
8 实现难度 提供并行库 扩充语法成分 新语言 改动多少 图 4 并行语言的实现方法 2.3 小结 并行编程模型除了数据并行和消息传递之外 还有共享变量模型 函数式模型等等 但 它们的应用都没有数据并行和消息传递那样普遍 因此本书不再介绍 况且只要知道了一两 种并行编程模型 再自学其它的模型也会比较容易些 并行语言的发展其实十分迅速 并行语言的种类也非常多 但真正使用起来并被广为接 受的却寥寥无几 因此这里并没有介绍某一具体的并行语言 而只是给出了并行语言产生的 基本方法 对FORTRAN和C的扩充是最常见的并行语言产生方法 MPI并行程序设计就是 和FORTRAN或C结合起来实现的