（计算机软件与理论专业论文）openmp转化为mpi关键技术研究.pdf

摘要 摘要 o p e n m p 是面向s m p 体系结构的并行编程标准，m p i 是面向m p p 体系结 构的并行编程标准。随着主流超级计算机系统由s m p 向m p p 过渡，o p e n m p 必然向m p i 过渡。但是它们之间差异很大，手工转化十分困难。通过对这两种 编程规范和编译技术的研究，本文提出了将o p e n m p 转化为m p i 的基本方法， 该方法支持o p e n m p 1 ，2 。 数据划分是优化针对m p p 系统的m p i 程序的重点和难点。本文所提出的 数据划分方法要求数据空间和计算空间具有一定程度的一致性。该条件是从实 际科学计算模式中总结出来的，能很好适用于常见科学计算程序。本文提出应 该以w h i l e 循环为基本单位寻求一致数据划分，尽量减少w h i l e 循环内的数据通 讯。本文寻找一致数据划分的基本思路是首先寻找单个循环中所有可能的数据 划分方法，然后在此基础上求得循环问一致数据划分。在求得数据划分之后反 过来确定计算划分。然而即使找到了一致数据划分，还是有可能出现“数据对 不齐”的现象，此时可能需要边界通讯。为了尽量减少不必要的数据通讯，本 文仔细分析了出现上述情况的原因，总结并提出了数据划分的几种约束，并根 据约束关系的强弱来对齐数据。由于考虑了约束关系，该算法能找到较优解， 且开销不大。最后本文提出了产生通讯代码的算法。 【关键字】 o p e n m p ，m p i ，共享，计算划分，数据划分 第1 页，共4 5 页 a b s t r a c t a b s t r a c t o p e n l v l pd o m i n a t e sp a r a l l e lp r o g r a m m i n gs p e c i f i c a t i o n sf o rs m p a r c h i t e c t u r e ， w h i l em p ii sd e s i g n e df o rm a s s i v ed i s t r i b m e dm e m o i ya r c h i t e c t u r e i ti si m p o r t a n t t ot r a n s l a t eo p e n m pt om p i ，b u tt h ed i f f e r e n c eb e t w e e nt h e mi st o os i g n i f i c a n tt o a c c o m p l i s hs u c ht r a n s l a t i o nb yh a n d a f t e rs t u d y i n gt h e s et w os p e c i f i c a t i o n sa n d c o m p i l i n gt e c h n i q u e ，t h i sp a p e rp r e s e n t sa b a s i co p e n m p - - m p it r a n s l a t i o nm e t h o d t h em e t h o ds u p p o r t sa l lf e a t u r e so p e n m p s p e c i f i c a t i o n1 2d e s c r i b e s d a t a p a r t i t i o ni sk e yt oo p t i m i z em p ip r o g r a m sw r i t t e nf o rm p ps y s t e m t h i s p a p e rb r i n g sa b o u t an e wd a t ap a r t i t i o nm e t h o d ，w h i c hn e e d st h a td a t as p a c ei sp a r t l y c o n s i s t e n tw i t hi t e r a t i o ns p a c e t h i sp r e c o n d i t i o ni ss o m e w h a ts t r i c tb u ti ss u m m e d u pf r o mr e a ls c i e n t i f i cc o m p u t i n gp r o g r a m sa n dc a n f i tt h e mw e l l a f t e ra n a l y z i n g m a n y r e a ls c i e n t i f i cc o m p u t i n g p r o g r a m s ，t h i sp a p e rp u t sf o r w a r dt h a ti t i sn e c e s s a r y t ot r e a taw h i l e l o o pa sad a t ap a r t i t i o nu n i ta n dt of i n do u tc o n s i s t e n td a t ap a r t i t i o n s i nw h i l e l o o p st om i n i m i z ec o m m u n i c a t i o n s w ef i r s tf i n da l lp o s s i b l ed a t ap a r t i t i o n s i ns i n g l ed o l o o p st h e nf i n do u tc o n s i s t e n td a t ap a r t i t i o n sb e t w e e nt h e m a f t e r f i n d i n gc o n s i s t e n td a t ap a r t i t i o n s ，d a t ap a r t i t i o n so f t h es a m ea r r a yi nd i f f e r e n tl o o p s w i l lh ea l i g n e dt om i n i m i z eb o u n d a r yc o m m u n i c a t i o n s t h ep a p e rp u t sf o r w a r da n e wm e t h o db a s e do nt h ec o n c e p t d a t ap a r t i t i o nc o n s t r a i n s t oa l i g nd a t ap a r t i t i o n s o ft h es a n l e a r r a y a t l a s tt h e p a p e rg i v e s o u tt h e a l g o r i t h m t o g e n e r a t e c o m m u n i c a t i o nc o d ei f b o u n d a r yc o m m u n i c a t i o n si sl i e o d e d k e yw o r d s o p e n m p ，m p i ，s h a r e dv a r i a b l e p r i v a t ev a r i a b l e ，c o m p u t a t i o np a r t i t i o n ，d a t a p a r t i t i o n 第2 页，共4 5 页 第一章引言 第一章引言 1 1 高性能计算机与并行处理技术 在科学和工程计算领域都有一大批“巨大挑战性( g r a n dc h a l l e n g i n g ) ”计 算问题。它们的涉及面极其广泛：从计算模型数值模拟( 如数值天气预报、核 爆炸模拟试验等) ，工程分析与设计( 各种偏微方程有限元分析、空气动力学计 算等) ，人工智能与模式识别( 如博弈决策树搜索、密码破译、图象处理等) ， 到大规模数据处理( 如石油勘探、卫星遥感数据处理等) 等等诸多领域。对国 计民生和国家安全有着举足轻重的影响。这些问题对于计算能力的要求几乎是 无限的，能够轻易耗尽任何能够提供的计算能力。因此各国对发展高性能计算 机都十分重视，纷纷将研究开发超高性能计算机系统列为重要战略计划( 例如 美国的a c s i 、h p c 及网格计算等计划) ，并为此投入了大量人力、物力、财力。 近3 0 多年来，随着v l s i 和计算机体系机构等技术的发展，单机速度按“摩 尔定律”以令人惊喜的速度增长，但是一方面单机性能及其增长速度远远不能 满足时代需求，要想在现有元技术条件下最大限度提高计算机性能只能通过多 机协作也就是并行处理达到；另一方面单机速度有理论上的极限，摩尔定律不 可能永远有效下去，迟早有一天人类提高计算能力的途径会转到并行处理上来。 事实上，从向量机到当前的超级计算机，都采用了并行体系结构。不仅如此， 现在s u p e r - - t h r e a d 结构是单个微处理芯片设计研究的主流方向，这意味着未来 的单处理芯片也将依赖较强的并行性来提高速度。 1 2 高性能计算机体系结构分类 1 2 1 向量机 向量机采用基于流水线的向量部件支持向量操作的快速实现，主要进行向 量处理。向量机的典型体系结构如图1 所示。 第3 页，共4 5 页 第一章引言 1 2 2 对称多处理机 图1 向量多处理机系统 对称多处理机( s m p ) 体系结构的机器由若干共享单一主存的处理机组成。 为了减少多处理机对共享主存的争用，通过宽频带多总线连接这些多处理机。 虽然共享主存，每个处理机都有各自的c a c h e ，并且由硬件来维护同一主存 单元在多个处理机c a c h e 之间的一致性。s m p 的典型体系结构如图2 所示。 j 图2 s m p 系统 s m p 体系结构的主要优点是编程简单，优化也较容易。但是这种体系结构 也有致命的缺陷：由于总线频率、长度和带宽的限制，s m p 系统的可扩展性不 好，寻址空间不大，规模一般较小( 处理机数量一般从4 到几十不等) ，处理能 力也有限。 第4 页，共4 5 页 曰上 ，工一 工塑 上一 第一章引言 1 2 3 分布式主存多机系统 分布式主存多机系统的每个节点都有自己的局部存储器，它们之间通过一 定的拓扑结构互联( 如总线结构、环形结构、m e s h 结构、超立方结构等) ，一 般都是专用的网络，各节点之间通过消息机制进行通讯。九十年代以来，由于 工作站和p c 机的价格不断下降与性能的迅速提高以及高速网络的问世，以机 群为代表的超级计算机系统逐步成为超级计算机的主流。从体系结构的角度看 机群系统属于分布式主存多机系统，它将现有的高性能工作站、p c 机等作为计 算资源，以专用或通用网络连接在一起，通过消息机制在各节点之间分布数据 和通讯。分布式主存多机系统的典型结构如图3 所示。 图3 m p p 系统 由于分布式主存多机系统的存储器不是共享的，而是通过互联网络连接起 来，所以这种系统的扩展性很强，其结点数可能达到上万( 如i n t e l 的“红色 选择”由9 0 0 0 个c p u 组成) ，因此又称为大规模并行处理系统( m a s s i v e p a r a l l e l p r o c e s s i n gs y s t e m ，简称m p p ) 。m p p 能达到的处理能力比s m p 系统强得多， 在公布的t o p 5 0 0 机器中分布式主存多机系统占据绝大多数。 1 2 4 分布式共享主存多机系统 由于纯粹的m p p 系统编程困难，超级计算机设计人员实现了分布式共享存 储计算机，这种系统在纯粹的m p p 系统上添加了复杂的硬件或软件维护全局地 址空间以及c a c h e 一致性，这样虽然系统的主存在物理上是分布式的，但逻 第5 页，共4 5 页 一9 囡一幸 9 囡一 一9 甲二 第一章引言 辑上是共享的。这种系统的优点在于系统的可扩展性和可以达到的处理能力都 比s m p 系统强得多；由于实现了共享主存，可以使用o p e n m p 编程，比较简单。 这种体系结构的缺点在于系统的成本很高且可伸缩性较纯粹的m p p 系统差，随 着规模的增大其效率会降低。 1 3 自动化编译工具的意义和作用 1 3 1 并行化编译系统 为了充分利用并行计算机的计算能力必须为每个需要在并行机上运行的应 用编写并行程序。编写并行程序与编写串行程序相比，其程序的移植、维护、 调试均非常困难，最困难的是要求程序员有充分的并行处理概念，程序员只有 掌握了诸如：多处理、私有变量、同步、多级存储等概念后才能编写出高质量 的并行软件，而现在一般的并行计算的用户都是从事科学研究的，并非是计算 机研究人员，让他们掌握这些复杂的概念意义不大。使用并行化编译系统是一 个可行的替代方法，它可以将串行程序自动地转化为等价的并行程序。虽然并 行化编译技术有一定的局限性，但是一方面它能使程序更易于移植、调试和维 护；另一方面它能够提供有效的分析功能可以为用户提供有用的信息，从而有 利于用户改善程序的性能。因而是任何一个并行机上最重要的工具之一。 并行编译系统是一种系统软件，它随着体系结构的变化而变化。迄今为止 超级计算机经历了向量机、对称多处理机和m p p 系统三个阶段。相应的，并行 编译系统也对应了这三个阶段，不同的阶段面l 临的问题和解决的方法各不相同。 对向量机的而言，只有最内层循环可以向量化，所以相对简单。向量化的主要 主要方法是数据流分析加并行变换。这一阶段实验性程序是一些被称为k e r n e l 的程序。向量化技术已经比较成熟。 对s m p 而言，由于执行并行循环需同步，有时还会引起数据在不同处理机 的c a c h e 中迁移，因此会有较大的额外开销，这时我们希望并行执行的计算 量越大越好，计算量越大则额外开销的比重也就越小，从而并行化的效果越佳。 因此一般我们尽可能选择外层循环进行并行化。显然，并行化和向量化是两种 第6 页共4 5 页 第一章引言 完全不同的技术，简单的向量化技术扩展( 即所谓的向量并行化技术) 对于s m p 收效甚微甚至有负作用。为了寻找有效的并行化技术，九十年代初i l l i n o i s 大学 的c s r d 小组展开了实验性研究工作，实验对象主要是p e r f e c tb e n c h m a r k 和一 些实际应用程序。这些程序大部分是实用程序的简化版或是模仿实用程序而编 写的，循环问的关系相对复杂，已不能一个循环一个循环单独分析，必须在一 个较大的范围内对程序进行分析。他们在分析了这些程序后指出：数组私有化、 归约识别、非线性递归标量识别、符号数据相关性分析和过程间分析是非常重 要的并行化技术。尽管实现这些新技术有很大难度，但通过一段时间的研究， 这些新技术大部分都得以实现。到九十年代中期，相继出现了i l l i n o i s 的p o l a r i s 、 s t a n f o r d 的s u i f 和我们研制的a f t 等s m p 的并行化编译系统。这些系统的并 行化效果有了明显提高，并行化编译的研究达到了一个新高潮。由于s m p 机器 上并行的几个线程之间通过共享内存通讯，而每个节点平均访存时间一样，且 和普通的单c p u 系统访存速度差不多，程序的m e m o r y 性能比程序的并行性对 程序总体性能的影响小得多。因此针对s m p 系统做并行优化编译时的重点是充 分挖掘串行程序的潜在并行性，考虑完并行性之后才会考虑每个节点的c a c h e 优化。 到了m p p 系统情况又有所不同。在m p p 系统中一个节点存取其它节点的 内存时需要通过网络通讯，其速度比存取节点局部内存要慢- n 两个数量级， 因此程序的通讯量对运行性能有很大影响，提高并行程序的数据局部性成为 m p p 并行化系统不可回避的问题和提高优化效果的重要途径。在针对m p p 系 统做并行化时，必须将开发并行性和提高数据局部性结合起来考虑，并在它们 之间做一定的平衡，必要时宁可牺牲并行性以减少大规模的数据通讯，使得程 序的运行性能达到最佳。九十年代初，以r i c e 大学为代表，开始了针对m p p 系统的并行化编译研究。在研究s m p 并行化编译技术时，如果需要分析一个程 序，还可以将整个程序分解为几个较大的子块进行分析；但是在研究m p p 并行 化编译技术时。如果我们需要分析程序，那么必须将整个程序作为一个整体来 进行分析，因此较s m p 的实验性工作而言，m p p 的实验性工作难度更大。针 对s m p 的并行化编译技术对m p p 而言是必不可少的，但这些技术对m p p 而言 还十分有限。目前m p p 的并行化编译现状令人不能满意，造成m p p 并行化编 第7 页共4 5 页 第一章引言 译研究停滞的原因是实验工作的停滞。m p p 的实验性程序大多是一些称为 k e r n e l 的程序，这些程序多为人工拼凑而成，一般不超过几百行代码，循环之 间没有多少逻辑联系，带有很浓的向量化味道。m p p 的实验性研究程序，本应 该对s m p 的研究程序有所超越，但是实际上却是一种退化。因此有必要展开新 一轮的实验工作，寻找适合m p p 的并行化关键技术。 1 3 2 o p e n m p 与m p i 自动转化工具 过去十几年里以服务器为代表的共享存储计算机走向了成熟，从事科学和 工程计算的用户逐步将他们的传统软件移植到了共享存储的并行计算机上，成 为o p e n m p 程序。o p e n m p 在传统的串行程序中加入编译指导命令( o p e n m p d i r e c t i v e ) ，告诉编译器相应区域的数据属性和语句执行方式，指导编译器产生 合适的并行代码。由于s m p 系统共享主存，o p e n m p 使用共享变量作为通讯方 式，每个并行执行的线程都可以看到共享变量。这样线程间通讯体现于对同一 个共享变量的读写，不必使用显式的通讯语句。另外o p e n m p 提供了不少同步 机制( 如锁机制，临界区语句等) ，使用起来很方便。因此，o p e n m p 编程相对 比较简单。在s m p 系统走向成熟的同时，大规模分布式计算机技术也在完善之 中，以机群为代表的m p p 系统逐步成为超级计算机的主流。m p p 系统的主流 编程方式为消息传递机制，m p i 是这种编程机制的代表。由于m p i 程序进程 间通讯需要调用m p i 通讯库来实现，且所有需要参加通讯的进程都必须同步； 另外由于m p i 是纯粹的多进程编程模式，所有的变量都是私有的，进程间通讯 只能通过显式地调用通讯语句来实现，所以m p i 程序比o p e n m p 程序难编和难 调试得多。 s m p 系统中并行的几个线程之间通过共享内存通讯，而每个节点平均访存 时间一样，且和普通的单c p u 系统访存速度差不多，程序的m e m o r y 性能比程 序的并行性对程序总体性能的影响小得多。因此针对s m p 系统做并行优化编译 时的重点是充分挖掘串行程序的潜在并行性。而m p p 系统访问非本地内层开销 极大，要想提高程序效率必须同时考虑程序的并行性和数据的局部性，并在这 两者之间做一定的平衡。考虑程序的并行性已是一个困难的问题，再加上提高 第8 页，共4 5 页 第一章引言 数据局部性这一个非常困难的问题，使得针对m p p 程序的优化非常难做。 为了解决m p p 系统编程和调试困难的问题，设计人员实现了分布式共享存 储多机系统，这种系统在纯粹的分布式存储多机系统上添加复杂的硬件来维护 全局地址空间以及c a c h e 一致性。o p e n m p 程序在这些系统上也能取得较好 效果。但这种系统的成本很高且可伸缩性较差，随着系统规模的增大其效率会 降低。除了使用硬件还可以用软件在纯粹的分布式主存多机系统上实现共享存 储，代表系统有中科院的j i a j i a 和国外的t r e a d m a r k 。在这种软件的支持下 o p e n m p 程序也能不加改变就可以运行。但这种技术的缺点在于不能充分利用 系统的硬件性能。无论是使用硬件还是使用软件实现共享存储，用户都很难对 这种系统上的o p e n m p 程序做进一步优化因而难以最大限度地挖掘程序的潜在 效率。 o p e n m e 程序已经包含了足够的并行性信息( o p e n m p 的d i r e c t i v e 语句说 明了数据的属性和语句的并行执行方式) 。如果能充分的利用这些并行性信息， 那么在为m p p 系统编写和优化m p i 程序时只要把重点放在提高数据局部性上 就可以了，这无疑会大大减少工作量和工作的难度。况且现在已积累了大量的 o p e n m p 程序，而s m p 系统上的并行化编译技术也比较成熟，大多数s m p 系 统上的并行化编译器都可以把串行程序变为o p e n m p 程序，所以o p e n m p 转变 为m p i 可以充分利用已有的大量软件资源。另外，把o p e n m p 转化为m p i 不 仅可以在转化过程中做一定的优化而且可使用m p i 性能测试工具对得到的m p i 程序做迸一步调试和优化。但是o p e n m p 和m p i 是完全不同的编程模式，它们 之间没有一一对应的关系，手工将o p e n m p 转化为m p i 很容易引入并发程序开 发中常见的错误，对今后的调试工作带来极大麻烦。况且考虑数据的局部性对 程序改写人员的要求极高，让程序员掌握这么专业的技术代价太大且没有必要。 因此最好的途径是开发将o p e n m p 自动转化为经过优化的m p i 程序的自动化编 译工具。 由于o p e n m p 程序已经很清楚地说明了程序的并行化信息，开发将o p e n m p 转化为m p i 的自动化工具所要用到的关键优化技术是提高数据的局部性。a f t 是我所自主研发的并性化编译器，它能够将串行f o r t r a n 程序自动转化为 o p e n m p 格式的并行f o r t r a n 程序。我们在原来的a f t 基础上又增加了将 第9 页，共4 5 页 第一章引言 o p e n m p 格式的f o r t r a n 程序转化为经过优化的m p i 格式的f o r t r a n 的功能模块。 本文主要介绍这个功能模块的实现方法。本文的结构大致如下：首先介绍了将 o p e n m p 转化为m p i 的基本方法，然后介绍a f t 提高数据局部性的主要算法。 第1 0 页，共4 5 页 第二章基本转化方法 第二章基本转化方法 2 1 0 p e n m p 与m p i 的主要区别 虽然o p e n m p 与m p i 都是并行编程规范，但它们面向的对象不同，编程模 式也不同，是完全不同的两种编程标准。这主要体现在以下几点： 夺o p e n m p 面向s m p 结构的机器，采用多线程执行模式，线程间共享地址空 间，通过共享变量通讯，共享变量为所有线程公有。m p i 面向分布式存储 结构的机器，采用多进程执行模式。每个进程都有各自独立的地址空间， 根本没有共享变量的概念，所有的变量都是私有的。进程间交换数据需要 显式的通讯，且涉及到的进程都需要参与同步。 夺同步的实现方式不同。在o p e n m p 中有c r l l l c a l 和a t o m i c 编译指导命 令，b a r r i e r 和l o c k 库函数，通过这些命令和库函数实现多线程间的同 步。在m p i 中没有临界区和l o c k 函数，只能通过阻塞的点对点通讯实现 类似功能。 夺o p e n m p 程序在执行期间遇到并行区时由主线程创建其它线程，退出并行区 时主线程等待其它线程结束并将它们销毁。m p i 程序则很难动态的创建进 程，一般情况下，所有进程存在于整个程序运行周期。 夺编程模式不同。o p e n m p 通过在程序中加入编译指导命令( d i r e c t i v e ) 说明 数据属性和代码执行方式，具体实现完全交给编译器做。m p i 程序所有的 执行细节都需要程序本身体现，进程间通讯需要显式调用m p i 提供的库函 数。 由此可见o p e n m p 与m p i 之间没有一一对应关系，要想把o p e n m p 程序转 化为m p i 程序必须首先处理这些不同点。 2 2 a f t 将0 p e n m p 转化为m p i 的总体流程 图4 说明了a f t 将o p e n m p 转化为m p i 的总体流程。a f t 读入o p e n m p 格 式的f o r t r a n 程序，经分析后将它转化为a f t 系统的原始内部表示( r a w l r ) ， 第1 l 页共4 5 页 第二章基本转化方法 r a w l r 是对o p e n m p 格式的f o r t r a n 程序最原始的内部表示方法，o p e n m p 编程 图4 a f t 将o p e n m p 转化为m p i 的总体流程图 规范和f o r t r a n 语言中各种特殊的语法成分都可以表示出来。然后a f t 对得到 的r a w l r 做规范化( c l e a n u p ) ，消除f o r t r a n 程序中一些特殊的、非规范的成 分。规范化包括e n t r y 语句消除、s a v e 变量消除、特殊g o t o 语句变形、i f 语句变形、循环语句规范化以及程序结构化等。其中最主要的功能是程序结构 化，它可以将非结构化程序变换为结构化程序，从而提高了分析的效率，并为 语义分析创造了条件。经过规范化后原始的内部表示转换为规则的内部表示 ( i r ) ，这种表示较之原始内部表示更加简单、规范、易于处理。然后a f t 在 得到的规则i r 上做分析和变换，根据o p e n m p 的语义将它转换为等价的体现 m p i 语法的i r ，最后u n p a r s e 该i r ，输出m p i 格式的f o r t r a n 程序。 a f t 指定进程号为0 的进程( 简称0 进程，后文同) 执行串行区代码，并 行区由多进程模拟多线程并行执行。绝大多数支持o p e n m p 的f o r t r a n 编译器不 支持并行区嵌套，将内层并行区串行执行( 包括i n t e l 的i f c 编译器) ，这是因为 一方面支持并行区嵌套比较麻烦，另一面并行区嵌套对提高科学计算程序的性 能没有帮助。a f t 也是如此，内层并行区由遇到它的进程串行执行。 2 3 a f t 将o p e r t m p 转化为m p i 的基本方法 夺实现共享变量 在o p e n m p 中多线程共享地址空间，共享变量为所有线程公有。一个线程 第1 2 页，共4 5 页 第二章基本转化方法 更新共享变量时不需要通知其它线程且一个共享变量的更新能立刻被所有线程 看到。因此o p e n m p 程序中有数据相关的线程间的通讯体现于它们对同一共享 变量地读写，它们之间不需要显式通讯语句。在m p i 中所有申明的变量在每个 进程中都有一个副本，进程各自的地址空间都是私有的，有数据相关性的进程 间的通讯只能显式地调用m p i 通讯库来实现。然而某些o p e n m p 程序不能在编 译时确定程序运行时共享变量被各线程访问的情况( 例如在一个并行区中每个 并行执行的线程访问的共享变量由条件语句确定，其条件又决定于输入，且这 些线程间可能有相关性) ，这种o p e n m p 程序转化为m p i 格式时不仅不能确定 是否需要显式的通讯，也无法确定通讯语句的写法。为了保证这种情况也能正 确处理，必须首先实现共享变量。 a f t 用0 进程专门管理共享变量，所有对共享变量的访问都转化为对这个 进程的相应的私有变量的访问。这个进程平时负责执行串行区代码，当第一次 遇到并行区时成为数据服务器，直到退出并行区。由于0 进程必须知道其它进 程的具体请求内容( 也就是哪个进程对哪个共享变量做了哪种请求) ，才能做出 正确的反应，所以凡是要读写共享变量的进程必须先发一消息告诉0 进程它具 体的请求内容，然后再执行m p i 通讯语句完成对共享变量的读写。0 进程非阻 塞地从各进程收取请求，一旦收到一个请求则根据其内容做出相应反应，完成 某个进程读写共享变量的通讯操作，然后再补上从这个进程接收请求的操作。 退出并行区时其它进程向0 进程发q u i t 消息，0 进程收到来自其它所有进程 的q u i t 消息之后退出服务，执行紧接着的串行区。0 进程的主体代码如下： 件t h ec o d eo f0p r o c e s sd a t as e r v e r i d oi = 1 n u m p r o c s 。- - 1# n u m p r o c s 变量存放进程总数 c a l l m p i j r e c v ( r e q _ f r o m _ p r o c _ i ) l l 轮询其它进程发出的请求内容 e n d d o d o w h i l e ( n u m q u i t s 。l t n u m p r o c s 1 ) n u m q u i t s 为e 发送q u n 消惑的进程 数 d o i = l 。n u m p r o c s l c a l l m p i t e s t ( r e q _ f r o m _ p r o c _ i ) 是否a 收翻进程i 发出的消息 i f ( r e q _ f r o m _ p r o c _ i i s r e c e i v e d ) t h e n 如果b 收勃 i f ( r e q _ f r o m _ p r o c _ i i sq u i t ) t h e nf f 羞收蓟q u h 消息 第1 3 页，共4 5 页 第二章基本转化方法 n u m q u 旧s 2 n u m q u 旧s1 l j e l s e c a l l m p i s e n d m p i r e c v ( d a t a j 硒q u i r e d _ b yp r o c e s s _ 1 ) c a l l m p i i r e c v ( e e q f r o m _ p r o c _ i ) 磅卜一个瓿该进程收消息的操作 e n d i f e n d i f e n d d o e n d d o pt h ec o d eo t h e rp r o c e s s e se x e c u t ew h e nv i s r r i n gs h a r e dd t a f c a l l m p l 一s e n d ( r g q ) c a l lm p is s e n d ，m p ir e c v ( d a t a ) + t h e c o d e o t h e r p r o c e s s e s e x e c u t e w h e n q u i i t i n g p a r a l l e l r e g i o n v c a l lm p i s s e n d ( r e q ) l i l a c r e q 为a u r r 值得注意的是，m p i 提供多种通讯模式，这些通讯模式之间存在着细微的差别， 必须小心选择收发消息所使用的的m p i 库函数，否则会产生错误。为了保证能 从各个进程监听请求消息且不引起不必要的阻塞，0 进程必须使用非阻塞地方 式从其它各个进程收消息，所以使用m p ii r e c v 函数。m p ii r e c v 函数向系 统提交一个r e c v 请求，不等实际收到消息内容就可以继续往下执行，同时该 函数相联一个状态旬柄，通过查询该句柄就可以知道消息内容有没有收到。 非0 进程在读某个共享变量的时候，应该使用阻塞性操作m p ir e c v 访问 0 进程，这就保证在执行下一条语句之前所需数据已经读到相应的存储单元。 同理，非0 进程在写某个共享变量时也应该使用阻塞性操作。值得注意的是， 阻塞的s e n d 操作有两种：m p is s e n d 和m p is e n d 。这两种阻塞性的s e n d 操作有细微的区别，m p is e n d 操作结束意味着需要s e n d 的内容己被复制到 m p i 系统的缓冲区内，但并不保证对方已收到消息。而m p is s e n d 操作结束 则保证需要发送的内容已被对方接收到。非0 进程在写某个共享变量时应该使 用m p is s e n d 函数而不能使用m p is e n d 函数，否则会产生错误。考虑如下 第1 4 页，共4 5 页 第二章基本转化方法 程序段： i f ( p i d e q 1 ) t h e n c a l l m p 一s e n d ( r e q ) c a l l m p l 一s e n d ( d a t a ) e n d i f ( p i d n e 0 ) t h e n c a l l m p i _ b a r r i e r ( m p ic o m m _ w o r _ k ) e n d i f i f ( p i d e q 2 ) t h e n c a l l m p i _ s e n d ( r e q ) c a l l m p i _ r e c v ( d a t a ) e n d 该程序的本意是1 号进程发送某个数据给0 号进程，再由2 号进程把1 号更新 的数据从0 号进程中读出来。m p i _ c ! o m mw o r k 是包含进程1 和2 的通讯子， c a l lm p ib a r r i e r ( m p ic o m mw o r k ) 的目的是保证进程2 的r e c v 操 作在进程l 的s e n d 操作之后。但是这段程序并不能达到预想的效果。因为进 程1 的c a l lm p is e n d ( d a t a ) 语句完成的时候只是说明了需要s e n d 的 数据已经送到了系统缓冲区并不表示0 号进程已经开始接收数据。因此虽然有 同步操作保证2 号进程的r e c v 操作在1 号进程的s e n d 操作之后，但不能保 证0 进程处理l 进程请求在处理2 进程请求之前，因此有可能2 号进程收到的 是未经l 号进程更新的老数据。如果把s e n d 改s s e n d 操作就不会出现这种 情况，因为s s e n d 操作结柬时就能保证0 进程已收到1 号进程发的数据，而 同步操作保证了2 号进程的r e c v 操作在1 号进程的s e n d 操作之后，所以l 号进程一定能收到更新的数据。 由于共用同一个申明的变量在各进程中的副本的地址各不相同，所以其它 进程不能以地址的形式通知0 进程它们所要读写的共享变量。为解决这个问题 我们在0 进程里保存一张将变量名转换为该变量在0 进程里的地址的h a s h 表。 0 进程在启动服务前初始化h a s h 表，将所有在多进程并行执行的时候需要用到 的共享变量的名称和其在0 进程里的地址记录到该h a s h 表中( f o r t r a n 中没有地 第1 5 页，麸4 5 页 第二章基本转化方法 址，但m p i 提供了m p i 函数，可做到这一点)。其它进程在访_get_address 问共享变量时先把需要访问的共享变量的名字传给0 进程，0 进程根据变量名 查1 l a s h 表找到该变量在0 进程中的地址，使用该地址就可以得到该共享变量的 值。 夺正确处理带有o p e n m p 编译指导命令的函数和过程 o p e n m p 允许在函数和过程( 下文统称函数) 中包含o i ) e n m p 编译指导命 令，它们能决定函数中相应语句的执行方式( 例如从串行区调用一个包含 p a r a l l e l 命令的函数，主线程在执行到函数中该命令处会创建出多线程并行 执行该命令标示出的代码段) 。但m p i 规范很难动态创建进程，一般情况下所 有进程存在于整个程序运行周期。要想使多个进程共同处理函数中的代码和数 据的唯一的办法是让多个进程共同进入函数。因此0 进程在执行串行区时其它 进程也执行串行区，遇到条件判断时( 比如i f , w h i l e 等语句) 0 进程向其它进 程广播它算出来的条件的值，这样就能保证所有进程都在恰当的时候进入同一 个函数。非0 进程在执行串行区时所有变量都访问自己的私有拷贝，虽然可能 算错但不影响程序正确性。 函数调用点所处的并行区层次会影响函数中语句的执行方式。由于同一个 函数可能在不同的并行区层次里被调用，所以在编译时无法确定函数里语句所 处的具体的并行区层次。为此a f t 按照并行区层次对语句执行方式的不同影响 将每个函数u n p a r s e 成三个版本：在串行区被调用的版本，在第一层并行区被调 用的版本和在大于一层并行区被调用的版本。a f t 在t m p a r s e 时根据函数调用 点所处的并行区层次调用相应版本的函数。通过上述两种方法，a f t 可以确保 正确处理带有o p e n m p 编译指导命令的函数。 夺确定变量属性 在o p e n m p 中有一类专门和o p e n m p 结构联合使用的语句，用以说明在这 些结构中变量的属性。这类语句主要有：p r i v a t e 、f i r s t p r i v a t e 、 l a s t p r i v a t e 、r e d u c t i o n 和d e f a u l t 。若存在结构嵌套的情况，内层结 构的属性说明语句会屏蔽外层结构的属性说明语句，显然这满足栈式管理方式。 a f t 在u n p a r s e 时在变量表中为每个变量维护一个属性堆栈同时维护一个全局 第1 6 页，共4 5 页 第二章基本转化方法 的d e f a u l t 堆栈( 用来存放变量的d e f a u l t 信息) 。当a f t 遍历语法树遇 到属性说明语句时将变量属性和d e f a u l t 信息压入相应栈中。由于a f t 将内 层并行区串行化，若嵌套的多层并行区中有一层将某个变量的属性设置为私有， 更内层的并行区中无论如何设置该变量的属性在运行时都只会访问本进程的私 有拷贝，因此a f t 认为这种变量的属性实际上是私有的，a f t 在将变量属性压 栈时会根据当前栈顶的值做相应的调整：若栈顶为p r i v a t e 则无论变量的说明 属性如何都一律压入p r i v a t e 属性，若栈顶为s h a r e d 则压入变量的说明属 性。a f t 在u n p a r s e 的过程中每当退出一个o p e n m p 结构时从各个变量的属性 栈和d e f a u l t 栈里弹出进入该结构时压入的属性。 o p e n m p 中几种主要结构的转化 p a r a l l e lr e g i o n 结构 在串行区遇到该结构时0 进程启动数据服务，其它进程并行执行该结构内 的代码，所有共享变量都从0 进程取得。我们不支持并行区嵌套，内层并行区 由进入这个结构的进程串行执行。 w o r k s h a r i n g 结构 包括o m pd o 和o m ps e c t i o n s 。若该结构处于串行区内则该结构里的 代码由0 进程做。若该结构处于第一层并行区内，此时0 进程作为数据服务器， 其它进程分做该结构的代码。若处于内层并行区，则该结构的代码由进入这个 结构的进程串行执行。 c o m b i n e dr u i a l l e lw o r k - - s h a r i n g 结构 该结构为以上两个结构的联合。在串行区遇到该结构时0 进程启动数据服 务，其它进程分做该结构内的代码，所有共享变量都从0 进程取得。在并行区 遇到该结构时由进入这个结构的进程串行执行。 实现l o c k 函数和临界区 m p i 不提供l o c k 函数，只能通过阻塞式的点对点通讯实现类似功能。a f t 在实现共享变量的基础上使用消息队列和阻塞的m p l s e n d m p i _ r e c v 操作 实现了和o p e n 船的l o c k 函数相同功能的m p i 函数。由于在串行区和内层串 第1 7 页，共4 5 页 第二章基本转化方法 行化并行区中l o c k 函数不起作用，a f t 在i r 转化阶段会删除这些冗余的 l o c k 函数：第一层并行区内的l o c k 函数则被替换为实现出来的相同功能的 m p i 函数。 在进入第一层并行区时，0 进程除了管理共享变量还为每个l o c k 变量维 护一个请求队列。每个要执行和l o c k 相关的操作的进程使用m p l s e n d 函数 向0 进程发送请求消息，并使用m p ir e c v 函数等待0 进程的回答( 由于 m p ir e c v 函数是阻塞性的，它将一直睡眠到0 进程给它发送消息) 。0 进程从 其它各个进程接收请求，若收到l o c k 请求则将发送该请求的进程在所请求 l o c k 变量对应的请求队列里按f i f o 方式排队：若收到解锁请求则先删除队 列头然后向排在请求队列头的进程发送消息允许其进入临界区。下面列出0 进 程在收到其他进程l o c k 、u n l o c k 和t e s t l o c k 请求时所做的主要动作： 1 若收到一个来自x 进程的l o c k ( v a r ) 请求则依次做以下动作： 找到l o c k 型变量v a r 所对应的请求队列，若该队列为空则把请求进程的 进程号x 记录到该请求队列中并给请求进程发一个消息允许它进入临界区 若队列不为空，则把请求进程的进程号记录到请求队列尾部 若收到一个来自进程x 的u n l o c k ( v a r ) 请求则