（计算机应用技术专业论文）一种面向网格的并行计算模型及算法实现研究.pdf

上海大学硕士学位论文 坠! ! ! s 塑生! 塑坠型! 堕! ! ! 竖型旦! ! 堡竖塑 摘要 并行计算模型是为研究并行算法的性能，开发具有可移植性并行程序而建立 的一种理论计算模型。本文研究面向网格的可扩展并行计算模型与算法设计，构 建面向网格环境的可扩展并行算法框架，体现网格计算的特点，充分发挥网格计 算优势，支持网格抢先式调度系统功能。 本文构造和实现基于思维进化计算的网格计算模型与并行算法，支持网格环 境下的动态资源分配。文中的主要工作包括：提出一种基于空间分解并行策略的 二级并行计算模型；构造基于思维进化的m e s p p e a 的并行算法；采用可分解 可拼接编码、信号量技术等，支持动态资源分配，提高网格服务质量。网格平台 运行结果证明上述算法收敛性能及可扩展性方面都得到了提高。 文中将趋同、异化操作引入到并行演化计算中，构造m e s p p e a 并行算法框 架。对构成m e s p p e a 的方法和技术进行深入的分析。其中可分解可拼接编码 是一种自适应编码，趋同操作和异化操作针对多维函数优化问题做了改进。 本文在“自强3 0 0 0 ”集群环境并行实现了m e s p p e a 算法，分析了算法的 并行效率。加速比实验表明算法具有良好的加速比。m e s p - p e a 解精度实验显示 解的精度与节点规模增加成正比，这点非常具有使用价值，表明m e s p p e a 算 法可以很好的支持网格环境下的动态资源分配。 本文进一步针对网格环境下动态资源分配的特点实现了算法的并行，给出在 网格环境下算法会遇到的问题及改进方法，实现了对网格环境下动态资源分配的 支持。文中论述算法在网格环境下的执行过程，给出了m e s p p e a 算法动态资 源分配情况下的实验结果。上海高校网格e 一网格计算应用平台上的动态资源变 化实验表明，该算法可以支持抢先式网格调度，提高网格服务质量。 本文最后给出了进一步的研究方向。框架技术使得从一个构件库中建立应用 变得容易。同时构件采用框架统一定义的接口，从而使构件间通信简单，易于实 现。整合网格平台上的数据管理功能，开发可重用的并行框架将成为本文需要研 究的进一步工作。 关键词： 网格计算，并行计算，演化计算，思维进化计算，m e s p - p e a ，动态资源调度 上海大学硕士学位论文 二墅! 塾竖型螋卫竺堕匹! 墅墅望! ! ! 塑堕 a b s t r a c t p a r a l l e l c o m p u t a t i o n a l m o d e l sa l et h et h e o r e t i c a l c o m p u t a t i o n a l m o d e l s d i s c u s s i n gt h ep e r f o r m a n c e so ft h ep a r a l l e la l g o r i t h m sa n dd e v e l o p i n ge a s ym i g r a t i o n p a r a l l e lp r o g r a m s n l em a i na i mo ft h i sp a p e ri st or e s e a r c hi n t og r i d e n a b l e d s e a l a b l ep a r a l l e lc o m p u t a t i o n a lr r a x l e la n d a l g o r i t h md e s i g n , b u i l dag r i d - e n a b l e d s e a l a b l ep a r a l l e la l g o r i t h mf r a m g w o r k , w h i c hp r e c i s e l yp r e s e n t sc h a r a e t e r i s t i co f 蒯 c o m p u t a t i o nb ys u p p o r t i n gp r e e m p t i v es c h e d u l i n gf u n c t i o n a l i t yo fg r i dm a k ef u l lu s e o f a d v a n t a g eo f 鲥dc o m p u t a t i o n ag r i d c o m p u t a t i o n a lm o d e la n da l g o r i t h m b a s e do nm i n de v o l u t i o n a r y c o m p u t a t i o ni s c o n s t r u c t e da n di m p l e m e n t e d , w h i c hs u p p o r t st h ed y n a m i c a l l y r e s o u r c ea l l o c a t i o nu n d e r 鲥de n v i r o n m e n t t 量l em a i ne f f o r t sa r ed i r e c t e dt o w a r d s p r e s e n t i n gab i - l e v e lp a r a l l e lc o m p u t a t i o n a lm o d e l p a r a l l e l i z a t i o no fm e s p - p e a a l g o r i t h m , u s i n gs e m a p h o r et e c h n o l o g ya n ds p l i c i n g d e c o m p o s a b l ec o d es c h e m at o i m p r o v eq u a l i t yo fs e r v i c e 弛e x p e r i m e n t si n 鲥dp l a t f o r mp r o v et h a tc o n v e r g e n c e e m c i e n e ya n ds e a l a b i l i t vo f m e s p p e a a r ei m p r o v e d 硼1 cs i m i l a r t a x i e sa n dd i s s i m i l a t i o na r ei n t r o d u c e di n t ot h ep a r a l l e le v o l u t i o n a r y c o m p u t a t i o na n dt h ep r o g r a mf r a m e w o r ko fm e s p - p e ai sc o n s t r u c t e d m e a n w h i l e t h et e c h n o l o g i e si n c l u d e di nm e s p - p 琶aa l ea n a l y z e d m e s p p e aa d o p t s s p l i c i n g d e c o m p o s a b l ee n c o d i n gt h a ti sa na d a p t i v ee n c o d i n g ，u s e ss i m i l a r t a x i e sa n d d i s s i m i l a t i o no p e r a t i o n sw h i c hi ss u i t a b l ef o rf u n c t i o no p t i m i z a t i o n m e s p p e ai s i m p l e m e n t e do nc l u s t e re n v i r o n m e n t a n dt h ep e r f o r m a n c e so f m e s p p e aa r ea n a l y z e db yt h ee x p e r i m e n t sc a r r i e do u ti n “z i q i a n g3 0 0 0 ”n l e e x p e r i m e n t so fs p e e d ，u 口i n d i c a t et h a tm e s p - p e ah a sap e r f e c ts p e e d - u p t h e e x p e r i m e n t sa b o u tp r e c i s i o no fs o l u t i o n sd e m o n s t r a t et h a tp r e c i s i o ni se n h a n c e dw i t h t h ei n c r e m e n to fn u m b e ro fc o m p u t i n gn o d e ，w h i c hi sv e r yv a l u a b l ei np r a c t i c a l a p p l i c a t i o na n di l l u s t r a t em e s p p e a c a nw e l ls u p p o r td y n a m i cr e s o u r c ea l l o c a t i o no n 西de n v i r o n m e n t t h i st h e s i sf u l l e rp a r a l l e l i z em e s p p e aa l g o r i t h mo ng r i d p u tf o r w a r dt h e p r o b l e m st h o s ew i l lo c c u rt h e r ea n dg i v et h em e t h o d st or e s o l v et h e mt os u p p o r tt h e r e s o u r c ea l l o c a t i o nd y n a m i c a l l yo f 商d e x e c u t i o np r o c e s so ng n di sd e s c r i b e d 。 e x p e r i m e n tr e s u l t s o f d y n a m i cr e s o t l l v ：ea l l o c a t i o n o f m e s p p e a a r c p r e s e n t e d mf r a m e w o r km a k e sr e u s eo fc o d ea v a i l 曲l e w h i c hl c a d st ob u i l da p p l i c a t i o nf r o m c o m p o n e n tl i b r a r ye a s i l y m e a n w h i l e c o m p o n e n ti n t r o d u c e su n i f i e di n t e r f a e eo f f r a m e w o r ka n dm a k e sc o m m u n i c a t i o nb e t w e e nc o m p o n e n t ss i m p l y n l ef u r t h e rw o r k w i l lb ee m p h a s i z e do nd e v e l o p i n gc o n s t r u c t i v ep a r a l l e lf r a m e w o r kc o m b i n a t i o nw i t h d a t am a n a g e m e n tf u n c t i o no fg r i dp l a t f o r m k e y w o r d s ： g r i d c o m p u t i n g ，p a r a l l e lc o m p u t i n g ，e v o l u t i o n a r yc o m p u t a t i o n , m i n d e v o l u t i o n a r yc o m p u t a t i o n , m e s p p e a ，d y n a m i cr e s u u r e ea i l o c a t i o n i i 上海大学硕士学位论文 堡! 婴塾型! 塑旦! 坐堕! ! 型墅旦堡! 堕! 壁 图表目录 图1 1 - 1 上海高校网格e 网格计算应用平台示意图4 图1 1 2 主从模型示意图 图1 1 3 孤岛模型与跳石模型示意图。 图2 1 1 上海高校网格层次结构图 7 9 图3 2 1 阻塞与非阻塞调用的对比2 9 图3 2 2 死锁情况 图3 2 3 安全情况3 1 图3 2 4 分布存储系统上的并行i o 结构。 图3 2 5 并行i 0 实例一 3 2 3 3 图4 1 - l 上海高校网格e - 网格计算应用平台体系结构。3 5 图4 5 1 函数n 资源动态增加测试 图4 5 - 2 函数也资源动态增加测试 4 1 4 2 图4 5 3 函数b 资源动态增加测试4 3 图4 5 - 4 函数f 4 资源动态增加测试 图4 5 5 函数f 5 资源动态增加测试 图4 5 6 函数佑资源动态增加测试 图4 5 - 7 函数f 1 资源动态减少测试4 7 图4 5 8 函数岔资源动态减少测试4 8 图4 5 9 函数f 3 资源动态减少测试。 图4 5 - 1 0 函数f 4 资源动态减少测试 图4 5 1 1 函数f 5 资源动态减少测试 图4 5 1 2 函数f 6 资源动态减少测试 图5 1 1 加速比曲线图 4 9 5 0 5 1 图5 2 1 函数f l f 6 不同节点所得解的精度曲线图 表格3 1 1 迭代t 次后所得的适应度 表格3 1 - 2 迭代t + 1 次后所得的适应度。 表格4 5 1 函数f i 资源动态增加测试 表格4 5 - 2 函数f 2 资源动态增加测试 表格4 5 - 3 函数b 资源动态增加测试 表格4 5 - 4 函数f 4 资源动态增加测试 1 9 。1 9 4 2 4 3 表格4 5 5 函数6 资源动态增加测试4 5 表格4 5 - 6 函数f 6 资源动态增加测试 表格4 5 4 函数f l 资源动态减少测试 4 6 表格4 5 - 8 函数岔资源动态减少测试4 8 表格4 5 9 函数b 资源动态减少测试。 表格4 5 1 0 函数f 4 资源动态减少测试 4 9 表格4 5 1l 函数f 5 资源动态减少测试。5 1 表格4 5 1 2 函数佑资源动态减少测试。 v 上海大学硕士学位论文 ! 堡! ! 壁趔! 坐坠型! 堕! ! 磐g 墅坐! 兰墅型 表格5 1 1 加速比表5 4 表格5 2 1 函数f l 不同处理器数的精度比较5 5 表格5 2 - 2 函数位不同处理器数的精度比较5 5 表格5 2 - 3 函数b 不同处理器数的精度比较5 6 表格5 2 - 4 函数f 4 不同处理器数的精度比较5 6 表格5 2 5 函数f 5 不同处理器数的精度比较 表格5 2 - 6 函数彤不同处理器数的精度比较 v i 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工作。除了 文中特别加以标注和致谢的地方外，论文中不包含其他人已发表或撰写趔 的研究成果。参与同一工作的其他同志对本研究所做的任何贡献均己在讫 文中作了明确的说明并表示了谢意。 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规定，即：学校j 权保留论文及送交论文复印件，允许论文被查阅和借阅；学校可以公布 文的全部或部分内容。 ( 保密的论文在解密后应遵守此规定) 签名：奎垒i 刍导师签名：幽日期： e 4 0 7 , ；2 5 上海大学硕士学位论文 ! 些! ! 壁型! 坐旦鲤! ! ! ! ! 竺韭墅旦! ! ! 竺塑 第一章绪论 1 1 本文的研究背景 1 1 1 网格计算研究现状 网格通过网络连接地理上分散的各类计算机、数据库、各类设备和存储设备 等，形成对用户相对透明的虚拟的高性能计算环境，应用包括分布式计算、高吞 吐量计算、协同工程和数据查询等诸多功能。网格被定义为一个广域范围的无缝 的集成和协同计算环境i l 】。网格计算模式已经发展为连接和统一各类不同远程资 源的一种基础结构，实现计算资源、存储资源、数据资源、信息资源、知识资源、 专家资源的全面共享。全球性的业务需求要求具有强大的问题解决能力以应付那 些异常复杂的问题，这一需求已经促进全球工业部门对众多到处存在的计算资源 进行动态协作，以便能够合作工作。网格给现有的技术环境带来了新的研究内容。 这种高级的协同计算能力是几乎所有工业和业务领域的问题解决所必需的，其范 围囊括了从科学研究，商务解决方案等诸多领域。 目前国内外许多政府部门、研究机构、跨国公司和著名大学的许多科研人员 从事网格计算系统的研究，已经开展了许多论坛、实验环境和研究项目。较有代 表性的网格计算项目包括：g l o b u s 项目 2 1 、l e g i o n 项目 3 1 、n s f 中间件( n m i ) 1 4 】、 u n i c o r e 项目 5 1 、c h i n a g r i d 项目 6 1 1 7 】等。 g l o b u s 项目是一个多机构的研究工作，它旨在为计算网格创建基本的基础设 施以及高级服务。计算网格被定义为硬件和软件的基础设施，为了获得高端的计 算能力，它能够提供可靠的、一致的、普遍并且廉价的方法【s 】。它现在已经发展 成为在不同种类的虚拟组织之间进行资源共享( 硬件、软件以及应用等) 的基础 设施。g l o b u s 为网格中定义的主机高级服务提供具有低级基础设施的分层式软 件体系结构。这些高级服务与资源发现、分配、监控、管理、安全、数据管理以 及访问都有关系。较低层次的基础设施为主机高级服务提供框架。l e g i o n 是弗吉 尼亚大学的一个中间件项目计划，是为了网格应用而设计的基于对象的系统软 上海大学硕士学位论文 ! 堡堕窭型! 塑堡竺堡堕! ! ! 呈g 堕旦! ! 翌! 型 件。l e g i o n 项目的目标是通过为处理器、数据系统、文件系统等提供标准的对象 表示阴，从而推动分布式系统软件的原则性设计。l e g i o n 应用是根据这些标准对 象进行开发的。用户组可以构建一个共享的虚拟工作区，以便在研究及信息交换 方面进行协作。u n i c 0 i 也计划由德国联邦教育与研究部提供资金支持，它的设 计目标包括：统一的并且易于访问的图形用户界面、基于抽象作业概念之上的开 放式体系结构、一致安全性体系结构、具有本地管理过程的最小接口以及对现有 和新兴技术的利用。n m i 是由美国国家科学基金会发起的，主要用于帮助科学 家和研究人员通过i n t e r a c t 有效地共享仪器、实验室及数据、以便相互进行协作。 n m i 由网格的研究集成部署支持中心及企业桌面集成技术联盟组成。网格的研 究集成部署支持中心主要是定义、开发、部署以及支持、集成稳定的中间件基础 设施。企业桌面集成技术联盟提供软件用于支持更广范围的桌面安全、视频以及 具有目录模式的企业应用。这就大大方便了启用目录领域间的认证以及授权的联 合模式。除此之外，还负责约定最佳实践指导原则、体系文档结构、策略，并为 中间件的管理提供服务。 中国教育科研网格c h i n a c _ r r i d 整合了全国2 0 所重点高校的大量网格资源，建 立了资源共享、配置灵活、跨学科、跨地域的网格环境，开发了具有重要国际影 响的网格中间件c g s p ，部署了生物信息学、图像处理、计算流体力学、海量信 息处理、大学课程在线五类具有重要社会经济效益的特色网格应用。系统总体设 计和关键技术达到国际先进水平。中国教育科研网格c h i n a c r r i d 是教育部在“十 五”2 1 l 工程公共服务体系建设中设立的重大专项，主要解决中国教育科研网中 网络计算面临的无序性、自治性和异构性等问题，满足高校科学研究的迫切需要。 使用网格技术将中国教育科研网上分散、异构、局部自治的巨大资源整合起来， 通过有序管理和协同计算，消除信息孤岛发挥综合效能、实现资源的广泛共享、 提供高效的计算服务、数据服务和信息服务等。 1 1 2 上海高校网格e _ 网格应用平台简介 上海大学为上海市教委领导下的上海市网格技术b 研究院依托单位。为推进 网格技术的发展，促进网格技术应用的研究，上海市教委领导下的上海市网格技 术b 研究院建设目标是，以新一代的信息基础设施一网格为平台，把分布在不同 2 上海大学硕士学位论文 坠! ! ! 墨型唑卫生! 坚! 墅g 墅旦! ! ! 竺塑 地点的、不同单位的、不同计算节点的各种计算和信息服务资源，例如处理能力、 存储能力和信息服务能力，整合为一个单一的虚拟系统，提供给上海市教委的用 户使用。创造跨学科跨地区科研交流的合作环境、促进解决重大科技项目的攻关、 解决前沿学科领域的难题、推动基础理论研究进展与创新。 上海市网格技术b 研究院建设的目的是为上海市创造以网格平台为基础的 广阔交流合作环境。在这环境下促进国内外科技人才的聚合，组织有效的合作科 学研究活动，以全新的模式培养和教育研究生，使上海高校的科技创新和学科发 展在观念、运行等方面实现新的发展；同时为上海市经济和科技实力的提升做出 贡献。上海高校网格平台将在e - 研究院中发挥网格基础设施的作用。上海高校 网格项目包含网格平台建设、网格节点建设和网格示范应用三个部分。本文所要 研究的面向网格的并行计算模型与应用，属于网格示范应用中“上海高校网格一 计算密集型网格应用及相关中间件研制”项目的一部分。 上海高校网格e 网格计算应用平台的作业调度采用分级调度结构。调度结构 主要由两级调度组成：即本地作业调度器( l o c a ls c h e d u l e r ) 和全局调度器( g l o b a l s c h e d u l e r ) 。本地调度器主要负责接收全局调度器分派来的用户作业，实现该作 业在本地资源中的调度和分配，将其提交到指定资源上运行，同时还接受全局调 度对用户作业提交的各种控制事件，及时对运行作业进行有效处理，通常都拥有 自己的调度策略和资源使用约束。网格系统中，四个主要的资源节点上都配置本 地集群作业管理系统，其中在上海超级计算中心使用了l s f ( l o a ds h a r i n g f a c i l i t y ) 集群作业管理调度系统作为本地作业调度系统，其它三个集群使用了 o p e n p b s ( p o r t a b l eb a t c hs y s t e m 的一种开源系统) 集群作业管理调度系统作为 本地作业调度系统。全局调度器，也叫中央调度器( c e n t r a ls c h e d u l e r ) ，或一种 元调度( m e t a - s c h e d u l e r ) ，它是网格作业调度的核心组件。通过网格将所有用户 作业提交给中央调度器，由它负责为用户作业进行全局范围内的宏观资源决策和 分配，然后根据不同作业所映射的网格资源，将其重定向分派到对应的本地调度 系统中；同时根据用户作业的控制命令实现对作业进行有效监控。在该项目中， 上海超级计算中心、上海大学和华东理工大学分别提供了各自的高性能计算资 源，并利用网格技术建立了符合o g s i 规范的异构资源管理环境，使各种局部的 计算资源、存储资源、信息资源等能够在网格环境下以统一的方式被管理和调度 3 上海大学硕士学位论文 ! 堡! ! 壁型! 坐! 堕堡堕! 塑塑型旦! 堕竖堑 使用。其中上海大学“自强3 0 0 0 ”集群共有1 7 4 个计算节点，每个节点拥有2 个3 0 6 g h zi n t e lx e o nc p u ，2 g b 内存，l 块3 6 g b 硬盘，集成r a i d 控制器。 系统拥有1 个管理节点和1 个存储访问节点，采用i o i o o m 网络交换机作为内 部管理网络和c o n s o l e 网络。峰值速度为2 1 5 4 ( o n o p s ) ，l i n p a c k 值是 1 5 1 1 ( o f l o p s ) 。上海高校网格e 网格计算应用平台如图1 1 1 所示。 图1 1 - 1 上海高檬网格e - 网格计算应用平台示意图 1 1 3 网格计算系统特征 网格包括各种信息资源，例如数据库、软件以及各种信息获取设备等，它们 都连接成一个整体。分散资源的汇集和共享是网格最重要的特征。具体来说，网 格的主要特征有如下一些方面： ( 1 ) 动态性和结构不可预测性 对于网格所拥有的资源或者功能，在下一时刻可能会出现故障；而原来没有 的资源，可能随着时间的推移会不断加入进来。网格的动态性包括动态增加和动 态减少两个方面的含义。 网格资源的动态变化特点要求网格管理必须充分考虑并解决好这一问题，对 于网格资源的动态减少或者资源出现故障的情况，要求网格能够及时采取措施， 实现任务的自动迁移，做到对高层用户透明或者尽可能减少用户的损失。 4 上海大学硕士学位论文 ! 堕坠壁型! 塑旦堕堕! ! 竺g 墅旦! ! 坚竖型 ( 2 ) 共享性 网格资源虽然是分布的，但它们却是可以充分共享的。共享是网格的目的， 没有共享就没有网格。分布是网格硬件在物理上的特征，而共享是在网格软件支 持下实现的逻辑上的特征。 ( 3 ) 扩展性 元计算系统初期的计算规模较小，随着超级计算机系统的不断加入，系统的 计算规模也随之扩大。要在网格资源规模不断扩大、应用不断增长的情况下，不 降低网格计算的性能。 ( 4 ) 分布性和异构性 网格的分布性是指网格的资源是分布的，网格系统由分布在i n t e r a c t 上的各 类资源组成，包括各类主机、工作站甚至p c 机，因此网格计算必然是分布的。 异构性是指网格计算可运行在l i n u x 、l r n i x l n t 等各种操作系统下，也可以是 上述机型的集群系统、大型存储设备、数据库或其他设备。怎样实现异构机器之 间的协作和转换是网格计算需要解决的问题。 ( 5 ) 自适应性 在网格计算中，某一资源出现故障或失败的可能性较高。资源管理需要动态 的调节以获得最好的性斛1 0 1 。 ( 6 ) 自治性和多重管理 由于构成网格计算系统的超级计算资源通常属于不同的机构或组织，使用不 同的安全机制，因此网格资源的拥有者对他的资源具有最高级别的管理权限，同 时需要不同的机构或组织共同参与网格的统一管理。 1 1 。4 消息传递并行编程环境m p m p i ( m e s s a g ep a s s i n gi n t e r f a c e ) 是消息传递并行程序设计的标准之一，支 持m p i 的i o 规范和进程管理规范。m p i 正成为并行程序设计事实上的工业标 准。m p i 设计的初衷是使异构系统以及异构集群之间的并行程序设计简单化。 m p i 引入消息数据类型属性以支持异构系统计算。数据类型定义消息中不连续的 数据项及其可能不同的数据类型。数据类型由应用程序在执行时通过基本的数据 类型创建。支持异构系统计算的方法是预先定义一些基本数据类型，m p i 实现过 5 上海大学硕士学位论文 堡! 型唑堡业! ! 堕趔望坐竖塑 程中对这些类型进行转换，例如转换为x d r 格式，接收时进行反转。消息传递 模型中，各个并行执行任务之间通过传递消息来交换信息、协调步伐、控制执行。 机动灵活和控制手段的多样化，是消息传递模型能够提供高效执行效率的重要原 因。m p i 提供两种基本的并行程序设计模式，即主从模式和对等模式。可以说绝 大部分m p i 程序设计都是这两种模式之一或者两者的组合【1 ”。 并行计算的消息传递模型与其它的并行计算模型相比有几个优点。首先，消 息传递程序在许多m i m d 架构的机器上能很好的运行。由于多机系统不支持全 局的地址空间，消息传递机制可以与它们很好的配合。同时，消息传递模型鼓励 设计者最大化本地计算，最小化通信，从而在运行于多处理器计算机上表现出较 高的c a c h e 命中率，达到较高的性能。从另外一个角度讲，消息传递模型给多处 理器计算机的程序员提供了用于管理多层次存储的工具。 主从模型一般有一个主节点与若干个从节点组成。主节点主要负责数据域的 切割、分配任务以及收集结果数据，同步各从节点计算的工作。从节点负责接收 主节点分配来的任务，执行之，运行完毕将结果返回主节点，然后继续听从主节 点的调遣，如图1 1 2 所示。 图f 1 2 主从模型示意图 对等模型将各个节点都视为等同，各节点独立运行任务。在对等模型中，根 据各独立节点之间消息传递方式不同可分为孤岛模型与跳石模型。孤岛模型中， 允许将个体发送给任何其它节点，如图1 1 - 3 ( a ) 所示，它不对个体可迁移到何处 加以限制：跳石模型中，对迁移做了限制，它只允许移民移入相邻的结点，图 1 1 3 佑) 对此概念做了说明。由于限制移民可迁移的目的地数目，跳石模型较大 程度上减少通信开销。孤岛模型由于允许更松散的迁移自由，在某些方面代表了 较好的自然模型。但是，这种模型在实现时会有显著的通信开销和延迟。 6 上海大学硕士学位论文 ! 生墅塑坚! ! ! 坐堡! 堡! ! ! ! 型堂型旦坐塑塑 ( a ) 孤岛模型( b ) 跳石模型 图1 1 - 3 孤岛模型与跳石模型示意图 1 2 本文的结构 全文主要首先提出一种基于空间域分解的二级并行计算模型；在此基础上， 应用二级并行计算模型构造思维进化与空间分解并行演化算法( 巳s p p e a ) ， 对并行化过程中所涉及的若干关键问题提出相应的解决方法；然后针对网格环境 的特征，采用自适应的可分解可拼接编码与信号量技术支持网格的动态资源分 配，从程序一级提高网格服务质量。最后讲述上海高校网格e 网格计算应用平台 上函数优化的性能测试以及相应韵性能分析。 本文的第二章首先提出二级并行计算模型：接着，对演化计算、思维进化计 算作了详细的介绍；最后应用二级并行计算模型构造m e s p p e a 并行算法框架。 本文的第三章详细描述构造m e s p p e a 并行算法框架所采用的各种具体实 现技术，包含思维进化计算的趋同和异化操作、最优值并行化、矩阵块分发以及 可分解可拼接编码；然后对m e s p p e a 并行化实现过程中的划分、通信模式、 数据依赖、负载平衡、死锁以及并行i o 访问进行详细的分析并提出了相应的解 决方法。 本文的第四章研究网格环境下资源分配的动态特性、提出采用信号量技术支 持网格动态资源变化特性，提高网格服务质量。上海高校网格e - 网格计算应用平 台上执行的动态资源变化实验表明m e s p p e a 支持网格资源变化的特性。 本文的第五章对以“自强3 0 0 0 ”高性能计算机为主节点的网格平台上进行的 加速比和求解精度实验结果进行分析，并且进一步从加速比和最优解的实用价值 两个方面对并行算法的效率进行分析。 本文第六章对本文所作的工作进行总结，并指明了进一步需要研究的方向。 7 上海大学硕士学位论文 堡! ! 塾型堕旦塑坚! 墅业型型! 兰塑 第二章二级并行计算模型及应用 网格资源动态性使得网格环境下的并行化变得更加困难。传统的并行机上的 并行编程模型已经无法适应网格这个特殊背景。本章对网格环境下的并行编程模 型进行探索，提出了一种二级并行计算模型，将该模型应用到演化计算中，构造 思维进化与空间分解的并行算法框架。 2 1 二级并行计算模型原型 消息传递是目前使用最为广泛的、至少是在大型并行机上实现并行计算的一 种主要方式。消息传递模型具有的高度可移植性、允许用户显式地控制并发程序 的优点，使得在m p i 的基础上探索并行编程模型具有更加广泛的意义。文献【1 2 】 对层次并行程序作了介绍，包括并行软件体系结构( 高层) 、并行程序框架( 中 间层) 和代码( 底层) 三个设计层次【1 2 】。 并行计算中，粒度是一个重要的概念。所谓粒度，意指计算的并行度，即整 个算法中并行计算部分所占的比例。粒度的选择是并行计算能否具有高效率的关 键。粒度过大，会对并行算法的可扩展性造成影响；粒度过小，各并行计算单元 之问的协调和通信开销相比总的计算量的比例也就越大。因此需要进行合适的权 衡。上海高校网格e - 网格计算应用平台采用多层计算机网络互联，通讯开销比较 大，因此本文采用大粒度并行方式以减少通讯开销所占的比例。 分层思想把问题划分开来各个解决，易于控制，易于延展。上海高校网格e 网格计算应用平台的层次结构如图2 1 1 所示。上海高校网格e 网格计算应用平 台具有两层层次架构并采用两级调度结构组成。全局调度系统负责为用户作业进 行全局范围内的宏观资源决策和分配，将其重定向分派到对应的本地调度系统 中。本地调度系统负责接收全局调度系统分派来的用户作业，实现该作业在本地 资源中的调度和分配。从图2 1 1 中可知，当任务提交到网格系统时，第一级并 行发生在各个集群资源之间，第二级的并行发生在各个计算资源的计算节点之 间。从上述中我们发现：对于一个复杂问题，如果从逻辑上将复杂问题分解成若 干子问题并映射到各个集群资源上：接着将子问题空间域分解并映射到某个集群 资源内的计算结点上。这种二级并行计算模型将简化网格系统下的并行程序的开 发，加快并行程序开发的速度。 8 上海大学硕士学位论文 坠! 盥坠g 翌! ! 塑里! 堡! ! ! 地g 堕坚坐! ! 堡! 堡 【髑 s f 驴p 删1 i 嗣格资器胡度器l 么i 豪孓 嚏善 上 孽：熠p 自委i3 0 0 【上鸯大i眇自弱l2 9 0 ( 鲢东理=，s 妇埘 上糟程j坤 _ - 蚓白的白白白白白白白白白髑 图2 1 1 上海高校网格层次结构图 面向网格的二级计算模型描述如下：第一步，采用求解域分解设计方法将任 务粗粒度分解成若干个子问题并映射到各集群资源；第二步，将若干子问题求解 空间进一步分解并映射到某个集群资源内的计算结点上。本文的m e s p p e a 具 体应用中，通过求解区域和子空间分解，基于趋同和异化进行演化操作。并行演 化计算的各子群体存在较大的相似性，只需对其中的最优子群体进行并行化以提 高计算效率。 二级并行计算模型有利于简化算法并行化的难度。在网格环境下，细粒度并 行化已经不符合网格架构的要求。目前所述的各种并行编程模型都是基于传统的 并行机，没有针对网格这个特殊的环境给出一个良好的编程模型。因此在网格环 境下提出二级并行计算模型，探索新的求解模型将是非常具有意义的；第二点， 提供对自适应计算能力的支持。通常在网格环境下，对于某个特定问题所需的资 源并不是总能满足的。如果不从程序一级提供对自适应计算能力的支持，将极大 的浪费网格的资源，降低网格的利用率。若程序提供对自适应计算能力的支持， 充分利用网格系统中的所有空闲资源，直到满足该应用所需的所有资源。充分利 用网格系统的所有空闲资源，使应用程序提前进入运行队列，节省计算时间，提 高了网格的利用率，提高了网格的服务质量。 9 上海大学硕七学位论文 旦! 堕! ! 旦里! ! 坐堡竺! 竺墅璺塑坐! ：墅堕 2 2 演化计算 ( 1 ) 演化计算简介 演化算法( e v o l u t i o n a r ya l g o r i t h m s 。简称e a s ) 是基于生物进化原理的普 适性全局优化算法。它采用简单的编码技术来表示各种复杂的结构，并通过对一 组编码表示进行简单的遗传操作和优胜劣汰的自然选择来指导学习和确定搜索 的方向1 3 l 。演化计算具有自组织、自适应、自学习的特征；同时，优胜劣汰的 自然选择和简单的遗传操作使它具有不受其搜索空间限制性条件( 如连续、可微) 的约束及不需要其它辅助信息( 如导数) 的优点，因而越来越受到人们的重视。 演化算法模拟生物进化过程与遗传变异机制来求解问题。首先，必须将优化 变量x = ( ，屯，毛) 7 对应到某生物种群的个体，并指定相应个体的适应度。 定义2 1 ( 遗传编码) 一个具有性质2 1 的字符串q 呸吒称为是优化变量x 的 一个遗传编码 a = q a 2 q lj x = “，而，而) 7 ，( 2 1 ) 三称为x 的编码长度，a = a t a 2 吼称为x 的编码，记为d 脚，而x 称为 字符串a 的解码，记为x = e - 1 ( 。 依生物学术语，把每一q 看作是一个遗传基因，它的所有可能取值( 即q 的 取值范围) 称为等位基因，则彳= 西的可认为是由个基因所组成的一个染色体， 或者说是一个个体。 定义2 2 ( 个体空间与种群空间) 设r 表示等位基因，三为给定的编码长度， 集合既= 臼= q 屹吼 a i e f ，i = 1 ，2 ，工) 称为是个体空间。对任何正整数t - n ，乘积 h t = hl x h lx x h 。 l 1 f 一 称为是m 阶种群空间；2 阶种群空间研称为是母体空间。月l 中的任一元 素称为个体，日z 中的元素称为m 阶种群，磁中的元素称为一对母体。 对每一个个体爿，演化算法按照定规则指定其相应的适应度。通常，适应 上海大学硕十学位论文 里! ! 坚巴塑堡旦竺! ! ! ! ! ! 塑坚i 坐! 兰竺生 度确定规则应使个体的适应度与其对应的个体表现型j 的目标函数值砷相关 联，石越接近于目标函数的全局极大值点，其适应度越大；反之，其适应度越 小。这样的适应度指定规则通常可由下述定义2 3 所定义的适应值函数产生。 定义2 3 ( 适应值函数) 设瞄表示正实数集。一个映射f ：i ) - - - r o + 称为是演化算 法求解问题的一个适应值函数，如果f 与，有相同的全局最大值点，且满足： 厂( 五) 2 f ( x 2 ) 0 j f ( x 1 ) 2 ，( 义：) 有了上述的定义，我们可建立演化算法的一般框架： 演化算法的一般过程如下： s t e p i ：( 初始化) 确定种群规模及终止准则( 如设置最大进化代数或所期 望达到的近似解精度) ；随机生成个个体作为初始种群x ( o ) ；置进化代数计 数器f 卜o 。 s t e p 2 ：( 个体评价) 计算种群j ( f ) 中每一个个体的适应度。 s t e p 3 ：( 种群进化) 3 1 ( 选择) 将选择算子作用于种群膏( f ) 。 3 2 ( 繁殖) 将繁殖算子作用于选择后的种群，并生成下一代种群量( f + 1 ) 。 s t e p 4 ：( 终止检验) 如果贾o + 1 ) 满足终止准则，则输出j p + 1 ) 中具有最大适 应度的个体作为最优解，终止计算；否则置t 么，则称b 为优秀 子群体。 定义2 8 设子种群空间为尸= 嘏，昱9 o o ，只) ，只为第f 个子群体，互为第i 个 子群体最优个体的适应度，t 为子种群数量。若巧 = 么，则称0 为替换 ，j j 子群体。 由于演化计算存在若干缺点，本文将思维进化计算的趋同和异化思想引入到 演化计算中，构造思维进化与空间分解并行演化算法( m i n de v o l u t i o na n ds p a c e d e c o m p o s i t i o nb a s e dp a r a l l e le v o l u t i o n a r ya l g o d t l u n ，简称m e s p p e a ) 。按照二级 并行计算模型，第一级并行化需要将各个子群体分别映射到各计算资源。演化计 算迭代一段时间后，各个子群体之间存在一定的相似性，在m e s p p e a 并行框 架中，只对当前的全局最优个体采用可分解可拼接编码模式进行第二级并行化， 在第一级并行化的基础上进一步向目标迈进。 m e s p p e a 算法框架描述如下： s t e p l ：假定子群体规模为r a ，处理器个数为, 1 ；确定整体广告板( 记录每代种 群中各子种群的优胜个体信息) 和局部广告板( 记录每个子种群的演化信息) ； s t e p 2 ：检查当前文件目录下是否存在中间文件，若存在从对应文件中读取保 存的整体广告板和局部