改进遗传算法,优化网格任务调度改进遗传算法,优化网格任务调度
引言 是如何把分布在不同地理位置上的计算资源、存储资源、通信资源、软件资源、信息资源和知识资源
等通过Internet整合成一台巨大的超级计算机,实现各种资源的全面共享,是网格任务调度的主要工作任务。资
源管理是网格技术的关键。 用户通过向网格系统提交计算任务,以此来共享网格资源,网格调度程序再把
这些任务分配给合适的资源。高效的调度策略或算法可以充分利用网格系统的处理能力,达到提高应用程序性
能的面对。在目前的网格调度算法研究中,主要目标是提高吞吐率和系统的使用率,实现经济系统和用户的约
束条件,使得在整个系统中网格应用任务的完成时间达到化。 遗传算法(IGA)是建立一个调度的集合并
从其中
引言引言
是如何把分布在不同地理位置上的计算资源、存储资源、通信资源、软件资源、信息资源和知识资源等通过Internet整合
成一台巨大的超级计算机,实现各种资源的全面共享,是网格任务调度的主要工作任务。资源管理是网格技术的关键。
用户通过向网格系统提交计算任务,以此来共享网格资源,网格调度程序再把这些任务分配给合适的资源。高效的调度策
略或算法可以充分利用网格系统的处理能力,达到提高应用程序性能的面对。在目前的网格调度算法研究中,主要目标是提高
吞吐率和系统的使用率,实现经济系统和用户的约束条件,使得在整个系统中网格应用任务的完成时间达到化。
遗传算法(IGA)是建立一个调度的集合并从其中找出优化的调度,将这种特性遗传给下一代。遗传算法通过适应度函数
交叉和重组得出的调度。这是一种迭代的算法,它的优点是在不断进化的过程中吸收系统发生改变,能够适应动态变化的网格
系统。
本文将改进的遗传算法(IGA)用于网格任务调度,通过IGA寻找满足完成所有任务时间短的优化方案。
1 背景描述背景描述
网格是一个集成的计算与资源环境,网格技术作为一种高性能广域分布式计算模型,已在众多研究机构的中成为热门研究
话题。
在网格技术的众多问题中,网格计算中的任务调度在一般形式下是一个NP问题,没有解。在调度算法的高效性、资源的
异构性以及资源分配决策的并行性和分布性等方面,传统的调度算法并不能很好地适应网格资源的特性。因此,如何对网格资
源进行合理分配和管理,满足各种应用的服务需求,实现资源的优化利用,就成为该领域的研究关键。
网格任务调度根据任务间是否存在通信关系可以分为对相互间存在通信任务的任务组的调度和对相互独立的任务组的调
度。在算法实现中都假定资源的信息是可获取的。
网格任务调度的实质就是在一个由m个需要调度的任务、n个可用的任务执行单元(主机或集群)、k个数据存储单元构成
的网格环境下,把m个任务T={t1,t2,…,tm}以合理的方式调度到n台主机的过程,目的是得到尽可能短的总完成时间。把每
个执行单元广义地当作一台主机来看待,把k个数据存储单元当成一个存储系统整体来看待。
m个任务在n台不同主机上的预测执行时间EET是一个m×n的矩阵。矩阵中的每一行代表某一个任务在n台机器上的不同执
行时间,每一列代表在同一台机器上的m个任务的不同执行时间。
通信开销矩阵CCT描述了网格环境下,不同“任务对”在各主机之间进行数据传输的通信开销。任务必须分配到一台主机
上,所需要的数据也必须从它的父任务发送过来,父任务可能有多个。个任务没有通信开销,其后的所有任务都可能有通信开
销,因此CCT是一个m×m的矩阵。
m个任务在n台不同机器上的预测短完成时间MCT是一个m×n的矩阵,MCT(i,j)除了包含EET(i,j)外,还应考虑通
信和等待通信的时间开销T(i,j),T(i,j)=max((CCT(i,v)+TW(i,k)),k=1,2,…,i-1),TW(i,k)为第
i个任务等待其父任务准备好数据的时间。
调度的目标是在考虑通信开销和给定代价及约束集合现状之下,任务集合总的完成时间短。
负载均衡性可以用每个调度方案中各台主机的长执行时间与短执行时间的比值来衡量,该值越小,则该调度方案中各台主
机的负载均衡性越好。
2 改进遗传算法在网格任务调度中的应用改进遗传算法在网格任务调度中的应用
2.1 改进遗传算法改进遗传算法
遗传算法求解问题的基本步骤为:
(1)定义适应度函数和相应的隶属度函数;
(2)确定算法的初值和初始种群;
(3)对种群进行选择、交叉、变异操作,产生新的种群;