（计算机软件与理论专业论文）基于骨架的并行编程环境中结构骨架库的研究.pdf

摘要 随着科学、技术和社会经济的发展，人们对计算机处理能力提出了更高的要 求，特别是在基因工程、气象等大规模科学计算领域。理论上，问题的并行求解 是一种有效的解决方案。然而，并行程序开发是比较困难的，其根本原因在于并 行计算机体系结构的多样性。 为了简化并行程序的开发，我们提出了一种基于两级抽象的三层并行编程模 型，分别为抽象语言层、并行语言层和实现层。其中，抽象语言层属于设计阶段， 并行语言层和实现层属于实现阶段。该模型可以将并行程序开发过程中的创造性 工作和非创造性工作区分开来，创造性工作在抽象语言层由编程者完成，非创造 性工作在并行语言层和实现层由机器完成，可以有效地降低并行程序编程难度和 提高程序的开发效率。我们还对其支撑平台进行了有益的探索，骨架库是我们基 于骨架的编程系统中的重要组成部分，骨架库的研究对于系统的实用性、可编程 性和可扩展性方面具有重要作用。 本文主要工作是对骨架库中的结构骨架进行深入的研究，主要包括以下几个 方面的内容：( 1 ) 提出了一种并行骨架的抽象形式，通过对其进行扩展，可以形 成各种结构骨架，如s i n g l e t o n 骨架、f a r m 骨架、p i p e li n e 骨架、t a s k q u e u e 骨架。这样，一方面可以使得并行结构骨架之间的相互组合变得容易；另一方面 也为算法骨架的实现提供了必要的条件。( 2 ) 对系统底层通信库m p i 的调用接口 进行了简化，以方便编程者进行性能调整。同时也使得编程者对特定骨架的通信 特性有更清晰的认识。( 3 ) 对骨架描述方法进行了研究，提出了一种基于x m l 的通用骨架描述方法，并使用该方法对现有结构骨架进行了统一描述，以便更好 地指导编程者，使其能较为准确地选择、比较和使用并行结构骨架。( 4 ) 在 p c 机群和m p i c h 组成的并行计算平台上对两个经典实例一一数组求和及矩阵一 向量乘法问题均进行了基于m p i 、基于结构骨架的并行实现，并对它们的性能进 行了评价。运行结果表明，基于结构骨架的并行程序开发方法在基本不损失性能 的同时，降低了并行程序的开发难度，提高了并行程序的开发效率。 关键词：骨架；并行结构骨架；并行程序设计；并行编程环境；x m l ；c + + 模版 a b s t r a c t w i t ht h e d e v e l o p m e n t o fs c i e n c e ，t e c h n o l o g ya n ds o c i a l e c o n o m y , t h e r e q u i r e m e n to fc o m p u t i n gp o w e ri si n c r e a s i n g l yd e m a n d e d ，p a r t i c u l a r l yi nl a r g e - s c a l e s c i e n t i f i cc o m p u t i n g ，s u c ha sg e n o m i ce n g i n e e r i n ga n dw e a t h e re t c t h e o r e t i c a l l y , f i n d i n gp a r a l l e ls o l u t i o nf o rp r o b l e m si sa ne f f e c t i v es c h e m e h o w e v e r , d e v e l o p i n g p a r a l l e lp r o g r a mi sq u i t ed i f f i c u l tb e c a u s eo ft h em u l t i p l i c i t yo fp a r a l l e lc o m p u t e r a r c h i t e c t u r e t os i m p l i f yp a r a l l e lp r o g r a md e v e l o p m e n t ，ap a r a l l e lp r o g r a m m i n gm o d e lb a s e d o nt w o l e v e la b s t r a c t i o nh a db e e np r o p o s e d i ti sd i v i d e di n t ot h r e et i e r s ，a b s t r a c t l a n g u a g e ，p a r a l l e ll a n g u a g ea n di m p l e m e n t a t i o nt i e r t h ef i r s tb e l o n g st od e s i g ns t a g e ， o t h e ri m p l e m e n t a t i o ns t a g e s c r e a t i v ea n dn o n - c r e a t i v ew o r kc a l lb e s p l i t i n d e v e l o p i n gp a r a l l e lp r o g r a m s ，a n dt h ef o r m e ri sd o n eb yp r o g r a m m e r si na b s t r a c t l a y e r , t h el a t t e ri sd o n eb ym a c h i n ea u t o m a t i c a l l y s ot h ee f f i c i e n c yo fp r o g r a mi s i m p r o v e dg r e a t l y i na d d i t i o n , t h es u p p o r t i n gp l a t f o r m h a sa l s ob e e n e x p l o r e d s k e l e t o nl i b r a r yi sa ni m p o r t a n tc o m p o n e n to ft h es k e l e t o nb a s e dp r o g r a m m i n g s y s t e m ，t h u st h es t u d yo ni tp l a y sa ni m p o r t a n tr o l ei na p p l i c a b i l i t y , p r o g r a m m a b i l i t y a n de x p a n d a b i l i t y a r c h i t e c t u r es k e l e t o n si nt h es k e l e t o nl i b r a r ya r es t u d i e dd e e p l yi n t h i st h e s i s t h em a i nc o n t e n t sa r el i s t e da sf o l l o w s ：f i r s t ，a na b s t r a c tp a r a l l e l s k e l e t o ni sp r o p o s e d ， a n da r c h i t e c t u r es k e l e t o n ss u c ha s s i n g l e t o ns k e l e t o n ，f a r ms k e l e t o n ，p i p e l i n e s k e l e t o n ，a n dt a s k q u e u es k e l e t o nc a nb ep r o d u c e db a s e do ni t t h u s ，i tc a nm a k e c o m b i n a t i o no fp a r a l l e la r c h i t e c t u r es k e l e t o n se a s i l y , a n da l s op r o v i d et h en e c e s s a r y c o n d i t i o nf o rr e a l i z i n ga l g o r i t h ms k e l e t o n s s e c o n d , t h ei n t e r f a c e so fb o t t o m c o m m u n i c a t i o nl i b r a r yo fs y s t e ma r es i m p l i f i e di no r d e rt oa d j u s tp e r f o r m a n c ef o r p r o g r a m m e r s a tt h e s a l t l et i m e ，i ti sh e l p f u lf o rp r o g r a m m e r st oh a v eac l e a r u n d e r s t a n d i n g o fc o m m u n i c a t i o nc h a r a c t e r i s t i co f s k e l e t o n t h i r d ，s k e l e t o n d e s c r i p t i o ni ss t u d i e d ，a n dag e n e r a lm e t h o do fs k e l e t o nd e s c r i p t i o nb a s e do nx m l i s p r o p o s e d t h i sd e s c r i p t i o nc a nb e t t e rg u i d ep r o g r a m m e r t os e l e c t ，c o m p a r ea n du s e a r c h i t e c t u r es k e l e t o n s f i n a l l y , t h ep l a t f o r mb a s e dp cc l u s t e ra n dm p i c hf o rp a r a l l e l c o m p u t i n g i s b u i l t ，a n dt w ot y p i c a li n s t a n c e s ，t h es u mf o r t h ea r r a ya n dt h e m u l t i p l i c a t i o n f o rm a t r i x v e c t o r , a r ei m p l e m e n t e db a s e do nm p ia n da r c h i t e c t u r e s k e l e t o n s p e r f o r m a n c ee v a l u a t i o ni sp r e s e n t e d t h er e s u l ts h o w st h a t p a r a l l e l p r o g r a m m i n gm e t h o db a s e d o na r c h i t e c t u r es k e l e t o n si m p r o v e sp r o g r a m m a b i l i t ya n d e f f i c i e n c yw i t h o u tl o s so fp e r f o r m a n c eb a s i c a l l y k e yw o r d s ：s k e l e t o n ；p a r a l l e la r c h i t e c t u r es k e l e t o n ；p a r a l l e lp r o g r a m m i n g ；p a r a l l e l p r o g r a m m i n ge n v i r o n m e n t ；x m l ；c + + t e m p l a t e 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文e l , 不包含其他人已经发表或撰写过的研究成果，也不包含 为获得或其他教育机构的学位或证书而使用过的材料。与我一同工作 的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表 示谢意。 学位论文作者签名：签字日期：年 月 日 学位论文版权使用授权书 本学位论文作者完全了解江西师范大学研究生院有关保留、使用 学位论文的规定，有权保留并向国家有关部门或机构送交论文的复印 件和磁盘，允许论文被查阅和借阅。本人授权江西师范大学研究生院 可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采 用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名： 签字日期：年 月 日 导师签名： 签字日期：年月 日 基丁骨架的并行编程环境中结构骨架库的研究 第一章绪论 1 1 研究背景和意义 随着科学、技术和社会经济的发展，人们对计算机处理能力提出了更高的要 求，特别是在2 l 世纪人类所面临的基因工程、全球气候准确预报、海洋环流循 环等大规模科学计算领域。虽然它们对计算提出了巨大的挑战，但也为并行计算 和高性能计算提供了巨大的应用空间n 嵋1 。随着超级并行计算机的飞速发展，尤 其是机群式超级计算机提供越来越方便的并行计算资源，如何充分利用这些并行 计算机资源，已对并行计算及其应用构成严峻的考验。 从1 9 7 2 年世界上诞生的第一台并行计算机i l l i a ci v 至今，已经研制出了 多种体系结构的并行计算机，如单指令流多数据流s i m d 计算机、并行向量处理 机p v p 、对称多处理机s m p 、大规模并行处理机m p p 、i 作站机群c o w 和分布式 共享存储d s m 多处理机等。然而并行计算机体系结构的多样性，增加了并行程序 的开发难度，进而影响了并行计算的应用范围。 以高性能计算为平台的大规模并行计算，虽然在科学与技术的众多领域取得 了一些研究成果，但我们必须清醒地认识到目前高性能计算领域的现状，高端应 用软件的开发和高效并行算法的研究与高端计算机的发展产生了严重的失衡。这 必将导致目前高性能计算系统并不能充分利用并行计算机的硬件资源。同时，对 并行程序的设计和开发也带来了很大的困难。这些都使得并行程序的编写更多地 局限于计算机学科的科学和工程技术人员，很难被广大应用人员和程序开发人员 所掌握。 并行程序的开发与传统的串行程序的开发一样，对于一个应用问题，必须设 计出相应的算法，而算法的设计都是建立在特定的计算模型之上，也就是算法要 适合该计算模型。然而，两者最大的不同之处是，并行计算机存在多种体系结构， 因而也存在多种计算模型。而串行计算机的体系结构是统一的，也就是“冯诺 伊曼模型”。因此，对于并行程序的开发，可能会使得某一体系结构下的并行程 序不能运行在另一种体系结构的并行机上，或者会导致很大的性能损失，因而开 发的难度较高，程序的可移植性较差。串行程序的开发不存在这个问题，所以开 发难度相对较低，程序的可移植性较好。此外，与串行程序的开发相比，并行程 序的开发更需要相应的方法学及相关辅助工具的支持。虽然关于这方面的研究比 较多，但是依然不成熟。总之，如何最大程度的降低并行程序开发的难度，提高 硕士学位论文 并行程序的开发效率，同时又对性能不能造成太大的损失，是我们必须认真面对 的紧迫任务。 通常，并行程序的开发过程是首先建立现实问题的并行求解模型，再针对该 模型设计高效的并行算法，对该问题的求解进行精确描述和定量分析，对各种算 法进行性能上的比较，最后通过并行程序设计，实现问题和并行机的结合。可见， 并行程序的开发重点应放在对问题的并行求解上，而不是一些与问题具体实现的 细节上。因此，如何让用户更多的关注问题本身，隐藏底层的实现细节，并且可 以充分利用顺序程序开发中的成功经验、方法和工具，是我们关注的重点。 在前期研究h 叫町的过程中，我们提出了一种基于骨架( s k e l e t o n ) 的并行程序 开发方法和模型。本文是对前期工作的继续和完善，重点对基于骨架的并行编程 环境中结构骨架库进行深入的研究，旨在不断提高系统的实用性、可扩展性及可 移植性等，简化并行程序的开发，提高并行程序的开发效率。 1 2 并行程序开发方法概述 并行应用程序的开发是一件困难和易错的工作。如何提高并行应用程序的可 编程性，适应更多的应用问题，计算机科学工作者对并行程序开发方法进行了大 量的研究。根据程序开发过程所经历的不同阶段，可以把并行程序开发方法的研 究分成三个领域：面向问题的方法、面向算法的方法和面向语言的方法n 5 1 。 1 2 1 面向问题的并行程序开发 面向问题的方法是从问题的规范描述出发开发并行程序。它与顺序程序开发 的出发点是相同的，只是在开发过程中要考虑问题潜在的并行性开发、并行求解 和如何实现其并行性的问题。简而言之，与顺序程序的开发类似，一种途径是采 用形式化的程序综合与推导的方法，使用一系列的语义转换规则，将规范描述语 言所描述的问题逐步求精，从而得到程序设计语言所表示的可执行程序。然而， 并行程序的形式化开发，与顺序程序相比要复杂得多，具有代表性的并行程序的 验证和开发系统模型有c s p n 6 1 ，u n i t y n7 培1 ，a c t i o ns y s t e m n 刚等；另一种途径是 采用并行算法的设计和实现技术，通过在某种并行计算模型上设计出解决特定问 题的并行算法，然后实现该并行算法，将其映射为可在特定并行计算机上执行的 并行程序啪1 。 1 2 2 面向算法的并行程序开发 面向算法的方法既不是指顺序算法的并行实现，也不是单一地考虑某一个问 题的算法设计，而是研究问题的求解规律，即算法设计过程的规律性，根据现实 世界算法问题所固有的行为上的相似性对算法问题进行分类，使得同一类中的所 有算法问题的求解符合某种特定的设计模式。这样，通过对设计模式的并行性开 2 基丁罱架的并行编稃环境中结构骨架库的研究 发，就能解决一类问题的并行程序开发心“2 2 1 。 1 2 3 面向语言的并行程序开发 面向语言的方法可分为两类。一类是显式并行性开发方法，即研究并行的语 言或模型，通过在语言或模型中提供一些并行性定义的机制，程序设计人员使用 这些机制来刻画并实现算法问题中的并行性。对并行语言与并行模型的研究，包 括传统的p r a m ，p v m ，m p i 等曾在并行计算领域占主体地位的低层次模型， h a s k e l l 、u n i t y 等高抽象程度的模型，b s p 、l o g p 等集中了大量研究工作的中等 抽象程序的模型等。2 5 3 。另一类是隐式并行性的开发，即通过在语言的编译器中 加入识别程序中所存在的可并行单位的功能，使得经编译后产生的代码为并行的 代码矧。 1 2 4 三类方法的比较 在对并行程序开发方法的研究中，更多的研究集中于面向问题的方法和面向 语言的方法，而对面向算法的方法研究较少。到目前为止，尽管各个领域都取得 了一些成果，但尚未有一种公认的切实可行的并行程序开发方法。 通过形式化方法推导程序一直是程序设计的理想，国内外都非常重视这方面 的研究，尽管这一方法在理论上已日益成熟，但真正应用起来往往仅限于开发一 些小程序，而且其方法难以为一般的用户所运用，而并行程序的复杂性又增加了 形式化开发的难度，因此，并行程序的形式化开发离实际的应用仍有一段距离。 对于并行算法设计方法的研究，尽管现已开发了许多问题的并行算法，但由 于并行算法设计的复杂性，至今尚无一套普遍适用的系统的设计方法。在进行并 行算法的设计时，一方面要考虑问题本身的特性，另一方面还要考虑底层的并行 计算机的特性，更为严重的是在特定并行模型下设计的并行算法往往只能实现于 某一类特定结构的并行计算机，并获得较好的性能，从而使得算法的通用性差， 对同一问题需要针对不同的并行计算机设计相应的并行算法。 代码的并行化编译一般要经过相关性分析、优化和代码生成三个阶段。它的 主要思想是通过对源代码中数据流和控制流的分析，寻找出一些不具有相关性的 片段，将它们并行化。这一方法从源代码出发，一开始就将变量等程序实现方面 的细节考虑进去，这些细节往往掩盖了问题本身具有的并行性，因此必然带来更 高的复杂性，而且，并行化编译面向的是细粒度的并行，程序效率难以提高，程 序并行化的程度也受到原顺序程序的局限，一个好的并行程序往往并非来源于一 个好的顺序程序。 显式并行化方法通过在语言或模型中提供并行性描述和实现的机制，而将并 行性开发的任务完全交给了程序员。由于缺乏系统的开发方法，从问题的求解到 硕十学位论文 并行实现的整个过程对程序员而言是一个复杂和困难的工作。而且，由于程序员 水平与风格的差异，软件的质量与效率往往难以得到保证。 面向算法的并行程序开发是一个相对研究较少的领域，从某种意义而言，它 也是一种隐式并行化的工作，但与并行化编译有本质的不同，它将并行化的工作 从语言一级提高到算法一级，减少了琐碎的实现细节的影响，而更关注算法问题 本身所固有的并行性，同时，通过对算法问题的分类与抽象，可以利用顺序算法 的设计经验，构造特定的算法结构模式，预先开发出其中的并行性，此时，程序 设计人员可以不必显式地进行并行性开发，从而简化了并行程序的开发过程，降 低了并行程序开发的复杂性，是一种切实可行的并行程序开发方法的研究途径。 1 3 并行编程环境 从编程的角度来看，并行编程环境为构建并行程序提供了基本工具、语言功 能和应用编程接口( a p i ) ，涵盖了并行程序的设计、编码、调试和性能调整等方 面。不同的体系结构，导致了并行编程模型及其支撑环境的多样性。与串行程序 开发环境相比，并行软件开发技术及开发环境极不完善，用户通常不能使用高层 抽象进行并行程序开发，仍需了解必要的硬件细节，再进行并行程序设计。显然， 要提供一种通用的并行开发环境是非常困难的事情，因为到目前为止还没有一个 统一的并行计算机体系结构，更不可能有统一的并行编程模型。 并行编程环境在并行程序开发过程中发挥着重要作用，一个好的并行编程环 境，可以对主流编程模型及开发语言提供较好的支持，从而简化程序的开发过程， 提高并行程序的开发效率和降低并行程序开发的门槛。 1 3 1 并行编程环境的分类 依据不同的分类标准，并行编程环境存在多种分类方法。根据所支持的编程 模型，主要分为消息传递的并行编程环境、共享存储的编程环境、数据并行的编 程环境。 ( 1 ) 共享存储的并行编程环境通常是基于线程级细粒度并行，仅被s m p 和 d s m 并行计算机所支持，可移植性较差。但是由于它们支持数据的共享存储，所 以并行编程的难度较小。 ( 2 ) 消息传递的并行编程环境通常是基于粗粒度的进程级的并行，几乎被 所有当前流行的各类计算机所支持，且具有较好的可扩展性。但是，消息传递的 并行编程只能支持进程间的分布式存储模式。因此，学习和使用消息传递并行编 程的难度均大于共享存储和数据并行这两种编程模式。 ( 3 ) 数据并行编程强调的是局部计算和数据选路操作，它比较适合于使用 规则网络、模板和多维信号及图像数据集来求解细粒度的应用问题。可被s m p 、 4 基丁- 骨架的并行编稃环境中结构骨架库的研究 d s m 、m p p 并行计算机支持，并且容易学习。其典型代表是h p f 。 根据程序员在并行开发过程中与编程环境的交互程度及系统所提供的语言 成分，大体上分为三类，分别为显式并行编程环境、隐式并行编程环境和半隐式 并行编程环境。 ( 1 ) 显式并行编程环境提供显式的并行处理原语，需要程序员在程序中处 理所有与并行实现有关的细节问题。典型的表现形式有，消息传递库p v m 和m p i 以及其它基于远程调用的并行实现技术等。 ( 2 ) 隐式并行编程环境主要通过并行编译器自动化技术，自动完成串行程 序到并行程序的转换。另外，还有基于函数和逻辑语言实现的并行编程系统。 ( 3 ) 半隐式并行编程环境所提供的编译器能够把语言中的一些指令语言翻 译成并行实现，同时又向程序员提供控制并行的显式成分，以达到性能调整的目 的。其实现形式有：基于并行语言的编程系统( h p f 、c c + + 、l i n d a 3 ) 、基于活 动对象的面向对象的并行编程系统( a b c + + 啪1 ，c h a r m + + 啪1 ) 、基于模板以及与其类 似技术实现的系统。 1 3 2 主流并行编程环境 在并行计算领域，存在多种不同的并行编程模型，最具代表性的有共享存储 模型、分布式存储模型及分布式共享存储模型。不同的编程模型使得各种编程环 境存在较大的差异。上世纪9 0 年代，出现了许多并行编程环境，但是占据主流 的并行编程环境是基于共享存储模型的o p e n m p 啪3 和基于分布式存储模型的 m p i 。 ( 1 ) o p e n m p 在共享地址空间结构中，由于所有的处理器都被连接到一个共享的内存单元 上，处理器在访问内存时使用相同的内存编址空间，因此，某一个处理器写入内 存的数据会立刻被其它处理器访问到。 对称多处理机( s m p ) 体系的发展和实践直接导致了1 9 9 7 年o p e n m p 标准的出 现，并且已经成为共享内存环境上多线程并行程序设计的标准。它基于现有的串 行语言，采用制导扩展的形式，提供功能强大的一组编译制导和库函数，提供 c c + + 和f o r t r a n 的接口。o p e n m p 的执行模式采用f o r k - j o i n 的形式( f o r k ，创 建新线程或者唤醒已有线程；j o i n ，即多线程的会和) 。并行区域是o p e n m p 语言 的基本结构，由主线程创建一组线程、启动并行执行，并行区域的结尾处有隐式 的b a r r i e r 同步。线程组中的每个线程执行并行域的动态范围内的语句序列。线 程的同步机制包括c r i t i c a l 、a t o m i c 、b a r r i e r 和m a s t e r 。o p e n m p 制导中提供 p r i v a t e ，s h a r e d 等子句的方式控制变量在不同线程之间的共享。任务分割的制 导结构有p a r a ll e lf o r d o 、p a r a ll e ls e c t i o n s 、p a r a ll e lw o r k s h a r e 和s i n g l e 。 硕- 十：学位论文 此外，o p e n m p 环境变量可以在程序执行中修改，比如线程数、循环的缺省调度 方式、嵌套并行的开关状态等。 o p e n m p 具有良好的可移植性，支持多种编程语言，包括f o r t r a n7 7 、f o r t r a n 9 0 、f o r t r a n9 5 以及c c + + ；同时能够支持多种平台，包括大多数的类u n i x 系 统以及w i n d o w sn t 系统( w i n d o w s2 0 0 0 ，w i n d o w sx p ，w i n d o w sv i s t a 等) 。 ( 2 ) m p i m p i ( m e s s a g ep a s s i n gi n t e r f a c e ) 是于1 9 9 4 年5 月发布的一种编程接口标 准，而不是一种具体的编程语言。该标准是由消息传递接口论坛 ( m e s s a g e p a s s i n gi n t e r f a c ef o r u m ) 发起讨论并进行规范化的。m p i 以库的 方式支持进程间的数据交换，提供f o r t r a n 和c c + + 的编程接口。在消息传递 的并行编程中，一组进程所执行的程序是用标准串行语言书写的代码加上用于消 息接收和发送的库函数调用。 在基于m p i 的编程模型中，计算是由一个或多个彼此通过调用库函数进行消 息收、发通信的进程所组成。在绝大部分m p i 实现中，一组固定的进程在程序初 始化时生成，一个处理器生成一个进程。这些进程可以执行相同或不同的程序( 也 就是对应的s p m d 或m p m d 模式) 。进程间的通信可以是点到点的，也可以是群体 操作。 目前，m p i 已成为可扩展并行系统上高性能并行程序设计的事实标准。但是， 由于消息传递编程模型抽象层次较低，程序员必须处理一些不必要的底层细节问 题，因此，学习入门难度高，开发效率低，且很难达到代码的重用。总之，对于 消息传递编程，通常仅限于具有一定并行计算基础的工程技术人员，这影响了 m p i 并行应用程序的开发和应用范围。 1 3 3 主流语言的绑定 ( 1 ) c c + + 语言绑定 标准的命令式语言c c + + 语言是不具备表达并行性的语言成分，为了表达并 行性，可以以库的方式提供对c c + + 的绑定，进而实现并行编程。相对于其它实 现并行编程的策略，该方式是较为灵活的一种实现。通常分为两种形式的库，一 种是操作系统级的，另一个是用户级的。前者如p o s i x 线程库就是一系列和c c + + 整合的系统调用，用于多线程编程。用户库中具有代表性的如m p i 标准的各种实 现，通过为c c + + 编程人员提供支持并行编程的a p i 和库例程来实现并行编程。 并行虚拟机p v m ( p a r a l l e lv i r t u a lm a c h i n e ) 是一种支持网络并行计算的支撑 软件，也是通过其提供的库例程直接为c c + + 语言所调用。p v m 并行编程环境也 支持异构环境的集群编程，尤其适用于单一用户环境或者小到中型的集群环境， 同时它也支持m p p 平台。c o r b a 是分布式跨平台的面向对象编程标准，可用来开 6 基丁骨架的并行编程环境中结构骨架库的研究 发多智能系统，基于c o r b a 的程序可以融合不同平台和不同编程语言的模块，它 的m i c o 口别实现作为c o r b a 标准的完全实现也支持c c + + 语言。 ( 2 ) f o r t r a n 语言绑定 f o r t r a n 作为最早出现的计算机高级程序设计语言之一，广泛应用于数值、 科学和工程计算领域并发挥着重要作用。更重要的很多专用的大型数值运算计算 机针对f o r t r a n 做了优化。其最大的特点是接近数学公式的自然描述，同时具有 易学，语法严谨，可以直接对矩阵和复数进行运算中，程序执行效率高等特点。 自其诞生以来，人们已经积累了大量高效而可靠的源程序。此外，f o r t r a n 也广 泛应用于并行计算和高性能计算领域，如m p i 的实现中就已经提供了f o r t r a n 语 言的绑定。随着f o r t r a n 9 0 ，f o r t r a n 9 5 ，f o r t r a n 2 0 0 3 的相继推出使f o r t r a n 语 言具备了现代高级编程语言的一些特性。实际上f o r t r a n 语言己经成为并行编程 的主流语言之一。 1 3 4 并行编程环境的主要性能指标 开发并行编程环境是一项复杂的和困难的工作。例如，如何准确地定位程序 出错的位置以及原因等的调试问题就是并行编程环境中关键问题之一。一个并行 编程环境是否成熟的标志主要表现在以下几个方面： ( 1 ) 易用性：指用户使用并行编程环境的难易程度。用户包括并行编程领 域中的专业人员也包括一些非专业人员。不管哪一种用户，对并行编程中的细节 都是不可见的。如传统的m p i 编程，通常只适合专业人员而不适合非专业人员。 ( 2 ) 可编程性：指程序员使用并行编程环境所提供的工具及基本设施进行 软件开发的难易程度，它在一定程度上决定了并行编程工具的开发能力及其易用 性。提高可编程性通常可以简化并行程序设计。 ( 3 ) 可扩展性：指当系统的处理机数目增加时程序对新加入的处理机的利 用率，一个可扩展的程序可以很好地利用新增加的计算资源。 ( 4 ) 可靠性：指在一定的环境下及给定的时间内，系统不发生故障的概率。 其中最重要的一点就是要增强容错功能。 ( 5 ) 可复用性：是指代码或算法等的重复使用。恰当地进行复用，可以提 高软件的开发效率和软件质量等。 1 4 本文研究的内容及组织结构 本文主要完成基于骨架并行编程环境中结构骨架库的研究，具体内容如下： ( 1 ) 提出了一种并行骨架的抽象形式，通过对其进行扩展，可以形成各种 结构骨架，如s i n g l e t o n 骨架、f a r m 骨架、p i p e l i n e 骨架、t a s k q u e u e 骨架。 同时，为实现骨架组合提供了必要条件。 7 硕十学位论文 ( 2 ) 对系统底层通信库m p i 的调用接口进行了简化，以方便编程者进行性 能调整。同时也使得编程者对特定骨架的通信特性有更清晰的认识。 ( 3 ) 对骨架描述方法进行了研究，提出了一种基于x m l 的通用骨架描述方 法，并使用该方法对现有结构骨架进行了统一描述，以便更好地指导编程者，使 其能较为准确地选择、比较和使用并行结构骨架。 ( 4 ) 在p c 机群和m p i c h 组成的并行计算平台上对两个经典实例一一数组 求和及矩阵一向量乘法问题均进行了基于m p i 的实现和基于结构骨架的实现，并 对它们的性能进行了评价。 本文主要探讨了基于s k e l e t o n 并行编程环境下结构骨架库中的一些关键问 题，并对其可编程性、可扩展性和可移植性进行了深入的研究，本文的组织结构 如下所示： 全文共分六章。 第一章介绍了本文的研究背景和意义，对并行程序开发方法和并行开发环境 的相关内容进行了简单的介绍，最后给出了本文的研究内容和组织结构。 第二章主要介绍基于骨架的并行程序设计方法。首先简单介绍了设计模式及 其在并行领域中的应用，接着对骨架的相关内容进行了简要介绍，并给出了三种 具有代表性的基于骨架的并行编程系统，最后，对我们的基于两级抽象的并行骨 架系统进行了比较详细的介绍。 第三章首先对我们的骨架系统中的两类骨架进行较为详细的介绍，接着以结 构骨架为重点，对其进行深入分析与设计，并提出了一种描述骨架的新的方法， 以四种典型的结构骨架为例给出了其描述和接口。最后介绍了对底层通信库的有 益探索。 第四章在简要介绍结构骨架库的主要目标及其相关的实现技术之后，给出了 四种典型骨架的预实现，最后对底层通信库的实现也进行了简要介绍。 第五章以机群作为并行骨架实例的计算平台，通过具有代表性的实例对骨架 系统进行说明，并给出实验结果。 第六章对本文所做的工作进行了总结，并指出了下一步所要进行的相关工 作。 1 5 小结 本章首先介绍了本文的研究背景和意义，接着介绍了三种主要的并行程序开 发方法并进行了简单的比较。同时，对主流的并行编程环境，并行编程环境的分 类和性能指标等进行了介绍，并概括了本论文的主要内容和结构。 基丁骨架的并行编程环境中结构骨架库的研究 第二章基于骨架的并行程序设计方法 2 1 设计模式概述 设计模式最早由c h i s t o p h e ra l e x a n d e r 提出，应用的领域是城市规划和建 筑学。但是设计模式的思想不仅仅局限于此，已经在多种计算学科中被使用， 其中对计算机软件的影响也是非常巨大的。最初由b e c k 和c u n i n g h a m 引入软件 工程社区，随着g a m m a 、h e l m 、j o h n s o n 和v 1 i s s i d e s 的g o f 泓1 一书的出版，标 志着它在面向对象编程领域占据了重要的地位。 设计模式可以理解为对面向对象软件设计经验的总结。设计模式使人们可以 更加简单方便地复用成功的设计和体系结构，而不是解决任何问题都要从头开 始，从而可以帮助设计者更快更好地完成系统设计，提高了软件的开发效率，并 得到结构良好的优秀软件。 2 1 1 设计模式的概念与描述 根据g a m m a 在g o f 中给出的定义，设计模式是对被用来在特定场景下解决一 般设计问题的类和相互通信的对象的描述。它通过刻画部件静态和动态的结构及 其之间的合作关系，成功地应用于解决商业数据处理、电子通信、图形用户界面、 数据库、分布式通信软件等软件构造中的问题。 g a m m a 提出了描述设计模式的统一格式，包含了设计模式的多方面内容，有 助于学习、比较和使用设计模式。对一个设计模式，可以从模式名和分类、意图、 别名、动机、场景、适用性、结构、参与者、协作、效果、实现、代码示例、已 知应用和相关模式等方面进行描述。对设计模式进行全面的描述，可以让使用者 更容易地选择合适的设计模式并将其应用到具体问题中。 2 1 2 并行领域中的设计模式 目前，设计模式已经在面向对象的设计方法学领域中取得了很好的应用和发 展，用于描述一些系统的、普遍的和重复出现的设计问题及其解决方案。但是， 这一概念的使用并不局限于面向对象领域，是可以根据领域的需要对其进行扩展 和应用。 在并行计算中，设计模式用于描述重复出现的具有相似结构与通信同步行为 的并行计算问题及其解决方案。与面向对象中设计模式概念不同的是，面向对象 中设计模式的抽象程度是设计一级的，而在并行程序开发中，设计模式并不只停 9 硕十学位论文 留在设计级，它提供了预先的实现，如流水线并行、分而治之方法、各种拓扑 下的数据并行等，使设计模式的抽象程度扩展到了实现级。 与一般的并行程序开发不同，基于并行设计模式的并行程序开发，强调将并 行程序中的通信部分和串行应用部分分离，从而可以使得并行程序得到快速的开 发，提高重用性及可编程性。 2 2 骨架概述 关于并行骨架的研究，最早开始于上世纪8 0 年代的算法骨架( a l g o r i t h m s k e l e t o n ) 口5 1 。到目前为至，也研究出了很多基于骨架的并行编程系统，具有代 表性的系统如e s k e l 啪1 、m u s k e l 7 l 、a s s i s t 鼬3 9 1 等。但是，各种基于骨架的系统 对骨架的描述和定义并不统一，影响了骨架库的可扩展性和可移植性。另外，早 期的系统仅支持有限的骨架，降低了系统的实用性。后来的系统虽然提供了对系 统骨架的扩充方法，但它是基于另一种新的语言或工具，如c o 。p 。s m l 系统所使用 的m e t a c o ：p 。s 。这样，虽然解决了骨架的扩充问题，但在基于骨架的系统间并不 能重用，究其原因，最根本的是没有对骨架提供一种通用的模型和描述方法。 并行骨架被看成是高层次的并行程序设计语言构件，其中包含了并行性、通 信、同步以及其它相关信息h 。与并行设计模式相比，它具有更高级的抽象层次， 并隐藏了内部的实现细节，从而简化了并行程序的开发。可见，并行骨架的作用 在于：通过提高并行开发的抽象层次，简化并行程序设计，提高程序开发效率。 通过骨架的实现细节对用户透明，提高骨架的可重用性和可移植性。在特定 的体系结构上，骨架的实现能够充分利用优化技术，从而有效提高并行程序的性 能。基于骨架的并行程序设计领域将基于骨架与基于模式的并行研究工作很好地 融合在一起h 刳，以提供一种通用的、更高层次的并行程序设计方法。 2 2 1 骨架分类 由于多年来世界各地有许多组织和项目小组从事并行骨架的相关研究h3 l 。 因此，出现了许多关于骨架分类的研究，如c o l e m 3 、d a r l i n g t o n h 5 i 、r a b h ih 6 1 、 p 3 l h 7 1 等的骨架分类。此外，基于不同指导思想，所开发骨架的种类也各不相同。 像基于b m f ( b i r d m e e r t e n sf o r m a lis m ) 的s k e t op r o j e c t h 踟开发了一些基于基 本数据结构的骨架，如l i s t s ，t r e e s ，m a t r i c e s 等；基于b a c s 的a l p s t o n e p r o j e c t h 钔则开发了不同拓扑结构的骨架，如p i p ea n dr i n g 、g r i da n dt o r u s 、 h y p e r c u b e 、t r e e 等。这样，多种骨架分类导致了使用时的混淆，阻碍了基于骨 架的并行程序设计方法的发展，因此，提出一种通用的骨架分类是很有必要的。 一般来说，根据并行性的种类进行骨架的分类是最通用的分类方法，它将骨 架分为任务并行骨架与数据并行骨架。其中，任务并行骨架描述了独立任务之间 l o 基丁骨架的并行编样环境中结构骨架库的研究 的并行性；而数据并行骨架则描述一个任务中数据的并行性。 常见的任务并行骨架包括：( 篁) p i p e s y s t o l i c ：管道和脉动方式，计算被划 分为系列阶段( s t a g e ) ，数据流逐段通过它们，并发地执行。t a s k q u e u e f a r m ：每个从进程从任务队列中选择一个任务执行，允许其产生新的任务 并添加到任务队列中，直到任务队列为空时并行程序结束。递归划分d i v i d e a n dc o n q u e r ：问题被动态、递归划分为可以并行求解的子问题，再对子问题并 行求解，然后递归合并子问题的解。它不仅开发出保守并行性( 所有子任务都需 要完成) ，还开发出推测的并行性( 检测所有可能的并行性，当某个子任务无进 一步的并行性时，才终止) 。 常见的数据并行骨架包括：m a p 骨架：是最直接地并行性，将函数直接作 用于每个数据上。r e d u c e 骨架：在b m f 或各类函数式语言中，归约操作是最 常见的。将每个数据按给定操作进行运算，并返回最终结果，如求和、求积等。 ( 蚕) s c a n 骨架：并行前缀计算。 2 2 2 骨架组合 基于骨架的并行程序设计中，用户通过选择高层次的、预定义的、可实现并 行性的骨架来指导并行程序