第3章并行算法 本章首先介绍了并行算法的各种分类方法，然后讲述了如何在目前特别流行的一种并行 系统机群系统上设计高效的并行算法，说明了在机群系统上适合什么样的并行算法，给出 了一些基本的原则和方法，为以后的并行程序设计打下基础。 3.1并行算法分类 并行算法是给定并行模型的一种具体、明确的解决方法和步骤。按照不同的划分方法， 并行算法有多种不同的分类 根据运算的基本对象的不同，可以将并行算法分为数值并行算法（数值计算）和非数值 并行算法（符号计算）。当然，这两种算法也不是截然分开的，比如在数值计算的过程中会 用到查找、匹配等非数值计算的成分，当然非数值计算中也一般会用到数值计算的方法，别 分为什么类型的算法主要取决于主要的计算量和宏观的计算方法。 根据进程之间的依赖关系可以分为同步并行算法（步调一致） 、异步并行算法（步调 进展互不相同)和纯并行算法（各部分之间没有关系）。对于同步并行算法，任务的各个部 分是同步向前推进的，有一个全局的时钟（不一定是物理的）来控制各部分的步伐：而对于 异步并行算法，各部分的步伐是互不相同的，它们根据计算过程的不同阶段决定等待、继续 或终止；纯并行算法是最理想的情况各部分之间可以尽可能快地向前推进，不需要任何同 步或等特， 但是 般这样的问愿是少见的 根据并行计算任务的大小，可以分为粗粒度并行算法（一个并行任务包含较长的程序段 和较大的计算量入细粒度并行算法（一个并行任务包含较短的程序段和较小的计算量）以 及介于二者之间的中粒度并行算法。一般而言，并行的粒度越小，就有可能开发更多的并行 性，提高并行度，这是有利的方面，但是另一个不利的方面就是并行的粒度越小，通信次数 和通信量就相对增多，这样就增加了额外的开销，因此合适的并行粒度需要根据计算量、通 信量、 计算速度、通信速度进行综合平衡，这样才能够取得高效率。 3.2并行算法的设计 对于相同的并行计算模型，可以有多种不同的并行算法来描述和刻画，由于并行算法设 计的不同，可能对程序的执行效率有很大的影响，不同的算法可以有几倍、几十倍甚至上百 倍的性能差异是完全正常的。 并行算法基木上是随若并行机的发展而发展的，从本质上说，不同的并行算法是根据问 题类别的不同和并行机体系结构的特点产生出来的， 个好的并行算法要既能很好地匹配并 行计算机硬件体系结构的特点，又能反映问愿内在并行 对于SMD并行计算机一股适合同步并行算法，而MMD并行计算机则适合异步并行算 法。对于SPMD和MPMD这些新流行起来的并行计算机，设计并行算法的思路和以前并行算 法的思路有很大的不同。下面针对机群系统，重点讲一下SPMD和MPMD并行算法的设计。 对于机群计算，有一个很重要的原则就是设法加大计算时间相对于通信时间的比重，减 少通信次数甚至以计算换通信。这是因为 对于机群系统 通信的开销要远 计算的开销，因此要尽可能降低通信的次数，或将两次通信合并为一次通信。基于同样的原
9 第3章 并行算法 本章首先介绍了并行算法的各种分类方法 然后讲述了如何在目前特别流行的一种并行 系统 —机群系统上设计高效的并行算法 说明了在机群系统上适合什么样的并行算法 给出 了一些基本的原则和方法 为以后的并行程序设计打下基础 3.1 并行算法分类 并行算法是给定并行模型的一种具体 明确的解决方法和步骤 按照不同的划分方法 并行算法有多种不同的分类 根据运算的基本对象的不同 可以将并行算法分为数值并行算法 数值计算 和非数值 并行算法 符号计算 当然 这两种算法也不是截然分开的 比如在数值计算的过程中会 用到查找 匹配等非数值计算的成分 当然非数值计算中也一般会用到数值计算的方法 划 分为什么类型的算法主要取决于主要的计算量和宏观的计算方法 根据进程之间的依赖关系可以分为同步并行算法 步调一致 异步并行算法 步调 进展互不相同 和纯并行算法 各部分之间没有关系 对于同步并行算法 任务的各个部 分是同步向前推进的 有一个全局的时钟 不一定是物理的 来控制各部分的步伐 而对于 异步并行算法 各部分的步伐是互不相同的 它们根据计算过程的不同阶段决定等待 继续 或终止 纯并行算法是最理想的情况 各部分之间可以尽可能快地向前推进 不需要任何同 步或等待 但是一般这样的问题是少见的 根据并行计算任务的大小 可以分为粗粒度并行算法 一个并行任务包含较长的程序段 和较大的计算量 细粒度并行算法 一个并行任务包含较短的程序段和较小的计算量 以 及介于二者之间的中粒度并行算法 一般而言 并行的粒度越小 就有可能开发更多的并行 性 提高并行度 这是有利的方面 但是另一个不利的方面就是并行的粒度越小 通信次数 和通信量就相对增多 这样就增加了额外的开销 因此合适的并行粒度需要根据计算量 通 信量 计算速度 通信速度进行综合平衡 这样才能够取得高效率 3.2 并行算法的设计 对于相同的并行计算模型 可以有多种不同的并行算法来描述和刻画 由于并行算法设 计的不同 可能对程序的执行效率有很大的影响 不同的算法可以有几倍 几十倍甚至上百 倍的性能差异是完全正常的 并行算法基本上是随着并行机的发展而发展的 从本质上说 不同的并行算法是根据问 题类别的不同和并行机体系结构的特点产生出来的 一个好的并行算法要既能很好地匹配并 行计算机硬件体系结构的特点 又能反映问题内在并行性 对于SIMD并行计算机一般适合同步并行算法 而MIMD并行计算机则适合异步并行算 法 对于SPMD和MPMD这些新流行起来的并行计算机 设计并行算法的思路和以前并行算 法的思路有很大的不同 下面针对机群系统 重点讲一下SPMD和MPMD并行算法的设计 对于机群计算 有一个很重要的原则就是设法加大计算时间相对于通信时间的比重 减 少通信次数甚至以计算换通信 这是因为 对于机群系统 一次通信的开销要远远大于一次 计算的开销 因此要尽可能降低通信的次数 或将两次通信合并为一次通信 基于同样的原
因，机群计算的并行粒度不可能太小，因为这样会大大增加通信的开销。如果能够实现计算 和通信的重叠，那将会更大地提高整个程序的执行效率。 因此，对于机群计算，可以是数值或非数值的计算，这些都不是影响性能的关，也可 以是同步、松同步或异步的，但以同步和松同步为主，并行的粒度一般是大粒度或中粒度的。 +个好的算法一般应该呈现如下的计算模式： 计算 通信 通信 或 等待， 图5适合机群系统的SPMD并行算法的计算模式 图5没有考虑计算与通信的重叠若能够实现计算与通信的重叠，那将是更理想的计 算模式。 计算与通信的重叠部分 计算一 通信 计算 通信 计算 通信 图6计算与涌信垂叠的SPMD并行算法的计算模式 图6是加入了计算和通信重海技术后的P并行算法的计算模式 对于MPMD并行算法，各并行部分一般是异步执行的，而不是象SPMD那样的同步或松 同步方式，因此只要能够大大降低通信次数，增大计算相对于通信的比重，则该MPMD算 法就可以取得较高的效率。图7给出了MPMD算法的一种比较合适的计算模式
10 因 机群计算的并行粒度不可能太小 因为这样会大大增加通信的开销 如果能够实现计算 和通信的重叠 那将会更大地提高整个程序的执行效率 因此 对于机群计算 可以是数值或非数值的计算 这些都不是影响性能的关键 也可 以是同步 松同步或异步的 但以同步和松同步为主 并行的粒度一般是大粒度或中粒度的 一个好的算法一般应该呈现如下的计算模式 计算 通信 通信 或 或 等待 等待 图 5 适合机群系统的SPMD并行算法的计算模式 图 5 没有考虑计算与通信的重叠 若能够实现计算与通信的重叠 那将是更理想的计 算模式 计算与通信的重叠部分 计算 通信 计算 通信 计算 通信 图 6 计算与通信重叠的SPMD并行算法的计算模式 图 6 是加入了计算和通信重叠技术后的SPMD并行算法的计算模式 对于MPMD并行算法 各并行部分一般是异步执行的 而不是象SPMD那样的同步或松 同步方式 因此只要能够大大降低通信次数 增大计算相对于通信的比重 则该MPMD算 法就可以取得较高的效率 图 7 给出了MPMD算法的一种比较合适的计算模式
计算→ 通信 计算：公→ 通信 计算 通信 图7适合机群系统的MPMD并行算法 3.3小结 在并行计算中，由于并行算法可以对性能产生重大的影响，因此受到广泛的重视，并行 算法也成为一个专门的十分活跃的研究领域。并行算法设计也是并行程序设计的前提，没有 好的并行算法，就没有好的并行程序，因此在并行程序设计之前，必须首先考虑好并行算法 该算法要能够将并行机和实际的问题很好地结合起来，既能够充分利用并行机体系结构的特 点，又能够揭示问题内在的并行性。 11
11 计算 通信 计算 通信 计算 通信 图 7 适合机群系统的MPMD并行算法 3.3 小结 在并行计算中 由于并行算法可以对性能产生重大的影响 因此受到广泛的重视 并行 算法也成为一个专门的十分活跃的研究领域 并行算法设计也是并行程序设计的前提 没有 好的并行算法 就没有好的并行程序 因此在并行程序设计之前 必须首先考虑好并行算法 该算法要能够将并行机和实际的问题很好地结合起来 既能够充分利用并行机体系结构的特 点 又能够揭示问题内在的并行性
第二部分基本的MPI并行程序设计 本部分讲述基本的MPI并行程序设计所需要的知识，包括MPI的简单介绍，一个相对完 备的MPI子集，对等模式和主从模式MPI程序的编写，MPI的一个具体实现MPICH在Lix和 NT操作系统下的安装和MP程序的执行 通过本部分的学习，可以掌握MP最基本和最常见的程序设计方法，编写出能满足一般 需求的MPI并行程序。这一部分主要基于MPL1来进行讲解，不涉及MPI-2的内容
12 第二部分 基本的MPI并行程序设计 本部分讲述基本的MPI并行程序设计所需要的知识 包括MPI的简单介绍 一个相对完 备的MPI子集 对等模式和主从模式MPI程序的编写 MPI的一个具体实现MPICH在Linux和 NT操作系统下的安装和MPI程序的执行 通过本部分的学习 可以掌握MPI最基本和最常见的程序设计方法 编写出能满足一般 需求的MPI并行程序 这一部分主要基于MPI-1来进行讲解 不涉及MPI-2的内容
第4章MPI简介 本章对MP进行简要介绍，使读者对MPI有一个宏观的总体了解，为下面深入理解MPI, 掌握MPI并行编程技术提供必要的准备。在本章不涉及编程细节。 4.1什么是MPI 对M的定义是多种多样的，相不外平下面二个方面，它们限定了M的内承和外延 MPI是 个库，而不是 一门语言。许多人认为MPI就是 种并行语言 ,这是不准确的 但是按照并行语言的分类，可以把FORTRAN+MPI或C+MP,看作是一种在原来串行语言基 础之上扩展后得到的并行语言。MPI库可以被FORTRAN77 C/Fortran90/C+调用，从语法上 说，它遵守所有对库函数过程的调用规则，和一般的函数过程没有什么区别。 ②MPI是一种标准或规范的代表，而不特指某一个对它的具体实现。迄今为止，所有的 并行计算机制造商都提供对MPI的支 可以在网上免费得到MP在不同并行 计算机上的实 一个 确的MPI程序， 可以不】 修改地在所有的并行机上运行 ③MPI是一种消息传递编程模型，并成为这种编程模型的代表和事实上的标准。MPI虽 然很庞大，但是它的最终目的是服务于讲程间通信这一目标的。 在MPI上很容易移植其它的并行代码，而且编程者不需要去努力掌握许多其它的全新脚 念，就可以学习编写MPI程序。当然，这并不意味着MPI已经十分完美，必须承认MPI自身 还存在着 在本书的后续章节将对它进行讨论 消息传递方式是广泛应用于多类并行机的 一种模式，特别是那些分布存储并行机，尽管 在具体的实现上有许多不同，但通过消息完成进程通信的基本概念是容易理解的。十多年 来，这种模式在重要的计算应用中已取得了实质进步。有效和可移植地实现一个消息传递系 统是可行的，因此，通过定义核心库程序的语法、语义，这将在大范围计算机上可有效实现， 将有益于广大用户，这是MP产生的重要原因。 4.2MPI的目的 MPI为自己制定了一个雄心勃勃的目标，总结概括起来，它包括几个在实际使用中都十 分重要但有时又是相互矛盾的三个方面：1较高的通信性能；2较好的程序可移植性；3强 大的功能。其体地说，包括以下几个方面： ·提供应用程序编程接口。 ●提高通信效率。措施包括群免花储器到花储器的名次重复拷贝，允许计算和通信的 重叠 ·可在异构环境下提供实现 ●提供的接口可以方便C语言和Fortran77的调用。 ●提供可靠的通信接口。即用户不必处理通信失败。 ●定义的接口和现在已有接口（如PVM,NX,Express,.p4等）差别不能太大，但是 允许扩展以提供更大的灵活性。 定义的接口能在基本的通信和系统软件无重大改变时，在许多并行计算机生产商的 平台上实现。接口的语义是独立于语言的。 3
13 第4章 MPI简介 本章对MPI进行简要介绍 使读者对MPI有一个宏观的总体了解 为下面深入理解MPI 掌握MPI并行编程技术提供必要的准备 在本章不涉及编程细节 4.1 什么是MPI 对MPI的定义是多种多样的 但不外乎下面三个方面 它们限定了MPI的内涵和外延 ¨ MPI是一个库 而不是一门语言 许多人认为MPI就是一种并行语言 这是不准确的 但是按照并行语言的分类 可以把FORTRAN+MPI或C+MPI 看作是一种在原来串行语言基 础之上扩展后得到的并行语言 MPI库可以被FORTRAN77/C/Fortran90/C++调用 从语法上 说 它遵守所有对库函数/过程的调用规则 和一般的函数/过程没有什么区别 MPI是一种标准或规范的代表 而不特指某一个对它的具体实现 迄今为止 所有的 并行计算机制造商都提供对MPI的支持 可以在网上免费得到MPI在不同并行计算机上的实 现 一个正确的MPI程序 可以不加修改地在所有的并行机上运行 Æ MPI是一种消息传递编程模型 并成为这种编程模型的代表和事实上的标准 MPI虽 然很庞大 但是它的最终目的是服务于进程间通信这一目标的 在MPI上很容易移植其它的并行代码 而且编程者不需要去努力掌握许多其它的全新概 念 就可以学习编写MPI程序 当然 这并不意味着MPI已经十分完美 必须承认MPI自身 还存在着一些缺点 在本书的后续章节将对它进行讨论 消息传递方式是广泛应用于多类并行机的一种模式,特别是那些分布存储并行机 尽管 在具体的实现上有许多不同, 但通过消息完成进程通信的基本概念是容易理解的 十多年 来 这种模式在重要的计算应用中已取得了实质进步 有效和可移植地实现一个消息传递系 统是可行的 因此 通过定义核心库程序的语法 语义 这将在大范围计算机上可有效实现 将有益于广大用户 这是MPI产生的重要原因 4.2 MPI的目的 MPI为自己制定了一个雄心勃勃的目标 总结概括起来 它包括几个在实际使用中都十 分重要但有时又是相互矛盾的三个方面 1 较高的通信性能 2 较好的程序可移植性 3 强 大的功能 具体地说 包括以下几个方面 l 提供应用程序编程接口 l 提高通信效率 措施包括避免存储器到存储器的多次重复拷贝 允许计算和通信的 重叠等 l 可在异构环境下提供实现 l 提供的接口可以方便 C 语言和 Fortran 77的调用 l 提供可靠的通信接口 即用户不必处理通信失败 l 定义的接口和现在已有接口 如PVM NX Express p4等 差别不能太大 但是 允许扩展以提供更大的灵活性 l 定义的接口能在基本的通信和系统软件无重大改变时 在许多并行计算机生产商的 平台上实现 接口的语义是独立于语言的