基于粒子群的网格任务调度算法研究.doc

第10期季一木等：基于粒子群的网格任务调度算法研究67基于粒子群的网格任务调度算法研究季一木1, 王汝传1,2(1. 南京邮电大学 计算机学院, 江苏 南京210003；2. 南京大学 计算机软件新技术国家重点实验室, 江苏 南京 210093) 摘 要：为了更好地解决异构动态环境下的资源管理问题，提出了一种网格环境下的任务调度模型。该模型考虑了当前网格虚拟组织下的计算资源、存储资源和带宽资源，模型的最优化目标是实现三者利用率最高和代价最低，即构造min-max函数。与遗传算法相比，利用粒子群优化算法对min-max函数求解提高了资源的利用率和任务的执行效率，同时在随着迭代次数增加的情况下，搜索速度、寻优率和避免早熟方面也有明显的提高。关键词：网格计算；任务调度；粒子群优化算法；遗传算法中图分类号：TP301 文献标识码：A 文章编号：1000-436X(2007)10-0060-07Study on PSO algorithm in solving grid task schedulingJI Yi-mu1, WANG Ru-chuan1,2(1. Department of Computer Science and Technology, Nanjing University of Posts and Telecommunications, Nanjing 210003, China;2. State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing 210093, China)Abstract: In order to resolve the resources management in dynamic heterogeneous environment, a kind of task scheduling model for grid environment was proposed. The model considers the computing resources, storage resources and bandwidth resources of current virtual organization in grid, and the optimal target of the model is to achieve the max-ratio and the min-cost of the above three kinds of resources, viz to build the min-max function. To compare with GA(genetic algorithm), PSO(particle swarm optimization) was applied in solving the min-max function so that the ratio of using resources and the efficiency of scheduling task are enhanced. Meanwhile, with the rise of iterative times, the searching speed, optimization ratio and avoiding pre-maturity are also distinctly enhanced.Key words: grid computing; task scheduling; particle swarm optimization algorithm; genetic algorithm1 引言收稿日期：2007-03-02；修回日期：2007-08-04基金项目：国家自然科学基金资助项目（60573141，60773041）；江苏省自然科学基金资助项目(BK2005146)；江苏省高技术研究计划（BG2005037，BG2005038，BG2006001）；国家高技术研究发展计划（“863”计划）基金资助项目（2006AA01Z201）；南京市高科技项目( 2006软资105) ；现代通信国家重点实验室基金资助项目（9140C1101010603）；江苏省计算机信息处理技术重点实验室基金资助项目( kjs050001，kjs06006)Foundation Items: The National Natural Science Foundation of China ( 60573141,60773041); The Natural Science Foundation of Jiangsu Province(BK2005146);The High Technology Research Programme of Jiangsu Province(BG2005037, BG2005038, BG2006001);The National High Technology Research and Development Program of China(863 Program) (2006AA01Z201);The High Technology Research Programme of Nanjing(2006RZ105); The Foundation of National Laboratory for Modern Communications(9140C1101010603) ;The Key Laboratory of Information Technology Processing of Jiangsu Province ( kjs050001, kjs06006)网格系统的实现分为资源层、中间件层和应用层3个层次。资源管理和任务调度是网格系统中间件层的核心模块之一1。主要包括资源的发现、预测、调度以及负载均衡等组成部分。目前,网格资源管理方法是用户直接利用信息服务GRIS(grid resource information service)搜索作业执行需要的资源。这种搜索方法比较传统,如果随着资源数目的增加,整个网格系统的性能将会受到影响。资源管理中的调度模块功能与狭义的任务管理模块是一致的。资源管理模型有分级模型、市场经济模型和成本/时间综合优化模型等2。开放网格服务架构OGSA (open grid services architecture)网格服务资源框架WSRF(web service resource framework)的实现GT4(globus toolkit 4.x)也没有很好地将优化智能搜索算法融入其中3，所以研究网格任务调度的智能优化算法及其实现显得尤为重要。网格的任务有2种类型，一种是相互独立的任务，另一种是相互关联的任务。本文在研究相互独立任务的基础上，并对关联网格任务的调度策略提出了求解思路。目前大多数研究也是基于相互独立任务的调度问题，而PSO算法在求解此类调度问题上有着天然的优势。对于相互关联的任务，PSO算法首先要构建DAG图,然后按照有向图顺序来执行提交的任务，因而文中给出了一个从有向图到任务调度映射的结构图。如何将网格环境中的广域动态资源映射到用户随机提交的任务中，该问题是一个NP难问题。目前一些启发式算法在解决这类问题时收到很好的效果, 其中粒子群算法4正是其中一种。粒子群算法在求解该类问题时的优点包括：收敛速度快、容易克服早熟、能够优化多目标、能够柔性控制和容易分布式运算等。文献5介绍了粒子群算法在动态环境下极值问题求解上得到了很好的运用，而网格本身就是一个动态环境下的问题求解和任务协同环境，所以本文将粒子群算法用在网格任务调度模型的求解上，结合文献6中粒子群算法和遗传算法的比较，可见粒子群算法较遗传算法有优势，本文在最后也通过实验证明了这一点。2 相关工作和创新对于作业执行中资源管理所进行的优化资源选择是决定网格计算性能的重要因素之一。除了传统和常用的先来先服务FCFS、直接用户分配UDA(user-directed assignment)、机会负载均衡OLB(opportunistic load balancing)、Min-min、Max-min、贪心Greedy和快速贪心Fast Greedy算法等类多项式算法7,8外，Di Martino 9、Song S.10,11和林剑柠等人12采用遗传算法来求解网格计算任务调度问题。Zhihong Xu 13和Hui Yan等人14提出了基于蚁群算法的网格任务调度问题求解，都取得了较好的成果。Tao Wang等人7提出了一种通用的网格任务调度算法，基本上综合了以上介绍的大部分算法，但是并没有介绍PSO算法。粒子群优化算法(PSO, particle swarm optimization)源于对鸟群捕食的行为研究, PSO同遗传算法(GA, genetic algorithm)类似, 是一种基于迭代的优化工具。系统初始化为一组随机解, 通过迭代搜寻最优值。PSO并没有像GA采用交叉(crossover)和变异(mutation), 而是粒子在解空间追随最优的粒子进行搜索。与GA相比，PSO的优势在于实现简单, 没有许多参数需要调整, 在设计实现上需要编写的代码量少等优点，所以本文提出并实现了基于粒子群的网格任务调度算法，与文献8相比，本文的创新概括有以下3点：1）提出了网格任务调度模型，该目标函数考虑了资源利用率和任务执行效率两方面；2）通过PSO算法来实现了对所建立的多目标函数求解，文献8仅采用传统的min-min调度算法；3）与遗传算法进行了比较，并取得了更好的应用效果。3 网格任务调度模型网格资源管理和任务调度是在网格用户提交请求后, 由资源分配和调度策略相结合, 通过组合优化算法实现任务和资源之间的映射15。目前网格中资源分配和任务调度模型有基于作业关联度进行动态分组并考虑通信和计算开销的算法研究,基于服务质量的算法研究,基于信度模型的算法研究, FCFS策略, BestFit策略, 优先权优先策略, MinMin算法, MaxMin算法, Xsufferage算法, Reservation策略和BackFilling算法等714。在前人研究的基础上,这里的资源分配和任务调度以多目标优化为寻优条件，多目标是指执行时间最少、网络传输延时最小和资源吞吐率最高3个目标下的最优化问题求解，即Optimal_RS= Execute_time, Delay_time, Highest_output。假设某一虚拟组织VO下用户提交了M个任务，记作T=T1，T2，Tm。网格任务有相互独立的,也有相互关联的（各个任务间存在相互调用或访问的接口）,结合现有的相互独立网格任务调度算法研究成果16,利用PSO算法17对网格虚拟组织下的独立任务进行调度和资源分配;另一个研究就是对相关任务的资源分配问题的规划求解,由于这些任务存在着相互制约的关联性,所以很难实现他们的完全同步,但是对于相关联的任务之间也存在部分独立并行执行的情况,下面将对关联任务调度模型中对如何确立约束关系，以及并发执行的任务划分展开理论分析。3.1 独立网格任务调度模型在第一种任务间相互独立的情况下,假设有R个节点，且每个网格节点所具有的三类资源分别记作(Rpj)i (i=1,2,R; j=1,2,3)。其中每个任务对每个节点中的3类资源的需求量分别记作(Rqj)i (i=1,2, ,R; j=1,2,3)。建立模型前进一步做如下设定:三类资源的每单位资源利用成本分别为c1、c2和c3，且用户提交的任务数M大于网格节点数R，即MR。同样假设同一任务对于网格环境下不同节点的资源需求代价是相同的,但是由于任务数多于节点数，所以在进行合理的资源分配同时就需要进行任务的调度，对于某一网格节点,可以通过线性加权函数来给出一个在不同节点间可以比较的标量。根据实际应用情况统计三类资源的代价比重设定w1、w2和w3，因此第i个任务分配到第j个节点上的总代价为其中，cik是一个由每个任务对三类资源的代价矩阵。在提交任务的同时提交各任务完成成本上限，记为(Cost)i(i=1,2,M),即用户的满意度。根据以上分析,为了更好解决在一个节点上分配多个任务的情况，可建立min-max目标函数和相应的约束条件。1) min-max目标函数(1)(2)式(1)是网格资源分配和任务调度的最佳方案，实现资源利用代价最小，该分配方案是通过粒子群算法来实现的，f(T)表示任务执行的总代价。式(2)是在对应式(1)最小代价下使所有任务调度执行的效率最大，E(T)表示任务执行的总效率。2) 约束条件(3)(4)(5)(6)(7)式(3)是资源分配的约束条件，表示用户提交任务所需求的三类资源在某一网格节点上必须同时得到满足，这是分配的必要条件，但不是分配方案的最终条件，如果同时有多个节点的资源满足某一个任务的请求，则此时选择一个优化算法来实现最优分配显得非常重要。式(4)表示用户提交任务完成代价能满足用户满意的最大上界,本文将任务完成时间、存储空间和通信延时通过线性加权在表示格式上统一抽象成一个无量纲的标量输出，所以在模型中将计算力、存储和带宽资源直接统一为无量纲的费用来表示。式(5)是某个任务在各个网格节点上的满意度，表示第i个任务在第j个网格节点上的满意度，其与某个节点上已经分配的任务数执行代价成负指数关系。式(6)是某一个任务是否在网格节点上运行的判断条件，可见Nij是一个由元素0或1组成的MR阶随机矩阵组成。式(7)说明必须将M个任务全部分配到R个网格节点上，同时由于式(3)的约束，则不可能出现所有任务集中到某一网格节点上执行的最坏情况。对于相互独立的分配到同一个网格节点上的不同任务间的调度问题，我们采取的调度策略是常用的短作业优先11。在实际操作中,用户可以根据自己的实际需求在提交任务时给出相应的权重w1、w2和w3，而网格节点资源的代价c1、c2和c3可以是一次性初始化完成。这类情况下任务的执行与求解传统的0-1规划等NP难问题原理是一样的，在网格资源分配和任务调度方面用于求解该问题的智能启发式算法在前面相关工作部分已经详细论述。3.2 关联网格任务调度模型在第二种任务间存在相互关联的情况下,假设有关联任务（如图1(a)和图2(a)所示）。同3.1节，整个虚拟组织下有三类资源Ri(i=1,2,3)，分别表示计算资源、存储资源和带宽资源。图1 存在独立同步网格关联任务调度和资源分配向最大深度树的转化任务调度根据图1(a)中每个任务的权值(a,b,c),3个常数a、b、c分别代表某一个任务完成并顺利到达下一个任务所需要的计算资源、存储资源和带宽资源。当然，在用户提交任务的同时还要考虑到不同任务对不同资源的需求量不同，给出三类资源对应的价值加权值w1,w2和w3。与2.1节不同的是，这些任务间是有关联的，如图1(a)所示，任务T0和T1，T0和T3是有关联的,记作。所以，结合图1(a)中的执行顺序, 使得资源分配和同一网格节点上关联任务间的调度达到最优。最优目标从服务提供者的角度体现在计算能力、内存占用和通信带宽的利用效率上,从服务请求者的角度，最优目标体现在任务的截止时间、优先级、安全性和费用等方面。以上两方面很好的结合将是建立min-max最优目标函数模型的初衷。经过深度值排序递归算法11来判断任务间的先后关系，即 根据上面的浓度排序递归算法，很容易得到图1(b)所示的树型存储结构和任务调度次序，没有前驱节点的任务可以作为树的根节点。显然，T0是树的根节点，且任务T1和T3的是2个独立任务可实现同步调度。另一种判断约束关系的方法是根据已知的DAG图来建立一个各个任务的前驱和后继节点的二维表，建表的原则如下：对于用户提交的任务数非常大的情况下，将会出现很多的同步调度情况(如图2(a)，此时就转化成独立任务优化求解问题了（同3.1节），则一样可以通过PSO算法来求解3.1节所建立的模型。对于相互依赖的任务，可以将他们分派到同一个网格节点中进行。所以这种情况(如图2(a)，该DAG图可以通过以上的递归算法很容易得到图2(b)所示的树型存储结构，任务调度有次序化后被存储在多个独立子树中，这些独立子树是可以同步执行的，采用化整为零的思想，则可以把他们看作是2.1节模型中的独立任务。图2 同步网格关联任务调度和资源分配向最大深度树的转化可见，关联网格任务调度与独立网格任务相比，主要工作就在于DAG图中的约束关系处理，本文参考文献18中的基于深度值递归排序算法将DAG图转化为深度树，通过对树的深度排序将很容易得出各个任务间的前驱和后继关系。同时对于任务的调度要考虑到图1和图2这2种情况。1)独立子任务的调度：采用短作业优先原则；2)存在前驱和后继任务间的调度：采用前驱节点优先的原则。4 网格任务调度的粒子群算法这部分仅是对于在任务相互独立的情况下的PSO算法实现,对于第二种情况更多关注的是如何划分任务,即从已知的任务有向DAG图中提取出他们之间可以并发执行的任务。一旦确定任务执行的流程之后，资源的分配就无需利用优化算法求解(包括PSO算法)。PSO算法的思想17：PSO中每个优化问题的解都是搜索空间中的一个被抽象成没有大小和质量的“粒子”。所有的粒子都有自己在空间中的位置和一个适应值, 每个粒子还有一个速度决定他们飞翔的方向, 然后粒子们就追随当前的最优粒子在解空间中搜索PSO 初始化为一群随机粒子(随机解)，然后通过迭代找到最优解. 在每一次迭代中，粒子通过跟踪2个“极值”来更新自己。第一个就是粒子本身所找到的最优解，这个解叫做个体极值pBest。另一个极值是整个种群目前找到的最优解，这个极值是全局极值gBest。另外，也可以不用整个种群而只用其中一部分作为粒子的邻居，那么在所有邻居中的极值就是局部极值。根据上面的分析，可以得出粒子群的迭代公式为(8)(9) 其中，式(8)和式(9)为传统PSO算法核心的速度()/位移()更新公式。t表示迭代次数，和为学习因子，通常=2。粒子群算法提出后得到快速的发展, 在算法的行为分析, 收敛性分析等方面都有研究人员的大量工作, PSO 算法与其他进化算法方法的一个显著区别就是所需调整的参数很少, 但是这些关键参数的设置对算法的精度和效率却存在显著影响4。粒子群算法应用到3.1节的模型要做相应的初始化设定工作。粒子位置由向量X表示，定义X为其中，表示任务n分配在节点上，不同的任务分配到同一节点上的调度次序采用短作业优先的调度准则。速度由Vx位向量表示 其中，,初始化粒子位置xi为之间的整数，粒子的速度随机取之间的整数。所以，根据式(1)和式(2)建立网格资源管理和任务调度模型，提出粒子群算法在网格资源管理和任务调度中的应用(见算法1)。算法1 求解min-max模型的粒子群算法描述1) 将粒子群划分成若干个两两相互重叠的子群;2) 初始化粒子群体,每个粒子位置向量X的每一维随机取(1R)之间的整数;3) 每个速度向量Vx的每一维随机取(R1)(R1)之间的实数，按短作业优先调度同一节点上的任务并用评价函数评价所有粒子;4) 将初始评价值作为个体历史最优解Pi,并寻找各子群内的最优解Pl 和总群体内最优解Pg，重复执行步骤5)步骤8)直到满足终止条件或达到最大迭代次数;5) 对每一个粒子X按式(1)计算、Vx按照式(2)计算、其中X向上取整，当过其范围时按边界取值;6) 用评价函数评价所有粒子;7) 若某个粒子的当前评价值优于其历史最优评价值,则记当前评价值为该历史最优评价值,同时记当前位置为该粒子历史最优位置Pi;8) 寻找当前各子群内最优解和总群体内最优解，若优于历史最优解则更新,子群内有多个体同为最优值的情况 则随机取其中一个为子群内当前最优解Pl。由于该问题属于约束优化，为了提高产生可行解的效率，PSO算法可减少无效的搜索空间，从而提高搜索速度。评价函数完成对不可行解的修正，以及调度方案的解码和评价；对任务分配到某节点资源不能满足要求的情况则对该任务重新分配节点；对不能达到满意度的调度方案采用罚函数，可见评价函数的执行直接影响算法的执行效率。5 仿真结果与分析实验将10个任务在5个网格节点上进行分配和调度，这10个任务从独立任务调度和关联任务调度模型两方面分别进行50次独立实验。实验1：用户提交的10个任务是相互独立的，在粒子群PSO算法和遗传GA算法下进行10次不同迭代后产生的运算结果和执行效率，如图3所示。实验2：图3 10个相互独立任务在PSO和GA算法上的执行情况用户提交的10个任务是存在关联的，关联情况可依据事先建立的任务关联表来判断，同样在粒子群PSO算法和遗传GA算法11进行了实验，实验在相同迭代次数下执行的效果相差无几的，但是他们在任务调度效率上存在着明显的区别，如图4(b)所示。由图3和图4可见，粒子群PSO算法和遗传GA算法在50次相同实验下，相同迭代次数下对PSO算法与GA算法在两类网格任务调度模型上的执行效果和效率进行了对比。明显在求解min-max目标函数时，无论是在求解最佳值(最小开销)还是在任务调度效率上，PSO算法都较GA算法优越。通过实验可以得出以下两点结论：1)充分利用了粒子群算法的群体并行搜索的高效性，PSO比GA算法可以在较少的迭代次数下收敛(如图3(a)和图4(a)所示)；2)在网格任务调度中PSO 的优化性能比GA算法高，尤其是对规模较大的复杂问题能够快速有效地求解(如图3(b)和图4(b)所示)。图4 10个存在关联的任务在PSO和GA算法上的执行情况6 结束语资源管理及任务调度是网格中的两大关键技术，本文通过粒子群算法能很好的实现全局资源优化分配的目标，目标函数考虑的评价参数全面实用，即考虑到了计算资源、存储资源和网络带宽资源的利用率，也考虑到了任务执行效率，并且利用启发式PSO算法求解，与遗传算法进行了比较，相比之下，PSO算法有更好的应用效果。目前，只是针对两类网格任务调度模型进行了优化，如果进一步能利用代理技术实现因网格节点的失效而将任务转移，考虑到实现的可行性，就近原则迁移，并不需要重新进行资源的重新分配，从而提高系统的调度性能。另一方面，网格是一个动态环境，如何利用PSO算法以及多粒子群协同优化算法19等实现动态可变作业的调度优化也将是我们进一步研究的目标20，支持用户随机提交作业。最终的目标是能设计出的一种基于代理技术的任务调度模型，并将这些技术和算法融入到网格开发平台中21。参考文献：1CHENG K W, YANG C T, LAI C L, et al. A parallel loop self-scheduling on grid computing environmentsA. Parallel Architectures, Algorithms and NetworksC. 2004.409-414.2陈宏伟, 王汝传. 费用时间优化的网格有向无环图调度算法J. 电子学报, 2005, 33(8):1375-1380.CHEN H W, WANG R C.A grid DAG scheduling algorithm for cost2 time optimizationJ. Acta Electronica Sinica, 2005, 33(8): 1375-1380.3LEE H M, CHUNG K S. A resource management and fault tolerance services in grid computingJ. Journal of Parallel and Distributed Computing, 2005,65: 1305-1317.4SALMAN A, AHMAD I. Particle swarm optimization for task assignment problemJ. Microprocessor and Microsystems, 2002, 26(8): 363-371.5LI D, DAM K H. Comparing particle swarms for tracking extrema in dynamic environmentA. Congress on Evolutionary Computation (CEC 2003) Proceedings 2003 IEEEC .2003.1772-1779.6HABIB S J, Al-KAZEMI B S. Comparative study between the internal behavior of GA and PSO through problem-specific distance functionA. Genetic and Evolutionary Computation ConferenceC. 2005.2190-2195.7WANG T, ZHOU X S, LIU Q R, et al. OD: a general resource scheduling algorithm for computational grid A. Computer and Computational Sciences, IMSCCS 06C. 2006 . 644-647.8王树鹏, 云晓春, 余翔湛. 基于生存性和Makespan的多目标任务调度算法研究J. 通信学报,2006, 27(2):42-49.WANG S P, YUN Y C, YU X Z. Research on multi-objective grid task scheduling algorithms based on survivability and makespanJ. Journal on Communications,2006, 27(2):42-49.9MARTINO D V. Sub optimal scheduling in a GRID using genetic algorithmsA. Parallel and Distributed Processing SymposiumC. 2003.22-26.10SONG S, HWANG K, KWOK Y K. Risk-resilient heuristics and genetic algorithms for security-assured grid job schedulingA. Computers, IEEE TrcmsactionsC. 2006.703-719.11林剑柠, 吴慧中. 基于遗传算法的网格资源调度算法J. 计算机研究与发展, 2004,14(12):2195-2199.LIN J N, WU H Z. Scheduling in grid computing environment based on genetic algorithmJ. Journal of Computer Research and Development, 2004,14(12):2195-219.12SONG S S, KWONG Y K, WANG K. Security-driven heuristics and A fast genetic algorithm for trusted grid job schedulingA. Parallel and Distributed Processing Symposium, Proceedings 19th IEEE InternationalC. 2005.65a.13XU Z H, HOU X D, SUN J Z. Ant algorithm-based task scheduling in grid computingA. Electrical and Computer Engineering, 2003. IEEE CCECE 2003C. 2003.1107-1110.14YAN H, SHEN X Q, LI X, et al. An improved ant algorithm for job scheduling in grid computingA. Machine Learning and CyberneticsC. 2005. 2957-2961.15丁箐, 陈国良, 顾钧. 计算网格环境下的一个统一资源映射策略J. 软件学报, 2002, 13(7):1303-1308.DING Q, CHEN G L, GU J. A unified resource mapping strategy in computational grid environmentsJ. Journal o