基于PSO算法的网格任务调度策略.pdf

万方数据

依赖关系，即任务rh(1蛐可划分为数据传输子基于PSO算法的网格任务调度策略引言1网格任务调度问题优化模型TaskschedulingingridbasedPSOalgorithmsystemPSO’S‘'premature”problem．许多学者的关注，并取得一定的研究成剿卜4J。GA第29卷第2期辽宁工程技术大学学报(自然科学版)鹏2，于俊发2，喻春明2in鲥dmethodproposedthe舒d2010年4月迟玉红L2，白University，Beijingandparticles，andbalancing，significantlyperformanceutilization，and由于网格环境的动态性、异构性等特点，以及网格资源在任务执行过程中的状态难以预测，从而使得网格任务调度问题异常复杂。近年来，已引起算法是解决网格任务调度问题常用且有效的启发式算法15】。但与PSO算法相比，前者开销较大，执行时间较长，而后者搜索速度快，运算简单，更加有效率【6】，且PSO算法的局部模型较全局模型有更好的收敛性和健壮性171。基于以上问题研究，本文提出基于局部模型PSO算法网格任务调度策略，并在处理粒子越界问题时，采用“圆桌运动”方法，改善了PSO算法易陷入局部最优问题，有效提高网格任务调度的性能。1．1任务模型的确定由于现有的网络环境对任务调度的整体影响是不能忽略的。因此，本文所调度的任务之间虽然彼此独立，但不排除任务内部存在依赖关系，即子任务(SubTask)tsl。由这样若干可一次调度，任务内部具有依赖关系，而彼此之间相互独立的任务组成的集合，本文将其称为元任务(MetaTask)。如图1，元任务MetaTask是由乃，乃，⋯，珀共日个相互独立的任务组成。每个任务内部可存在任务D和计算子任务C。由于本文主要研究的是网JournalUniversity(NaturalScience)(1．清华大学计算机科学与技术系，北京100084：2．中国人民解放军65053部队，辽宁大连l摘要：为了合理地协调和分配网格资源，降低网格任务完成时间，有效保持网格资源负载平衡，通过分析网格任务调度的关键问题和PSO算法的优化原理，建立了网格任务调度的元任务模型和性能指标的数学模型，确定了粒子编码和解码方式，提出了一种基于局部模型PSO算法的网格任务调度策略，并在PSO算法处理粒子边界问题时，采用了“圆桌运动”的新方法。仿真实验结果表明，算法可行有效，并且改善了PSO算法易陷入局部最优的问题。关键词：网格；任务调度；元任务；PSO算法；局部模型中图分类号TPl8；TP393文献标识码：Aon(1．Department13,China)system，greatlyperformance．theschemeconditions，themoving”．Thealgorithm；localv01．29No．2ofLiaoningTechnicalApr．2010文章编号：1008—0562(2010)02．0274．0413)CHIYuhon91。，BAIPeng‘，YUJunf．a‘·YUChunmingZofComputerScienceTechnology，Tsinghua100084,Chinas2．Unit65053，PLA，Dalian1161Abstract：Itischallengefindoptimalsolutionwhichrationallycoordinateallocatereducecompletiontime，efficientlybalanceworkloadimproveThispaperinvestigateskeyissuestaskprinciplealgorithm，developsmodelmetametricsscheduling．Alsohasdevelopednewforcodingencodingusinglocalbestmodel．Togiveboundaryproposescalled‘'round-tableexperimentalresultsshowthatapproachconlributesoverall10adimprovesapplicationexecutionavoidsKeywords：grid；taskscheduling；metatask；PSO基金项目：国家重点基础研究专项基金资助项目(G2007cb311003)；国家自然科学杰出青年摹金资助项目(60625304)’作者简介：迟玉红(1972．)，女，黑龙汀建i江人，博上研究生，讲师，主要研究方向包括嘲格计算、入1二智能及图像处理，E-mail：[e-mail]．c