基于遗传算法的网格资源调度算法

第41卷第12期2004年12月

计算机研究与发展

JOURNALOFCOMPUTERRESEARCHANDDEVELOPMENT

Vol.41,No.12Dec.2004

基于遗传算法的网格资源调度算法

林剑柠　　　吴慧中

(南京理工大学计算机科学与技术系　南京　210094)(oliverljn@http://wendang.chazidian.com)

摘　要　网格将多种资源组织在一个统一的框架下,为各种复杂的计算任务提供资源.因此计算任务在各种资源之间的调度成为了一个关键的问题.简述了在异构资源之间调度任务的重要性,提出了一种基于遗传算法的任务调度算法.该

算法采用资源-任务的间接编码方式,通过DAG图获取子任务的层次关系,并将子任务按照层次深度排序,解决了种群中的非法问题.在单一资源上采用短任务优先和父节点优先两个原则来安排子任务的执行次序,以避免出现任务堵塞的现象.

关键词　资源调度;网格计算;遗传算法;深度值中图法分类号　TP393

SchedulinginGridComputingEnvironmentBasedonGeneticAlgorithm

LINJian-NingandWUHui-Zhong

(DepartmentofComputerScienceandTechnology,NanjingUniversityofScienceandTechnology,Nanjing210094)

Abstract　http://wendang.chazidian.computationalgridsprovidemechanismsforsharingandaccessinglargeandheterogeneouscollectionsofre-moteresources.However,howtoschedulethesubtasksintheseheterogeneousresourcesisacriticalprob-lem.Inthispaper,ascheduling-algorithmbasedongeneticalgorithm(GA)isaddressed.Thechromosomecodingmethodandtheoperatorofgeneticalgorithmarediscussedindetail.Therelationshipbetweensub-taskscanbeobtainedthroughtheDAG,andthenthesubtasksarerankedaccordingtotheirdepth-value,whichcanavoidtheemergenceofinvalidatechromosomes.Inthesingleresource,twoprinciplesareadopt-edtodeterminethesequenceofthesubtasks:oneistheshort-subtaskprior;theotherisparent-subtaskpri-or.

Keywords　resourcescheduling;gridcomputing;GA;depth-value

其繁琐复杂的问题,它在一般形式下是一个NP完

1　引　　言

网格计算是伴随着互联网而迅速发展起来的专门针对复杂科学计算的新型计算模式.在网格计算环境中,大型的计算任务往往被分解成若干个彼此联系的子任务,这些子任务向资源管理系统提出资源请求.在通常的情况下,子任务的数量多于资源的数量,因此为了提高资源的使用效率同时使计算任务在尽可能短的时间内完成.资源调度是一个极

　收稿日期:2004-09-21

　基金项目:国防预研课题基金项目(51404020303BQ0220)

全问题.

已经有人在资源调度算法中做了大量研究:

Buyya提出了一种基于应用经济模型的优化调度模型[1],其目的是在资源的拥有者和使用者之间建立一种“交易”,以尽可能低的费用满足资源使用者进行计算任务的最低要求;Vincenzo介绍了一种基于遗传算法的资源调度算法,其目的是为了尽可能地提高资源的使用率和吞吐量.另外Abraham等人介绍了模拟退火等进化算法在网格资源调度中的

[2,3]

2196计算机研究与发展2004年

应用[4],Xu等人介绍了蚁群算法[5]的应用.但是他们没有考虑到任务之间的依赖关系.实际上,网格中的任务关系有两种:一种是指一组相互独立的任务,即任务之间没有通信和数据依赖;另外一种则是任务间有交互,即DAG图调度.本文介绍了一种基于遗传算法的调度策略,采用资源-任务的间接编码方式,在满足任务之间逻辑关系的条件下,尽可能地缩短任务的完成时间,提高资源的使用效率.

体中的每一位都是正整数,每一位的位置编号代表子任务的编号,而该位置上的正整数值代表该子任务所占用资源的编号,如图1所示:

图1　资源-任务编码

2　问题描述

本文主要讨论的是当子任务数量远大于资源数量时的调度策略,如何获取资源信息、子任务的分解方法不在讨论范围内,不做详细讨论.本文的调度算法分为两级:一个是系统级层,即在不同的资源上分配子任务;另一个是资源级层,即在同一个资源上运行的子任务的调度策略.前者采用遗传算法迭代选择,后者采用短任务优先原则和父节点优先原则.首先我们假设:①某一个大型的计算程序已经被分解为若干个子任务,而且每个子任务之间的数据依赖关系已知.②资源的实时状态已知,每个子任务在每一个资源上执行的代价已知;资源与资源之间的通信延迟已知,任意两个存在数据依赖关系的子任务之间的数据传输量已知.③在同一个资源上执行的子任务遵循FCFS原则.我们还做出如下约定:对于任意的计算程序,其分解的子任务,我们用如下的集合表示:sb={sbi sb1,…,sbn,1≤i≤N},N是计算程序分解后子任务的数量.子任务i在资源j上执行的时间用E[i][j]表示;资源i和资源j之间的传输延迟用Tr[i][j]表示.

其中,Si表示子任务的编号,Ri表示子任务Si执行时占用的资源的编号.在产生初始种群时,每一个染色体中的资源编号Ri都是随机产生的,经过交叉、变异算子后,子任务Si可能占用任何一个可用的资源,所以最优解一定对应某一个染色体编码.产生了一个染色体后,还必须对其进行解码,得到不同资源上子任务的分布情况.将子任务按照占用的资源分类,生成多组按照资源编号分类的子任务序列,每个序列的编号就是某一个资源的编号,序列中的元素就是在该资源上执行的子任务,这样我们就得到了所有子任务在多个资源上运行的分布情况.采用这种编码和解码的方式,可以很方便地得到子任务集合在多个资源上的分布情况,而且对于运行在不同资源上的子任务,不需要考虑它们之间的逻辑关系,只需考虑在同一个资源上运行的子任务之间的逻辑关系.下面介绍如何处理在同一个资源上运行的所有子任务之间的逻辑关系和它们的执行顺序.3.3　约束关系处理

在同一个资源上运行的任何两个子任务都必须满足DAG图规定的逻辑关系.假设Si,Sj都在某个序列中,且Si,Sj满足Si※Sj,即任务i必须在任务j之前执行.但是如果在执行序列中任务j先于任务i执行,则出现死锁现象.所以必须采用一定的方法,避免出现死锁现象.3.3.1　基于深度值的排序[6]

前面提到的所有子任务之间的逻辑关系可以用一张DAG图表示,可以对DAG图进行分层,每层有一个深度值,深度值越小,代表优先级越高.深度值的计算公式如式(1):

0,sbi无父节点

level(parent(sbi))),level(sbi1+max(

　其他sbi,

(1)

其中,parent(sbi)返回的是子任务sbi的父节点集,3　遗传算法的应用

3.1　遗传算法简介

遗传算法(GA)是Holland于1975年受生物进化论的启发而提出的.并行性和全局解空间搜索是GA的两个最显著的特点.网格计算中的资源调度一般形式下是一个NP问题.由于遗传算法的并行性和全局解空间搜索的特点,因此非常适合求解NP问题.下面将介绍该算法的几个关键步骤.3.2　染色体的编码和解码

染色体的编码形式有很多种,可以采用直接编码(直接对子任务的执行状态编码),或者间接编码方式.本文采用间接编码方式,对每个子任务占用

,

　12期林剑柠等:基于遗传算法的网格资源调度算法

2197

集合中具有最大深度值的父节点的深度值.可以采

用深度遍历的方法获取DAG图节点的深度信息.获取层次深度信息后,对在相同资源上运行的子任务序列,就可以按层次深度值由小到大排序,这样优先级越高的子任务执行顺序越靠前,对于同一个资源上的所有子任务,经过排序后得到的子任务执行序列就可以避免出现死锁现象.3.3.2　短任务优先原则

在同一资源上运行的不同深度值的子任务,按深度值排序可以保证子任务之间数据逻辑关系的合法性.但是对于深度值相同的子任务,它们之间不存在伊赖关系,可以并行执行.如果在同一资源上出现多个深度值相同的子任务,它们以任意的次序执行,可能会造成堵塞现象.以图2为例,子任务sb3,sb4,sb5深度值相同,且它们占用的资源情况如图3,如果E[3][0]>E[4][0],则短任务sb4将被长任务sb3堵塞,而且由于任务sb6是任务sb4的子节点,因此sb6也被堵塞.如果对于同一资源上运行的同深度值可并行的子任务,采用短任务优先的调度原则,短任务优先执行,可以解决长任务堵塞短任务的问题,即如果sb4先于sb3执行,则sb6和sb3可以并行执行,资源R0上子任务的执行时间不变,而资源R2上的执行时间由于sb6的提前运行而减少

.

的子任务,除了考虑它们的运行时间长短外,还要考虑它们是否拥有自己的子节点,有子节点的子任务优先执行.以图2为例,子任务sb3,sb4,sb5深度值相同,子任务占用的资源情况如图3所示,sb4有子节点,sb3本身为叶子节点;这时由于sb3先运行,则堵塞了sb6的运行.如果提前运行sb4,则sb3,sb6可以并行执行.资源R0上子任务的执行时间不变,而资源R2上的执行时间由于sb6的提前运行而减少.3.4　适应值计算

根据第3.2节所介绍的编码方法,对每个染色体按照资源编号分类,得到每个资源上运行的子任务集合,按照第3.3节中介绍的原则得到每个资源上子任务的运行序列.根据子任务之间的逻辑关系和子任务的运行序列,可以计算出每个资源完成该资源上所有子任务花费的时间,取最大花费时间的倒数为适应值的大小,因此花费时间越长,适应值越小.

计算适应值必须计算每个子任务的完成时间,假设子任务i在资源j上的完成时间为fin[i][j],则fin[i][j]=start[i][j]+E[i][j],其中start[i][j]为子任务i在资源j上的开始执行时间.start[i][j]由3个因素决定:①资源的空闲时刻.②子任务i的所有父节点任务的最晚完成时间.③最晚父节点任务所在资源与子任务i所在资源之间的通信延迟.计算公式如式(2),其中rs[j]是资源j上最近的一次空闲时刻;max(fin(parent(i)))返回值是子任务i的所有父节点任务的完成时间的最大值;Tr[m][j]是该父节点任务所在资源m和子任务所在资源j之间的通信延迟.　start[i][j]=max{rs[j],　　max(fin(parent(i)))+Tr[m][j]}.(2)3.5　交叉和变异

在交叉操作前,要选择适当的个体进行交叉操作.个体选择的方法很多,例如轮盘赌选择方法[7]、

[7]

随机遍历抽样选择等等.这里交叉算子采用

[7]

Syswerda(1989)提出来的OX交叉算子,交叉点的位置随机确定.经过交叉生成的两个子个体,我们分别对它们计算适应值.如果生成的子个体的适应值大于父个体,则按照一定的概率替换父染色体.反之,则选择原种群中适应值最小的染色体比较,如果新子个体的适应值大于最低适应值,则替换原染色体;否则舍弃生成的子染色体,并重新选择父染色体进行交叉操作.

变异算子一定程度上克服了遗传算法的早熟收敛,有利于增加种群的多样性.这里变异算子实质图2　子任务的DAG

图

图3　子任务的资源分配图

3.3.3　父节点优先原则

对于一些子任务节点,它们本身可能就是父亲节点,拥有自己的子节点;也有可能没有子节点,本

2198计算机研究与发展2004年

了防止某个子任务在迁移后,执行的时间增大而造成种群退化,规定迁移后子任务占用的资源不是随机产生,而是在除了该子任务目前占用的资源外的资源集合中,选择使该子任务执行时间最短的资源,将其迁移到该资源上执行.

由于我们采用的是资源-任务的间接编码方式,交叉和变异算子生成新染色体的过程实际上是对子任务占用的资源的重新分配.在交叉和变异操作后,对所有子任务重新按其占用的资源分类,并对在同一资源上运行的子任务,按照深度值的大小排序,这样就不会出现死锁现象.因此在交叉和变异操作后生成的新个体依然符合子任务之间的逻辑关系.

显然,如果效率越高,则说明该资源上每个子任务之间的等待时间越短,子任务之间并行程度越高.在所做的100次实验中,每次资源的平均运行效率都在60%以上.

本文还对链状结构的DAG图和矩阵结构的DAG图做了实验,其结构图如图7所示;假设20个子任务、5个可用资源,实验结果如图8和图9所示.实验证明,在不同的DAG结构下,采用遗传算法调度子任务,也优于采用SJLF和LJLF算法.

4　算法流程

(1)初始化矩阵E和矩阵Tr,并根据DAG图

生成每个子任务之间的逻辑关系,计算每个子任务的深度值;

(2)随机产生大小为M的初始种群;根据每个资源上的子任务的执行序列,计算每条染色体的适应值;(3)选择染色体进行交叉操作和变异操作,计算新生成染色体的适应值,生成新的种群;

(4)判断是否满足遗传算法的终止条件,如果满足,则停止计算,输出最小时间和对应的染色体;如果不满足,则返回(3).

图4　20子任务-3资源实验结果

5　实验结果

我们进行了两组实验,分别假设有20个子任务3个可用资源和20个子任务5个可用资源,每个子任务在不同资源上的运行时间和资源之间的传输延迟是随机产生的,任务之间的逻辑关系假定为树形结构.初始种群的大小是100,变异率是0.05,交叉率是0.7.本文算法与SJLF和LJLF两个常用算法比较,实验结果如图4和图5所示.实验证明,在不同资源的条件下,采用遗传算法调度子任务,所有子任务全部完成的时间均小于采用SJLF和LJLF算法调度.

图6是在子任务数量为20、资源数量为5的条件下,每次运行算法产生调度结果后的全部资源的平均运行效率,这里运行效率定义为ef

fect=

[4]

[4]

图5　20子任务-5资源实验结果

该资源上运行的子任务的运行时间.

内容需要下载文档才能查看

　12期林剑柠等:基于遗传算法的网格资源调度算法

2199

虑了子任务在资源上的执行时间和资源之间的传输

延迟这两个关键因素,但实际的网格环境中的任务特性包括更多的因素,因此下一步我们将包括更完整的网格环境中子任务的特性,考虑更多网络因素,例如资源负载的动态变化以及资源的稳定性等方面;我们在本文中假设使用的子任务信息在执行调度任务前已经获取,下一步将考虑如何实时获取相关的资源信息和子任务信息,并根据实时的资源信息动态调度子任务.

参

1

图7　两种DAG图结构

考文献

RBuyya,DAbramson,JGiddy.Aneconomydrivenresourcemanagementarchitectureforglobalcomputationalpowergrids.Int'lConfonParallelandDistributedProcessingTechniquesandApplications,LasVegas,2000

2VincenzoDiMartino.Schedulinginagridcomputingenvironmentusinggeneticalgorithms.MarcoMililottithe16thInt'lParallelandDistributedProcessingSymp(IPDPS2002),Florida,USA,2002

3VincenzoDiMartino,MMililotti.Sub-optimalschedulinginagridusinggeneticalgorithms.ParallelComputing,2004,30(5/6):553～565

图8　链状结构的DAG

图比较

4AjithAbraham,RajkumarBuyya.Nature'sheuristicsforschedul-ingjobsoncomputationalgrids.The8thInt'lConfonAdvancedComputingandCommunications(ADCOM2000),Cochin,India,2000

5ZhihongXu,XiangdanHou,http://wendang.chazidian.comECE2003-CanadianConfonElectricalandComputerEngineering,Montreal,Canada,2003

6钟求喜,谢涛,陈火旺.基于遗传算法的任务分配与调度.计算机研究与发展,2000,37(10):1197～1203

(ZhongQiuxi,XieTao,ChenHuowang.Taskmatchingandschedulingbyusinggeneticalgorithms.JournalofComputerRe-searchandDevelopment(inChinese),2000,37(10):1197～1203)

7王小平,曹立明.遗传算法.西安:西安交通大学出版社,2002(WangXiaoping,CaoLiming.GeneticAlgorithms(inChinese).Xi'an:Xi'anJiaotongUniversityPress,2002)

图9　矩形结构的DAG图比较

6　总　　结

本文提出了一种基于遗传算法的网格资源调度算法,讨论了使用遗传算法解决网格环境中多个子任务在异构资源之间的调度问题,包括问题的提出、

解决方法和实验结果分析,并给出了资源-任务的间接编码和解码的方法,采用对DAG图中节点分层的方法来防止死锁的产生.通过对不同资源条件和不同结构的DAG图的实验证明了该算法优于传统的SJLF和LJLF.

,　　林剑柠　男,1978年生,博士研究生,

主要研究方向为仿真网格.

　　吴慧中　女,1942年生,教授,博士生导师,主要研究方向为计算机图形学、计算机仿真和虚拟现实.