（计算机软件与理论专业论文）基于模板的可视化并行程序设计平台的研究与实现.pdf

基于模板的可视化并行程序设计平台的研究与实现 摘要 随着高性能计算技术的发展及大规模科学与工程问题对高性能计算的需求 日益增强，并行计算成为研究的热点。但并行编程不像串行程序设计那样简单， 它涉及到并行通信与同步等复杂问题，尤其是对于非计算机专业用户来说，开 发并行程序解决他们领域内的问题更为困难。因而开发出可视化、简单易用、 界面友好的并行程序设计平台必将促进并行计算的普及和推广。 本文从方便用户进行并行程序设计的角度出发，以逐步求精、层次式的设 计思想，开发了一个基于模板的可视化并行程序设计平台。平台主要由三层构 成：在应用层，用户通过图形的方式确定进程间的通信关系；在进程层，平台 提供图标方便用户完成相应的程序设计；在代码层，平台通过代码产生器自动 生成并行程序。本文主要研究工作包括以下几个方面： 第一，通过研究常用的并行程序编程范式，建立并行范式模板，使用户可 以直接切入并行程序的逻辑结构，通过范式模板在平台的应用层快速高效的定 制、建立满足实际并行问题的进程逻辑图形结构。 第二，通过研究并行消息传递函数库m p i 的底层机制和参数特点，在代码 层抽象出并行代码模板。通过图形图标隐藏了消息传递函数的复杂性，对用户 来说并行底层机制是透明的，从而方便了非专业用户设计并行程序。 第三，以可视化、模板化的思想，图形图标的抽象方式，设计开发出基于 模板的可视化并行程序设计平台。 关键词：并行计算，消息传递接口，可视化，并行范式模板，并行代码模板， 并行编程环境 本论文主要工作得到了国家自然科学基金“协同模板中的约束信息可视化” ( 6 0 5 7 3 1 7 4 ) 、安徽省教育厅自然科学研究项目“安全远程并行可视化计算环境建设” ( 2 0 0 4 k j 0 9 7 ) 、安徽省高等学校青年教师科研资助计划项目“并行算法模板技术及应用环 境研究”( 2 0 0 5 j q l 0 1 4 ) 及合肥工业大学研究生教育创新实践基地“台肥工业大学高性能 与协同计算开放实验室建设”的共同资助。 s t u d ya n di m p l e m e n t a t i o no f v i s u a lp a r a l l e lp r o g r a m m i n gp l a t f o r m b a s e do nt e m p l a t e a b s t r a e t w i t ht h ed e v e l o p m e n to fh i g hp e r f o r m a n c ec o m p u t i n g ( h p c ) t e c h n o l o g ya n d t h e e v e r l a s t i n gd e m a n d i n gf o rh p co fl a r g es c a l ep r o b l e mi n s c i e n c ea n d e n g i n e e r i n g ，p a r a l l e lc o m p u t i n gi sb e c o m i n go n eo ft h er e s e a r c hh o t s p o t s h o w e v e f ， p a r a l l e lp r o g r a m m i n gi sd i f f i c u l te s p e c i a l l yf o rn o n - p r o f e s s i o n a lp r o g r a m m e r s ，n o t a ss i m p l ea sc o m m o np r o g r a m m i n g ，b e c a u s ei td e a l sw i t hs o m ec o m p l e xp r o b l e m s s u c ha sp a r a l l e lc o m m u n i c a t i o n ，s y n c h r o n i z a t i o na n ds oo n t h e r e f o r e ，o n c ea u s e r - f r i e n d l y , s i m p l ee a s yv i s u a lp a r a l l e lp r o g r a m m i n gp l a t f o r mi sd e v e l o p e d ，i t w o u l dp r o m o t et h ep a r a l l e lc o m p u t i n gp o p u l a r i z a t i o na n dp r e v a l e n c e t h ed i s s e r t a t i o nf o c u s e so ns i m p l i f y i n gp a r a l l e lp r o g r a m m i n g ，a n dap a r a l l e l p r o g r a m m i n gp l a t f o r m ，c a l l e dv p p e ( v i s u a lp a r a l l e lp r o g r a m m i n ge n v i r o n m e n t ) t h a te m p l o y st e m p l a t e s ，i sd e s i g n e da n dd e v e l o p e db a s e do nt h ei d e ao fp h a s et o d e t a i ls t e pb ys t e pa n dh i e r a r c h yd e s i g n t h ep l a t f o r mi sc o m p o s e do ft h r e el a y e r s ： u s e r sc a ne x p r e s sap a r a l l e lp r o g r a mw i t hg r a p ht od e s c r i b et h er e l a t i o n s h i po f p r o c e s s sc o m m u n i c a t i o nl o g i c a l l yo nt h ea p p l i c a t i o nl a y e r ；c a nd e s c r i b et h e p r o c e s s e sw i t hi c o ni nd e t a i l st oa c c o m p l i s hp r o g r a m m i n go nt h ep r o c e s sl a y e r ；a n d c a no b t a i np a r a l l e lp r o g r a mb yc o d eg e n e r a t o ro nt h ec o d el a y e r t h em a i nc o n t e n t si n c l u d e ： ( 1 ) p a r a l l e lp a t t e r nt e m p l a t e sa r ee s t a b l i s h e db yr e s e a r c h i n go nc o m m o np a r a l l e l p r o g r a m m i n gp a t t e r n s ，w h i c hm a k e su s e r st u r ni n t ot h ef r a m e w o r ko fp a r a l l e l p r o g r a m sd i r e c ta n dc a nc o n s t r u c ta n dc u s t o m i z ep r o c e s sl o g i c a lg r a p hs t r u c t u r e e f f i c i e n t l y ( 2 ) p a r a l l e lc o d et e m p l a t ei sa b s t r a c t e da n di m p l e m e n t e db ys t u d yo fp a r a l l e l m e s s a g e - p a s s i n gi n t e r f a c ef u n c t i o n s m e c h a n i s ma n dc h a r a c t e ro fp a r a m e t e r s f o r u s e r s ，t h eb o t t o mp a r a l l e l m e c h a n i s mi s t r a n s p a r e n t a n dt h e c o m p l e xo f m e s s a g e - p a s s i n gf u n c t i o ni sh i d d e nb yg r a p ha n di c o n ( 3 ) av i s u a lp a r a l l e lp r o g r a m m i n gb a s e do nt e m p l a t e sw a sd e v e l o p e db yt h ew a yo f g r a p h sa n di c o n sa b s t r a c t i o n s k e y w o r d s ：p a r a l l e lc o m p u t i n g ，m e s s a g ep a s s i n gi n t e r f a c e ，v i s u a l i z a t i o n ，p a r a l l e l p a t t e r nt e m p l a t e ，p a r a l l e l c o d e t e m p l a t e ，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 插图清单 图2 1 平台系统框架图9 图2 2 平台应用层编程视图。1 0 图2 3 进程端口位置编号1 1 图2 4 进程的4 个方位。1 1 图2 5 进程对立边l l 图2 6 水平对立方位寻找过程1 2 图2 7 一个端1 3 在u p 方位调整过程1 3 图2 8 进程层类间逻辑结构图1 4 图2 9 表示进程控制流的各种图标1 4 图2 1 0 进程层编程视图1 5 图2 1 1 判断鼠标是否在进程流程图的连线上1 6 图2 1 2 在进程流程图中插入新图标的过程1 7 图2 1 3 在进程流程中删除一个对象的过程1 8 图3 1 当前主流范式结构图。2 3 图3 2 范式模板的结构框架图2 4 图3 3 流水线范式创建的流程图一2 6 图3 4 进程农庄范式创建的流程图。2 7 图3 5 主从式范式创建的流程图2 8 图3 6 分而治之范式创建的流程图一3 0 图3 7 二维网孔范式创建的流程图3 2 图4 1 生成并行代码示意图二3 6 图4 2 平产生代码函数的调用关系图。3 9 图5 1 平台应用层用户界面4 3 图5 2 平台进程层用户界面。4 3 图5 3 计算l 的积分曲线图4 5 图5 4 两个从进程的主从式范式结构图。4 5 图5 5 主进程的控制流图4 6 图5 6 从进程的控制流图4 6 图5 7 测试结果的加速比4 8 表格清单 表4 - lm p i 中预定数据类型和f o r t r a n 7 7 数据类型的对应关系4 0 表5 1 测试结果统计表4 8 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成 果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得 盒胆王些太堂 或其他教育机构的学位或 证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了 明确的说明并表示谢意。 靴做储躲2 觋 签字聃：习年月哆日 1 1 | 学位论文版权使用授权书 本学位论文作者完全了解金胆王些态堂有关保留、使用学位论文的规定，有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授 权金壁王丝盔堂可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采 用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者躲瑚己 签字醐：叨和钼”7 日 学位论文作者毕业后去向： 工作单位：创新科技( 中国) 有限公司合肥分公司 通讯地址：合肥市高新区黄山路 导师签名： 签字日期& 乎 l 6 乌1 日 j 电话：1 3 8 6 6 7 0 5 9 5 4 邮编：2 3 0 0 8 8 致谢 时光飞逝，值此论文付梓之际，我要衷心的感谢三年来一直对我提供热心 帮助和关心的老师和同学。 首先我要感谢我的导师刘晓平教授。三年来，刘老师不仅在学术上给予我 耐心细致的指导，同时也对我在生活上和学习上给予了无微不至的关怀，每一 次和刘老师的交谈对我都是一次进步、每一次刘老师对我的鼓励都让我记忆犹 新。刘老师认真负责的态度、勤奋严谨的作风、对问题的实质性把握无不影响 着我，使我受益匪浅，对此我表示衷心感谢l 感谢v c c 研究室( 合肥工业大学计算机与信息学院可视化与协同计算研究 室) 的老师和同学们，他们对本论文的工作和撰写提出了很多宝贵意见，在我 研究生的整个学习期间，大家互相关心，相互帮助。特别是郑利平师兄、安竹 林师兄的无私指导和帮助，以及与我们计算组卫兴武和凌实的密切合作，感谢 在v c c 做本科设计的同学李星，本课题的完成也凝结着他们的劳动成果，感谢 路强师兄、罗月童师兄、金灿、毛峥强、曹力和孔洁琼等在学习和生活中对我 的帮助。 感谢所有关心和帮助过我的老师、同学和朋友们，在我的研究工作中凝聚 着他们的关心和友谊。能够顺利完成本论文，还要感谢我的亲人和女友在生活 和学习上给予我的关怀和鼓励。 最后，向本文所引用的文献作者们表示感谢! 王恩柱 2 0 0 7 年6 月 第一章绪论 “由于计算机技术的高速发展，科学计算和计算机仿真已经成为科学研究中 除理论研究和科学实验以外的第三种方法”【1 1 。随着科学技术的发展、研究对象 的复杂化和实用化，科学计算的规模日趋庞大；人们逐渐认识到单机性能不能 满足大规模科学与工程计算问题的计算要求，高性能计算机是实现高性能计算， 解决挑战性计算问题的唯一途径。高性能并行计算机的研制和应用水平的提高， 一直是各国共同追逐的目标，已经成为衡量一个国家科技、经济和国防综合实 力的重要标志【2 】。 1 1 并行计算 随着网络和分布式系统的出现和发展，多计算机和多c p u 共同协同处理的 计算逐渐成为研究科学与工程技术问题的一种崭新的手段和方式。这种以高性 能计算机为平台的，应用于科学与工程的大规模并行计算，已发展成为一门新 的学科一一大规模科学与工程计算。新一代计算机软件的开发都开始考虑用“分 布”、“并行”的思想来设计和实现。分布和并行意味着资源利用率和计算效 率的提高，因此并行计算已经发展成为当前计算机技术的主要研究方向之一。 1 1 i 并行计算的发展和现状 1 9 9 1 年，美国开始执行“高性能计算与通信”( h i g hp e r f o r m a n c e c o m p u t i n g a n d c o m m u n i c a t i o n ，h p c c 计划) 项目 3 1 ，目的是通过加强研究和开发解决一批 重要的科学与技术挑战问题，保持其在高性能计算和计算机通信领域的世界领 先地位，利用高性能计算机与网络技术刺激生产，以提高国民经济、国家安全、 教育和整体环境的竞争力。 h p c c 项目提出的背景是一大批“巨大挑战( g r e a t c h a l l e n g e ) ”问题需要 解决，包括天气与气候预报；分子、原子与核结构；大气污染；燃料与燃烧； 生命科学中的大分子结构；新型材料特性；国家安全等有关问题。在美国提出 h p c c 计划后，日本相继提出了真实世界计算计划，欧洲提出了万亿次机计划， 我国8 6 3 高科技计划也将并行机列为关键技术【4 】。 并行和分布计算技术自上世纪6 0 年代中期和7 0 年代后期分别出现以来， 其处理方式经历了从阵列机、向量机及向量并行机、共享存储的对称多处理器 系统( s m p ) 、分布存储的大规模并行处理系统( m p p ) 到非一致访问的分布共 享存储( n u m a ，n o n u n i f o r mm e m o r ya c c e s s ) 并行机系统和计算机机群系统 ( c l u s t e r s ) 的演变过程。 当前，并行计算发展的基本状况是：并行软件的发展远远落后于并行计算 体系结构的发展；并行计算的运用远远落后于并行计算技术的发展；并向尽量 采用商品化的软、硬件甚至系统来构成并行计算系统平台的方向发展。 1 1 2 国内外并行计算的研究概况 我国并行和分布计算技术的研究，按照周兴铭院士的观点【5 l ，已经经历了 三个阶段。第一阶段，自上世纪6 0 年代末至7 0 年代末，主要从事大型机中的 并行处理技术的研究；第二阶段，自7 0 年代末至9 0 年代初，主要从事向量机 和并行多处理机系统的研究；第三阶段。自8 0 年代至今，主要从事m p p 系统 工作站机群系统的研究。 1 9 8 3 年1 2 月2 2 日，我国第一台每秒运算亿次以上的计算机_ 银河”在 长沙研制成功。经过2 0 几年的发展，我国高性能计算机已形成了三大系列即银 河系列、曙光系列和神威系列。这些高性能计算机在石油、地质勘探、中长期 数值预报、卫星图像处理、银行、保险、财会、税务、邮电、交通以及政府部 门，大规模事务处理、航空航天、信息安全、生命科学等领域及国防建设中发 挥了重要作用。在2 0 0 4 年6 月份的全球高性能计算机t o p s 0 0 排名中，曙光 4 0 0 0 a 位居第1 0 位【6 1 。现在，中科院计算所已在技术上为下一代的曙光5 0 0 0 的研制做了充分准备。 目前国内并行计算在并行计算机的硬件平台，特别是机群系统在国际具有 较强的竞争力；并行软件在石油、气象、核物理、生物等方面的应用比较成熟。 国内并行计算的发展前景应该是适合各类行业应用领域的并行行业软件的研 发。 美国在并行计算研究领域中，一直处于领先地位。其研究重点已从原来的 m p p 系统转向可伸缩并行机和各种类型的计算机机群。对可伸缩并行机系统， 特别是c c n u m a ( c a e h ec o h e r e n t n u m a ) 方式比较看好，在机群方面主要在于 如何减少节点机间的通信开销和机群的工作环境进行研究。日本的高性能计算 技术也一直位居前列，由日本宇宙开发事业团、日本原子能研究所以及海洋科 学技术中心共同于2 0 0 2 年成功开发出的矢量型超级计算机地球模拟器( e a r t h s i m u l a t o r ) ，连续几年在全球高性能计算机t o p 5 0 0 排名中名列榜首，其运算性 能达到了3 5 6 1 t e r a f l o p s l 6 】( 1t e r a f l o p s = 1 秒钟进行1 万亿次的浮点运算) 。 德国在上世纪9 0 年代致力于m p p 系统的研究，并取得一定的成果，现在德国 的研究机构已意识到推广并行应用的重要意义，已确定今后的研究重点将转向 并行应用和并行编程等方面。 1 1 3 基于集群的高性能计算技术 集群系统是一种并行或分布式系统，它由一些互联的独立计算机组成，并 作为一个单独、统一的计算资源来使用。集群系统具有投资风险小、可扩展性 好、可继承现有软硬件资源、开发周期短及可编程性好等特点。 集群系统通常是由若干计算机通过网络连接而成，有一台计算机作为主节 点( h e a d n o d e ) ，它通常装有双网卡，对外负责提供集群的服务接口，对内负 2 责集群的管理；其它计算机作为计算节点( c o m p u t i n g n o d e ) ，是计算服务的主 要提供者。 本文所研究开发的平台服务器端，正是在合肥工业大学高性能与协同计算 开放实验室的集群系统上运行集群系统使用完全商业化的硬件，也就是说集 群从硬件上看跟普通的个人计算机网络是一样的。而集群能够高效协同的工作 主要归功于强大的软件，这些软件有基于消息传递的并行环境，如p v m 【7 j ， m p l l 8 】等；作业管理调度软件，如p b s 9 】，m a u i 1 0 1 等；集群管理软件，如c 3 1 1 】； 甚至集群软件包，如o s c a r t l2 1 ，r o c k s 1 3 】等。 1 2 并行程序设计环境及国内外研究现状 大量并行计算平台的出现，大大提高了很多应用程序的运行速度。特别是 随着集群系统的出现，可以以较低的成本搭建并行计算系统，这也使得并行分 布式应用程序开发环境的重要性随之不断增加。随着并行应用的发展，人们对 并行程序的设计模型和支持它们的工具与环境提出了更高的要求。特别是现实 中缺乏合适的并行软件开发方法和工具，许多并行应用的性能无法得到充分的 提高。 1 2 1 并行编程语言和环境 不同的并行计算机体系结构导致了不同的并行编程语言和环境，这些语言 和环境包括从低层的并行编程原语到高层的并行编程原语。其目的是能为程序 员提供更多的灵活性和能控制与协调并行程序的运行。随着并行机的普及和推 广，从当初只支持非常低级的并行原语到现在很多不同的高级并行编程语言和 环境的大量出现【h 】，这些都促进了并行的应用和推广。下面对近代并行编程语 言环境从共享存储并行编程环境和分布存储并行编程环境两方面分别做简要的 介绍。 ( 1 ) 共享储存并行编程环境 钔p t h r e a d s ：p t h r e a d s ”】是p o s i x 线程的简化版本，提供了互斥和条件变量两 种类型的同步原语，其功能和界面类似于s o l a r i s 线程的功能和界面。 p t h r e a d s 只能在单一地址空间中使用。 b 、o p e n m p ：o p e n m p 1 6 】由几家硬件和软件供应商共同制定的共享存储的应用 程序接口，它支持f o r t r a n 、c 、c + + 语言。一个典型的o p e n m p 程序开 始运行于单一任务，当遇到并行结构时，就派生出一组并行任务，每一个 任务都有其自己的数据环境。 c ，高性能f o r t r a n ：高性能f o r t r a n 简称为h p f 1 7 1 是一个支持数据库并 行的并行语言标准，从编程的角度，它提供的是一个共享存储界面。 ( 2 ) 分布储存并行编程环境 每个处理器都有自己的局部存储器，所有的局部存储器构成了整个地址空 3 问，地址空间的编址方式有局部和全局两种。 a ) m p i ：m p i 是国际上通用的消息传递接口，是一种国际标准，它可以与c ， f o r t r a n ，c + + ，j a 、，a 等语言相结合而构成并行程序设计语言。m p i 有许多实现版本如l a m - m p i ，m p i c h 等，每一种实现版本中均包含了消息 传递函数库( 用于程序设计) ，和程序运行环境。另外，m p i 不仅支持集群 硬件系统，还支持在大规模并行处理( m a s s i v e l yp a r a l l e lp r o c e s s i n g ) 计算 机，对称多处理( s y m m e t r i cm u l t i p r o c e s s i n g ，s m p ) 计算机等环境上运行， 同时也支持各种操作系统。因此，采用m p i 编写的程序有非常好的移植性 1 8 , 1 9 。本文所研究开发的并行程序设计平台是基于消息传递接口m p i ( m a s s a g ep a s s i n gi n t e r f a c e ) 来实现的。 b ) p v m ：p v m 【2 0 】是由美国t e n n e s s e e 大学、o a kr i d g e 国家实验室和e m o r y 大学联合研制的一个网络计算环境，一个支持网络并行的自由软件。 p v m ( p a r a l l e lv i r t u a lm a c h i n e ) 是一种常用的基于消息传递的并行编程环境， 它把工作站网络构建成一个虚拟的并行机系统，为并行应用提供了运行平 台。使用p v m ，用户可以构造一个虚拟机( v i r t u a lm a c h i n e ) ，它由一组全相 连的节点组成。每个节点可以是任意一台u n i x 计算机，可以是共享存储或 分布存储多机系统，也可以是串行、向量或并行计算机。应用程序可以将 p v m 看成是一个基于消息传递模型的虚拟并行计算机系统，同时在一定程 度上支持共享存储模型。 p v m 和m p i 都为用户提供基于消息传递的并行编程环境，但它们之间也存 在许多差别 2 h ：m p l 只为用户提供一个消息通信库，而p v m 在提供通信库之 外，还提供了为p v m 程序创建机群环境( 即p v m 虚拟机) 的标准方法，并定 义了运行时任务到虚拟机中节点的映射机制；p v m 最大的优点是灵活性，包括 异构平台上的可移植性、交互性和容错功能；m p i 相对于p v m 来说，提供了 更加丰富，更为高效的通信函数。 1 2 2 并行程序设计环境研究现状 并行程序设计是并行处理研究中的一个重要的部分，作为用户与并行机的 接口，它的发展不仅影响并行机性能的发挥，而且在很大程度上关系到并行计 算机的推广和普及应用。并行程序设计研究面临着许多问题，如研究并行程序 的设计和开发环境，提供给用户一个集成的可视化的并行程序开发环境等。并 行应用程序设计开发上的复杂性及并行系统中应用软件的缺乏，使得并行程序 的编程和调试相当困难，大大阻碍了并行计算机系统和并行计算的推广和应用。 并行程序设计涉及到任务的划分、处理机的分配与映射、处理机间的通信 与同步等问题，与串行程序设计相比要复杂得多。这要求进行并行程序设计的 用户具有较深的理论和较高的实践技能，从而使推广并行计算应用的难度增大。 目前并行程序设计可以分为两类，一类是基于共享内存，另一类是基于消 4 息传递；不论哪一种，对非专业人员来说，开发并行程序都是困难的。对于中、 低端高性能计算用户的计算量通常没有高端用户那么大，因此，他们并不单一 地追求程序的运行效率。由于没有对并行机理和多机通信方式进行深入的理解， 他们更加关注于并行用户环境的易用性和编程过程的简单性 2 h 。不必陷入复杂 的并行语言的编程细节之中【2 2 1 。并行用户环境是并行计算机用户的工作平台， 它直接影响到高性能计算机的应用和推广。 而上文提到并行语言环境p t h r c a d s 、o p e n m p 、h p f 及消息传递软件系统 m p i 、p v m 等，主要是解决系统核心运转以及组织各部分有效工作的底层问题， 尽管考虑到了应用程序的接口，但易用性仍然不够。为了满足用户对并行的需 求，充分利用并行计算系统中的资源，需要为用户提供一个良好的并行程序开 发环境，使并行计算系统和结构对用户透明，从而减少并行应用程序开发设计 的复杂性。 因此，研究简单易用、功能强大的并行程序设计环境是当前并行计算的一 个重要研究方向，也是使并行计算便于推广的重要手段。开发出简单易用、界 面友好的并行程序设计环境必将促进并行计算的普及和推广【2 3 】。 针对以上实际问题，国内外许多研究机构和专家学者对并行程序开发环境 进行了不少的研究工作。 如h e n c e t “2 5 1 ( h e t e r o g e n e o u sn e t w o r kc o m p u t i n ge n v i r o n m e n t ) 是一个在 p v m 基础上为开发网络并行程序而设计的x w i n d o w 环境，集图形化的创建、 编译、运行和分析于一体，它采用图形化的任务描述手段对一个并行问题进行 描述。但h e n c e 由于子任务间不能有数据依赖，因而表达能力不强。文献 2 6 】 中开发的并行系统是通过在源程序中加入f o r k 和j o i n 两个进程操作原语实现 ，并行表示的，系统对用户提交的并行程序预编译产生可并行的子任务。该环境 可用来开发一些并行计算问题，但它有许多不足，如f o r k j o i n 的结构性不强， 预编译开销较大，子任务间不允许有数据依赖等。如d p n d p 27 1 ，其并行开发模 型采用的是m i m d 结构，d p n d p 支持并行模板化设计，而且支持库实现。尽 管如此，d p n d p 不提供创建新模板的工具，只有在一个指定的c + + 框架才能 建立模板。文献 2 8 】中实现了面向对象并行程序开发环境p a r a o b j e c t 。该平台在 底层封装了现有的并行程序开发环境p v m ，实现节点任务的分配和节点之间的 通信。它由对象平台类、并行对象类及邮件对象类组成。本平台在一定程度上 减轻了用户了解底层并行系统机制的难度。但未提供用户交互的可视化功能， 而且用户仍然需要自己编写负责并行化的代码。如c 0 2 p ，s 2 9 , 3 0 l ，其面向的是共 享内存式多处理机结构，支持多种级别的抽象，它容许用户设计高级别模板的 应用程序，运行调整转向更低级别的抽象，但通常生成的是多线程j a v a 代码。 匈牙利的m t a s z t a k i 并行与分布式系统实验室开发的p - g r a d e 3 1 , 3 2 是一种 以控件形式与用户进行交互的并行程序开发环境，由编程工具，运行工具和分 5 析工具组成，但它主要运行在u n i x 平台下，据作者了解目前还不支持w i n d o w s 平台。v p e 3 3 是新加坡理工大学在p v m 上为i b mr s 6 0 0 0 工作站开发的一个 小型的可视化并行程序开发环境，虽然功能强大，但针对特定的硬件平台，只能 面向并行计算专家及专业人士。南京大学研制了面向专业领域的h o o p e l 3 4 】并 行开发环境，采用面向对象的方法封装了领域多发的并行任务。 1 2 3v p p e 的提出 以上并行程序设计环境在一定程度上为用户提供了方便，但大多针对特定 的领域或特定的软、硬件平台，或一些特定的用户而不具备很好的通用性，很 难满足一些中低端要求的非专业用户对设计并行程序的需求。并行程序设计环 境要满足简单易用的要求，必然要朝着可视化、模板化的方向发展。 相比较上一节提到的各种系统，v p p e ( v i s u a lp 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 ) 在并行结构方面的限制更少，其并行的实现仍是借助于m p i 技 术。 其次，在大部分系统中，用户经常受限于只能使用系统支持的高层结构， 而如果用户的程序需要特定的不能被系统支持的结构或模型，那么将很难甚至 无法开发出并行程序。而在v p p e 中，几乎任何复杂的结构都能在平台的应用 层创建，应用层是v p p e 中最高开发层。 最后，v p p e 中通过并行范式模板和并行代码模板这两种模板技术能最终 生成完整的并行源代码，两类模板分别在不同的层次上实现，相对独立。而且， 也可以对己创建的并行程序进行修改。而上述提到的系统很少能生成并行源代 码，大部分都是中间代码，如p - g r a d e 。这些中间并行程序必须调用消息库 函数如m p i 或p v m 才能运行。 1 3 本文研究内容及组织结构 1 3 1 本文研究内容 本文通过对并行程序设计环境研究现状及存在问题的分析，国内外相关研 究工作的成果的借鉴，以及作者所在的合肥工业大学v c c 研究室在并行计算、 可视化、模板等方面已有工作的基础上【3 5 , 3 6 , 3 7 , 3 8 , 3 9 , 4 0 ，提出了一种在w i n d o w s 平台下的基于模板的可视化并行程序开发方法，设计实现了基于模板的可视化 并行程序设计平台，并应用于合肥工业大学高性能与协同计算开放实验室。本 文主要工作包括以下几个方面： 第一，调研有关并行计算方面的文献资料，分析并行计算技术的发展趋势 及并行程序设计环境的研究现状。 第二，通过研究常用的并行程序编程模式，抽象并建立并行范式模板，使 用户可以直接切入并行程序的逻辑结构，在并行程序设计的高层快速高效地定 制、建立满足实际并行问题的进程逻辑图形结构。 6 第三，通过研究并行消息传递库m p i 函数的底层机制和参数特点，抽象出 并行代码模板。以图形图标的方式隐藏了消息传递函数的复杂性，对用户来说 并行底层机制是透明的，从而方便了非专业用户设计并行程序。 第四，以可视化、模板化的思想，图形图标的抽象，设计开发出基于模板 的可视化并行程序设计平台。 1 3 2 论文组织结构 论文的其它章节内容安排如下： 第二章：并行程序设计平台框架。介绍了可视化并行程序设计平台中所涉 及到的相关概念和术语。接着介绍了平台的总体框架并从四个方面详细介绍了 平台的系统设计：应用层设计、进程层设计和代码产生器的设计( 也即代码层 的设计) 。然后简要说明了使用该平台进行并行程序设计的步骤和方法。 第三章：并行范式模板技术及其实现。从模板引入并行程序设计平台到常 用并行范式模板的定义，再到关键技术的实现细节做了详细的介绍。 第四章：并行代码模板及源代码的自动生成。继第三章并行范式模板技术 及实现的基础上，分析和阐述了文章的第二个核心内容一一并行代码模板。介 绍了并行代码模板提出的背景，及并行源代码自动产生的技术细节。 第五章：平台应用实例。介绍了平台的用户界面及平台的功能和特点。然 后以一个简单的应用实例的设计过程说明了基于模板的可视化并行程序设计平 台v p p e 的易用性和可行性。 第六章：总结与展望。对本文研究工作进行了全面的总结，同时提出了平 台的不足和对今后工作的展望。 l 4 本章小结 本章首先介绍了并行计算的发展和现状；然后对并行计算在国内外的研究 情况进行了概述和分析；简述了基于集群的高性能计算技术，这是本文所研究 可视化并行设计平台的后端工作环境；最后详细介绍了并行程序设计环境及国 内外研究现状。 第二章并行程序设计平台框架 2 i 相关概念和术语 在本课题的研究、设计以及实现基于模板的可视化并行程序设计平台的过 程中，涉及到诸多概念和术语，为方便理解，在此一一列举说明。 可视化：指使用一些可视的表现形式来表达程序、数据、系统结构或系 统动态的行为。 可视化编程环境：指计算机能够理解给定的图形表示。并把用户与鼠标之 类的设备之问的交互转换成程序的代码部件，用这种方式建立一个程序编辑、运 行、测试、调试的环境。所有的部件基本可以通过鼠标点中或拖曳等方法对图 形进行操作和组合来生成。 并行计算机：由多个处理单元组成的计算机系统，这些处理单元相互通 信和协作，能快速，高效地求解大型复杂问题。 并行算法：相对于串行算法而言，目标就是以增加空间的复杂性来减少 时间的复杂性，即增加空间的维数，增加处理器的台数，来减少算法实现所需 的时间。 并行计算：并行机上所作的计算，又称高性能计算或超级计算。 并行程序设计：相对于串行程序设计而言，致力于可并行问题的实现及 相关并行软件的开发。并行程序是并行算法的体现。 范式：描述了一类经常出现的问题和解决这类问题的方法 并行范式模板：并行范式模板就是一类并行程序的抽象，是一个可以重 复使用的进程拓扑结构的抽象，它抽象定义了一组拥有特定规律的拓扑结构的 进程。 进程农庄：一种并行编程范式，指对一个实际的问题能分解成若干个同 类的相互的独立的子任务进程进行解决，各子任务进程间互不通信。 流水线：把一个任务划分成若干个个前后衔接的任务片断，每个任务片 断的输出作为下一个任务片断的输入。在所开发的平台中由一组线性结构的进 程组成，各进程仅仅与其相邻的进程通信。 进程：进程是对一个可并行的实际问题分解为若干个子问题或予任务的 抽象，在平台的应用层由一矩形框表示，在进程层由控制流的图标描述。 端口；端口是对子任务间通信数据的抽象，用来表达进程间如何通信、 通信的数据大小和数据类型，一个进程或通信动作图标可以附着若干个端口， 端口又分为输入端口和输出端口，在实现中用不同的颜色来表示通信输入端口 和通信输出端口，在应用层中用一个小的矩形框来表示。 m p h 是一种消息传递接口，实际上是一个消息传递函数库的标准说明， 是目前国际上最流行的并行编程环境之一，m p l 只是为程序员提供了一个并行 8 环境库。 进程拓扑：由进程、端口和信道依照一定的约束关系组织在一起形成的 能够表达用户并行程序的整体逻辑结构和功能结构的进程互连拓扑图。 图标：所谓图标就是在进程层抽象出的用来表示控制流的图形符号。 2 2 总体框架 平台采用面向对象的思想进行分析、设计和开发，按照功能可以分为以下 两个部分：并行编程模块和远程计算模块，而并行编程模块又由以下几部分组 成t 应用编辑器、进程编辑器和串行代码编辑器，分别对应平台的三层结构， 应用层、进程层和代码层，如图2 - 1 所示。文章主要讨论平台的并行程序编辑 部分，而对远程计算模块不做深入讨论。所研究讨论的并行范式模板基于应用 层设计，而并行代码模板对应进程层和代码层。 图2 - l 平台系统框架图 9 平台并行编程模块在面向对象的基础上又采用层次式设计思想。整个程序 的编程从上到下分为三层：应用层编程、进程层编程和代码层编程。环境中的 三层设计结构是一个逐步求精、细化的过程，它们互相补充，共同实现并行程序 的设计、开发和最终代码的产生。 2 3 平台系统设计 2 3 1 应用层设计 应用层是平台并行编程模块中的最高层，进程、通信端口和通信信道都是 在这一层完成定义，因此，对用户来说，必须清楚对实际问题如何进行抽象和 分解。而在应用层所完成的工作只是功能和逻辑上的定义，不涉及具体的实现， 进程的具体实现和整个应用程序的并行机制在这一层被隐藏，也就是说，进程被 看作是黑箱子，我们只关心进程间的消息传递，即进程间互连的拓扑结构。在这 一层用户通过对进程、通信端口和通信信道的图形进行编辑可以定义并行程序 的整体逻辑框架，以图形的方式显示并行程序的整体逻辑结构，例如进程的个 数，进程间通信的信道个数，端口的个数，并行的方式( 例如主从式，管道) 等。实际上，应用层主要的功能是将并行程序的整体逻辑框架用比较直观的图 形表示出来，如图2 2 所示。 图2 2 平台应用层编程视图 在应用层抽象出以下几个类：应用类( c a p p l i c a t i o n ) ，进程类( c p r o c c s s ) ，端 口类( c p o r t ) 和信道类( c c h a n n c l ) 。应用类是对实际可并行问题的抽象；进程类 是对一个可并行的实际问题分解为若干个子问题或子任务的抽象，在应用层中 用一个较大的矩形框来表示一个进程；端口类是对子任务间通信数据的抽象， 在应用层中用一个小的矩形框来表示一个端口，由于通信的数据分为输入和输 l o 出两种情况，在实现中用不同的颜色来表示通信输入端口和通信输出端口；信 道类是对子任务间如何通信的抽象，在应用层中用一条带箭头的线表示，从输 出端口开始指向输入端口。 为了实现应用层设计，友好的用图形表达出并行机制，同时为并行范式模 板的建立和下一层进程层的设计和实现提供了坚实的底层技术支撑，抽象出以 下相关概念和数据结构。 ( i )进程端口位置 每个进程拥有十六个端口位置，均分于进程的四条边，即每个进程的上、 下、左、右边平均拥有四个端口位置。依顺时针方向从进程上方的左边第一个 端口位置开始依次编号为0 、l 、2 、3 、4 1 5 。其位置结构如图2 3 所示，中 间正方行表示进程，周围每一个小正方形表示一个端口位置。 进程的每个端口位置上的信息，包含端口的起点坐标、端口有无、以及此 位置上端口的指针。其位置定义如下： t y p e d e fs t r u c t “p r o c k s s 旦o r t p o s2 i t i o n c o o r d i n a t ep o r t c o o r d i n a t e ；瑞口+ 的左上赢坐标 b o o lf u l l o r e m p t y ；t r u e 表示此位置有端口，f a l