（计算机软件与理论专业论文）曙光3000上基于泛型编程的并行结构库的研究与实现.pdf

丫 7 1 2 2 1 2 摘要 并行程序的开发是并行计算中一个公认的难题。其中一个重要的原因在于 缺乏系统的开发并行程序的方法和相关的辅助工具。现有的大多数并行程序设 计模型本质上是对并行程序编码的研究，它们为并行程序的设计编码提供一个 抽象的平台，但缺乏指导程序员在其所提供的平台上 进行并行程序开发、推导 和验证的方法。如何在一个给定的抽象模型的平台上设1 十 出符合问题要求的并 行程序，完个取决于程序员的技巧和经验;程序的可靠性、开发效率都难以得 到保证。 在本文的前期研究中，我们提出了一种系统的 基于泛型编程的并行程序开 发方法和模j q ，该模型支持从问题到并行程序的整个程序开发过程，并提供 了 泛烈算法结构库和泛型并行结构库作为编程者进行抽象并行程序开发的支持。 编程者通过在该模型下开发并行程序，将并行程序开发过程中的创造性工 作和 非创造性工作区分开来，创造性工作由编程者完成，非创造性工 _ 作由机器完成， 有效地提高了 程序的开发效率。 泛型并行结构库是 卜 述描述的并行编程模型中的一个重要组成部分通过 对编程者提供泛型并行结构库的支持，编程者在并行实现时，无需关注大部分 的低层次细节，极大地减轻了 编程者的负担，提高了并行程序的可编程性，可 重用性和可靠性等。本文工作即是对该模型中的泛型井行结构库的几个主要模 式进行开发、设计与实现。因此，本文工作涵盖了以下几点: i )本文 对并行计算中的 管理者一卜 人、 流水线并行和丁作池二 种并行结构 进行了深入研究， 并为这三种结构进行抽象出了三种并行结构模式。 其 中，如何应用设计模式 ( d e s i g n p a tt e rn) 和泛型程序设 计 ( g e n e r i c p r o g r a m m i n g ) 思想， 抽象出 灵活、高 效、 优雅的 并行结 构模式是本文 研究的难点和关键之一; 2 )以本文抽象出的三种并行结构模式为基础，实现出相应的并行结构模 板，以支持抽象并行程序的实现。 3 )以人 量的具体算法实例和多组的对比实验， 对本文开发的二 种并行结构 模板的可重用性、可编程性、可靠性和运行效率，f -j 传统的 p v 叨mp l 并行编程方法进行了比较和分析。 关键词:设计模式 泛型编程 泛型并行结构库 p v m/ mp i 并行编程 ab s t r a c t d e v e lo p m e n t o f p a r a l l e l p r o g r a m s i s c o n c e r n e d a s a n a c k n o w l e d g e d d i f f ic u lt y i n p a r a l l e l c o m p u t i n g d e v e l o p i n g p a r a l l e l a n i m p o rt a n t r e a s o n i s t h e l a c k o f s y s t e m i c m e t h o d o n r a m a n d s o m e i n t e r r e l a t e d a s s i s t a n t d e v e l o p m e n t t o o l s . mo s t p a r a l l e l b a s i c a l l y p r o g r a m m i n g m o d e l s a t p r e s e n t t h e y o ff e r a b s t r a c t o f me t h o d t h a t c a n p r o g r a ms . i t d e c i d e s p a r a l l e l p r o g r a m i n g u i d e p l a t f o r m s f o r p r o g r a mme r s a r e s t u d y i n g o n p a r a l l e l p 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 g a n d c o d i n g , b u t l a c k t o d e v e l o p , d e r iv e a n d v e r i f y p a r a l l e l o n p r o g r a m m e r s s k i l l s a n d e x p e r ie n c e s t h a t h o w t o d e s ig n a a c c o r d w it h p r o b l e m s r e q u i r e m e n t a t a g i v e n a b s t r a c t m o d e l p la t f o r m . s o t h e c o r r e c t n e s s a n d d e v e l o p m e n t e ff i c i e n c y o f p r o g r a m s a r e d i ffic u l t o f b e in g g u a r a n t e e d i n t h i s t h e s i s s p r o p h a s e s t u d y , w e p r o p o s e d a d e s ig n - p a t t e r n - b a s e d p a r a l l e l p r o g r a m d e v e l o p m e n t m e t h o d a n d m o d e l , w h i c h s u p p o rt s t h e w h o l e p r o c e s s o f p a r a l l e l p r o g r a m d e v e l o p m e n t , fr o m p r o b l e m s p e c i f i c a t i o n s t o p a r a l l e l p r o g r a m s . t h i s m o d e l s t i l l i n t r o d u c e s t h e i d e a o f d e s ig n p a tt e rn , w h i c h s u p p o rt s t h e w h o l e d e v e l o p m e n t p r o c e s s t h r o u g h p r o v i d i n g g e n e r i c a lg o r it h m i c p a t t e r n d a t a b a s e a n d g e n e r i c p a r a l l e l s t r u c t u r e d a t a b a s e . t h r o u g h d e v e l o p i n g p a r a l l e l p r o g r a m in t h i s m o d e l , d e v e lo p e r s d i s t i n g u i s h e c r e a t i o n a r y l a b o r w h i c h d o n e b y d e v e l o p e r s f r o m n o n - c r e a t i o n a ry l a b o r w h ic h d o n e b y c o m p u t e r , s o i m p r o v e e f fi c i e n c y o f d e v e l o p m e n t g e n e r i c p a r a l l e l s t r u c t u r e d a t a b a s e i s a n i m p o rt a n t c o m p o n e n t o f p a r a l l e l p r o g r a m m in g m o d e l d e s c r i b e d b e f o r e . t h e p u r p o s e o f t h i s t h e s i s i s t o d e v e l o p , d e s ig n a n d i m p l e m e n t s e v e r a l p a r a l l e l s t r u c t u r a l p a t t e r n s o f g e n e r i c p a r a ll e l s t r u c t u r e d a t a b a s e i n t h e m o d e l . s o , t h e p r im a ry w o r k s w e h a v e d o n e i n t h i s t h e s i s a r e li s t a s f o l l o ws 1 ) t h e t h e s i s s t u d y s t h r e e c o m m o n p a r a l l e l s t r u c t u r e s , t h e n a b s t r a c t a n d g e t t h r e e p a r a l l e l s t r u c t u r a l p a t t e rn s . o n e e m p h a s i s i s h o w t o a p p ly t h e i d e a o f d e s i g n p a t t e r n a n d g e n e r i c p r o g r a m m i n g t o a b s t r a c t io n i n o r d e r t o g e t h i g h e r r e u s a b i l it y 2 ) i m p l e m e n t t h r e e p a r a l l e l s t r u c t u r a l p a tt e rn s a n d g e t t h r e e s t r u c t u r a l t e m p la t e s i n o r d e r t o s u p p o r t im p l e m e n t i o n o f a b s t r a c t p a r a l l e l p r o g r a m s 3 ) t e s t a l l p a r a l l e l s t r u c t u r a l t e m p l a t e s a b o u t p e r fo r m a n c e , p r o g r a m m a b i l it y , r e u s a b i l it y a n d r e l i a b i l it y , c o n t r a s t e d i t w it h t r a d it io n a l p v m / m p l p a r a l l e l p r o g r a m m i n g m e t h o d t h r o u g h d e v e l o p i n g m a n y e x a m p l e s a n d a n a l y z i n g t h e s e k e y w o r d : d e s i g n p a t t e r n , g e n e r i c p r o g r a m m i n g , g e n e r ic p a r a l l e l s t r u c t u r a l d a t a b a s e , p v m/ mp i p a r a l l e l p r o g r a m m i n g 江西师范大学硕士学位论文 第一章 绪论 1 . 1引言 在信息技术高度发展的今天，随着人类社会活动、科学技术与文化教育的 不断进步，并行计算显得越来越重要。我们知道，计算机发展中永恒的主题是 追求超高运算速度 许多有关国计民生的科学研究课题如地球物理、 生物医学、 遥感技术、计算化学、海洋探测、大气污染、超声波应用、核酸模拟、结构力 学、跨声速流计算、地块偏移、潮汐模拟、计算几何、遗传工程、工业自 动化、 军事指挥、经济决策、情报分析、卫星图像处理、天气预报、人口预测、导弹 轨道i 算、社会现象模拟等需要加工的数据信息及其加工处理的工作量随时间 指数增长，已达到天文数字的量级。因此对计算机速度提出越来越苛刻的要求。 然而，现有的计算机算法 ( 程序)主要是串行的，即他们规定了程序在机器上 执行的次序并月 _ 还规定了每步只能执行单一的操作，因而程序的运行速度完全 依赖于串行计算机部件的处理能力和速度。大家都知道，任何部件都有它们的 物理极限一它们的速度不会超过光速。因而在计算机软件和硬件中引入并行化 是解决大规模问题的关键技术。 但是目前，并行程序设计还没有达到科学化、实用化、大众化的阶段。其 根本的原因在于 并行计算机系统结构的复杂性和多样性，由十缺乏一个如同串 行计算机系统的“ 冯. 诺伊曼模型” 那样的统一的计算模型，并行程序的开发无法 在一个统一的标准一 进行，从而导致了其复杂性、低效性、不可移植性等问题。 另一个重要的原因在于缺乏系统的开发并行程序的方法和有关的辅助工具。现 有的并行计算模型基本上都是语言级的，它们为并行程序设计提供一个抽象的 平台，但缺乏指导程序员在其所提供的平台上进行并行程序开发、推导和验证 的方法。如何在一个给定的抽象模型的平台上设计出符合问题要求的并行程序 完全取决于程序员的技巧和经验，程序的可靠性、开发效率都难以得到保证。 目前有关统一并行计算模型有很多建议，提出了许多并行计算模型，但各 种计算模型之间无法统一到同 一 框架，这可能是目前数学理论还没有为统一模 型提供描述基础。因此，探索一种能简化并行程序开发的过程，提高并行程序 开发的高效性的实用的并行程序开发方法是很有必要的。在本文的前期研究 1 6 - 2 6 1 中，我们提出了一种系统的基于泛型编程的并行程序开发方法和模型。 本文的工作是其中的一个重要组成部分。 江西师范大学硕士学位论文 1 . 2并行程序开发方法研究概述 并行计算的研究己有二十多年的历史，计算机科学工作者对并行程序开发 方法作了大量的研究。然而，并行应用程序的开发仍然是一件困难、易错的t . 作。从程序的开发过程所经历的不同阶段出发，可以把并行程序开发方法的研 究分成三个领域:面向问 题的方法、 面向 算法的方法和面向语言 的方法 4 1 . 并行程序的开发司以分别有止个出发点，即可以从最初始的问题规范出发， 可以从顺序的算法出发，也可以从顺序程序出发，分别研究与开发其中的并行 性，从而得到可在并行计算机上执行的并行程序。 1 . 2 . 1面向问题的并行程序开发 自向问题的方法是从问题的规范描述出发，开发并行程序的方法。它与顺 序程序开发的出发点是相同的，只是在开发过程中要考虑问题潜在的并行性开 发、并行求解和如何实现其并行性的问题。因此，概括而言，与顺序程序的开 发类似，一种途径是采用形式化的程序综合与推导的方法，使用一系列的语 义转换规则，将规范描述语言 所描述的问题逐步求精，从而得到程序设计语言 所表示的可执行程序。并行程序的形式化开发，与顺序程序和比要复杂得多， 现有的广为人知的并行程序的验证和开发系统模型有 c s p , u n i t y, a c t i o n s y s t e m , s h a r e d - s t a t e m o d e l s 等; 另 一 种 途径 是 采 用并 行 算 法的 设计 和 实 现技 术， 通过在某种并行计算模型上设计出解决特定问题的并行算法，然后实现该并行 算法，将算法映射为可在特定并行计算机上执行的并行程序。 1 . 2 . 2面向算法的并行程序开发 面向算法的方法并不是指顺序算法的并行实现，也不是单一地考虑某一个 问题的算法设计，而是研究问题的求解规律，即算法设计过程的规律性，根据 现实世界算法问题中所固有的行为上的相似性对算法问题进行分类，使得同一 类中的所有算法问题的求解符合某种特定的设计模式。这样，通过对设计模式 的并行性开发，就能解决一 类问题的并行程序开发。 1 . 2 . 3面向语言的井行程序开发 面向语言的方法可分为两类。一类是显式并行性开发方法，即研究并行的 语言或模型，通过在语言 或模型中提供一些并行性定义的机制，程序设计人员 使用这些机制来刻画并实现算法问题巾的并行性。对并行语言与并行模型的研 江西师范大学硕士学位论文 1 . 2并行程序开发方法研究概述 并行计算的研究己有二十多年的历史，计算机科学工作者对并行程序开发 方法作了大量的研究。然而，并行应用程序的开发仍然是一件困难、易错的t . 作。从程序的开发过程所经历的不同阶段出发，可以把并行程序开发方法的研 究分成三个领域:面向问 题的方法、 面向 算法的方法和面向语言 的方法 4 1 . 并行程序的开发司以分别有止个出发点，即可以从最初始的问题规范出发， 可以从顺序的算法出发，也可以从顺序程序出发，分别研究与开发其中的并行 性，从而得到可在并行计算机上执行的并行程序。 1 . 2 . 1面向问题的并行程序开发 自向问题的方法是从问题的规范描述出发，开发并行程序的方法。它与顺 序程序开发的出发点是相同的，只是在开发过程中要考虑问题潜在的并行性开 发、并行求解和如何实现其并行性的问题。因此，概括而言，与顺序程序的开 发类似，一种途径是采用形式化的程序综合与推导的方法，使用一系列的语 义转换规则，将规范描述语言 所描述的问题逐步求精，从而得到程序设计语言 所表示的可执行程序。并行程序的形式化开发，与顺序程序和比要复杂得多， 现有的广为人知的并行程序的验证和开发系统模型有 c s p , u n i t y, a c t i o n s y s t e m , s h a r e d - s t a t e m o d e l s 等; 另 一 种 途径 是 采 用并 行 算 法的 设计 和 实 现技 术， 通过在某种并行计算模型上设计出解决特定问题的并行算法，然后实现该并行 算法，将算法映射为可在特定并行计算机上执行的并行程序。 1 . 2 . 2面向算法的并行程序开发 面向算法的方法并不是指顺序算法的并行实现，也不是单一地考虑某一个 问题的算法设计，而是研究问题的求解规律，即算法设计过程的规律性，根据 现实世界算法问题中所固有的行为上的相似性对算法问题进行分类，使得同一 类中的所有算法问题的求解符合某种特定的设计模式。这样，通过对设计模式 的并行性开发，就能解决一 类问题的并行程序开发。 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等集中f 大量 研究 工作的中等抽象程序的模型等。另一类是隐式并行性的开发，即通过在语言的 编译器中加入识别程序中所存在的可并行单元的功能，使得经编译后产生的代 码为并行的代码。 1 . 2 . 4三类研究的比较 在对并行程序开发方法的研究中，大量的研究集中于面向问题的方法和面 向语言的方法，而对面向算法的研究较少。到目前为止，尽管各个领域都取得 了一些成果，但尚未有一种公认的切实可行的开发易编写、可移植、高性能的 并行程序的方法 通过形式化方法推导程序一直是程序设计的理想，国际国内都非常重视这 方面的研究，尽管这一方法在理论上己日益成熟，但真正应用起来往往仅限于 开发一些小程序，而且 其方法难以为一般的用户所运用，而并行程序的复杂性 又增加了形式化开发的难度，因此，并行程序的形式化开发离实际的应用仍有 一定的距离。 并行算法的设计方法的研究一直伴随着并行计算研究的历史，尽管现已开 发 厂 许多问题的并行算法，但由于 并行算法设计的复杂性，至今尚无一套普遍 适川的系统的设计方法。并行算法的设计不仅要考虑问题的特性，还要考虑其 将运行于的并行计算机的特性，且在特定并行模型下设计的并行算法往往只能 实现于某一类特定结构的并行计算机，算法的通用性差，随着新的并行计算机 体系结构的日 益出现，对同一问题需要不断设计新的相应的并行算法。 代码的并行化编译一般要经过相关性分析、优化和代码生成三个阶段。它 的主要思想是通过对源代码中数据流和控制流的分析，寻找出一些不具有相关 性的片段，将它们并行化。这一方法从源代码出发，一开始就将变量等程序实 现方面的细节考虑进去，这些细节往往掩盖了问题本身具有的并行性，因此必 然带来更高的复杂性，而且，并行化编译开发的是细粒度的并行，程序效率难 以提高，程序并行化的程度也受到原顺序程序的局限，一个好的并行程序往往 并非来源于一个好的顺序程序。 显式并行化是近年来研究较多的方法，它通过在语言或模型中提供井行性 描述和实现的机制，而将并行性开发的任务完全交给了程序员。由于缺乏系统 的开发方法，从问题的求解到并行实现的整个过程对程序员而言 是一个复杂与 江西师范大学硕士学位论文 究，包括传统的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等集中f 大量 研究 工作的中等抽象程序的模型等。另一类是隐式并行性的开发，即通过在语言的 编译器中加入识别程序中所存在的可并行单元的功能，使得经编译后产生的代 码为并行的代码。 1 . 2 . 4三类研究的比较 在对并行程序开发方法的研究中，大量的研究集中于面向问题的方法和面 向语言的方法，而对面向算法的研究较少。到目前为止，尽管各个领域都取得 了一些成果，但尚未有一种公认的切实可行的开发易编写、可移植、高性能的 并行程序的方法 通过形式化方法推导程序一直是程序设计的理想，国际国内都非常重视这 方面的研究，尽管这一方法在理论上己日益成熟，但真正应用起来往往仅限于 开发一些小程序，而且 其方法难以为一般的用户所运用，而并行程序的复杂性 又增加了形式化开发的难度，因此，并行程序的形式化开发离实际的应用仍有 一定的距离。 并行算法的设计方法的研究一直伴随着并行计算研究的历史，尽管现已开 发 厂 许多问题的并行算法，但由于 并行算法设计的复杂性，至今尚无一套普遍 适川的系统的设计方法。并行算法的设计不仅要考虑问题的特性，还要考虑其 将运行于的并行计算机的特性，且在特定并行模型下设计的并行算法往往只能 实现于某一类特定结构的并行计算机，算法的通用性差，随着新的并行计算机 体系结构的日 益出现，对同一问题需要不断设计新的相应的并行算法。 代码的并行化编译一般要经过相关性分析、优化和代码生成三个阶段。它 的主要思想是通过对源代码中数据流和控制流的分析，寻找出一些不具有相关 性的片段，将它们并行化。这一方法从源代码出发，一开始就将变量等程序实 现方面的细节考虑进去，这些细节往往掩盖了问题本身具有的并行性，因此必 然带来更高的复杂性，而且，并行化编译开发的是细粒度的并行，程序效率难 以提高，程序并行化的程度也受到原顺序程序的局限，一个好的并行程序往往 并非来源于一个好的顺序程序。 显式并行化是近年来研究较多的方法，它通过在语言或模型中提供井行性 描述和实现的机制，而将并行性开发的任务完全交给了程序员。由于缺乏系统 的开发方法，从问题的求解到并行实现的整个过程对程序员而言 是一个复杂与 江西师范大学硕士学位论文 困难的_ l 作。而且，由于 程序员水平与风格的差异，软件的质量与效率往往难 以得到保证。 面向算法的并行程序开发，从某种意义而 言，是一种隐式并行化的工作， 但与井行化编译有木质不同，它将并行化的工作从语言一级提高到算法一级， 减少了琐碎的实现细节的影响，而更关注的是算法问题类本身固有的并行性， 同时，通过对算法问题的分类与抽象， 可以利用顺序算法的设计经验，构造特 定的算法结构模式，预先开发出其中的并行性;另一方面，可以将并行计算中 常见的并行结构如数据并行、流水线并行、工作池、管理者一工人等的结构与 行为进行抽象描述，构造出相应的并行结构模式，以支持对算法结构模式所开 发出的井行性的实现，这样一来，使程序设计人员可以不必完全显式地进行并 行开发，从而简化了并行程序的开发过程，降低了并行程序开发的复杂性，是 一种切实可行的并行程序开发方法的研究途径。 1 . 3设计模式研究概述 日前，设计模式的上 要应用领域是面向对象程序设计与软件构造领域，因 而人们对 一 般的设计模式概念的理解局限在面向对象软件工程领域与软件构 造。本小节对设计模式的思想、概念进行简要的概述，详细介绍了目前典型的 四个基于模式的并行程序开发系统以及我们自己的设计模式概念。 1 . 3 . 1设计模式的思想 设计模式的概念最早起源于建筑设计大师c h r i s t o p h e r a l e x a n d e r 关于城市规 划和建筑设计的著作 建筑的永恒方法。他提出的设计模式概念成为其后用 于 面向对象的设计模式的基础，也为不同领域中设计模式的概念提供了基本的 框架。 将设计模式概念引入面向对象软件工程领域的标志是g a m m a 等人著作的 5 一书。 其中对设计模式的定义为:“ 对被用来在特定场景下解决 一 般设计问 题的类和相互通信的对象的描述”。一般而言，一个模式有四个基本要素:模 式名称 ( p a tt e r n n a m e )，是一个助记名， 它用一两 个词来描述模式的问 题、解 决方案和效果;问题 ( p r o b le m )，描述了应该在何时使用模式;解决力 一 案 ( s o l u t i o n )，描述了设计的组成部分，它们之间的相互关系及各自 的职责和协 作方式: 效果 ( c o n s e q u e n c e s )，描述了 模式应用的效果及使用模式应权衡的问 题。 最初将设计模式概念引入到软件开发领域是为了 能充分利用己有的软件开 江西师范大学硕士学位论文 困难的_ l 作。而且，由于 程序员水平与风格的差异，软件的质量与效率往往难 以得到保证。 面向算法的并行程序开发，从某种意义而 言，是一种隐式并行化的工作， 但与井行化编译有木质不同，它将并行化的工作从语言一级提高到算法一级， 减少了琐碎的实现细节的影响，而更关注的是算法问题类本身固有的并行性， 同时，通过对算法问题的分类与抽象， 可以利用顺序算法的设计经验，构造特 定的算法结构模式，预先开发出其中的并行性;另一方面，可以将并行计算中 常见的并行结构如数据并行、流水线并行、工作池、管理者一工人等的结构与 行为进行抽象描述，构造出相应的并行结构模式，以支持对算法结构模式所开 发出的井行性的实现，这样一来，使程序设计人员可以不必完全显式地进行并 行开发，从而简化了并行程序的开发过程，降低了并行程序开发的复杂性，是 一种切实可行的并行程序开发方法的研究途径。 1 . 3设计模式研究概述 日前，设计模式的上 要应用领域是面向对象程序设计与软件构造领域，因 而人们对 一 般的设计模式概念的理解局限在面向对象软件工程领域与软件构 造。本小节对设计模式的思想、概念进行简要的概述，详细介绍了目前典型的 四个基于模式的并行程序开发系统以及我们自己的设计模式概念。 1 . 3 . 1设计模式的思想 设计模式的概念最早起源于建筑设计大师c h r i s t o p h e r a l e x a n d e r 关于城市规 划和建筑设计的著作 建筑的永恒方法。他提出的设计模式概念成为其后用 于 面向对象的设计模式的基础，也为不同领域中设计模式的概念提供了基本的 框架。 将设计模式概念引入面向对象软件工程领域的标志是g a m m a 等人著作的 5 一书。 其中对设计模式的定义为:“ 对被用来在特定场景下解决 一 般设计问 题的类和相互通信的对象的描述”。一般而言，一个模式有四个基本要素:模 式名称 ( p a tt e r n n a m e )，是一个助记名， 它用一两 个词来描述模式的问 题、解 决方案和效果;问题 ( p r o b le m )，描述了应该在何时使用模式;解决力 一 案 ( s o l u t i o n )，描述了设计的组成部分，它们之间的相互关系及各自 的职责和协 作方式: 效果 ( c o n s e q u e n c e s )，描述了 模式应用的效果及使用模式应权衡的问 题。 最初将设计模式概念引入到软件开发领域是为了 能充分利用己有的软件开 江西师范大学硕士学位论文 困难的_ l 作。而且，由于 程序员水平与风格的差异，软件的质量与效率往往难 以得到保证。 面向算法的并行程序开发，从某种意义而 言，是一种隐式并行化的工作， 但与井行化编译有木质不同，它将并行化的工作从语言一级提高到算法一级， 减少了琐碎的实现细节的影响，而更关注的是算法问题类本身固有的并行性， 同时，通过对算法问题的分类与抽象， 可以利用顺序算法的设计经验，构造特 定的算法结构模式，预先开发出其中的并行性;另一方面，可以将并行计算中 常见的并行结构如数据并行、流水线并行、工作池、管理者一工人等的结构与 行为进行抽象描述，构造出相应的并行结构模式，以支持对算法结构模式所开 发出的井行性的实现，这样一来，使程序设计人员可以不必完全显式地进行并 行开发，从而简化了并行程序的开发过程，降低了并行程序开发的复杂性，是 一种切实可行的并行程序开发方法的研究途径。 1 . 3设计模式研究概述 日前，设计模式的上 要应用领域是面向对象程序设计与软件构造领域，因 而人们对 一 般的设计模式概念的理解局限在面向对象软件工程领域与软件构 造。本小节对设计模式的思想、概念进行简要的概述，详细介绍了目前典型的 四个基于模式的并行程序开发系统以及我们自己的设计模式概念。 1 . 3 . 1设计模式的思想 设计模式的概念最早起源于建筑设计大师c h r i s t o p h e r a l e x a n d e r 关于城市规 划和建筑设计的著作 建筑的永恒方法。他提出的设计模式概念成为其后用 于 面向对象的设计模式的基础，也为不同领域中设计模式的概念提供了基本的 框架。 将设计模式概念引入面向对象软件工程领域的标志是g a m m a 等人著作的 5 一书。 其中对设计模式的定义为:“ 对被用来在特定场景下解决 一 般设计问 题的类和相互通信的对象的描述”。一般而言，一个模式有四个基本要素:模 式名称 ( p a tt e r n n a m e )，是一个助记名， 它用一两 个词来描述模式的问 题、解 决方案和效果;问题 ( p r o b le m )，描述了应该在何时使用模式;解决力 一 案 ( s o l u t i o n )，描述了设计的组成部分，它们之间的相互关系及各自 的职责和协 作方式: 效果 ( c o n s e q u e n c e s )，描述了 模式应用的效果及使用模式应权衡的问 题。 最初将设计模式概念引入到软件开发领域是为了 能充分利用己有的软件开 江西师范大学硕士学位论文 发经验。这是因为设计模式通常是对于某一类软件设计问题的可重用的解决方 案。优秀的软件设计师都非常清楚，不是所有的问题都需要从头开始解决，他 们更愿意复用以前曾经使用过的解决方案，每当他们找到一个好的解决方案， 他们会一遍又一遍地使用，这些经验是他们成为专家的部分原因。因此，在许 多面向对象的系统中可以看到类和相互通信的对象的重复模式。这些模式解决 特定的设计问题，使面向对象设计更灵活、优雅，最终重用性更好。他们帮助 设计者将新的设计建立在以往工作的基础上，重用以往成功的设计 一 方案。一些 熟悉这些模式的设计者不需再去发现它们，而能够立即将它们应用 几 设计问题 中。 1 . 3 . 2并行程序设计领域中的设计模式 目前，设计模式的应用主要存在于面向对象的软件工程领域，其概念一直 沿用g a m m a 的设计模式定义。 然而，这 ， 概念的使用并不局限于面向对象的构 造，而是可以根据领域的需要对其进行扩展和应用。尽管不像面向对象领域中 对设计模式的研究那么成熟，其他领域在这方面的相关研究工作也是一直在进 行着。一般地，并行计算中，设计模式用于描述重复出现的具有相似结构与通 信同步行为的井行计算问 题及其解决方案。与面向 对象中设计模式概念不同的 是，面向对象中设计模式的抽象程度是设计一级的，而在并行程序开发系统中， 设计模式并不只停留在设计一级，而更重要的是，它提供了 预先的实现。在并 行程序设计 领域， 使 用设 计 模式思想的 研究_ 作有2 , 3 , 4 , 6 , 7 - 1 5 ,3 6 , 3 7 - 4 0 等。 在 并行计算中使用设计模式思想的系统有早期的 c o d e ( b r o w n e e t a l ., 1 9 8 9 ) , f r a m e w o r k s ( s i n g h e t a l ., 1 9 9 1 ) ，近期的 e n t e r p r i s e ( s c h a e f f e r e t a l ., 1 9 9 3 ) , c o d e 2 ( b r o w n e e t a l ., 1 9 9 5 ) , h e n c e ( b r o w n e e t a l . , 1 9 9 5 ) , t r a c s ( b a r t o l i e t a l ， 1 9 9 5 ) , d p n d p ( s iu a n d s in g h , 1 9 9 7 ) 等 3 近 年 来， 相 关的 系 统 有爱 t 堡大 学的 骨架库 e s k e l 1 0 ， 佛罗里达大学的模式语言 1 3 1 等， 尤其是 a l b e r t a大学， 在 f r a m e w o r k s , e n t e r p r is e推出之后，于 2 0 0 0年又开发出了 c o 2 p 3 s ( c o r r e c t o b j e c t - o r i e n t e d p a t t e r n - b a s e d p a r a l l e l p r o g r a m m i n g s y s t e m ) 8 , 9 1 a 1 . 3 . 3典型的基于设计模式思想的并行程序开发系统简介 1 . 3 . 3 . 1 f r a m e w o r k 筒介 f r a m e w o r k s是最早在l _ 作站机群环境下通过对己有的顺序程序进行重构开 发并行性的系统之一。 该系统中的 模式称为模板 ( t e m p l a t e s ) ， 应用程序由以 类 似于远过程调用的形式进行通信、交互的模块组成。模块的通信界面由一个输 江西师范大学硕士学位论文 发经验。这是因为设计模式通常是对于某一类软件设计问题的可重用的解决方 案。优秀的软件设计师都非常清楚，不是所有的问题都需要从头开始解决，他 们更愿意复用以前曾经使用过的解决方案，每当他们找到一个好的解决方案， 他们会一遍又一遍地使用，这些经验是他们成为专家的部分原因。因此，在许 多面向对象的系统中可以看到类和相互通信的对象的重复模式。这些模式解决 特定的设计问题，使面向对象设计更灵活、优雅，最终重用性更好。他们帮助 设计者将新的设计建立在以往工作的基础上，重用以往成功的设计 一 方案。一些 熟悉这些模式的设计者不需再去发现它们，而能够立即将它们应用 几 设计问题 中。 1 . 3 . 2并行程序设计领域中的设计模式 目前，设计模式的应用主要存在于面向对象的软件工程领域，其概念一直 沿用g a m m a 的设计模式定义。 然而，这 ， 概念的使用并不局限于面向对象的构 造，而是可以根据领域的需要对其进行扩展和应用。尽管不像面向对象领域中 对设计模式的研究那么成熟，其他领域在这方面的相关研究工作也是一直在进 行着。一般地，并行计算中，设计模式用于描述重复出现的具有相似结构与通 信同步行为的井行计算问 题及其解决方案。与面向 对象中设计模式概念不同的 是，面向对象中设计模式的抽象程度是设计一级的，而在并行程序开发系统中， 设计模式并不只停留在设计一级，而更重要的是，它提供了 预先的实现。在并 行程序设计 领域， 使 用设 计 模式思想的 研究_ 作有2 , 3 , 4 , 6 , 7 - 1 5 ,3 6 , 3 7 - 4 0 等。 在 并行计算中使用设计模式思想的系统有早期的 c o d e ( b r o w n e e t a l ., 1 9 8 9 ) , f r a m e w o r k s ( s i n g h e t a l ., 1 9 9 1 ) ，近期的 e n t e r p r i s e ( s c h a e f f e r e t a l ., 1 9 9 3 ) , c o d e 2 ( b r o w n e e t a l ., 1 9 9 5 ) , h e n c e ( b r o w n e e t a l . , 1 9 9 5 ) , t r a c s ( b a r t o l i e t a l ， 1 9 9 5 ) , d p n d p ( s iu a n d s in g h , 1 9 9 7 ) 等 3 近 年 来， 相 关的 系 统 有爱 t 堡大 学的 骨架库 e s k e l 1 0 ， 佛罗里达大学的模式语言 1 3 1 等， 尤其是 a l b e r t a大学， 在 f r a m e w o r k s , e n t e r p r is e推出之后，于 2 0 0 0年又开发出了 c o 2 p 3 s ( c o r r e c t o b j e c t - o r i e n t e d p a t t e r n - b a s e d p a r a l l e l p r o g r a m m i n g s y s t e m ) 8 , 9 1 a 1 . 3 . 3典型的基于设计模式思想的并行程序开发系统简介 1 . 3 . 3 . 1 f r a m e w o r k 筒介 f r a m e w o r k s是最早在l _ 作站机群环境下通过对己有的顺序程序进行重构开 发并行性的系统之一。 该系统中的 模式称为模板 ( t e m p l a t e s ) ， 应用程序由以 类 似于远过程调用的形式进行通信、交互的模块组成。模块的通信界面由一个输 江西师范大学硕士学位论文 发经验。这是因为设计模式通常是对于某一类软件设计问题的可重用的解决方 案。优秀的软件设计师都非常清楚，不是所有的问题都需要从头开始解决，他 们更愿意复用以前曾经使用过的解决方案，每当他们找到一个好的解决方案， 他们会一遍又一遍地使用，这些经验是他们成为专家的部分原因。因此，在许 多面向对象的系统中可以看到类和相互通信的对象的重复模式。这些模式解决 特定的设计问题，使面向对象设计更灵活、优雅，最终重用性更好。他们帮助 设计者将新的设计建立在以往工作的基础上，重用以往成功的设计 一 方案。一些 熟悉这些模式的设计者不需再去发现它们，而能够立即将它们应用 几 设计问题 中。 1 . 3 . 2并行程序设计领域中的设计模式 目前，设计模式的应用主要存在于面向对象的软件工程领域，其概念一直 沿用g a m m a 的设计模式定义。 然而，这 ， 概念的使用并不局限于面向对象的构 造，而是可以根据领域的需要对其进行扩展和应用。尽管不像面向对象领域中 对设计模式的研究那么成熟，其他领域在这方面的相关研究工作也是一直在进 行着。一般地，并行计算中，设计模式用于描述重复出现的具有相似结构与通 信同步行为的井行计算问 题及其解决方案。与面向 对象中设计模式概念不同的 是，面向对象中设计模式的抽象程度是设计一级的，而在并行程序开发系统中， 设计模式并不只停留在设计一级，而更重要的是，它提供了 预先的实现。在并 行程序设计 领域， 使 用设 计 模式思想的 研究_ 作有2 , 3 , 4 , 6 , 7 - 1 5 ,3 6 , 3 7 - 4 0 等。 在 并行计算中使用设计模式思想的系统有早期的 c o d e ( b r o w n e e t a l ., 1 9 8 9 ) , f r a m e w o r k s ( s i n g h e t a l ., 1 9 9 1 ) ，近期的 e n t e r p r i s e ( s c h a e f f e r e t a l ., 1 9 9 3 ) , c o d e 2 ( b r o w n e e t a l ., 1 9 9 5 ) , h e n c e ( b r o w n e e t a l . , 1 9 9 5 ) , t r a c s ( b a r t o l i e t a l ， 1 9 9 5 ) , d p n d p ( s iu a n d s in g h , 1 9 9 7 ) 等 3 近 年 来， 相 关的 系 统 有爱 t 堡大 学的 骨架库 e s k e l 1 0 ， 佛罗里达大学的模式语言 1 3 1 等， 尤其是 a l b e r t a大学， 在 f r a m e w o r k s , e n t e r p r is e推出之后，于 2 0