（计算机应用技术专业论文）退火进化算法在网格任务调度中的应用和研究.pdf

摘要 i i ii i1 11 11 1 i iir1 11iri 18 912 2 5 网格是一个集成的计算与资源环境，能够吸纳各种计算资源并将它们转化成 一种随处可得的、可靠的、标准的、经济的计算能力。网格计算适用于大型的 科学计算和项目研究，已成为继传统因特网、w e b 之后的第三次互联网浪潮，在 世界许多国家和地区得到了实际应用，在科学研究、信息共享、应用程序整合 等方面发挥着极大的作用。 任务调度问题则是网格研究和应用必须解决的一个关键问题。任务调度的目 标就是要对用户提交的任务实现最优调度，并设法提高网格系统的总体吞吐率。 网格计算的任务调度是一个n p 完全问题。近年来，人们提出了很多肩发性智能 化算法，诸如神经网络、模拟退火、禁忌搜索、遗传算法、蚂蚁算法等，它们 成为解决n p 问题及任务调度问题的有效工具。 退火进化算法是将遗传算法和模拟退火算法进行优化并混合的一种算法，它 即利用遗传算法具有较强的对全局把握能力，同时利用模拟退火算法的较强局 部搜索能力对遗传算法的种群进行概率性接受，一定程度上避免遗传算法“早 熟 的产生。 本文的工作主要是在对传统的遗传算法和模拟退火算法进行阐述，在分析传 统遗传算法和模拟退火算法的优点和不足后，对原有算法进行了优化；基于遗 传算法和模拟退火算法的开放性，对两种算法进行有机混合，并提出了基于d a g ( d i r e c t e da c y c l i cg r a p h ) 图约束关系的任务调度退火进化算法a e a ( a n n e a l i n ge v o l u t i o na l g o r i t h m ) 算法。然后将a e a 应用于具体的任务调度问 题，针对任务调度问题的具体情况设计出相应的算法，并最后予以实现。 关键字：网格计算；任务调度；退火进化；d a g 图 a b s t r a c t g r i di sa ni n t e g r a t e dc o m p u t i n ga n dr e s o l l r c e $ e n v i r o n m e n t i ti sa b l et oa b s o r b v a r i e t yo fc o m p u t i n gr e s o u r c e s ，a n dc o n v e r tt h e mi n t oaw i d e l y , a v a i l a b l e ，r e l i a b l e ， s t a n d a r de c o n o m i cc o m p u t i n gp o w e r g r i dc o m p u t i n gi se x t e n s i v e l ya p p l i e do nl a r g e s c i e n t i f i cc o m p u t a t i o na n dr e s e a r c hp r o j e c t s ，b e c o m et h et r a d i t i o n a li n t e m e ta n dt h e t h i r dw e bi n t e m e tw a v ei nt h ew o r l d ，g r i dc o m p u t i n gh a sb e e na p p l i e di nm a n y c o u n t r i e sa n dr e g i o n , a n dp l a y e das i g n i f i c a n tr o l ei ns c i e n t i f i cr c s c a r c l 1 ，i n f o r m a t i o n s h a r i n g ，a p p l i c a t i o nc o n f o r m i t ya n ds oo n g r i dt a s ks c h e d u l i n gp r o b l e mi st h er e s e a r c ha n da p p l i c a t i o no fak e yi s s u et h a t m u s tb ea d d r e s s e d s c h e d u l i n gg o a li st os u b m i tt h et a s kt h eu s e ro p t i m a ls c h e d u l i n g ， a n dt r yt oi m p r o v et h eo v e r a l lt h r o u g h p u to f t h eg r i ds y s t e m t a s ks c h e d u l i n go fg r i d c o m p u t i n g i sa l ln pc o m p l e t ep r o b l e m i nr e c e n ty e a r s ，p e o p l em a d eal o to fi n s p i r i n gi n t e l l i g e n ta l g o r i t h m ss u c ha , s n e u r a ln e t w o r k s ，s i m u l a t e da n n e a l i n g ，t a b o os e a r c h , g e n e t i ca l g o r i t h m ，a n ta l g o r i t h m , w h i c ha r ef i r m l ye s t a b l i s h e da ss h a r pt o o l so nn pp r o b l e ma n dt a s ks c h e d u l i n g a n n e a l i n ge v o l u t i o n a r ya l g o r i t h mi s am e t h o do p t i m i z a t i o na n dh y b r i dt h e g e n e t i ca l g o r i t h ma n ds i m u l a t e da n n e a l i n ga l g o r i t h m ；i ti st h eg e n e t i ca l g o r i t h mh a sa s t r o n gg r a s po ft h eo v e r a l lc a p a c i t y , b u ta l s ot h ea l g o r i t h mu s i n gs i m u l a t e da n n e a l i n g l o c a ls e a r c ha b i l i t yo fs t r o n g e rp o p u l a t i o n so fg e n e t i ca l g o r i t h mt h ep r o b a b i l i t yo f a c c e p t a n c e ，t oa v o i dt h em a t u r ep r o b l e mo fg e n e t i ea l g o r i t h m t h em a i no ft h i sp a p e ri sr e f l e c t e di nt h et r a d i t i o n a lg e n e t i ca l g o r i t h ma n d s i m u l a t e da n n e a l i n ga l g o r i t h md e s c r i b e di nt h ea n a l y s i so ft h et r a d i t i o n a lg e n e t i c a l g o r i t h ma n ds i m u l a t e da n n e a l i n ga l g o r i t h m ，a f t e ra n a l y z et h ea d v a n t a g e sa n d d i s a d v a n t a g e so ft h eo r i g i n a la l g o r i t h mo p t i m i z a t i o n ；b a s e do no p e no fg e n e t i c a l g o r i t h m sa n ds i m u l a t e da n n e a l i n g ，o r g a n i cm i xo f t h et w o a l g o r i t h m s ，a n dp r o p o s e d a n n e a l i n ge v o l u t i o n a r ya l g o r i t h m t h e nw i l lt h eu s e di n t h ep r a c t i c a la e at a s k s c h e d u l i n gp r o b l e m ，a c c o r d i n gt ot h es p e c i f i cc i r c u m s t a n c e so ft h et a s ks c h e d u l i n g p r o b l e m ，a n dt h ec o r r e s p o n d i n ga l g o r i t h md e s i g na n df i n a l l yt oa c h i e v e k e yw o r d s ：g r i dc o m p u t i n g ；t a s ks c h e d u l i n g ；a n n e a l i n ge v o l u t i o n ；d a gg r a p 目录 l 绑 论1 1 1 研究背景i 1 2 国内外研究现状2 1 3 研究内容及相关工作3 1 4 论文结构安排4 2 相关理论知识及技术5 2 1 网格计算相关简介5 2 1 1 网格计算的基本概念5 2 1 2 网格计算的基本原理6 2 1 3 网格计算的体系结构7 2 1 4 网格计算的特点8 2 1 5 网格计算的应用与发展现状8 2 2 任务调度简介9 2 2 1 任务调度的基本概念9 2 2 2 任务调度的主要目标1 0 2 2 3 常见任务调度类型1 1 2 3 d a g 调度1 2 2 3 1 经典的d a g 调度1 3 2 3 2 扩展的d a g 调度模型及算法1 4 2 3 3 国内关于d a g 调度的研究l5 2 4 软计算及相关算法。1 6 2 4 1 软计算概述16 2 4 2 遗传算法l6 2 4 3 模拟退火算法。1 9 3 退火进化算法2 l 3 1 退火进化算法简介。2 l l 3 2 退火进化算法流程2 l 3 2 1种群初始化。2 3 3 2 2 染色体交叉一2 3 3 2 3 染色体变异。：2 4 3 2 a 染色体的退火接受。2 5 3 2 5 染色体选择一2 5 3 3 退火进化算法收敛性讨论2 6 4 网格环境下任务调度设计2 7 4 1 基于d a g 图的染色体编码设计2 7 4 1 1基于d a g 图任务调度描述2 7 4 1 2 基于d a g 图任务调度建模2 7 4 1 3 染色体编码设计2 8 4 2 基于d a g 图的适应度函数设计3 0 4 2 1e t c 矩阵3 0 4 2 2 个体权重值。3 0 4 2 3 任务总执行时间3l 4 2 4适应度函数3 2 4 3 染色体s a 接受算法描述3 3 5 网格环境下任务调度实现。3 4 5 1 基于n e t f r a m e w o r k 4 0 的模块设计3 4 5 1 1 染色体基因类。3 5 5 1 2 人工智能类3 6 5 1 - 3 退火进化算法类3 7 5 1 4 染色体交叉变异类3 8 5 1 5 调度类3 9 5 2 算法测试与结论4 l 5 2 1 算法参数的设置4 l 5 2 2 仿真对比实验4 l 6 总结与展望4 4 6 1 工作总结。4 4 6 2 展望未来。4 4 参考文献4 5 致谢4 9 个人简历5 0 l 第一章绪论 1 绪论 1 1 研究背景 现代科学的研究步骤一般由观察、理论、实验和数值模拟来验证，随着计算机技术的 发展，数值模拟手段已经越来越受到各个领域科学家的青睐。但是，许多重要科学问题的 数值模拟非常复杂，需要高性能计算机或多计算机系统如m p p 、s m p 、集群或计算网格才 能求解。这些复杂得问题常被视为对科学的巨大挑战。这些挑战性问题涉及到以下领域： 量子力学，统计力学，相对论物理 宇宙学和天文物理 计算流体力学和湍流 材料设计和超导性 生物学、药理学、基因序列、遗传工程、蛋白质结构、酶活动和细胞建模 药物研制，人体器官和骨骼建模 全球气候和环境模拟 以分子动力学为例。模拟蛋白质和它周围水分子之间一微微秒的交互作用大约需要 g r a y x m p - - d , 时的时间。而有意义的实际物理过程几乎要经历一秒钟。在同样的机器上使 用同样的算法模拟这样的物理过程，将需要3 1 6 8 8 年【l 】。 以工作站机群为代表的并行计算模式无疑是并行分布式计算的重点研究领域，同时， 随着网络互联技术的发展，并行计算环境也从局域网范畴向广域网范畴拓展，在机群计算 的基础上出现了新的基于因特网的并行分布式计算模式即网格计算。网格计算最早在参照 电力系统的模型来解决海量计算问题时被提出，后来逐渐发展成基于i n t e m e t 的针对新型 复杂计算的模式，而后广泛地引用于科研项目和商业应用中。它已成为继传统因特网、w e b 之后的第三次互联网浪潮，在世界许多国家和地区得到了实际应用，在科学研究、信息共 享、应用程序整合等方面发挥着极大的作用 2 - 3 。 1 9 9 9 年5 月1 7 日，一项由美国加州大学伯克利分校开展的寻找地外生命迹象的科学 项目_ s e t l h o m e 启动了，s e t l h o m e 是s e a r c h f o re x l r at e r r e s t r i a li n t e l l i g e n c ea th o m e 的缩写，意为：在家里寻找外星文明。s e t i h o m e 项目主要是利用联网p c 的闲置能力分 析世界上最大的射电望远镜获得的数据，以帮助科学家探索外星生物，其计算模式的实质 就是网格计算。 从s e t i h o m e 项目启动正式启动以来，已经有3 0 0 万志愿者参加了这个项目，他们 从指定的站点下载射电望远镜收集的信息的片段，用自己的计算机运行分析，从中寻找宇 宙中生命的迹象，总处理数据量达到了1 5 t ，平均每位参与者让自己的电脑为s e t i h o m e 南京信息工程大学硕士学位论文 工作了1 7 个半小时，这相当于使用一台p c 机工作4 8 2 0 2 3 年，相当于使用超级计算机工 作4 8 年。这个项目充分利用了分布在世界各地计算机的力量，虽然整个计划耗资只有5 0 万美元，却拥有强大的威力。 无论在机群计算还是网格计算的实现中，如何对并行作业的任务进行调度是影响整个 系统成败和性能的关键因素，因而研究多处理器或多计算机的任务调度算法对于机群计算 和网格计算都具有十分重要的理论和实际意义。现已证明网格环境下的任务调度是一个n p 完全问趔训。 国际数学界研究n p 问题的历史开始于2 0 世纪7 0 年代。1 9 7 1 年，c o o k 找到第一个 n p 完全问题，寻求标准布尔方程解的为问题( s 问题) ，开创了n p 完全问题研究的历史。 到目前为止，大约有几千个问题已被证明是n p 完全问题。由于大量的n p 完全问题至今 没有找到有效算法，而指数型算法对解决规模较大的问题又十分困难，以求近似最优解为 目的的启发性算法自然受到了极大的重视【5 】。 近年来，人们提出了很多启发性智能算法，例如神经网络、模拟退火、禁忌搜索、遗 传算法、蚂蚁算法等，它们毫无争议地成为解决n p 问题及任务调度问题的锐利工具1 6 。 1 2 国内外研究现状 早在2 0 世纪4 0 年代，有学者开始通过计算机对生物的整个进化过程进行模拟，遗传 算法正起源于对生物技术的计算机模拟技术。遗传算法的概念最早是由b 嘲e y 在1 9 6 7 年 提出的，大量的关于遗传算法的理论和概念是在1 9 7 5 年由m i c h i g a n 大学的h o l l a n d 教授 提出的【7 1 。当时其主要目的是说明自然系统与人工系统的自适应过程嗍。h o l l a n d 教授研究 生物进化过程后提出了一种模拟自然界生物和进化的系统优化算法遗传算法。 以下是遗传算法发展的几个重要阶段及他们的提出者： h o l l a n dh ：2 0 年代6 0 世纪，h o l l a n d 通过研究自然界的生物遗传和进化现象及自然 界和人工系统的生成及它们与环境的关系，提出在系统优化问题上可以借鉴自然界生物遗 传的机制。7 0 年代初，h o l l a n d 教授提出了遗传算法的基本定理模式定理，奠定了遗 传算法的理论基础。8 0 年代，h o l l a n d 教授实现了第一个基于遗传算法的机器学习系统 分类器系统，开创了基于遗传算法的机器学习新概念，为分类器熊构造了一个完整的框架 嗍。 b 喇e yjd ：1 9 6 7 年h o l l a n d 教授的学生b a g l e y 在其博士论文中提出了“遗传算法” 一词，并发表了遗传算法应用方面的第一篇论文。他发展了复制、交叉、变异、显性、倒 位等遗传算子1 9 1 。 2 第一章绪论 d ej o n gka ：1 9 7 5 年d ej o n g 博士在其博士论文中结合模式定理进行了大量纯数值 函数优化计算实验，树立了遗传算法的工作框架，得到了一些重要而且有指导意义的结论 唧。 g o l d b e r gdj ：1 9 8 9 年，g o i d b e r g 出版了专著g e n e t i ca l g o r i t h m si ns e a r c h ， o p t i m i z a t i o na n dm a c h i n el e 撕n g ，该书系统总结了遗传算法的主要研究成果，全面而完整 论述了遗传算法的基本原理及应用唧。 模拟退火是一种全局优化方法，就是人为地引入噪声，使得当某算法陷入局部最优的 陷阱时，造成从该陷阱中逃脱的条件，再逐步减小噪声，以使得算法能停留在全局最优点。 其实，早在1 9 6 5 年，k h a s 就提出了这一想法，不过并未受到计算机科学与优化应用领域 的足够重视。直到1 9 8 3 年，k i r k p a t r i c k 提出模拟退火算法，才引起了优化应用领域的重视， 成为热点流行起来【l o l 。 由于遗传算法和模拟退火算法开放式的结构，以及与问题关联性较小的特性，很容易 互相混合或与其他算法混合，目前对遗传算法和模拟退火算法的研究主要集中在将算法组 合，以提高算法效率和收敛速度。 以下是几种常见的混合算法： 1 免疫遗传算法：人工免疫算法受生物免疫系统原理的启发，针对求解问题特征进行 人工疫苗接种，可充分利用问题本身的信息，和遗传算法结合时遗传算法的全局搜索能力 及免疫算法的局部优化相配合可大大提高搜索效犁1 1 l 。 2 小生境遗传算法：生物学上小生境指在特定环境中的一种组织功能，将每一代个体 划分为若干类，每个类中选出若干适应度较大的个体作为一个类的优秀代表，组成一个新 种群，再在同一种群中以及不同种群之间进行杂交、变异产生新一代个体群，同时采用预 选择机制或排挤机制或共享机制完成选择操作1 2 】。 3 混沌遗传算法：混沌是自然界广泛存在的一种非线性现象，它充分体现了系统的复 杂性。混沌运动具有类似随机变量的杂乱表现，具有随机性；初值条件极其微弱的变化会 引起混沌系统行为的巨大变化，具有对初始条件的极度敏感性。混沌运动的上述性质作为 避免陷入局部极小的优化搜索机制，恰好可以弥补遗传算法易陷入局部最优和收敛速度慢 的缺陷。可以利用混沌的遍历性产生初始种群，也可以运用混沌的遍历性对优良个体进行 变异操作，混沌遗传算法增强了遗传算法的全局寻优能力唧。 随着国内外对遗传算法和其他智能启发式算法的不断深入研究，现有的算法会得到改 进，更多的智能启发式算法以及理论也将会被提出。 1 3 研究内容及相关工作 3 南京信息：【程大学硕士学位论文 本文首先介绍了网格计算研究现状，分析了基于d a g 图的任务调度现状，然后对传 统的遗传算法和模拟退火算法的原理和一般流程进行了阐述，分析了遗传算法和模拟退火 算法并进行混合优化，设计了基于d a g 约束关系的任务调度退火进化算法。最后依据算 法的设计在开发平台上编码实现，通过多次实验结果验证了退火进化算法的可行性和优势。 本文针对网格计算中任务调度这个核心问题，研究了基于d a g 图的任务调度算法， 提出了一种用于解决d a g 任务调度的遗传退火算法，算法在很多地方作了改进： 编码方式的改进，将任务调度次序与任务在资源上的分配分别编码组合，使得搜索 空间扩大，避免遗漏可行解。 算法初始种群的格式化，对不符合调度约束条件的个体格式化，使得每个个体都具 有实际意义。 染色体交叉过程中充分展现自然种群进化中的随机性，染色体基因位随机，交叉基 因数随机。 避免陷入局部最优，对最优染色体个体利用退火算法迭代产生新个体加入到下一代 种群中，保证了种群的多样性。 可视化操作界面为调整算法参数带来方便。 1 4 论文结构安排 本文主要分为六章，每章的内容安排如下： 第一章介绍了本文相关研究背景，国内外研究现状和论文研究内容和意义。 第二章对网格计算、d a g 任务调度及软计算进行了简介，阐述了软计算中传统遗传算 法和传统模拟退火算法的一般流程，并分析了传统算法中存在的不足。 第三章针对传统算法进行优化，并阐述了整个算法流程，提出了基于d a g 图的任务 调度退火进化算法a e a 算法。 第四章对网格环境下基于d a g 图的任务调度进行描述，针对任务调度的特点重点设 计了编码方式，以及适应度求解依据，给出适应度函数，对优异个体的退火接受给出了伪 代码描述。 第五章在前三章的理论基础上对算法进行编程实现，描述了算法运行中涉及到的主要 对象，对关键类的描述给出了类图和该类字段、属性以及方法的介绍，关键算法处给出具 体代码。之后利用开发出的系统对算法进行验证给出实验结果图和结论。 第六章对论文所作工作进行总结，并阐述了论文后续工作，对算法的相关前景进行展 望。 4 第一章相关理论知识及技术 2 相关理论知识及技术 2 1 网格计算相关简介 2 1 1 网格计算的基本概念 网格是一个集成的计算与资源环境，能够吸纳各种计算资源，并将它们转化成一种随 处可得的、可靠的、标准的经济的计算能力。 网格计算起源于科学计算中的分布式高性能计算，主要目的在于聚合基于因特网的计 算资源，解决大规模应用的计算问题。它利用互联网技术，将分布在不同地理位置的计算 资源包括c p u 、存储器数据库等，通过高速的互联网组成充分共享的资源集成，使分散在 不同地理位置的计算机组成一台虚拟超级计算机，每一台参与的计算机就是其中的一个节 点”，所有的计算机就组成了一张节点网即网格。虽然单台计算机的运算能力有限，但成千 上万台计算机组合起来的计算能力就足以和超级计算机相比了。 网格计算主要研究如何把一个需要非常巨大的计算能力才能解决的问题分成许多小的 部分，然后把这些部分分配给多台计算机进行处理，最后把这些计算结果综合起来得到最 终结果。网格计算与传统分布式计算的主要区别是在没有集中控制机制的情况下，实现计 算资源、高级仪器资源、数据资源、信息资源、知识资源乃至专家资源的全面共享，并且 这种对计算资源进行大规模共享是动态的、柔性的、安全的和协作式的。 网格是高性能计算机、数据源、因特网三种技术的有机组合和发展，它与因特网相比 具有高性能、知识生产、一体化、资源共享等技术优点【1 3 】。图2 1 显示了一个分布式的网 格。 5 南京信息工程大学硕士学位论文 第二章栩关理论知识及技术 ，、 资源索引 同格信息服务g i s 3 釜 卜一- 一任务调度 资源 毒 控制 管理 x 卜_ _ - 1资源管理 1 嗯l 任务执行k 网格计算中间件 图2 - 2 网格计算的工作原理 网格计算节点可以是高性能的服务器、集群、多个机器组成的网络，也可以是工作站 或其他仪器设备。各计算节点向网格信息服务( g i s ：g r i di n f o r m a t i o ns e r v e r ) 注册，发布 各自节点的资源信息。各网格计算节点上的本地资源管理器负责管理本地资源。并与网格 中间件中的资源管理器协商资源的使用，本地任务管理器负责管理予任务在本地的执行。 网格用户通过网格计算中间件提交任务，获得网格计算服务。网格计算中间件由任务控制 管理、资源索引、资源管理、任务调度器、任务执行器等组成【1 4 】。 典型的网格计算执行过程为：任务控制管理组件负责网格计算与用户之间的交互，将 用户任务提交给任务调度器；任务调度器将用户任务分解成一系列的子任务，并将任务描 述转换成资源需求信息，并通过资源定位从网格信息服务g i s 中获得合适资源的具体信息， 并通过资源管理组件与资源节点进行协商获得资源，然后通过任务管理将各子任务及对应 的资源信息交给任务执行器；任务执行器根据资源协商的情况将各个子任务部署到相应的 资源上执行并对管理任务的执行，收集任务执行的结果并通过任务控制管理传递给用户 【1 4 】i 。 2 1 3 网格计算的体系结构 五层沙漏结构是由伊安福斯特等提出的一种具有代表性的网格体系结构。在基于“沙 漏模型”的网格体系结构中，沙漏的狭窄部分( 颈) 定义了一个核心的抽象和协议( 如t c p 和l _ 1 1 v r p ) 的小集合，不同的高层行为( 沙漏的顶部) 可以影射到这个小集合上面来，它 7 南京信息工程大学硕：i 二学位论文 们本身可以影射到不同的底层技术( 沙漏的底部) 上。从体系结构的定义来看，在沙漏颈 部定义的协议的数量一定要小。在这个结构中，沙漏的颈部由资源和连接协议构成，它们 使得对单个资源的共享变得更加便利。在这些层次上定义的协议应当设计成可以在基础结 构层定义的不同资源类型上实现。这些协议反过来用于构造集合( 服务) 层的大范围全局 服务和应用特定行为垆j 。 五层沙漏结构因为简单而影响广泛，它以协议为中心强调服务、a p i 与s d k 的重要性。 其示意图如下： 一朗 应用层 僦 汇聚层 、 f 资源层 资源与服务 的安全访问 与连接层 隶 构造层 图2 3 五层沙漏结构示意图 2 1 4 网格计算的特点 从工作原理可知，网格计算是将网络虚拟成一个“超级计算机”为用户提供服务，需 要对大量的、异构的、广域分布的网络资源进行整合，实现资源共享和任务协作。由于网 格计算是网络环境下多个节点参与的计算模式，因此它主要有以下特点： 网格系统是由分布在地理位置互不相同的资源组成的；网格上的任何资源都可以提供 给网格上的使用者使用，所以，分布与共享是它的第一个特点；而网格的局部具有全局的 某些特征，全局也体现者局部的特征，局部和整体之问存在着一定的相似性：同时，受网 格资源异构和多样的制约，随着时间的推移，网格资源会动态地增加或动态地减少，具有 动态性与多样性；网格的资源既受到网格的统一管理，也允许资源的拥有者对该资源有自 主的管理能力，且管理权限高于网格管理，使得网格具备了自治性与管理的多重性。 2 1 5 网格计算的应用与发展现状 8 第二章相关理论知识及技术 网格计算的思想自2 0 世纪6 0 年代就已经提出，但到9 0 年代以后才开始真正的发展。 上世纪9 0 年代初，针对网络上主机数量增加但利用率不高的情况，美国国家科学基金会 ( n f s ) 将4 个超级计算中心构建成一个能够进行元计算( m e t ac o m p u t i n g ) 的整体，为 重大科研领域的研究提供计算资源，解决科学与工程计算问题，此后相关的项目有i - w a y 和f a f n e r 。9 0 年代中期，网格计算研究内容主要关注网格计算的中间件研究与开发，以 解决不同节点和资源有效共享和协同工作的问题，2 0 0 0 年后。网格计算关注的是在动态、 多机构的虚拟组织中协调资源共享和协同解决问题，提出了开放网格服务结构( o g s a - o p e ng r i ds e r v i c ea r c h i t e c t u r e ) ，并逐步与w e b 服务相结合，支持x m l 、s o a p u d d i 等标 准，形成w e b 服务资源框架w s r f ( w e bs e r v i c er e s o u r c ef r a m e w o r k ) 1 1 6 j 。 国际网格技术的激烈竞争与迅猛发展，运用具有超强的计算能力的计算机来完成构建 全球网格的前景几乎是无法抗拒的，据专家预测网格计算作为信息产业的新热点，将是近 期内解决数据量极大的科学工程计算问题最直接和最有效的途径。随着网格计算技术的进 一步发展以及服务提供商的共同努力，网格计算将会应用于更广阔的领域及行业，网格计 算的发展势必成为互联网的又一次革命，对计算机网格技术的应用及其他产业的发展将产 生深远的影响 3 】。虽然全面的网格计算还距离很远，并且对于基础设施及服务的可靠性和 安全性要求也比较苛刻，但是，网格计算是一个崭新而重要的研究领域，它以资源共享、 高性能计算和创新性应用为主要特征，必将成为2 l 世纪社会、经济、科学、人文发展的重 要推动力。 2 2 任务调度简介 2 2 1 任务调度的基本概念 网格计算是近年来信息技术领域的热点研究课题，是支撑未来各类应用的国家信息基 础设施，而任务调度问题则是网格研究和应用必须解决的一个关键问题。网格计算任务调 度有以下特点： 网格中的资源不但是异构的而且网格的结构总是不停地改变，任务调度能够动态地自 适应：必须以分布、并行方式进行任务的管理与调度；任务调度是面向异构平台的；任务 调度不干涉各网格节点内部的调度策略；网格系统初期的计算规模较小，随着超级计算机 系统的不断加入系统的计算规模也必将随之扩大，因此，任务调度必须具有可扩展性。 通常，一个应用在网格平台的调度过程包括应用程序分析和分解、资源发现和选择、 任务调度、任务执行等几个方面。如图2 _ 4 所示。 9 南京信息工程大学硕士学位论文 图2 - 4 网格系统f 的任务调厦 应用分析与分解部分主要完成应用程序特征分析并将应用程序分解为一系列任务。应 用程序特征包括应用是否可以分解、分解得到的任务之间是否存在依赖关系、任务执行时 间估计等：应用分解根据应用特征将应用程序分解为若干个任务。资源建模部分主要完成资 源特性分析，资源特征主要包括处理机的系统结构、指令类型、存储容量、操作系统、计 算速度、负载情况，以及互连网络的通信速度、拓扑结构、路由机制、流控机制等。任务 调度部分将根据任务模型、资源模型和调度目标进行资源选择、分配任务到处理机并安排 任务在处理机上的执行时间【习。 在网格计算中，任务调度的实质就是将n 个相互独立的任务分配到m 个异构可用资源 上，使得总任务的完成时间最小以及资源得到充分利用。近年来，人们提出了很多启发性 智能化算法，诸如神经网络、模拟退火、禁忌搜索、遗传算法、蚂蚁算法等，它们毫无争 议地成为解决n p 问题及髑p 问题的锐利工具1 6 。 2 2 2 任务调度的主要目标 简单地说，网格计算任务调度的目标就是要对用户提交的任务实现最优调度，并设法 提高网格系统的总体吞吐率。网格( g r i d ) 是近年来信息技术领域的热点研究课题，是支撑未 来各类应用的新的国家信息基础设施( n a t i o n a li n f o r m a t i o ni n f r a s t r u c t u r e ) 。由于网格的核 心是资源共享，而任务调度直接决定了资源的有效利用，因此它就成为网格计算最重要和 最关键的问题之一。 具体的目标包括：最优跨度( o p t i m a lm a k e s p a n ) 、服务质量q o s ( q u a l i t yo fs e r v i c e ) 、负 载均衡( l o a db a l a n c i n g ) 、经济原则等。 最优跨度。跨度是一个最主要、最常见的目标，指的是调度的长度，也就是从第一个 任务开始运行到最后一个任务运行完毕所经历的时问。跨度越短，说明调度策略越好。当 l o 第二章相关理论知识及技术 用户向网格系统提交任务后，最大的愿望是网格系统尽快完成自己的任务。可见，实现最优跨 度是用户和网格系统的共同目标l l 酗。 服务质量q o s 。网格系统要为用户提供计算和存储服务时，用户对资源需求情况是通 过q o s 形式反映出来的。任务管理与调度系统在进行分配调度任务时，保障网格应用的q o s 是完全应当的【阍。 负载均衡。在开发并行和分布计算应用时，负载平衡是一个关键问题。网格系统更进 一步扩展了这个问题。网格任务调度是涉及交叉域和大规模应用的调度。解决好系统的负 载均衡是一个非常重要的问趔1 6 1 。 经济原则。网格环境中的资源在地理上是广泛分布的，而且每个资源都归属于不同的 组织，都有各自的资源管理机制和政策。根据现实生活中的市场经济原则，不同资源的使 用费用也应是不相同的。市场经济驱动的资源管理与任务调度必须使消费双方( 资源使用者 和资源提供者) 互惠互利，才能使网格系统长久地发展下去【1 6 1 。 2 2 3 常见任务调度类型 网格计算任务调度就是将用户提交的任务分配到可用的计算机系统资源上，并协调任 务在资源上执行顺序的过程。 基于a g e n t 的任务调度：a g e n t 技术源自于人工智能，其概念在6 0 年代就已提出来， 真正的发展在9 0 年代，现在正向计算机领域的各方面渗透面向a g e n t 技术是面向对象技术 的发展和飞跃，面向a g e n t 的软件开发方法是为了更确切地描述复杂的并发系统的行为而 采用的一种抽象描述形式，与面向对象技术一样，它是观察客观世界及解决问题的一种方 法。a g e n t 技术为复杂、开放、分布系统的开发和实现提供了新途径。面向a g e n t 技术的 智能性、代理性、学习性、合作性、持续性使它非常适合网格计算及其任务调度的实现。 基于a g e n t 的任务调度其基本设计思想是：将每个网格资源节点均封装成为一个a g e n t ，把 网格系统看成是一种多层次a g e n t 系统的集合。这样，所有分布于网格系统中不同地方的 网格资源节点( 如一个机群) 就构成了底层的a g e n t 系统，它们为基于网格的应用程序提供 高性能计算能力，于是，调度问题被简化成如何在各a g e n t 之间分配计算任务并随时根据 a g e n t 的变化情况进行调整，以及在各a g e n t 内如何进行子任务的继续分配。这样的层次 结构具有高度的可扩展性，便于在网格这样的庞大异构环境中运用【1 7 】。 基于p e t r i 网的任务调度模型：p e t r i 网理论是由德国的c a r l a d a mp e t r i 博士提出的， 主要研究分布式系统中并发、冲突现象的一种理论，它是描述和分析离散事件动态系统的 一种模型工具。它综合了数据流、控制流和状态转移，能自然地描述并发、同步、资源争 用等系统特性，而且本身自含执行控制机制，集规范表示与执行于同一模型。同时，p e t r i 南京信息j = 程大学硕士学位论文 网是严格定义的数学对象，借助数学开发的p e t r i 网分析方法和技术，既可用于静态的结构 分析，又可用于动态的行为分析瑚。 基于成本的任务调度：文献【1 0 】在经济原则的基础上为调度问题引入成本概念。其核 心思想是把诸如c p u 、存储器、带宽等不同类型资源的使用情况都转变成单一的成本，并 第二章相关理论知识及技术 2 3 1 经典的d a g 调度 在经典的d a g 调度模型中，处理器网络是全互联的，并且不考虑对通信资源的争用。 尽管对目标系统进行了高度简化，但在一般情况下经典的d a g 调度问题仍是n p 完全的， 因此主要依靠启发式算法求解。这些算法基于不同的调度策略，大致可以分为三类：列表 调度算法( l i s ts c h e d u l i n g ) ，聚簇算法( c l u s t e rs c h e d u l i n g ) 和基于任务复制的算法( t d b ， t a s kd u p l i c a t i o nb a s e ds c h e d u l i n g ) 。 列表调度算法是在由固定数量的处理器构成的网格上调度d a g 的算法。列表调度反 复执行以下三步直到所有节点都被调度： 1 为所有未调度节点确定新的优先级； 2 选择有最高优先级的节点进行调度； 3 将这个节点分配到能给出最小启动时间的处理器。 某些早期的算法在整个调度过程中仅在初始时执行一次第一步的操作，称之为静态列表算 法。反之，在每个调度步都重新计算节点优先级的算法称为动态列表算法。 s a r k a r 为经典的调度问题提出了一个两步策略【2 l 】： 1 假设在一个拥有足够数量的虚拟处理器网络上调度。这一步的结果将是一些任务子 集( 称为簇) ，同一子集中的所有任务都必须运行在同一个处理器上。 2 如果簇的数目大于目标系统中实际的处理器数目，那么进一步合并这些簇，以适应 物理处理器的数目，而且在合并的步骤中也合并了网络拓扑。 在一个调度中，一些节点必须从分配到其它处理器上的节点接收数据。因此即使是一 个高效率的调度算法，仍然很有可能发生某些处理器在某些时段保持空闲的情况。如果将 某些重要节点重复地分配到这些空闲时隙，可能会进一步降低并行程序的响应时间。基于 这一思想的算法称为t d b 算法。t d b 算法不仅要满足任务之间的偏序关系，而且要选择 需要复制的祖先节点已经查找放置复本的时隙，因此通常有较高的时间复杂度。不同t d b 算法之间的主要区别在于选择复制节点的策略。为了降低一个节点的启动时间，一些算法 只复制父节点，而另一些算法则尝试复制更高层的祖先节点。与前