（计算机软件与理论专业论文）基于并行设计模式的软件演化方法研究.pdf

大连理工大学硕士学位论文 摘要 成熟的应用软件系统已经被运行在单个u e 血o fe x e c 面o n ) 的硬件环境中来帮助 人们解决数据和业务逻辑问题。但是随着计算机的广泛应用，软件系统被应用到越来越 复杂的问题当中以至于单个u e 已经不能及时的处理，这就迫切需要多个u e 协同操作 来完成大量的数据和业务逻辑计算。所以对于这些应用系统的软件演化就成为一个解决 这个问题的主要方式，使它们能从单个u e 的串行平台转移到多个u e 的并行平台。 软件演化是在软件系统的生命周期内对软件进行维护和软件更新的一种动态行为。 系统需求的改变、功能实现的增强和运行环境的改变等等都无不需要对软件进行演化。 串行软件的并行化就是一种由于系统运行环境改变而引起的一种演化行为，它对串行代 码进行并行化使其适应多u e 的运行平台。重新分析并设计这个软件系统会浪费大量的 时间和精力，还容易产生一些错误。因此，对于串行软件进行自动并行化的研究成为解 决这个问题的途径。现在大量的串行代码自动并行化的系统已经出现，实现了串行程序 到并行程序的转化，但是它们是直接对串行程序中可并行化的代码进行并行化，使生成 的代码不易理解。 针对这些串行代码自动并行化系统，增加一个基于) a l 描述的并行设计模式来为 代码生成提供一个可重复利用的设计方案。在依赖性分析挖掘出串行代码中可并行化的 代码片段之后，利用x i l 对挖掘出的代码和并行化时选择的设计模式进行描述，为并 行化提供一个依据。然后通过x s l t 对l 描述的并行设计模式进行代码生成，并手 动添加模式内的业务逻辑生成一个可并行执行的代码，实现基于并行设计模式的软件演 化。 关键词：并行设计模式；依赖性分析；x m l 描述；x s l t ；软件演化 基于并行设计模式的软件演化方法研究 t h em e t h o dr e s e a r c hf o rs o 胁a r ee v o l u t i o nb a s e do np a r a l l e ld e s i g n p a c t e m a b s t r a c t i km a n l r e i m e m e t 印p l i c a t i o 璐s y s t e mh a v eb e e nf u l lo n 廿1 eh a r d 、a r ep l a 仃0 珊s 谢t l l s i n g l eu e ( u i l i to fe x e c u t i o n ) t oh e l pu st od e 甜谢t l lt l l ed a 恤锄db u s i n e s sl o g i c mq u e s t i o l l s a l o n gw i t l lt 1 1 ew i d e l yu s a g eo fc o i i 】l p u t e r l e ya r e 印p l i e dt 0d e 2 l l 、析t 1 1m o r e 觚dm o r ec o m p l e x p r o b l e ms 0 廿l a tt l l es i i l g l eu e c o u l dn o td i s p o s et h e s eq u e s t i o i l so nt i i i l e ，n ：忙nl o t so fu e sa r e i 圮e d e du i 苫e n t l yt oc o o p e r a t ew i t l le a c ho t h e rt 0f i i l i s ht l l el 引苫ed a ：t aa n db u s i n e s sl o g i c a l c o m p u t i i 培s o ，s o 行w a r ee v o l u t i o ni st l l em 咖m “1 1 0 df o rr c s o l v i i 增t l l i sq u e s t i o 玛觚l s f e r s s o f h a r et ot l l em u l t iu e sp l a t f o 皿行o ms i i l g l e i s o r w a r ee v o l u t i o ni sad y n a l i l i cb 加i o rw t l i c hm a j r l 切【i 1 1 s 砒l du p d a t e st h es o 疗w a r ei n l l i sl i f ec y c l e t h ec h a n g e so fr e q l l i r e m e n t ，呻r o v e m e mo ff u n c t i o ni i n p l e m e m a t i o n ，a n d c l l a r l g eo fr u m l i n ge n v i r o m n e m ，e t c ，a r ea l lr e q u i r et l l ee v o l u t i o nf o rm es o r w a r e p a r a l l e l i z a t i o no ft h es 嘶a lc o d ei s 距e v o l u t i o nb e h v i o rf o rt l l ec l 瑚1 9 eo fn 加n j n g e n v 的眦e m ，i tm a k e st h es 耐a lc o d ea d a p tt 0t l l em u l t iu e sp l 酬f o 肌i 沁锄a l y s i sa n dd e s i 印 o n es o f h v a r es y s t e m 、v i l lw 嬲t el o t so ft i m ea r l de n e 曜y ，孤1 dp r o d u c es o m e 嘶s t a k e s t h e r e f o r e ，t l l ea u t op a r a l l e l i z a t i o nf o rm i ss o m 眦i st l l e 、) r a yt os o l v et l l i sp r o b l e m n o w 。l o t s o fa l i t op 孤a l l e l i z a t i o ns y s t e m sh a v eb e e ng e n e r a l t e d ，a n dt h e ya c l l i e v et l l e 仃a n s f o n n a t i o n 疗o m r i a lc o d et 0p 撇l l e lc o d e b u tt l l e yp a r a l l e l i z et l l ep a r a l l e l iz a b l ec o d ei nt l l es e r i a lp r o 伊a m d i i 。e c t l ys ot l l a tt l l eg e n e r a t e dc o d ei sn o te 嬲yt ou i l d e r s 州 f o rt l l e s ea u 协p a r a l l e l i z a t i o ns y s t e m s ，a d da 订l - b a s e dp a r a l l e ld e s i 印p a 吮m d e s c r i p t i o nt 0p r o v i d ear e u s a b l es o l u t i o nf o rc o d eg e n e r a t i o n a 角e rd i g 咖go u tt l l e p a r a l l e l i z a b l ec o d ei nt l l es 嘶a lp r 0 伊锄s 谢t hd e p e n d e n c y 锄m y s i s ，u s ex m l t 0d e s c r i b et h e p a r a l l e l i z a b l ec o d ea n dp 删l e ld e s i 印p 甜e mu s e di np a r a l l e l i z a t i o 玛锄dp r o v i d ea b a s i sf o r p a r a j l e l i z i n g t h e n 谢t l lt l l eh e l po fx s l t t 0c o d eg e n e r a t i n gf o rp 踟m l e ld e s i 印p a t t e m d e s c r i b e db yx 1 l ，a d dt h eb u s i n e s sl o g i ci i lt h ep a t t e mm a i l u a l l yt op r o d u c ee x e c u t a b l e p a r a l l e l i z a b l ec o d e ，锄d a c l l i e v em ep a r a l l e ld e s i 印p a n e mb 雒e ds o 翩脚ee v o l u t i o n f i n a l l y k e yw o r d s ： p a r a e id e s i g np a t t e r n ：d e p e n d e n c ya n a l y s i s ：x m ld e s c r i p t i o n ： x s l t ：s o f l w a r ee v o l u t j o n i i 大连理工大学学位论文独创性声明 作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究 工作所取得的成果。尽我所知，除文中已经注明引用内容和致谢的地方外， 本论文不包含其他个人或集体已经发表的研究成果，也不包含其他已申请 学位或其他用途使用过的成果。与我一同工作的同志对本研究所做的贡献 均已在论文中做了明确的说明并表示了谢意。 学位论文题目：燧缰幽越毖鳓弛荔留丞 作者签名： 基越盟 1 日期： 望碰年公月么么日 大连理工大学硕士学位论文 大连理工大学学位论文版权使用授权书 本人完全了解学校有关学位论文知识产权的规定，在校攻读学位期间 论文工作的知识产权属于大连理工大学，允许论文被查阅和借阅。学校有 权保留论文并向国家有关部门或机构送交论文的复印件和电子版，可以将 本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印、或扫描等复制手段保存和汇编本学位论文。 学位论文题目： 作者签名： 导师签名： 大连理工大学硕士学位论文 引言 由于计算机技术的广泛应用，成熟的应用软件系统已经被人们广泛的应用于解决各 个领域中的数据和业务逻辑问题。但是随着科技的不断发展，计算机又被引入生物工程 等更复杂的领域当中，因此应用软件的规模也不断的增大，从而单个u e 的硬件平台对 于复杂的软件系统已经不能及时给予响应。所以，高性能的计算机硬件平台已经慢慢地 进入这些复杂的智能领域当中。随着高性能计算硬件平台的不断发展和在诸多领域的广 泛应用，并行计算也成为了许多科研和工程技术人员亟待掌握的一项研究开发手段 现有的应用软件系统已经是一个比较成熟的、体系比较庞大的、出错率很小的一个 应用系统。如果对其进行重新设计，以适应并行执行的运行环境，不但需要一段较长的 系统理解时间和重新架构时间，浪费了大量的人力和物力，还使新的系统可能会由于具 体的某一个细节不周而产生出错或崩溃现象，给软件系统的应用者带来了很大的麻烦。 2 0 世纪六七十年代研究人员就开始对串行代码并行化进行研究，并提出了串行程序 自动向量化的理论。自动向量化是自动并行化的前身，它利用源代码的依赖性分析结果 挖掘出源代码中可以向量化的部分，并尽量消除可以进行向量化的一些依赖，生成一个 可以并行执行的代码。到了8 0 年代大量的自动并行化系统已经出现，例如砒c e 大学的 p f c ，m a 巧l a i l d 的t i n y 等。在软件并行化的研究中，把自动并行化分为了两个相对独 立的部分，一个是对源代码的依赖性分析，另一个是利用依赖性分析挖掘出可以并行执 行的代码片段并对其进行并行化，如图1 1 所示。 图1 1自动并行化系统结构图 f i g 1 1 a r c h i t e c t u 心o fa u t op a r a j l e i i 2 a t i o ns y s t e m 基于并行设计模式的软件演化方法研究 依赖性在上个世纪六十年代就被研究人员提出来，但是没有马上应用到软件自动并 行化的过程当中，主要分为控制依赖性和数据依赖性。依赖性分析就是对源代码进行分 析，找出存在的控制依赖性和数据依赖性，通过代码的转化尽量消除这些依赖，以最大 地挖掘出其中可以并行执行的代码片段，以对其进行并行性转化。在并行性转化的过程 中，自动并行化系统利用依赖性分析结果和o p 盯i m 咿、m p i 等并行编程技术，对可并行 化的代码片段进行并行化。目前自动并行化的主要对象是程序中的循环部分，因为循环 占去了程序运行的大部分时问。利用并行计算技术可以大大缩短其运行时间，提高软件 系统的执行效率。 i n 忙l 的c 十+ 编译器也是一个自动并行化的软件系统，它的口o ( 过程间优化) 对于 包含许多常用中、小函数的程序，特别是循环内包含调用的程序可以极大地提高应用程 序的性能，如图1 2 所示。i n 纠c + + 编译系统利用o p m p 编程技术来进行并行化。 o 删p 是一个可移植的多线程应用程序开发的行业标准，它在细粒度( 循环级别) 和 粗粒度( 函数级别) 线程技术上具有很高的效率。但是0 p e n m p 是一个基于共享存储的 多线程编程技术，它不能应用于分布式存储的系统平台下。另外，i n 把lc + + 编译系统也 是一个直接转化系统，这使我们很不容易理解生成的并行代码。 m c * d e o _ 国 图1 2i p o 过程间优化流程 f 嘻l 上 f l o wo f i p 0 s p i o c e s s o 咖i z m l o n 本文提出一种基于并行设计模式的并行性软件演化方案，它是以源代码的依赖性分 析为依据( 主要是串行代码中的循环部分) ，利用x s u 对并行设计模式进行转化生成 一个可以执行的并行代码框架，再通过编程人员掭加处理问题的业务逻辑，形成一个可 以并行执行的代码，完成串行代码的并行性演化。依赖性分析通过对源代码的分析生成 了一些赋值或指令之间的执行约束描述。执行约束描述说明了执行语句之间的关系，从 而可以引导串行代码的并行化。设计模式为重复出现的问题提供了一个可重用的设计方 案，使不稳定依赖于相对稳定、具体依赖于相对抽象，避免会引起麻烦的紧耦合。利用 大连理工大学硕+ 学位论文 设计模式进行并行性转化还提高了软件的可重用性和可维护性，便于以后对代码进行修 正。 基于l 的并行设计模式主要从静态结构和动态特性两个方面进行了描述。其中 静态结构主要包含了模式中的参与者以及参与者之间的关系，动态特性中主要包含了模 式中参与者之间的交互信息。为了适应并行编程环境，基于x m l 的并行设计模式描述 对并行编程中的同步和通信等机制进行了扩展。这些同步和通信的描述总结了并行编程 中的相关机制，如在并行编程中通信主要有s e m 叩h o r e s 、m o n i t o r s 、m e s s a g ep a s s i n g 以 及r e m o t ep r o c e d 眦ec a l l 几种。利用这种描述方法，可以根据当前的通信信息描述生成 基于o p e 心佃或基于m p i 等通信方式，克服了现有的自动并行化系统只用一种通信模 式的缺点，使串行代码自动并行化对并行运行平台的要求大大减少，更好地扩充了并行 编程技术。 基于并行设计模式的软件并行性演化可以对源代码的依赖性分析，挖掘出可以并行 执行的代码片段，并以并行设计模式为指导，生成可并行执行的代码框架，从而把串行 的可执行代码转化成可以并行执行的代码，实现串行程序的并行性演化，减少代码重新 架构中的工作任务和逻辑错误，延长软件系统的声明周期。 基丁并行设计模式的软件演化方法研究 1 绪论 1 1 国内外研究现状 随着高性能计算机的不断发展与应用，并行编程已经成为一种发展趋势。但是现有 的大量软件系统都是由串行语言编制的，要使这些软件系统很好地运行在并行机上需要 花费大量的人力和物力来重新架构设计。因此，串行程序的自动并行化在并行研究领域 有着非常重要的意义。 在2 0 世纪6 0 年代，自动并行化方面还没有专门的研究，但是数据依赖已经被当时 的研究人员提出。数据依赖性包括数据依赖性和控制依赖性，它从串行代码中挖掘出可 以并行执行的代码片段，是自动并行化的基础和依据【l 硎。自动向量化是自动并行化的 前身，d a v i dk u c k 教授在自动向量化得研究当中确定了依赖性分析可以确定程序中可以 向量化的部分。对于一些阻碍向量化的依赖性可以通过各种程序变换尽可能地消去依赖 性使其向量化【3 1 。到了9 0 年代自动向量化的系统大量出现，例如础c e 大学的p f c ， m 矗r v l a l l d 的t i n v ，s t a 】怕r d 的s u i f 等。我国在自动并行化方面也取得了很大的进展， 如a f t 自动并行化系统，t i p s 交互式并行化系统。 现在较多的并行化系统都是基于共享存储的硬件平台进行并行化的，如i i l t e lc h 并行编译系统。lc + + 并行编译系统对串行代码进行分析，找出串行代码中可以并行 的部分和耗时的部分，通过o p e 心但编程技术对可并行执行的部分进行并行化。但是 o p e n m p 是一种基于共享存储的并行编程技术，这种基于共享存储的自动并行化生成的 并行代码只能运行在共享存储的硬件平台下，对于机群等靠网络传输的分布式存储系统 则不能很好地运行并行化的代码。另外，文献【4 5 】中对源代码进行依赖性分析从中找出 可以并行执行的部分( 主要是对于程序中的循环进行分析) ，并利用m p i 并行编程技术对 可以并行执行的嵌套循环进行了自动并行化。这种基于m p i 的自动并行化系统扩展了原 有的自动化系统的实现方式，使并行自动化从基于共享存储的系统平台扩展到了基于分 布式存储的系统平台，大大扩展了串行代码并行化后的可运行环境，也充分地利用了并 行执行的硬件系统，更好地使并行代码高效地运行。 串行代码的自动并行化研究是一种比较成熟的技术，这些并行化技术都是根据依赖 性分析查找出可以并行执行的部分并对其进行并行化，但是它们都没有利用并行设计模 式进行框架方案设计。这些自动并行化系统根据数据间的依赖性直接生成的并行化代码 可能会由于系统逻辑的复杂性而不容易被编程人员所理解，难以维护。并行设计模式给 大连理工大学硕十学位论文 出了一种可重复利用的设计方案，使编程人员很容易其中并行化的设计方案1 6 1 。利用并 行设计模式进行并行化指导不但使其他编程人员很容易理解并行化的总体框架，还使生 成的并行代码具有较好的可重用性和可维护性。 根据自动并行化软件获取程序信息的方式，自动并行化系统可分为人机交互式系统 和完全自动并行化系统【7 1 。人机交互式系统读入源程序文件，并在分析过程中根据用户 输入的信息来实现并行化。完全自动并行化系统只需要读入能够正确执行的串行源程 序，其他的步骤完全由系统自动来实现。目前大多数的自动并行化软件都是完全自动并 行化系统。基于并行设计模式的软件演化系统通过读入源程序并对其进行分析，利用并 行设计模式生成可并行执行的代码框架，然后通过编程人员添加的业务逻辑实现串行代 码的并行性转化。所以，基于并行设计模式的软件演化属于人机交互式系统。 1 2 本文的主要工作 目前已有的自动并行化系统对f o n r a n 和c c + + 都有了一定的处理，但是它们是根 据依赖性分析结果直接对串行代码进行并行化。由于自动并行化系统生成并行代码时都 是基于一定的逻辑，这使生成的可并行执行代码不容易被广大的程序员所理解，降低了 软件系统的可重用性和可维护性。另外，它们都是根据依赖性分析的结果利用o p e n m p 或m p i 等并行编程技术对串行代码进行并行化，没有充分结合这两种技术，生成的可并 行执行的代码就不能很好得适应硬件平台的扩展。o p e i 山口是一种基于共享存储硬件平 台的并行编程技术，i 是一种基于分布式存储的并行编程技术。只有充分结合这两种 类型的编程技术才能更好地实现串行代码自动并行化。基于并行设计模式的软件演化系 统利用数据依赖性挖掘出串行代码中可以并行执行的代码片段，并由代码片段的特点选 择合适的并行设计模式作为指导从而生成可并行执行的代码框架。这种代码框架主要包 含了并行执行时的同步机制和通信机制，其中的业务逻辑处理由于某一个问题的不确定 性还是需要编程人员进行手动编写，实现串行代码的并行化。 本文主要完成了以下三个主要方面： 首先利用l 对通用的设计模式进行扩展，在通用的设计模式描述中对动态行为 c o l l 籼m t i o n 添加了同步和通信描述，使其可以应用于并行设计模式的描述，以指导并 行程序的开发。 然后，在串行代码自动并行化的过程中，利用依赖性分析对串行代码进行分析挖掘 出可以并行执行的代码片段，选择合适的并行设计模式描述，并以x m l 对以上分析的 结果进行描述，为软件自动并行化中的第二步代码转化做准备。 基丁并行设计模式的软件演化方法研究 最后利用x s l t 对并行设计模式进行框架代码生成，然后再由编程人员添加业务逻 辑代码，实现可执行的串行代码的并行性转化。 1 3 本文的组织结构 第一章绪论。介绍课题提出的背景、国内外的研究现状和本文的主要研究工作。 第二章设计模式与并行设计模式。介绍了通用的设计模式和并行设计模式的相关 概念，并对其提出基于l 的模式描述方法以及利用设计模式进行代码生成的技术。 第三章软件演化的相关理论。介绍软件演化的相关理论以及并行性演化的相关技 术。 第四章基于x m l 的并行设计模式描述。介绍基于x m l 的设计模式描述细节以及 选择x m l 进行描述的原因。 第五章基于并行设计模式的软件演化。介绍如何利用并行设计模式进行软件的并 行性演化，并用x m l 对过程中的并行化后台框架进行描述，以更好地实现串行代码的 并行化。 第六章结论与展望。结合实验结果对全文进行总结，并对下一步工作提出计划。 大连理工大学硕士学位论文 2 设计模式与并行设计模式 2 1设计模式的基本概念 设计模式( d e s i 印p a n e m ) 是一套被反复使用、多数人知晓的、经过分类编目的、 代码设计经验的总结【6 。7 】。1 9 9 5 年g o f 【6 】( “四人帮”，g 锄m a ，h e l m ，j o l l l l s o n & v l i s s i d e s ， a d d i s o n w e s l e y ) 第一次将设计模式提升到了理论高度，并将其规范化。g o f 提 出了2 3 中基本设计模式，包括a b s t r a c tf a c t o 巧、a d a p t e r 等。在软件开发过程中， 它可以为我们提供一个可重用的设计方案来解决某一个重复发生的问题。利用设计模式 进行编程不但使他人可以很好地理解代码，还提高了代码的可重用性和可靠性。 2 1 1 设计模式的基本原则 为了提高代码的可复用性和可维护性，大量的编程人员都在不断地把设计模 式加入系统设计当中，利用设计模式提供的可重复利用的设计框架进行系统编程。 就是因为设计模式实现了开放封闭原则、单一职责原则、里氏代换原则和依赖倒 置原则【_ 7 1 ，还有一个是合成复用原则，设计模式才能实现代码复用和增加可维护性 的目的。 ( 1 ) 开放封闭原则 开放封闭原则是面向对象设计的基石，它是1 9 9 8 年由b e r t r a n dm e y e r 提出的。 其主要思想是指软件实体应该对扩展进行开放，而对修改进行关闭。这个原则要 求我们在进行模块设计时保证即使不修改代码也可以改变其行为。这种实现的关 键在于“抽象 ，就是说保证抽象层的稳定，而通过改变实现层来扩展行为集合。 在具体实践中，保持作为模块抽象模型的抽象体( 抽象类、基类等) 不变，而是 通过派生该抽象体产生新的行为。这样，只是通过增加代码而不是修改来实现行 为变更，避免了因修改而产生的问题。保证了系统的稳定性和延续性，从而提高 了代码的可复用性和可重用性。 ( 2 ) 单一职责原则 单一职责原则指对于一个类而言，应该仅有一个原因使它产生变化。如果能 想到多于一个的动机去改变这个类，那么这个类就应该具有多于一个的职责，应 该把多余的职责分离出去，分别再创建一些类来完成每一个职责。 每一个职责都是一个变化的曲线，当需求变化时会反映为类的职责的变化。 如果一个类承担的职责多于一个，那么引起它变化的原因就有多个。一个职责的 变化甚至可能会削弱或者抑制类完成其他职责的能力，从而导致脆弱的设计。 基于并行设计模式的软件演化方法研究 ( 3 ) 里氏代换原则 里氏代换原则( l i s k o vs u b s t i t u t i o np r i n c i p l e ，l s p ) 是面向对象设计的基本原 则之一，它强调只有当派生类可以替换掉基类而软件单位的功能不受到影响时， 基类才能真正被复用，而派生类也能够在基类的基础上增加新的行为。 里氏代换原则是对“开一闭”原则的补充。实现“开一闭 原则的关键步骤就 是抽象化，而基类与子类的继承关系就是抽象化的具体实现，所以里氏代换原则 是对实现抽象化的一种规范。 ( 4 ) 依赖倒置原则 依赖倒置的主要思想史如果一个类的一个成员或参数为一个具体类型，那么 这个类就依赖于那个具体类型。如果在一个继承结构中，上层类中的一个成员或 参数为下一个层类型，那么这个继承结构就是高层依赖于低层了。 ( 5 ) 合成复用原则 合成复用原则就是通过合成来实现复用而不是通过继承来实现一个新的对 象。在o o d 中有两种方法可以实现复用，一个是通过合成，一个是通过继承。通 过合成实现复用的好处是： 新对象存取成分对象的唯一方法是通过成分对象的接口。 这种复用是黑箱复用，成分对象的内部细节对外是看不见的。 这种复用所需要的依赖较少。 这种复用可以在运行时间内动态进行，新对象可以动态的引用与成分对象 类型相同的对象。 而通过继承来实现复用虽然具有新的实现容易和修改、扩展继承而来的实现 较容易等特点，但是继承复用破坏了包装，它将超类的实现细节暴露给子类。另 外，如果超类发生了变化，则子类也会发生一定的改变以及超类和子类的关系是 静态的，不能在运行时间内发生改变，没有足够的灵活性等。 2 1 2 设计模式的基本要素 设计模式是一套被反复使用、多数人知晓的、经过分类编目的、代码设计经验的 总结，它可以使人们更加简单方便地复用成功的设计和体系结构。但是一个好的设计模 式只有在描述清晰的前提下才能给使用者一个容易理解的思路和解决问题的方式。设计 模式描述主要包含下面四个基本元素f 6 】。 大连理工大学硕士学位论文 ( 1 ) 模式名称( p a 仕e mn 锄e ) 描述了这个设计模式的大体功能。一个好的设计模 式名称可以让我们进行讨论并在实践中应用，便于我们与其他人交流设计思想集设计结 果。 ( 2 ) 问题( p r o b l e m ) 描述了我们应该在何时使用模式。它解释了设计问题和问 题存在的前因后果。 ( 3 ) 解决方案( s o l u t i o n ) 描述了设计的组成成分，他们之间的相互关系以及 各自的职责和协作方式。以为模式就像一个模板，它可以应用于多种不同场合。 所以解决方案并不描述特定而具体的设计或实现，而是提供一个设计问题的抽象 描述和怎样一个具有一般意义的元素组合来解决这个问题。 ( 4 ) 效果( c o n s e q u e n c e s ) 描述了模式应用的效果以及使用模式应考虑的问题。 尽管我们描述设计决策时不不总提到模式效果，但是他们对于评价设计选择和理 解使用模式的代码具有重要意义。 模式名称、问题、解决方案和效果四个元素对设计模式从不同方面进行了描 述，是不可缺少的部分。随着设计模式描述的不断利用，许多元素被加到设计模 式当中，如模式分类、参与者、示例代码、相关模式等等。通过模式的不断丰富， 可以让编程人员更好的理解。 2 1 3 设计模式的分类 设计模式主要分为创建型模型、结构型模型和行为型模型。 创建型模型是处理对象的创建，它创建某一情景下的对象。创建对象的基本形式可 能会引起设计问题或给设计带来一定的复杂性，但是创建型模型能设法地解决这个问 题。创建型模式中包括抽象工厂模式、工厂方法模式、单件模式等。抽象工厂模式集中 处理了哪一个工厂应该被实例化。工厂方法模式则是一个创建对象的模式，它根据输入 的一个参数从工厂中选择一个相应的对象来进行创建。单件模式则是强制一个类只能创 建一个对象。 结构型模型是一个在两个实体之间建立关系的模型。当两个实体之间没有或他们之 间关系很弱但是又需要他们两个之间进行访问而实现一定的功能时，可以利用结构型模 型来进行设计。结构型模型主要包含了适配器模式、桥接模式等。适配器模式可以把一 个类的接口进行转化从而提供另一种形式的接口一共客户进行调用。这样就不需要对这 个类进行修改，避免了由于修改带来的错误。桥接模式是架设在两种不同解决方案之间 的桥梁，虽然位于桥的一边的方案会调用另一边的方案，但对于任何一边方案的改变都 不会影响到另一边。 基于并行设计模式的软件演化方法研究 行为型模型是一个识别和设计多个对象之间通信的模型，它增加了实施对象之间通 信的灵活性。行为型模式主要有观察者模式、策略模式等。观察者模式就是定义对象间 的一种一对多的依赖关系，当一个对象的状态发生改变时，所有依赖于她的对象都得到 通知并被自动更新。策略模式定义了一系列的算法，把它们一个个封装起来，并行使它 们可相互替换。它提供了一种替代继承的方法，避免程序中使用多重条件转移语句，使 系统更灵活，易于扩展。 2 2 设计模式的描述语言 一个好的设计模式思想需要一个好的容易被别人理解的描述语言进行描述。这个好 的描述语言需要具有简单性、结构性、可转化性、可扩展性和跨平台性等特点。简单性 说明它可以利用简单的逻辑来描述一个复杂的设计模式，便于编程人员之间进行讨论； 结构性说明它可以利用一个具有结构的体系来描述设计模式，便于计算计算识别和维 护；可转化性则说明这种描述语言可以进行转化，实现设计模式之间的转化以及设计模 式的重构；跨平台性则说明它可以在多个平台下应用，不受平台的限制。 2 2 1u m l 描述方法 u m l ( u 1 1 i 6 e dm o d e l m gl a l l g u a g e ，统一建模语言) 是一种用来对软件系统进行可 视化建模的语言，是面向对象开发系统的产品说明、可视化和编制文档的一种标准语言。 u m l 主要包括以下五种类型的图形，分别为用例图、静态图、行为图i 交互图和实现 图。 在设计模式进行描述中，u m l 主要利用类图对设计模式中的静态结构进行描述1 9 】， 主要包括类的定义及其所具有的属性和操作、类之间的关联关系等。设计模式中的动态 结构主要是利用i ，m i ，中的序列图进行描述，主要包含了设计模式中对象间的交互及其 相应的信息传递。 u m l 是基于图形来进行描述的，现在支持u m l 的工具很多但它们没有一个统一的 标准，所以在它们之间实现设计模式转化非常困难。 2 2 2 自然语言描述方法 基于自然语言的设计模式描述也是一种典型的描述方法，它从模式的名字、可以解 决的问题、应用意图、参与者、参与者之间的交互、用例代码等元素方面进行描述，以 便于编程人员进行理解并应用。自然语言是人类语言，我们可以对设计模式的每一个细 节进行详细的描述，以便于编程人员更好地对其进行理解与应用。 大连理工大学硕十学位论文 但是基于自然语言的设计模式描述不具有很好的结构性，虽然它容易被编程人员所 理解但是它却不利于计算机进行识别。基于自然语言描述的设计模式不具有很好的结构 性，所以计算机很难对其进行语法分析以识别出设计模式内的信息细节。 2 2 3g e b n f 描述方法 g e b n f ( 研印1 1 i c a le x t e n d e db a c k u sn o 册a 1f o m ) 是对e b n f 的一个基于图形描述 的扩展。e b n f 是表达作为描述计算机编程语言和形式语言的正规方式的上下文无关文 法的元语法符号表示法。g e b n f 利用终结符和非终结符来对设计模式中的元素进行描 述。如： 非终结符的一个元素为n 啪，用它来代表o 到9 之间的任一数字。则基于g e b n f 的描述方法中n 姗的形式如下： n u i i l ：11 2 1 31 4 1 51 6 1 7 | 8 1 9 i o 。 这种描述方式利用终结符和非终结符来代替非终结符以表达需要描述的信息，它可 以对非终结符进行任意扩展以描述设计模式中的细节。这种描述方法虽然容易扩展并行 可以在多个平台下共享，但是这种描述方式不具有结构性，不利于以后的维护。 2 2 4x m l 描述方法 l 是一种可扩展的结构性描述语言，它利用简单的结点标签来对设计模式进行 描趔旧】。基于x 池描述的设计模式具有跨平台性、易扩展性、易重构性等特点，而且 还利于计算机进行识别与应用。这些特点都是u m l 、n a ：t l 瑚ll 锄触g e 和g e b n f 等描 述方法所不能比拟的。 2 3 并行设计模式 并行设计模式是通用设计模式之外的一种，它为并行编程提供了一种可重复利用的 设计方案。并行设计模式主要包含两种类型，一个是算法模式，一个是结构模式j2 1 。 算法模式为我们提供解决某一个问题快速有效的方法，而结构模式【1 1 】贝0 为我们提供了一 个解决问题的策略，包括计算结构、数据流、及其同步和通信结构等。算法模式包括分 治模式等，结构模式m a i l a g e 删o r k e r 模式等。 文献 1 3 对并行设计模式从寻找并行性设计空间、算法结构设计空间、支持结构设 计空间和实现机制设计空间来进行描述。其中寻找并发性设计空间包含了任务分解模 式、数据分解模式等，通过任务分解和数据分解等模式来找到问题当中可以并发执行的 信息。算法结构设计空间则包含了任务并行模式、分治模式等，为解决某个问题提供一 基于并行设计模式的软件演化方法研究 种思路。支持结构空间则包含了循环并行、共享数据等模式，主要是讨论了支持结构， 并在最后的实现机制中对其进行实现。 2 4 设计模式的应用 设计模式为某一重复发生的问题提出了一个可以重复利用的设计框架。它可以为程 序设计提供一个简单的设计方案，提高了代码的可重用性和可维护性。在面向对象的软 件开发过程中，设计模式主要是用来指导编程人员进行软件结构设计。目前，对于设计 模式的应用已经开始像自动代码生成的方向进行转化【1 4 。1 引。 利用设计模式进行代码编程需要编程人员处理模式的结构逻辑以及模式内的业务 逻辑，这样可能会产生由错误理解或手动编写错误而使产生的代码不正确。为了减轻编 程人员的负担而使他们集中精力处理业务逻辑错误，研究人员提出了一种基于设计模式 的框架代码生成的思想【1 6 。1 8 】。设计模式是某一类相似问题共同点的一个抽象，由于每一 个具体问题的细节不同，利用设计模式只能生成一个可用的代码框架。这个代码框架为 我们提供了一个解决问题的基本步骤，但是每一步的具体细节还需要编程人员进行手动 添加。 。 在利用并行设计模式进行编程时，自动代码框架生成的作用是非常明显的。并行编 程是利用多个计算元素来进行问题求解，这样他就需要对多个计算元素之间的同步和通 信进行处理，是并行编程中难以处理的两个地方。但是通过并行设计模式的描述以及进 行代码框架生成，为编程人员处理了多个对象之间的同步和通信机制l l 9 1 。这样就为编 程人员减少了对于这两个部分处理时间和精力，也减少了由于手动编写而产生的一些错 误。另外，基于并行设计模式的框架代码生成还可以为习惯于串行编程的人提供个“串 行 的编程环境，使他们也可以进行并行编程。 2 4 1基于设计模式的并行编程 随着高性能计算机的广泛应用，并行编程已经成为一种发展趋势。并行编程技术主 要有0 p e n m p 等基于共享存储平台和m p i 等基于分布式存储平台的两大类型的编程机制。 现在的并行编程人员主要是理解需求后以o p e n m p 或m p i 等并行编程技术实现并行代 码设计，例如o p e 州p 中的p a r a l l e l 向r 和m p i 的m p is e n d 和m p il ：b e c e 等控制结构。 基于业务流程的编程方式最主要的特点就是它是按着业务流程一步一步地计算并求出 最终的结构。虽然这种编程方式实现了预期的效果，但是基于这种编程方式生成的代码 不利于以后的维护。因为它把程序中的各种功能模块整合在一起，没有使它们分成几个 独立的部分并对外提供一定的接口。这样在对代码进行更改时，编程人员就需要对大部 大连理工大学硕士学位论文 分相关的代码进行理解并进行修改。如果把这些功能的模块分成几个独立的部分，使他 们之间通过一定的接口来互相访问，当需要对代码进行修改时，我们只需要更改某一个 模块就可以，而不用对其他模块的代码也进行修改。 现在设计模式已经在串行编程中得到了广泛的应用并取得了很好的效果。设计模式 是一套被反复使用、多数人知晓的、经过分类编目的、代码设计经验的总结，它为一类 重复发生的问题提出了一个设计框架。这个设计框架提供了解决这个问题的大致方法， 对于这个问题的每一个细节，我们可以对这个设计框架进行细化以供我们来解决实际问 题。在实际系统编码中，编程人员根据设计模式的具体描述设计编写相对应的代码【1 7 。1 州。 基于设计模式的编程方式把一个大的系统分成了几个独立的部分，这些部分按着一个相 对的执行约束进行计算。这些独立的部分可以都是基于多个设计模式来进行实现，内部 的实现细节对其他的部分保密，只提供一些可以供其他部分进行调用的接口。这种实现 方式把每一部分都独立出来，实现多个功能之间的松耦合，当需要对系统进行更改时， 可以只更改其中的某一个部分，而不用破坏系统中其他的部分，大大提高了系统的可重 用性和可维护性。 并行编程虽然不是一个新的编程技术，但是并行编程还不为广大的编程人员所熟 知。在并行编程中主要是利用o p e i m p 和m p i 等编程技术来实现并行编程。并行设计 模式也是并行编程中一个较复杂的问题，主要的研究方向为并行设计模式的描述和应 用。对于并行设计模式的描述已经存在一些如自然语言、u m l 等描述方法。在并行设计 模式的应用方面，d p n d p ( d e s i 驴p a 眦ma n dd i s t r i b u t e dp r o c e s s i n g ) 、e n t e 删s e 、c o d e 2 、 c 0 2 p 3 s ( c o r r e c to b j e c t - o n e m e dp a 仕e m - b 嬲e dp a r a l l e lp r o g r a m m i n gs y s t e m ) 等系统已 经得到了一个很好的实验结果。 这些编程系统中包含了一个基于不同方式描述的并行设计模式库，以供编程人员选 择来进行并行编程。编程人员可以从这个库中选择一个或多个适合解决问题的设计模式 描述，并利用设计模式自动生成可并行执行的代码框架，并添加一些业务逻辑代码。通 过并行设计模式进行编程不但会自动生成一个可以并行执行的代码框架( 主要包括设计 模式中类的定义以及它们之间的同步和通信) ，节省了由于人工编写所耗费的时问和精 力，还为习惯于串行编程的人提供了一个“串行 的编程环境，使广大的不熟悉并行编 程的人也可以很好地进行并行编程。设计模式生成的代码框架包含了并行编程中的同步 和通信等代码处理，减少了由于并行编程中对这两个部分没有正确地处理而引起的错 误，如多个处理器为争取同一个资源而产生的死锁。另外，基于并行设计模式的编程为 我们提供了一个可重用的设计方案，提高了代码的可重用性和可维护性。这些优点都无 不显示了基于设计模式进行编程所代码的好处。 基于并行设计模式的软件演化方法研究 这些基于并行设计模式进行编程的系统都包含一个可维护的并行设计模式库，编程 人员可以从这个库中选择适合的设计模式来进行并行编程。如果库中的设计模式对于某 一个问题没有一个适合的解决方案，那么编程人员可以对这个库中的某一个设计模式进 行适当的修改或添加一个新的设计模式来解决这个问题。当我们利用并行设计模式进行 编程时，选择一个设计模式并提供它生成并行代码框架时所需要的一些参数，以生成一 个可以并行执行的代码框架【1 7 - 1 8 】。在c 0 2 p 3 s 系统中，编程人员需要提供一些例如模式 中参与者在实际代码中命名的参数等。当这个可执行的代码框架生成时，编程人员就可 以添加一些处理问题的业务逻辑生成一个可并行执行的程序，如把某一个大的问题分为 多个小的可以并行计算的子任务以及解决这些子任务的相关代码。由于每一个问题之间 都具有不同性，所以还不能对这部分进行自动生成。基于并行设计模式的并行编程步骤 如图2 1 所示。 图2 1 基于并行设计模式的编程结构 f i g 2 1 t h es 仇l c 胁r e0 fp a m l l e ld e s i 印p a t t e mb 雒e dp r o 彤瑚m i n g 在基于并行设计模式的并行编程系统中主包含了以下三个主要的部分，结构骨架、 抽象模块和具体模块。一个并行的结构骨架式一个封装了并行设计模式中的静态结构和 大连理工大学硕士学位论文 动态行为结构的属性的一个集合。这些属性被参数化并通过参数传递来进行具体化，生 成一个抽象的并行计算模块。这个抽象的并行计算模块与结构骨架之间存在了一种继承 关系。当对这个抽象模块进行应