（计算机应用技术专业论文）面向并行程序设计的可视化建模系统的研究与实现.pdf

中文摘要 随着各行业对计算能力及计算速度要求的增加，并行计算成为当今计算机科 学中一个重要的研究领域。但是并行程序设计是一个复杂且耗费精力的过程，在 编码阶段、测试和调试阶段都非常繁琐。如何降低并行程序的开发难度，提高并 行程序的设计开发效率成为并行计算领域一个关键性问题。为解决上述问题，本 文提出了基于模型的可视化并行程序设计的概念，并以此为基础设计并实现了面 向并行程序设计的可视化建模系统。 本文对国内外在简化并行程序的开发过程方面所做的研究与探索进行了总 结与分析，研究了现有的可视化并行程序设计的方法和技术，介绍了几个主要的 可视化并行程序开发环境，分析了各自的优缺点与适用范围。本文通过对传统并 行程序设计方法进行分析，并结合可视化并行程序设计的现有理论提出了基于模 型的可视化并行程序设计的概念。本文详细描述了可视化并行程序设计中的编程 模型、进程模型和通信模型，对各个模型进行了基本定义，并说明了各个模型在 并行程序设计中的作用。在理论分析的基础上，本文提出了面向并行程序设计的 可视化建模系统的设计方案，就系统功能、组织结构、构造块、构造规则、模型、 视图和分层视图的设计进行了详细阐述。面向并行程序设计的可视化建模系统的 设计方案充分考虑了系统的完整性、灵活性和可扩展性，力争为用户提供一个方 便实用的可视化并行程序设计平台。 本文以设计方案为基础借助e c l i p s e 插件技术和g r a p h i c a le d i t o rf r a m e w o r k 技术实现了面向并行程序设计的可视化建模系统p a r a m o d e l 。该系统具有良好的 可扩展性、友好的用户界面，能从真正意义上简化并行程序设计的开发过程，提 高并行程序的开发效率。 关键词：并行计算并行程序设计可视化建模系统模型 a bs t r a c t w i t ht h ei n c r e a s i n gr e q u i r e m e n tf o rt h ec o m p u t i n gc a p a b i l i t ya n ds p e e d ，p a r a l l e l c o m p u t i n gh a sb e c o m eo n eo ft h em o s ti m p o r t a n tr e s e a r c ha r e a so fc o m p u t e rs c i e n c e - h o w e v e r , t h ep r o c e s s o fd e v e l o p i n g p a r a l l e lp r o g r a m i sv e r yc o m p l e xa n d e n e r g y c o n s u m i n g h o wt od e c r e a s et h ec o m p l e x i t yo fp a r a l l e lp r o g r a m m i n ga n d a c c o r d i n g l yi n c r e a s et h ep a r a l l e lp r o g r a md e v e l o p i n ge f f i c i e n c yh a sb e c o m eo n eo f t h ek e yp r o b l e m si np a r a l l e lc o m p u t i n ga r e a f o rg i v i n gas o l u t i o nf o rt h ep r o b l e m s a b o v e t h i st h e s i sp r o p o s e st h ec o n c e p t i o na b o u tm o d e l b a s e d v i s u a lp a r a l l e l p r o g r a m m i n g ，a n dd e s c r i b e st h ed e s i g na n di m p l e m e n t a t i o no f ap a r a l l e lp r o g r a m m i n g o r i e n t e dv i s u a lm o d e l i n gs y s t e mt h a ti sb a s e do nt h ec o n c e p t i o n t h i st h e s i sa n a l y z e st h ec u r r e n tr e s e a r c ha b o u ts i m p l i f y i n gt h ep r o c e s so fp a r a l l e l p r o g r a m m i n g ，a n ds t u d i e st h ec u r r e n tm e t h o d o l o g ya n dt e c h n o l o g yo f v i s u a lp a r a l l e l p r o g r a m m i n g i t a l s oi n t r o d u c e ss o m e p o p u l a r v i s u a l p a r a l l e lp r o g r a m m i n g e n v i r o n m e n t ，a n da n a l y z e st h e i ra d v a n t a g e sa n dd i s a d v a n t a g e s b a s e do nt h ec u r r e n t t h e o r yo fv i s u a lp a r a l l e lp r o g r a m m i n g ，ac o n c e p t i o na b o u tm o d e l - b a s e dv i s u a lp a r a l l e l p r o g r a m m i n gi sp r o p o s e d t h et h e s i sd e s c r i b e s i nd e t a i lt h ep r o g r a m m i n gm o d e l ，t h e p r o c e s sm o d e la n dt h ec o m m u n i c a t i o nm o d e lw h i c ha r eu s e d i nt h ep r o c e s so f m o d e l b a s e dv i s u a lp a r a l l e lp r o g r a m m i n g ，a n da l s oe x p l a i n sw h a tr o l ee a c hm o d e l p l a y si nt h ep a r a l l e lp r o g r a md e v e l o p m e n t o nt h eb a s i so ft h et h e o r e t i c a lr e s e a r c h ， t h et h e s i sp r e s e n t st h ed e s i g np l a no ft h ep a r a l l e lp r o g r a m m i n go r i e n t e dv i s u a l m o d e l i n gs y s t e m t h e d e t a i l so fs y s t e mf u n c t i o n a l i t y , s y s t e mo r g a n i z a t i o n ， c o n s t r u c t i n gb l o c k sd e s i g n ，c o n s t r u c t i n gr u l e sd e s i g n ，m o d e ld e s i g n ，v i e wd e s i g na n d l a y e r e dv i e wd e s i g na l ea l s od e s c r i b e d g o o de x t e n s i b i l i t ya n df l e x i b i l i t yo ft h e s y s t e mi sa l s oc o n s i d e r e di nt h ed e s i g np l a n b a s e do nt h ed e s i g n ，t h et h e s i si m p l e m e n t st h ep a r a l l e lp r o g r a m m i n go r i e n t e d v i s u a lm o d e l i n gs y s t e mc a l l e dp a r a m o d e l t h ei m p l e m e n t a t i o nu t i l i z e st h ee c l i p s e p l u g i nt e c h n o l o g ya sw e l la sg r a p h i c a le d i t o rf r a m e w o r k t h ep a r a m o d e is y s t e m h a sg o o de x t e n s i b i l i t ya n df r i e n d l yu s e ri n t e r f a c e i tc o u l ds i m p l i f yt h ep r o c e s so f p a r a l l e lp r o g r a m m i n g a n di m p r o v et h ee f f i c i e n c yo f p a r a l l e lp r o g r a md e v e l o p m e n t k e yw o r d s ：p a r a l l e lc o m p u t i n g ，p a r a l l e lp r o g r a m m i n g ，v i s u a l i z a t i o n ，v i s u a l m o d e l i n gs y s t e m ，m o d e l 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特另j j j j l l 以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得：叁鲞盘堂或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：徐云、捉 签字日期： 矽刁年莎月尸日 学位论文版权使用授权书 本学位论文作者完全了解一苤鲞盘堂有关保留、使用学位论文的规定。 特授权：叁盗态堂可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名： 粥赴 签字日期：矽刁年6 月 | 1 e 3 翩躲俐q 婵醐：1 月f 日 第一章前言 1 1 研究背景 第一章前言 各个领域对高计算能力及高性能的需求越来越迫切。随着各行业中数据计算 量的增大及计算复杂度的增加，大量实际问题的求解过程在计算能力及计算速度 方面不断提出新的要求。由于单个c p u 的计算速度的限制，在单c p u 上求解复 杂问题的效率以及精度远不能满足实际问题的需要，将应用程序并行处理成为求 解复杂问题的有效途径。其基本思想是根据一定的规则将一个大的计算任务分解 成若干子任务，将不同子任务映射到不同的处理器上并行地执行，以缩短任务的 处理时间。编写这种形式的程序被称为是并行编程【l 】。并行编程技术与传统的 串行编程技术相比，在降低单个问题的求解时间、增加问题求解规模、提高求解 精度、保证应用程序的容错性与可用性方面均有显著优势，因而成为当今计算机 科学技术中越来越受关注的研究课题之一。 目前在硬件层面上，构建并行计算硬件环境的技术已日臻成熟，搭建一个理 论上计算能力相当强的并行计算环境已不再是难题。但是在软件层面上，并行应 用程序的设计和开发过程却很复杂【2 】。与串行程序不同，并行程序需要对求解 问题进行分解，寻找适合的分解方式，以确保各个子问题之间的依赖程度尽可能 降到最低。并行程序所特有的任务动态调度与映射机制会影响程序的行为，只有 通过选择合适的并行策略和处理器映射方式才能保证程序的高效性。并行程序的 结构与特定的系统结构相关联，程序结构与系统结构的紧密联系直接决定了并行 程序在各个系统间的移植性很差，同时并行程序还面临诸如安全性、公平性、可 扩展性等其它问题。因此并行程序设计是一个非常复杂且耗费精力的过程。传统 的并行程序开发过程中，由于缺乏有效的并行程序设计方法与工具，开发人员需 要选择特定的体系结构以及特定的并行语言，在编程过程中频繁地考虑底层细 节，例如问题的分解与分布，进程的创建与管理，进程到处理器间的映射，通信 和同步，负载平衡等。这使得开发人员无法把精力集中在程序自身的逻辑及性能 上，严重影响了开发效率。如何使底层细节与程序逻辑分开，高效地在并行计算 环境中进行各种并行计算应用程序的设计与开发，从一般意义上并简化并行程序 的开发过程是目前并行程序设计领域所面临的关键的问题。 一个具有良好扩展性且方便易用的可视化并行程序开发环境能够简化并行 第一章前言 应用程序的开发过程，降低开发难度，缩短开发周期，降低开发成本，对推动并 行计算在各个行业的应用与发展、提高各专业领域的计算机应用水平具有重要研 究意义及应用价值。 1 2 国内外研究现状 为解决并行程序设计困难的问题，国内外学者在并行程序设计模型【3 】【4 】及 语言 5 1 1 6 方面进行了许多探索与研究。其中两种最重要的并行编程模型是数据 并行编程模型和消息传递编程模型【7 】。采用数据并行编程模型进行并行程序设 计相对简单，但该模型只适用于解决数据并行类问题。而且该模型对编译器要求 比较高，只有具备了高效的编译器，数据并行程序才可以在共享内存和分布式内 存的并行计算机上取得高效率。消息传递模型主要基于p v m 8 或m p i 9 消息传 递接口，该模型为程序员提供了尽可能大的灵活性，有着更加广泛的应用范围。 它的缺点是编程相对复杂，它将各个并行任务之间复杂的信息交换及协调控制的 工作交给了程序员，从而在一定程度上加重了程序员的负担。 随着并行计算领域的发展，出现了一种新的网格并行编程模型【1 0 】。它适用 于在网格环境中进行并行程序设计与处理。但是现有网格技术不够成熟，在程序 开发模式上并没有质的改进，基于网格的并行计算在众多方面都受到限制。 以上编程模型提供了并行程序开发的几种方式，在一定程度上方便了程序设 计人员的开发。但是这些编程模型均集中在底层功能的调用，编程层次较低，不 支持应用层次上的设计与开发，没有从根本上解决并行程序开发过程的复杂性。 这些编程模型都有相应的并行编程语言或者函数库进行支持，其中一部分语言是 在标准c 语言或者f o r t r a n 语言的基础上加入关键字进行了语义扩充；一部 分语言是针对某种模型重新定义语法和语义，成为一门新的语言；还有一部分语 言，也是目前应用最广泛的一类，提供了兼容标准c 语言或者f o r t r a n 语言 的函数库，例如m p i 和p v m 。 国内外在并行程序设计方法领域也做了各个方面的研究与探索，其中主要包 括：并行设计模式、并行结构骨架、算法骨架、可视化并行程序设计的理论。这 些理论提出的骨架和模型相对于m p i 、p v m 等低层次的并行编程模型具有更高 的抽象程度，对于简化并行应用程序开发更加具有指导意义。 设计模式( d e s i g np a t t e r n ) 1l 】【1 2 】应用到并行程序设计过程中是并行程序设计 方法的一个突破，帮助程序开发人员复用成功的设计和体系结构。d p n d p ( d e s i g n p a t t e r n sa n dd i s t r i b u t e dp r o c e s s e s ) 【1 3 】是一个基于设计模式思想的并行程序设计 系统，对并行程序及并行算法设计的复用做了一定程度的研究。但是仅仅基于设 第一章前言 计模式的并行系统在适应性和可扩展性方面并不理想。 并行结构骨架( p a r a l l e la r c h i t e c t u r a ls k e l e t o n ) 【1 4 1 5 1 是2 0 世纪9 0 年代提 出的一种基于设计模式思想进行并行程序设计的方法，以定义模式的属性集的方 法描述相应模式的特征和行为，将多种设计模式进行再次的封装，并提供程序框 架。它描述了并行设计模式的通用的模型。该模型为描述和实现一个设计模式提 供了一个标准的方法。同时，对模型中的每一个模式能进行了充分的参数化，以 适应不同并行应用的结构和行为，它的通用性在很大程度上简化了并行程序的设 计，解决了基于设计模式的程序设计开发方法的局限性问题。但是目前并行结构 骨架理论尚处于理论研究阶段，要在实际并行程序开发过程中应用此理论还需要 大量的研究与探索工作。 算法骨架( a l g o r i t h m i cs k e l e t o n s ) 【16 1 17 1 思想和方法算法是由英国c o l e 博 士所提出的。算法骨架对并行应用算法中解决关键问题的方法进行一般化，用于 解决一类问题，并行实现的特定算法设计方法的描述，是一种设计高效并行算法 的理论方法。但是骨架致力于描述并行算法的模式的抽象模型，同样存在扩展性 差、缺乏适应性和通用性等问题。 为了进一步简化并行程序开发，一些学者将可视化( v i s u a l i z a t i o n ) 的概念引 入到并行程序的设计和实现过程中。可视化是通过丰富的图形手段对系统进行描 述和构造，能够有效管理系统复杂性，提高系统设计的可重用性，增强系统架构 的灵活性以及增强开发团队的沟通。目前，针对串行应用程序的可视化建模方法 和技术已经非常成熟，也制定了相应的行业标准。但是在并行程序开发领域，尚 且缺乏广泛认可的标准和技术。由于并行程序与串行程序开发的侧重点不同，简 单的移植无法对并行应用程序的设计与构造发挥应有的简化与规范作用。所以， 研究针对并行应用程序的可视化建模方法和技术具有重要的现实意义。 目前已有一些不同的图形化并行程序设计语言，以及相应的可视化并行应用 程序辅助开发环境。但是已有的辅助开发环境大部分是依赖于特定的硬件环境 的，这种依赖性决定了这样的辅助开发环境无法简单地移植到广泛的多处理器硬 件环境中，或者即使移植之后在新的环境中也无法发挥在原有环境下的优势。所 以目前尚且没有影响力比较大的、应用广泛的图形化并行程序设计语言和可视化 并行程序开发环境。 现有并行程序可视化理论给并行程序设计方法的研究指出了一些新的研究 思路与方向，对简化并行程序开发过程、结构化并行程序设计框架方面进行了研 究。如何将这些理论组织在一起并且应用于实践，以及如何在已有的理论基础上 进行创新，是一项非常有意义的工作，对于学习、研究和验证现有的并行程序设 计方法有巨大帮助。 第一章前言 1 3 本文主要研究工作和创新 并行程序设计是一个复杂且耗费精力的过程，在编码阶段、测试和调试阶段 都非常繁琐。如果能在并行程序设计初期引入可视化建模的方法，对并行应用程 序的问题域和求解域进行可视化描述，并以图形化的方式描绘适合的并行策略和 并行算法的精髓，为代码编写提供精确的可编程模型，那么，将大大简化并行程 序设计的复杂性。本文对目前国内外简化并行程序的设计方法进行了深入细致的 研究与分析，研究了现有的应用于并行程序设计的可视化方法和技术，在现有理 论的基础上提出了面向并行程序设计的可视化建模系统的设计方案，并基于 e c l i p s e 1 8 】集成开发环境和g e f ( g r a p h i c a le d i t o rf r a m e w o r k ) 技术进行了简单 的实现。具体包括以下工作： 对目前国内外简化并行程序设计的方法进行了了解与研究，就可视化并行 程序设计技术、并行设计模式、算法骨架、并行结构骨架等理论和它们之 间的联系进行了分析。 - 深入研究了可视化并行程序设计方法和技术，分析了几个典型的可视化并 行程序开发环境。 一 提出了基于模型的可视化并行程序设计的概念，定义了可视化并行程序设 计中的基本模型，并对各个模型进行了描述。 在基于模型的可视化并行程序设计的概念基础上，提出了面向并行程序设 计的可视化建模系统的设计方案。 - 对该设计方案中支持可视化并行程序设计功能的模块进行了简单的实现。 本论文在理论和应用上有如下创新性研究成果： 一 提出了基于模型的可视化并行程序设计的概念。 - 定义了描述并行程序的可行的各种模型，将模型进一步细分成更小粒度的 构造块，并且给出了构造块的定义、基本描述和图形化表示。 - 定义了构造规则，构造规则描述了如何将构造块组织成模型的规定和建议， 即一个结构良好的模型看起来应该像什么。 - 在构造块和构造规则的设计基础上，给出了编程模型、进程模型、通信模 型的更加详细的设计结果。 基于分层的思想进行了主视图和各级子视图的设计。 - 基于e c l i p s e 插件技术、g e f 技术和x m l 技术，构建了面向并行程序设计 的可视化建模系统。 第一章前言 1 4 本文内容和结构 本文通过研究可视化并行程序设计的方法和技术，提出了基于模型的可视化 并行程序设计的概念。在此概念的指导下提出了面向并行程序设计的可视化建模 系统的设计方案，并就该方案的具体实现技术进行了详细阐述。主要内容如下： 第二章介绍了可视化并行程序设计的概念，分析了几个典型的可视化并行 程序开发环境。 第三章分析了现有的可视化并行程序设计方法存在的问题，提出了基于模 型的可视化并行程序设计的概念，并提出了在可视化并行程序设计中用以描述并 行程序的基本模型。 第四章描述了面向并行程序设计的可视化建模系统的基本设计要素，从构 造块、构造规则、模型和视图多个方面系统地阐述了该建模系统的总体设计思路 和设计方案。 第五章就面向并行程序设计的可视化建模系统的实现技术进行了讨论和阐 述。 第六章对全文进行了总结和对未来工作的展望。 第二章可视化并行程序设计概述 第二章可视化并行程序设计概述 2 1 传统并行程序设计 并行程序设计是一个非常复杂且耗费时间的过程。目前，在并行计算领域仍 然缺乏有效的并行程序设计方法和工具，从而使得并行程序设计、调试和优化都 很困难。人们已经习惯于以串行的方式理解、设计和调试程序，但是实际上并行 程序设计中需要考虑的问题要比串行程序设计复杂得多。 首先，为了保证执行结果的正确性，并行程序必须包含在进程之间通信和保 持同步等机制，还要处理互斥区、死锁等问题，增加了程序的语义复杂性和语法 复杂性。其次，为了保证并行程序执行的效率，必须在处理器之间均匀的分配任 务，这个问题在串行程序设计中是不需要考虑的。最后，数据在各进程间必须进 行合理划分，以保持数据的局部性，否则频繁移动数据的开销会严重影响程序性 能。 由于并行程序的设计的复杂性，目前尚无一种普遍适用的系统的设计方法。 从现有的理论探讨及实践经验来看，并行程序的设计有两个基本途径 1 9 】，一是 将已有串行程序并行化，二是使用并行算法和并行策略进行并行程序设计。串行 程序的并行化过程，可以通过并行编译系统来实现，由编译器对串行程序的源代 码进行相关性分析，然后使用一系列程序变换技术将顺序代码转换成并行代码。 但是通常串行程序的并行化的效果很差，因为串行算法中编译器能够识别并可以 开发的并行性是很有限的。 使用并行算法进行并行程序设计，就是在特定的并行多处理机环境下，选择 适合的并行策略和支持的并行程序设计语言进行编程实现。在实践中，设计一个 使用并行算法的并行程序包括下面某些步骤或所有步骤【2 0 】： 识别能并发执行的任务。使用域分解或者功能分解将整个计算任务分解成一 些子任务。 映射各并发予任务到并行运行的多处理器上。 分布与程序有关的输入、输出和中间数据。 管理对由多处理共享的数据的访问。确定不同任务执行中所需要交换的数据 和协调各项任务的执行。 在并行程序执行的各个阶段对处理器进行同步。 第二章可视化并行程序设计概述 并行程序设计过程中需要考虑的因素比上面列出的步骤复杂的多。开发人员 不仅需要对并行计算硬件系统结构有清晰的认识，还要对选择的并行程序设计语 言所支持的实现细节非常熟悉，才能够设计出可行的并行应用程序。例如，在基 于消息传递的并行函数库中，p v m 是支持动态生成进程的 2 1 1 ，而m p i 1 则不 支持。在各类并行程序设计语言中动态任务生成的任务的通信交互方式等与并行 环境相关，同时也与所选择的并行编程模型相关。这种与并行底层环境的交互操 作在增加并行程序设计复杂性的同时，大大减少了开发设计并行程序的潜在用户 群。 事实上，相当一部分编写并行程序的用户并不是并行计算领域的专业人员， 他们仅仅想利用并行计算去解决自己相关领域的问题。这种并行程序设计方法对 于这部分用户而言无疑是个困难复杂的过程。同时由于程序设计人员风格与水平 的差异，并行程序的质量与执行效率难以得到保证。并行程序的设计不仅要考虑 具体待解问题的特性，还要兼顾并行计算环境的特性和并行程序设计语言的限 制，这种局限性将会大大制约着并行应用程序设计思想的普及。 2 2 可视化并行程序设计方法 可视化程序设计( v i s u a lp r o g r a m m i n g ) ，也叫做图形化程序设计( g r a p h i c a l p r o g r a m m i n g ) ，即通过丰富的图形手段对软件系统进行描述和构造。可视化程序 设计的优点体现在下面几个方面： 首先，可视化程序设计具有更好的灵活性和系统独立性。没有使用可视化技 术的传统程序设计过程依赖于特定的程序设计语言，和操作系统也紧密相关。设 计者在进行问题分析和模块划分之后，直接在源代码级别上进行程序设计和开 发。程序源代码只能在相同配置的机器上方便地移植，否则就要进行修改，所以 应用程序的系统独立性很差。可视化程序设计方法能够将程序设计过程中的系统 相关因素和系统无关因素分离开，帮助程序员将注意力集中在与底层系统无关的 程序功能和逻辑部分，减轻程序员的负担，提高开发效率。 通过可视化程序设计方法得到的直接产物，通常不是可运行的源代码，而是 一些定义良好的图。这些图进一步生成采用某种编程语言的程序源代码。这些图 包含良好的语义定义，能够完整的描述构造源代码程序所必需的主要数据结构和 算法，清楚地反映出程序中的数据流和控制流信息。所以，这些图中包含了生成 程序源代码所需要的全部有用信息。 其次，与传统程序设计相比，可视化程序设计更加简单、更容易掌握。可视 化程序设计中大量使用简单易懂的图形化元素。相反地，传统的程序设计首先需 第_ 章可视化并行程序设计概述 要设计者掌握一门语言，其次在设计过程中还经常使设计者陷在语法的束缚之 中，最终导致了大量时间和精力的浪费。由此可见，在硬件技术高速发展的今天， 对图形化的程序设计的支持越来越重要了。 可视化并行程序设计( v i s u a lp a r a l l e lp r o g r a m m i n g ) 【2 2 1 ，将可视化程序设 计的思想引入到并行程序的设计过程之中，体现了图形化表达和并行语义的结 合。 可视化并行程序设计必须考虑并行程序设计中特有的复杂性。在传统的串行 程序开发中，设计者习惯于将开发过程分为一系列定义清楚的子阶段：问题分析 与定义、系统分析、系统设计、系统实现等。在并行程序开发中，开发生命周期 的不同阶段之间有着不可避免的交互。不同进程之间由于数据依赖关系等也存在 着不同程度的交互。在存在数据共享的情况下，各个进程对数据的操作必须有序 地进行以保证数据的正确性。此外，在各个进程之间还需要进行负载平衡以获得 良好的计算效率。这些因素在串行程序中都是不需要考虑的，但是在并行程序设 计中却是非常关键的，需要额外增加足够的图形化元素予以表述，并定义适当的 语义约束。 2 3 几个可视化并行程序开发环境的介绍和分析 2 3 1f r a m e w o r k s 系统 f r a m e w o r k s 系统【2 3 】使用术语模块( m o d u l e s ) 来表示并行运行的进程，进 程之间通过远程过程调用( 1 冲c ) 进行通信。远程过程调用在模块的代码中用显 式语句描述，并使用消息传递的方法实现。每个模块最多有一个入口( e n t r y ) 过程可以被其他模块调用。如果一个模块的入口过程被调用，其他需要调用此过 程的模块会被挂起，直到调用结束。 系统还提供了图形化模板可以定义同一个模块所用实例的数目，以及数据在 这些实例中的分配方法。完整定义一个模块至少需要三个不同的模板：输入模板、 输出模板和主体模板。输入模板有三种类型：初始化( i n i t i a l ) 模板不需要真正 的输入数据，流水线输入( i n p i p e l i n e ) 模板用先来先服务的方法处理输入请求， 收集输入( a s s i m i l a t o r ) 模板要求每一个输入进程提供一个输入数据。输出模板 也有三种类型：完成( t e r m i n a l ) 模板不需要输出，流水线输出( o u t p i p e l i n e ) 模板使用流水线方式输出结果，管理者( m a n a g e r ) 模板把输出分配给一个模块 的多个实例。主体模板有两种类型：执行( e x e c u t i v e ) 模板和承包者( c o n t r a c t o r ) 模板，其中后者会创建某模块的多个实例。 第二章可视化， ：行程序设计概述 f r a m e w o r k s 系统使用可视化环境和模板机制大大简化了并行程序设计，但 是它的模板是不支持嵌套的，可供选择的模板结构是完全平面化的。这个缺陷大 大制约了该系统的适用范围。 2 3 2c o d e2 0 语言和可视化编程环境 使用c o d e 2 0 语言【2 4 】【2 5 】设计的并行程序由一组图例( g r a p hi n s t a n c e ) 组 成，彼此之间使用调用节点( c a l ln o d e s ) 交互。有向边表示进入离丌某个节点 的数据流通道。图例扮演了在传统程序设计中子程序的角色。图中除了调用节点 外，还有其他类型的节点。接口节点( i n t e r f a c en o d e s ) 定义了该图可以和其他 相匹配的图连接。计算单元节点( u n i to fc o m p u t a t i o nn o d e s ) 定义了基本的串 行计算。计算单元节点内计算表达方式就像传统串行程序中的子程序调用，输入 规则指明了计算在什么条件下允许执行。计算单元节点有输入输出端口用于通 信数据进出节点，输入输出边和端口绑定，因此多条边可以进出同一个节点。 用户画出的图仅仅是创建了一个模板而不是一个实例，实例只有在运行中调 用节点被引用时才生成。所以c o d e 2 0 语言可以处理需要用动态程序结构( 即 程序结构随着输入的不同而改变) 来描述的应用。这些动态结构可以使用一定的 输入输出规则来详细说明。在输入输出规则中，端口用抽象的索引来访问，索 引的范围由符号表达式来定义。 这种对动态程序结构的支持是c o d e 2 0 语言的一个很大的优点。不过它采 用的基于文本的描述手法并不完全符合用图形化方法定义程序结构这种思想。 2 3 3m e a n d e r 语言和可视化开发环境 m e a n d e r 语言【2 6 】【2 7 】是以一组固定的图形节点为基本元素、以标准c 语言 串行代码片段作为补充的混合型语言。使用m e a n d e r 语言创建的并行应用中用细 节图来表示并行控制流。控制流的表达主要是靠不同类型节点和不同类型边的满 足一定规则的组合来实现的。其中：s e q 节点代表串行计算代码；c c w c 节点 成对出现，用来表示进程的生成和结束，所有创建新进程的动作必须由c c 节点 发起，最终结束于w c 节点；s e n d r e c e i v e 节点代表显式的消息传递操作；d o 、 a l t 节点被用来定义条件和循环结构，每一个d o a l t 节点后紧跟着一个g u a r d 节 点，作为控制随后的串行代码执行的第一个节点。 m e a n d e r 环境支持分层设计，可以将细节图中某个结构化的子图封装到高层 细节图中的一个节点中。这里的结构化要求是指子图必须有且只有一条输入边和 输出边。这种类型的子图可以封装起来并单独存储，一方面可以限制细节图的规 模，另一方面还可以支持代码复用。 第二章可视化并行程序设计概述 此外m e a n d e r 环境还可以绘制进程图以描述进程拓扑结构。定义模板支持进 程复制的方法被用f 其中。 在m e a n d e r 环境中，定义进程创建和通信操作是在同一层次的，这种方法在 基于进程的并行程序开发环境中并不常见。这种方法虽然在一定程序上简化了程 序的描述，但是随着程序规模的增大，很容易产生大而混乱的图，其他用户将难 以理解和维护。 2 4 现有的可视化并行程序设计方法研究 从编程模型的角度看，现有的可视化并行程序设计方法可以分为三类【2 8 】： 基于模板的、基于数据流的、基于进程的。 2 4 1 基于模板的可视化并行程序设计 基于模板的可视化并行程序设计通过提供一些预定义的进程交互结构( 称之 为模板) 构建并行应用程序。 模板负责生成并行系统的基本交互进程和通信结构的框架代码，设计者自己 提供应用程序的细节处理过程，然后两部分被整合在一起构成完整的并行应用程 序。通常情况下，设计者根据不同的通信模型( 如流水线) 可以选择不同的模板。 这种方式的优点是通过模板将应用程序的并行部分从应用程序各自不同的 细节代码里分离开来，实现了代码复用。用户不必考虑通信与同步这一类的问题， 仅需要关注程序细节。 这种方式的主要缺点是适用性很差。在实际应用中，设计者经常面临处理各 进程之间的不规则通信的情形，导致无法在规则的通信架构中有效表达：或者即 使处理规则的通信架构，但是该架构在模板库中没有定义，致使设计者不得不自 行编写单独的进程交互：如果预定义模板的可扩展性不好，设计者不得不被迫使 用并不合适的并行结构。 在现有的可视化并行程序开发环境中，f r a m e w o r k s 系统、e n t e r p r i s e 并行编 程系统【2 9 】【3 0 】等都是典型的基于模板的可视化并行程序开发环境。f r a m e w o r k s 系统在上一节中已经介绍过了。e n t e r p r i s e 并行编程系统是f r a m e w o r k s 系统的后 续者。在它的术语中模板叫做资产( a s s e t s ) ，系统使用四个基本操作把一个串行 程序变成一个并行程序：资产扩张、资产转化、资产增值和资产复制。另外，该 系统还支持了递归。 第二章可视化并行程序设计概述 2 4 2 基于数据流的可视化并行程序设计 基予数据流的可视化并行程序设计主要使用数据流图来进行并行程序设计， 图中节点表示串行计算，边表示数据流，而箭头指明数据流方向。程序设计的结 果显示为一个有向图，反映出并行程序的串行代码片段之间的数据流的关系。 这种方式没有为通信和同步操作定义新的图形化元素，所以特别适合于以划 分数据为导向的并行应用程序。只要数据的划分比较合理，使得各计算节点间数 据独立，数据流图的方法就可以清楚地表示出程序的并行特性。设计者可以像编 写串行程序一样，不需要处理很多抽象的问题。 数据流图方法的局限性是对于通信和分支的支持很差。因为通信不能嵌套在 计算里面，所以只要遇到通信或者分支，计算过程就不得不分裂成不同的节点， 导致出现复杂庞大的数据流图。 c o d e 系列编程环境、h e n c e 编程环境【3 l 】是基于粗粒度数据流方法的可视 化并行编程环境。 2 4 3 基于进程的可视化并行程序设计 基于进程的可视化并行程序设计的主要思想，是让设计者自己定义进程结构 和显式的消息传递操作。并行程序的进程结构用一张进程图来表示，其中节点和 边分别表示进程本身和可能发生的通信。 同基于模板的方法相比，基于进程的方法适用性更强，因为不论规则、不规 则的并行结构它都可以表达。在该方法下设计者通过进程图建立完整的应用程 序，侧重于描述程序的并行控制流。 但是，基于进程的方法比其他两种方法需要设计者更多的亲自参与。 t r a p p e r 编程环境【3 2 】是最有名的基于进程的图形化编程环境之一，它是 一个商业化软件，并且对m p i 与p v m 两种消息传递机制提供支持。上一节中介 绍的m e a n d e r 环境也是属于这种类型的编程环境。 第三章基于模型的可视化并行程序设计研究 第三章基于模型的可视化并行程序设计研究 3 1 基于模型的可视化并行程序设计概述 模型是对现实世界中存在的事物或现象的简化描述 3 3 1 。这里所说的模型是 指软件模型，是对需要开发的应用程序的高层次抽象。一个良好的模型包括在给 定抽象层次上重点表达和刻画的元素以及元素之间的关系，忽略了与给定的抽象 水平不相关或者作用不大的次要元素。 每一个系统都可以从不同的方面用不同的模型来描述 3 3 1 ，因而每个模型都 是一个在语义上闭合的系统抽象。按照表达的侧重点不同，模型可以划分为结构 性的模型和行为性的模型，结构性的模型强调系统的结构和组织，行为性的模型 强调系统的动态语义。 在并行应用程序设计领域，每一个并行应用程序可以被看作是一个若干子计 算任务并发执行和协调同步的完整的系统。任务的划分需要用户在理解系统需求 的基础上自行分析和决策，而任务间的协调依赖于具体并行程序设计语言或者并 行编程库中对同步机制的支持。在实际的并行程序设计开发过程中，程序开发人 员极易将程序设计与具体实现混合起来，在程序设计阶段过多地去考虑底层并行 通信、数据共享、同步等实现细节，忽略了对需要解决问题本身的并行性分析。 由于不同并行计算体系结构的差异，并行程序设计语言机制的多样化与复杂性， 过度关注实现细节会极大影响到程序开发的效率和并行程序的可移植性。 因此，本文提出一种新的对并行应用程序进行设计的思路一基于模型的可 视化并行程序设计，将程序设计与具体实现分离开，通过可视化方法构建合理描 述该并行应用的各个方面的模型，确定设计方案，然后在建立的模型的基础上生 成具体应用程序代码。在这种方法中，并行程序开发的关键是如何基于并行程序 设计模型对实际问题进行并行求解，而不在于并行程序设计语言本身。对程序开 发人员而言，精力以及时间消耗主要集中于程序设计模型的选择、问题空间的求 解以及并行算法设计上，而不是具体代码实现的细节上。 基于模型的可视化并行程序设计，是在更高级的抽象层次上对并行应用程序 进行设计。设计者将并行应用程序看作一个完整的可运行的系统，从各个层次、 各个角度对系统进行可视化建模。尽管并行程序与并行计算环境体系结构的紧耦 合性造成了程序设计方法的多样性和复杂性，而且目前存在各式各样的并行算法 第三章基于模型的可视化并行程序设计研究 设计技术，但是大多数设计者在并行程序设计过程中总是遵循着定的规律和步 骤。例如，在开始进行并行程序设计的时候首先选择某一种编程模型共享存 储的或者消息传递的；为了获得较高的并行效率，根据待求解问题的性质，选择 合适的并行策略分治、流水线或者划分；必须特别关注各进程间的通信方式 和同步机制，避免死锁和通信出错等情况发生。通过对大部分并行应用程序进行 分析，可以进一步探索出类似的规律，为抽象出适合大部分并行应用程序设计过 程的各类模型提供了良好的实践依据。 基于模型的可视化并行程序设计，是以模型为核心的、采用可视化构建方法 的面向并行应用程序设计的新方法和新途径。在这种方法中，最重要的环节就是 合理定义描述并行应用程序的模型。模型的定义是围绕着并行应用程序中需要考 虑和设计的因素而展开的，即根据并行应用程序设计的潜在规则，将任务划分、 数据共享、消息通信、同步、处理器映射等设计因素从进程级别、通信级别、编 程级别重新划分和组合，形成具有良好独立性的、可扩展的模型。可视化的手段 在一定程度上降低了模型的表达复杂性，以直观、易懂的方式帮助设计者完成模 型的描述和组织，从而简化了并行应用程序的设计。 基于模型的可视化并行程序设计是一种结构化并行程序设计方法。该设计方 法将并行程序设计从并行语言实现提升到并行结构级别，减少了开发过程中受过 多并行实现细节的影响，更多地去关注同类并行问题本身固有的并行性。 基于模型的可视化并行程序设计体现了并行计算领域的软件工程的思想，以 实现良好的设计流程和设计方案的复用。每一个模型的提取本质上就是对并行应 用程序在一定程度上的抽象和简化，所以通过建模手段完成的模型系统是并行应 用程序的主要结构和特定细节的表示。因此，对系统建模是比代码级别的设计更 加简化的过程。由于编译器和并行运行环境的限制，并行应用程序设计的最终产 物仍然必须是某种并行编程语言下的源代码。基于模型的可视化并行程序设计方 法建议设计者通过基本建模过程完成对并行应用程序的设计，而从模型级别到源 代码级别的映射是一个自动化的过程。从模型生成具体并行应用代码的过程如图 3 1 所示。 第三章基于模犁的可视化并行程序设计研究 ，一一、 ，7 ，、( ：二j ，。、l 并t 符i j 程序设计i 模型 一 ，。l 71 i ，j p 。l 犬。土 i 具体并行应用代码 具体并行应用代码 并行模型骨架 并行代码框架 图3 1具体并行应用代码的生成过程 与代码级的程序设计相比，模型级的设计具有以下优点： 第一，模型比程