（计算机软件与理论专业论文）dpapd模型中的apla抽象并行程序的研究.pdf

摘要 并行程序设计是并行计算的两大难题之一，也是并行计算领域的一个研究热 点。并行程序设计的困难主要存在于两个方面：问题的并行求解和并行程序的编 码。问题并行求解的困难主要源于应用问题的多样性、问题并行求解所需的创造 性思维和计算机处理能力的机械性之间的矛盾。并行程序编码的困难主要源于并 行计算机系统结构的多样性，以及由于缺乏统一的并行计算机模型而导致并行程 序的复杂性、低效性、不可移植性等问题。 d p a p d ( d 髂j 印- p a 仕e m - b a s e dp 眦i l l e lp r o g r a md e v e l o p m 锄t ) 是在我们的前期研 究中提出的一种系统的基于设计模式的并行程序开发模型，该模型支持从问题到 并行程序的整个程序开发过程，并提供了设计模式库为程序员并行开发进行指 导。程序员根据该模型来开发并行程序，可以将并行程序开发过程中的创造性工 作和非创造性工作区分开来，创造性工作由编程者完成，非创造性工作由机器完 成，有效地提高了程序的开发效率。 a p l a ( a b s t m c tp r o 铲a m m i n gl m g u a g e ) 语言和设计模式库是d p a p d 模型的重 要组成部分。通过a p l a 语言和设计模式的使用，不仅为问题的并行求解提供了 算法设计方法和策略上的指导，而且提供了并行算法实现的抽象框架，使程序员 在不具备并行领域知识的情况下，就可以获得求解问题的抽象并行程序。本文工 作即是a d l a 语言进行并行方面的扩充，然后用它来抽象描述设计模式库。因此， 本文主要做了以下工作： ( 1 ) 对a p l a 语言进行并行方面的扩充，主要是扩充了一些用于并行运算的运 算符：如函数( 或过程) 的并行兼容运算符，函数( 或过程) 的并行组合运算符， 并行函数作用运算符等，从而使得它能够描述设计模式和抽象的并行程序； ( 2 ) 对并行计算中的并行分而治之、单步分而治之、并行分之限界三种模式进 行深入地研究，并用已扩充的a - p l a 语言描述出相应的框架，以支持抽象并行程 序的实现： ( 3 ) 根据d p a p d 模型中的开发步骤开发一些完整的实例，即运用已扩充的 a 科a 语言和d p a p d 模型中的设计模式，得到问题的抽象并行程序，并对此抽象 并行程序进行了证明。 本文的创新工作就是对d p a p d 模型进行了完善，主要包括两点：对a p i a 语言进行了并行方面的扩充；运用已扩充的a p l a 语言描述了3 个设计模式， 得到a p l a 程序框架。 关键词：设计模式，算法模式，并行结构模式，抽象并行程序 a b s t r a c t d e v e l o p m e n to fp a r a l l e lp r o g r a m si sn o to n l yo n eo ft h et 、od i f i c l l l t i e sb u t a l s oam a i nc o n c e mi nt h ef i e l do fp a r a l l e lc o m p u t i n g t h ed i f f i c u l t i e so fp a r a l i e l p m 口a m m i n gm a i n l ye x i s ti nt w o 嬲p e c t s ：p r o b l e mp a r a l i e ls o l v i n g 蛆dp a r a l l e l p r o g r a m d i n g 1 1 l em a i nd i f f i c u l t yo fp m b k mp a r a l i e is o l v i n gc o m e s 舶mt h e m u l t i p l i c i t yo fp r o b l e m sa l l dt l l ec o n t r a d i c t i o nb e t w e e nt l i ec r e a t i v i t yr e q u j r c df o r s o l v i n gp - o b l e m s 柚dt h em e c h a i l i s mo fc o m p u t e r s t 1 l em a 主nd i 峨c u l t yo fp a r a l l e l p m g r 唧c o d i n g m e sf r o m t l l em u l t i p l i c i t yo fp a m l l e lc o m p u t e r 盯c b i t e c t u r c s ，a n d c o m p l c x i t y ，l o w - e 伍d e n c y t r a i l s p l a n t a t i o no fp a f a l l e lp r o g r a m sc a u s e db yl a c ko fa u n i f i e dp a r a l l e i 鲫p u t e rm o d e l d p a p dj sad e s i 印一p a t t e m - b a s e dp a r a l l e lp r o 璺a md e v e l o p m c n tm e t h o d 卸d m o d e l ，w h i c hw ep r o p o s e dj n t h i st h e s i s sp r o p h a s es t u d y t h em o d e ln o to n l y s u p p o n st h e ，h 0 1 ep r o c e s so fp a r a n e lp r o g m l nd e v e l o p m e m ，f r o mp r o b l e m s p e c m c a t i o n st 0p a r a l l e lp r 0 掣锄s ，b u ta l s oa c t s 弱ag u i d e0 fa l g o r i t h md e s i 印 m e t l l o da n ds t r a t e g yf o rp r o g m m m e r st h r o u g hp m v i d i n gd e s i g p a t t e md a t a b a s e t h r o u g hd e v e l o p i n gp a r a l l dp m 孕锄i nt l l i sm o d e l ，d e v e l o p e r sd i s t i n g u i s h c r e a t i o n a r yl a b o rw l l i c hd o n eb yd e v e l o p e r s 丘o mn o n c r e a t i o n a r yl a b o rw h i c h d o n eb yc o m p u t e r ，w h i c hi m p r o v et h ee f f i d e n c yo fp r o 掣姗d e v e l o p m e n t a p l al a i l g i l a g e a l l dd e s i 印p a “锄sa r ei m p o n a n tc o m p o n e n t so f 【) p a p d m o d d t h r o u g l la p p l y i n ga p l al 柚g i l a g ea n dd e s i g np a t t e m s ，i tn o to n l ya c t sa sa g u i d eo fa l g o r i t h md c s i g nm e t h o da n ds t r a t e g yf o rp a r a l l e lp r o b l e ms o l v i l l g ，b u t o f f c r s 锄a b s t r a c t 丘锄ef o r t h ei m p l e m e n t a t i o no fp a r a l l e la l g 鲥t h n l ，w h i c hm e a l l s p m g m m m e r sc 柚g a i na b s t r a dp m l l e lp r o 掣锄sw j t h o u ta l l yk n o w l e d g ei n p a r a l l e lf i e l d t h c r e f o r e ，t h ep r i m a r yw o f kw eh a v ed o n ej nt h i sp a p e ra r cl i s t e da sf o l l o w ： ( 1 ) r a i s i i l gap a r a l l e le x t e n s i o no fa p l a ，w h i c hc a i ld e s c r i b ed e s i g np a t t e m s a n da b s t r a c t p a r a u e jp r o g 舳s ，i n d u d i n gp a r a l l e i c o m p a t i b l eo p e r a t o r 0 f f u n c t i o n s ( o rp r o c e d u r e s ) ，p a r a l l e l 伽p o s j t i o no p e m t o ro ff i l n c t i o n s ( o r p r o c e d u r e s ) ， p a m n e l - f u n c t i o n a p p l i c a t i o no p e r a t o r ，e t c ； ( 2 ) r e s e a r c h i n go nt h r e ed e s i g np a n e m sa n dd e s c r j b i n gc o n s p o n d i n gf h m e s b ye x p a d e da p l al a n g u a g e t o s u p p o r ti m p l e m e n t a t i o no f a b s t r a c t p a r a i i e i p r 0 掣a m s ； ( 3 ) d e v e l o p i n gs e v e r a lc o m p l e t ee x a m p l e sa n dg e t t i n gt h e i ra b s t r a c tp a r a l l e l - i u p i o 伊a m sb ye x p 柚d e da p l aa n dt h ed c s i 鲫p a t t e m s ，a c c o r d i n gt ot h ed c v e l o p m c n t s t e pi nd p a p dm o d e l ，w h j c hh a v ec a r r i e do nt h ep r o o f s o m ei 肌o v a t i o 璐o ft h i st h c s i sh a db e e nm a d c ：r a i s e dp a r a l l e le x t e n s i o no f a p l a ，d e s 嘶b e dt h r e ed e s i g p a t t c m s 锄d9 0 tc m t e s p o d i n gf r a m e sb y c x p a n d e da p l al a n g l a g e - l 【e y w o r d ：d e s i 鲫p a t t e m ，a l g o r i t h mp a t t e m ，p a r a i l e l s t n l c t u r a i p a t t e m ， a b s t r a c tp a r a l l e lp r o g r a m 1 v - d p a p d 模型中的a p l a 抽象并行程序的研究 1 1 研究背景和意义 第一章绪论 随着信息时代的到来，人们要求计算机系统提供更强的计算能力的需求总是 不断增长的。需要很高计算速度的领域包括科学和工程问题的数值建模和模拟， 如卫星数据处理、石油数据处理( 连续优化问题) ，调度问题、平面性问题及 v l s i 设计( 离散优化问题) 、地球物理、生物医学、遥感技术、计算化学、海 洋探测、大气污染、超声波应用、核酸模拟、结构力学、跨声速流计算、地块偏 移、潮汐模拟、计算几何、遗传工程、工业自动化、军事指挥、经济决策、情报 分析、天气预报、人口预测、导弹轨道计算、社会现象模拟以及美国h p c c 计划 ( h i 曲p e r 陆加锄c ec 0 m p u t i n ga l l dc 0 m m u i d c a l i 叽) 提出的重大挑战性问题等等。 这些问题都存在着大规模的复杂计算，需要存储容量很大，计算速度很高的超高 性能并行计算机来处理数据。计算机单机性能受到物理因素的制约不可能无限提 高，任何单一处理器远远不能满足高性能计算的需求。因此，并行计算已成为大 型科学与工程计算问题的主流技术。 然而目前，并行程序的开发是并行计算中一个公认的难题，其根本的原因在 于并行计算机系统结构的复杂性和多样性以及并行程序设计技术的不成熟性。串 行计算机体系结构可以使用一种统一的模型“冯诺伊曼模型，来表示，因而串行程 序基本上无须多大改变就可移植到其他的串行计算机上，并且无潜在的性能遗 失。但并行计算机的体系结构尚无统一的模型，因此，并行程序的开发是依赖机 器的，无法在一个统一的标准下进行，从而导致了其复杂性、低效性、不可移植 性等问题。另一个重要的原因在于缺乏系统的开发并行程序的方法和有关的辅助 工具。现有的并行计算模型基本上都是语言级的，它们为并行程序设计提供一个 抽象的平台，但缺乏指导程序员在其所提供的平台上进行并行程序开发、推导和 验证的方法。如何在一个给定的抽象模型的平台上设计出符合问题要求的并行程 序完全取决于程序员的技巧和经验，程序的可靠性、开发效率都难以得到保证。 由于以上原因，再加上目前还没有提供统一的并行计算模型的数学理论基 础，所以，虽然国际上存在许多流行的并行模型，但尚未有一种公认理想的并行 模型。因此，探索一种能简化并行程序开发的过程，提高并行程序开发的高效性 的实用的并行程序设计模型是很有必要的。在我们的前期研究1 1 4 2 l 中，提出了一 种系统的基于泛型编程和设计模式的并行程序设计模型。本文的工作是其中的重 要组成部分。 d p a p d 模型中的a p l 抽象并行程序的研究 1 2 并行程序开发策略研究概述 并行程序的开发关键是决定移植现有串行程序或串行算法还是从头开发新 的并行程序。从开发并行程序的出发点来看，现有三种不同的策略【1 3 】，即可以从 串行的算法出发，可以从最初始的问题规范出发，也可以从语言角度出发，分别 研究与开发其中的并行性，从而得到可在并行计算机上执行的并行程序。 1 2 1 从串行的算法出发 从串行的算法出发来开发并行程序，有两种不同的方法。一种是串行算法的 直接并行化，另一种是用已有算法求解新问题，即面向算法的方法。 1 2 1 1 串行算法的直接并行化 通过长期的研究与摸索，人们已经设计和积累了大量的串行算法。这些串行 算法在解决实际问题中是十分有效的。它们是人们智慧的结晶，是宝贵的财富。 在设计并行算法时，要充分利用这些算法，而不应该轻易抛弃它们。况且大量的 串行算法已经有现成的程序。如果能将串行算法并行化，那么这些串行程序也有 可能通过少量的修改而直接变成并行程序。许多并行编程语言都支持通过在原有 的串行程序中加入并行原语( 例如某些通信命令等) 的方法将串行程序并行化。 因此，在已有的串行算法的基础上，开发其并行性，直接将其并行化是并行程序 设计中优先考虑的方法。 直接并行化已有串行算法时要注意两个问题：第一，并非所有的串行算法都 可以并行化。某些串行算法有内在的串行性，比如在某些串行算法中，每一步都 要用到上一步的结果。只有当上一步完全结束后，下一步才能开始。这样，各步 之间就不能并行，只能考虑其它的并行化办法。例如模拟退火算法，每个温度下 迭代的出发点是上一个温度下迭代的结束点。这样就很难直接将各个温度的迭代 并行起来。第二，好的串行算法并行化后并不一定能得到优秀的并行算法；另一 方面，不好的串行算法并行化后也可能是优秀的并行算法。例如，串行算法中是 没有冗余计算的。但是在并行算法中，使用适当的冗余计算也可能使并行算法效 率更高。加入冗余计算的并行算法就可能比直接由串行算法并行化得到的算法效 率高。又比如，枚举不是一种好的串行算法。但是将其直接并行化后可以得到比 较好的并行算法。 直接并行化的关键在于分析和暴露原有串行算法中固有的并行性。直接并行 化也不是机械的，完全直接的。有时为了暴露算法的并行性，要对串行算法进行 一些适当的改动。总之，要在保证算法正确性的前提下，尽量提高算法的效率。 1 2 1 2 面向算法的并行程序开发 d p a p d 模型中的a p l 抽象并行程序的研究 面向算法的方法并不是指串行算法的并行实现，也不是单一地考虑某一个问 题的算法设计，而是研究问题的求解规律，即算法设计过程的规律性，根据现实 世界算法问题中所固有的行为上的相似性对算法问题进行分类，使得同一类中的 所有算法问题的求解符合某种特定的设计模式。这样，通过对设计模式的并行性 开发，就能解决一类问题的并行程序开发。 。 1 2 2 从最初始的问题规范出发 从最初始的问题规范出发来开发并行程序的方法，也称为面向问题的并行程 序开发。它与顺序程序开发的出发点是相同的，只是在开发过程中要考虑问题潜 在的并行性开发、并行求解和如何实现其并行性的问题。因此，概括而言，与顺 序程序的开发类似，一种途径是采用形式化的程序综合与推导的方法，使用一系 列的语义转换规则，将规范描述语言所描述的问题逐步求精，从而得到程序设计 语言所表示的可执行程序。并行程序的形式化开发，与顺序程序相比要复杂得多， 现有的广为人知的并行程序的验证和开发系统模型有c s p ，1 j n y ，a d i o n s y s t e m ，s h a r e d s i a t cm o d e l s 等；另一种途径是采用并行算法的设计和实现技术， 通过在某种并行计算模型上设计出解决特定问题的并行算法，然后实现该并行算 法，将算法映射为可在特定并行计算机上执行的并行程序。 1 2 3 从语言角度出发 从语言角度出发开发并行程序也称为面向语言的方法。它可分为两类：一类 显式并行性开发方法，即研究并行的语言或模型，通过在语言或模型中提供一些 并行性定义的机制，程序设计人员使用这些机制来刻画并实现算法问题中的并行 性。对并行语言与并行模型的研究，包括传统的邢i a m 、p v m 、m p i 等曾在并 行计算领域占主体地位的低层次模型，h a s k c n 、i 删等高抽象程度的模型， b s p 、l o g p 等集中了大量研究工作的中等抽象程序的模型等。另一类是隐式并 行性的开发，即通过在语言的编译器中加入识别程序中所存在的可并行单元的功 能，使得经编译后产生的代码为并行的代码。 1 2 4 三类研究的比较 在对并行程序开发方法的研究中，大量的研究集中于面向问题的方法和面向 语言的方法以及串行算法的直接并行化，而对面向算法的研究较少。到目前为止， 尽管各个领域都取得了一些成果，但尚未有一种公认的切实可行的开发易编写、 可移植、高性能的并行程序的方法。 通过形式化方法推导程序一直是程序设计的理想，国际国内都非常重视这方 d p a p d 模型中的a p l a 抽象并行程序的研究 面的研究，尽管这一方法在理论上己日益成熟，但真正应用起来往往仅限于开发 一些小程序，而且其方法难以为一般的用户所运用，而并行程序的复杂性又增加 了形式化开发的难度，因此，并行程序的形式化开发离实际的应用仍有一定的距 离。 并行算法的设计方法的研究一直伴随着并行计算研究的历史，尽管现已开发 了许多问题的并行算法，但由于并行算法设计的复杂性，至今尚无一套普遍适用 的系统的设计方法。并行算法的设计不仅要考虑问题的特性，还要考虑其将运行 的并行计算机的特性，且在特定并行模型下设计的并行算法往往只能实现于某一 类特定结构的并行计算机，算法的通用性差，随着新的并行计算机体系结构的日 益出现，对同一问题需要不断设计新的相应的并行算法。 代码的并行化编译一般要经过相关性分析、优化和代码生成三个阶段。它的 主要思想是通过对源代码中数据流和控制流的分析，寻找出一些不具有相关性的 片段，将它们并行化。这一方法从源代码出发，一开始就将变量等程序实现方面 的细节考虑进去，这些细节往往掩盖了问题本身具有的并行性，因此必然带来更 高的复杂性，而且，并行化编译开发的是细粒度的并行，程序效率难以提高，程 序并行化的程度也受到原顺序程序的局限，一个好的并行程序往往并非来源于一 个好的顺序程序。 显式并行化是近年来研究较多的方法，它通过在语言或模型中提供并行性描 述和实现的机制，而将并行性开发的任务完全交给了程序员。由于缺乏系统的开 发方法，从问题的求解到并行实现的整个过程对程序员而言是一个复杂与困难的 工作。而且，由于程序员水平与风格的差异，软件的质量与效率往往难以得到保 证。 面向算法的并行程序开发，从某种意义而言，是一种隐式并行化的工作，但 与并行化编译有本质不同，它将并行化的工作从语言一级提高到算法一级，减少 了琐碎的实现细节的影响，而更关注的是算法问题类本身固有的并行性，同时， 通过对算法问题的分类与抽象，可以利用顺序算法的设计经验，构造特定的算法 结构模式，预先开发出其中的并行性；另一方面，可以将并行计算中常见的并行 结构如数据并行、流水线并行、工作池、管理者一工人等的结构与行为进行抽象 描述，构造出相应的并行结构模式，以支持对算法结构模式所开发出的并行性的 实现，这样一来，使程序设计人员可以不必完全显式地进行并行开发，从而简化 了并行程序的开发过程，降低了并行程序开发的复杂性，是一种切实可行的并行 程序开发方法的研究途径。 d p a p d 模型中的a p l a 抽象并行程序的研究 1 3 设计模式研究概述 在面向对象的软件工程领域，设计模式可以使人们简单方便地重复使用成功 的设计和体系结构。因而人们对设计模式概念的理解一般局限在面向对象的软件 工程领域。但是这一概念的使用并不局限于这一领域，而是可以根据其他领域的 需要进行这方面的扩展。本节对设计模式的思想、概念以及它在并行程序设计领 域中的应用进行简要的概述，并且详细介绍了目前典型的四个基于模式的并行程 序开发系统以及我们自己的设计模式概念。 1 3 1 设计模式的思想 设计模式的概念最早是由建筑设计大师c l l r i s t 0 i ) h e r 舢e x 卸d c r 在关于城市规 划和建筑设计的著作建筑的永恒方法中提出来的。这一概念成为其后用于许 多计算方法中的基础。将设计模式概念引入面向对象软件工程领域的标志是 g a i i l m a 等人著作的【1 4 l 一书。其中对设计模式的定义为：“对被用来在特定场景 下一般设计问题的类和相互通信的对象的描述”。一个设计模式命名、抽象和确 定了一个通用设计结构的主要方面，这些设计结构能被用于构造可重用的面向对 象设计。设计模式确定了所包含的类和实例，它们的角色、协作方式以及职责分 配。每一个设计模式都集中于一个特定的面向对象设计问题或设计要点，描述了 什么时候使用它，在另一些约束条件下是否还能使用，以及使用的效果和如何取 舍。 设计模式可以使人们简单方便地重用成功的设计和体系结构。将已证实的技 术表述成设计模式也会使新系统开发者更加容易理解其设计思路。设计模式可以 帮助开发者做出有利于系统重用的选择，避免设计损害系统重用性。通过提供一 个显示类和对象作用关系以及它们之间潜在联系的说明规范，设计模式甚至能够 提高已有系统的文档管理和系统维护的有效性。简而言之，设计模式可以帮助设 计者更好地完成设计工作，而且所完成的设计工作更加灵活、优雅，最终可重用 性更好。 1 3 2 并行程序设计领域中的设计模式 在并行程序设计领域中，以设计模式的思想为基础的并行程序设计方法研究 是并行程序模型研究的一个重要分支。其中主要有分别以算法骨架，并行程序设 计典型 a r a l l e lp i o g r a 加m i n ga r c l l c t y p c ) ，结构骨架( 砌i t e c t i i r cs k c l e t o n ) 等概念为基 础的研究工作l 挎3 6 1 。在并行计算中使用设计模式思想的系统有早期的 c ( ，d e e c t a 1 ，1 9 8 9 ) 、f r 锄e w o r i d s i i l 曲 e t a 1 ，1 9 9 1 ) ，近期的 e l l t c r p f i s “s c h 神旋rc ta 1 ，1 9 9 3 ) 、c 0 d e 硼i r o w n ee ta 1 ，1 9 哟、h e n 旺徊加帅ec ta 1 ， d p a p d 模型中的a p l a 抽象并行程序的研究 1 9 9 5 ) 、n a c s ( b a n o l ie ta 1 ，1 9 9 5 ) 、d p n d p ( s i ua n ds m g l l ，1 9 叨等。近年来，相关 的系统有佛罗里达大学的模式语言p l p p 胁n e ml a n g i l a g e6 d rp a 蹦l e l p r o g r a 珊m i n 白【1 5 。，爱丁堡大学的骨架库e s k c l ( t l ”e d 曲u 嘈ls k c l e t o ni j k 町) 【1 7 删 以及另一项目e i l l l a i 赋【”“j ，亚琛工业大学开发的s l ( i l ( s k e l c t 0 i li l n 口e r a t i v e l a n g i l a g c ) ，日本东京所开发的关于算法骨架的s k e l bp r o j e c t ( s k d e c o n 【j b a m yi n 1 o k y o ) 【2 删，意大利的比萨大学计算机科学学院开发的一种结构化的并行程序设 计语言p 3 “p i s ap 硪i l l e lp r 0 野吼m i n gl 觚g u a g c ) 刚，亚伯大大学计算机科学部门 开发的c 0 2 p 2 s ( c 0 玎喇啊e c l o 订e t c dp a t c m b a s c dp r o 日啦m j n gs y s t c m ) 【3 l 阗等。 1 3 3 典型的基于设计模式思想的并行程序开发系统简介 1 3 3 1p i j m 简介 p l p p ( p a t t e mm g l i a g ef o rp a r a l l e ip r o g r a 瑚m i l l 曲，并行程序设计的模式语言 是由佛罗里达大学开发的。模式语言实际上是模式的集合，这些模式能够处理某 些领域的问题。在这语言里的模式以不同的方式相关联，包括级别划分或组合， 并且语言的结构帮助程序员决定如何运用模式。 运用模式语言开发并行程序，有时是从问题开始，然后选择模式语言中的模 式，最后得到源代码；有时是从已有的串行程序开始，通过对它进行并行化来提 高速度。模式语言中的大多数模式都是运用在后一种情况下的。因此，模式语言 支持并行程序开发的全过程，从设计阶段到具体程序的实现阶段。 在运用模式语言开发并行程序之前，算法设计师应该首先分析要解决的问 题；即判断问题规模是否充足地大以及结果是否很重要，从而看是否要努力快速 地解决它。然后，下一步就要确定问题的主要特征和问题包含的数据元素。最后， 设计师需要了解问题的哪部分是计算密集型的，因为这部分是问题能否并行化的 重点。 一旦分析完后，就要经历模式语言的四个设计阶段，这四个设计阶段分别为： 寻找并发设计阶段( m e 弛d 协gc o n c u 玎c i l c yd e s j 印s p a ) ，算法结构设计阶段( c l l c 砧9 0 r i t i 蚰s t m 咖r cd l c s i 口s p a c e ) ，支持结构设计阶段( m es u p p o r t i i l gs 仃u d u r e d e s i 印s p a c c ) ，实现机制设计阶段( t h eh i l p l c m e n t a l i o nm e d l a i l i 锄sd c s i 口s p a c c ) 。 寻找并发设计阶段是关于开发问题潜在并行性的。在这一阶段，设计者要能 够识别高级算法和问题潜在的并行性，并用于算法设计中。这一阶段的模式包括： 分解模式咖m p o s i t i o np a n e m s ) ，独立分析模式e p e n d e n c y - a n a l y s i sp a t t 咖s ) ， 设计评估( d e s i 盟e v a l u a t i o n ) 。在算法结构设计阶段，程序员工作于高级结构领域， 组织得到问题的一个并行算法。这一阶段的模式描述了开发问题并行性的总体策 略，包括：任务组织的应用模式、数据分解组织的应用模式、数据流组织的应用 d p a p d 模型中的a p l a 抽象并行程序的研究 模式。支持结构设计阶段是将算法转变为源代码，考虑如何组织并行程序，并考 虑如何管理共享数据的技术。这一阶段的模式包含两组模式：构造程序方法的模 式和代表通用共享数据结构的模式。实现机制设计阶段是寻找特定的软件构造， 实现并行程序。 并行程序设计的模式语言拥有几大优势：a 提供了重要问题的好的解决方案 的目录；b 提供了可扩展的库；c i 一种对于并行程序的设计方法。模式语言在一 定程度上降低了并行程序设计的难度，而且在长时间里，它能够成为不同程序设 计模型的质量评估的标准方法和并行程序设计工具的开发的基础。 1 3 3 2e s h i 简介 c s k e l ( m ee d m b u 蟛ls k e l e t o ni 加哟是由爱丁堡大学信息学院开发的一种结 构化的并行程序设计库，它为有经验的( 孙匹p i 程序员提供很多并行结构框架。 e s k d 的第一个版本e s k d l 是由m u 册vc o k 在2 0 0 2 年开发的。它是利用设计模 式思想，即并行计算的重复出现的模式和迭代可以被抽象为框架或模板，并且可以 把简单的操作作为参数。因此，提高了抽象的水平，并行程序可以用此框架或模板 来得到，从而更加方便。它的目的是最大化由它的部件模式所提供的概念的灵活 性，并且促进模式组合的动态选择。 在2 0 0 5 年1 月，由a n n e b e n o i t 和m l l i r a yc 0 1 e 等人共同开发的一改进版本 e s k e l l 2 加o 问世了。但该版本还存在以下4 个问题：1 如果d e d 模式必须从输入 缓冲区中获取数据，那么d c a l 模式的第一工人就只能有一个进程，且这个进程 只能是进程o ；2 d c a l 模式对输出缓冲区的输入还未实现，也只能通过1 中的方 式解决；3 以s p io c a i ，数据方式实现的d c a l 模式和以s p io c a i 数据方式且每 阶段有多于一个进程实现的p i p e l i n e 模式还未实现，现在只能通过s p g io b a i 数据方式实现；4 b u t t e i n y 、f 觚n 和h a l o s w a p 模式还未实现。而在2 0 0 5 年2 月 1 8 日，由a 衄eb e l l o i t 和m u r r a vc o l e 等人共同开发的最终改进版本c s k e l l 2 m 1 又问世了。此版本与之前c s k e l l 加0 版本的改进之处在于，解决了d e a l 模式中 输入缓冲和输出缓冲的问题，且解决了d e a l 和p i d e l i i l e 模式中出现的小问题。 由a n n eb c n o i t 和m u m yc 0 l e 等人共同研发的另一项目e l l h 柚c c ( 以模式和进 程代数提高网格应用的可预测性) ，是关于现在一研究热点网格。它是通过 开发和综合来自两个研究方案的结果来简化这种系统的有效编程象p e p a 的随 机过程代数被用来对同步系统的行为建模，而这些系统的一些行为方面不是可以 精确预测到的。基于程序设计的模式意识到，许多实际的应用是从很多知名的解答 范例中得来的，并且寻求使它对应用开发者开发这样一个特定问题而无须从零丌 始的范例更加容易。一个特殊范例的选择拥有关于隐含的调度依赖性的值得考虑 的信息。通过用p e p a 对这些进行建模，并且因此能包括来自网格计算不确定性的 d p a p d 模型中的a p l a 抽象并行程序的研究 方面，从而能加固系统，这些系统就能做出更好的调度以及动态重新编排。 1 3 3 - 3s k e t op j e c t 简介 s k e t bp m j e c t ( s k e l e t o ni j b a m yi i lt o k y o ) 是由日本东京科技研究所( j s l ) 开发 的一关于算法模式的系统。它是基于结构化算法的，主要包含以下两个方面：1 许多数据结构的并行模式的实现，目前已经实现的并行模式库有：表o i s t ) ，树( 嘶蚺 矩阵( m a 砸c 嘲，这些并行模式是用c + + 和h 伸i 实现的；2 对模式程序的最优机制， 调用了模式的程序可能会带来很多意想不到的负担，所以必须对模式程序的最优 机制进行研究。如：并行模式a c c u m u l a t e 是由于运用模式开发有效的并行程序和 使用模式管理不规则的数据都不是容易而提出的，这模式不仅有效地描述了并行 计算中的数据独立性而且为管理呈现了好多的代数性质。其他的关于最优化机制 的模式正在实现当中，且实现后将添加到模式库中。此系统的目的就是帮助程序 员更容易开发有效的并行程序。 相对于以前的并行程序开发系统，s k e t op m i e d 的优势主要体现它的扩展性 ( e x t e n s i b i l i t ) 上。这表现在，在此系统中，新的设计模式可以被定义，并且添加 到系统的设计模式库中。但同时，定义新的设计模式并将之添加到系统中这个功 能并不完善，因此，在一定程度上限制了s k e l o 的实用性。 1 j 3 4c 0 2 p 2 s 简介 o d 2 p 2 s ( c 0 玎c 麒o b j c c r i e n t e dp a t t 锄b a s c dp f o g 阳m 瑚i 玎gs y s t e m ) ，也叫 c 0 p s ，是由亚伯大大学计算机科学部门于2 0 0 2 年研发的。它是基于面向对象和 设计模式的并行程序设计系统。此系统中被分为三层：模式层t i e mh y c r ) ，中间 代码层( i l l t e 肋c d i a t e ) 和底层代码层( n a t i v ec b d el a y e f ) 。模式层为用户选择的设计 模式集产生框架代码，从而达到将框架代码对用户隐藏的目的，一定程度上提高 了用户并行编程的可靠性；后两层分别逐步地向用户暴露框架代码的细节，以使 得用户能够对之进行修改来提高性能。 在0 0 2 p 2 s1 1 之后，该系统又有升级版本，主要是增加了两个工具：一是图 形化工具m e 珏c 0 2 p 2 s ，用户可以通过使用此工具方便地定义一个新的设计模式， 并添加到设计模式库中，或是修改已有的设计模式；另一个是d c 删 ( d i s t r i b u t e d c 0 2 p 2 s ) ，它封装了内存环境和分布式内存设计模式模板库，使得用 户开发分粕式的程序与开发串行程序或共享内存的程序的难度接近。 与之前所开发的系统相比，此系统体现出一定的实用性和先进性。它针对并 行程序开发系统中的三大特性正确性( c o r r e t n e s s ) ，开放性( o p c 肌e s s ) 和扩展 性( e x t c n s i b i l j t y ) 做了较好的实现。它通过层的思想使得用户可以逐步修改底层细 节，以提高性能。而且，它的图形化工具m e t a c 0 2 p 2 s 使得用户可以修改或添加 d p a p d 模型中的a p l a 抽象并行程序的研究 设计模式，从而使得系统的使用范围更为广泛。 1 3 4d p a p d 模型中的设计模式思想与有关概念 在上述的并行程序设计系统中，对设计模式的使用存在一个矛盾，就是设计 模式的抽象性和并行实现的多样性之间的矛盾。由于设计模式要求通用的特点， 决定了其必须具备相当的抽象程度，而为了使其能够描述并行计算问题的详细解 决方案，又不得不涉及到计算、通信、同步等具体的问题。因此在上述的系统中， 设计模式跨越了设计和实现两级，这样一来，损害了设计模式的抽象性特点，使 其难以达到通用的目的，而且由于设计模式的概念不明确，从而难以对开发者提 供明确的指导。因此，在我们的前期研究中l 卜埘，根据并行计算的特点，将并行 计算中的设计模式分为两个抽象级别分别进行定义，设计级的设计模式用于描述 问题求解和算法设计的方法，我们将其定义为算法结构模式，而涉及实现的体系 结构级的设计模式我们则将其定义为并行结构模式。 在长期的算法设计研究中，人们总结了一些行之有效的算法设计方法，他们 可单独或结合起来进行问题的求解，如分而治之、回朔法、贪心法、分枝限界法、 动态规划法等等，这些算法设计方法都具有并行化的可能，如果将这些算法设计 方法并行化，则可以应用于一类问题的并行求解，因此我们将这些算法设计方法， 包括其并行性的抽象，描述为算法结构模式。 并行结构模式是对并行计算中重复出现的计算模式及其实现策略的抽象。在 并行计算中存在着一些常见的并行结构如流水线、数据并行、工作池、进程农庄 等等，将这些并行结构的结构与行为进行抽象描述，即为并行结构模式。 通过将设计模式分成两个抽象级别来定义，可以避免在问题求解的一开始就 把并行结构的因素考虑进来，从而掩盖问题的本质，影响问题的求解，这一点对 许多复杂的问题而言，由于其求解本身就很困难，因而显得尤其重要。 1 4 本文的组织 本论文的组织如下： 第一章绪论，介绍几种并行程序设计方法以及它们的研究现状，简要地概述 设计模式的思想、概念，以及几种典型的基于设计模式思想的并行程序开发系统 和我们自己的设计模式思想和有关概念。 第二章介绍了基于泛型编程和设计模式的并行程序开发模型d p a p d ，主要对 该模型中的程序设计思想、结构、泛型设计模式库和此模型下的开发过程进行了 介绍。 第三章介绍了a p h 语言的程序结构、函数和过程结构、a 肌类型及程序语 d p a p d 模型中的a p l a 抽象并行程序的研究 句，并且对它初步进行了扩充。 第四章介绍了模型中的设计模式库的研究、开发和实现，其中详细阐述了如 何使用己扩充的a p l a 语言进行实现。 第五章介绍了如何运用模型中的开发步骤开发完整的实例，即如何运用己实 现的设计模式库和已扩充的a p l a 语言得到a p l a 抽象并行程序：并且给出了证明。 第六章结束语。 d p a p d 模型中的a p l a 抽象并行程序的研究 第二章并行程序开发模型d p a p d 基于设计模式和泛型编程的并行程序丌发模型d p a p d 是在我们的前期研究中 提出的。本文工作是其中的重要组成部分。本章主要是对此模型的思想方法j 基 本概念及相关的问题等做一个详尽的阐述。 2 1 引言 当今的世界是并行计算的世界。并行化一直被认为是获得比过去更强有力计 算机系统的解决方案。甚至有过极端的乐观主义：“w h a t e v c rt h eq u 略t i 伽， p a r a l l e l i s mi sa n s w e r ”阳。近年来，随着工作站性能的迅速提高和价格的日益下降， 以及高速网络的发展，特别是网格【”j 的出现，利用工作站群作为高速并行计算的 平台已日益受到广泛的重视和欢迎，同时也为并行计算、高性能计算的应用提供 了巨大的潜力和应用的空间。因此，高性能计算机及高性能计算是目前学术界和 产业界广泛关注的热点之一。 但是并行程序的开发是并行计算中的两太难题之一。并行程序设计远比串行 程序设计难得多，其根本的原因在于并行计算机系统结构的复杂性和多样性。串 行程序设计，有建立在统一的“冯诺伊曼模型”串行机上，在语言构造和机器实 现之间是一一对应的关系，因此，这就保证了串行程序的可移植性而无潜在的性 能遗失。然而，在并行领域里，明确的资源分配方式使得程序几乎没有可移植性 可言。尽管高层语言能够被编译在不同的并行机上，但不同并行机的体系结构的 巨大差异，使得程序的性能差异也千姿百态，并且是不可预测的，除非根本上改 变要移植的进程。而另一个重要的原因，在于缺乏系统的并行程序开发的方法及 有关的辅助工具。现有的并行程序设计模型基本上是语言级的，它们为并行程序 设计提供一个抽象的平台，但缺乏指导程序员在其所提供的平台上进行并行程序 开发、推导和验证的方法。如何在一个给定的抽象并行模型的平台上设计出符合 问题要求的并行程序完全取决于程序员的技巧和经验，而程序的可靠性、开发效 率都难以得到保证。 因此，基于我们对并行程序开发设计的基本观点，在我们的前期研究工作【l d 2 j 中，我们提出了一种系统的并行程序开发方法和模型。在下面的小节中，我们将 对该模型的思想方法、基本概念以及相关