自适应邻域的多目标网格任务调度算法
摘要:针对网格计算中的多目标网格任务调度问题,提出了一种基于自适应邻域的多目标网格任务调度算法。该算法通过求解多个网格任务调度目标函数的非劣解集,采用自适应邻域的方法来保持网格任务调度多目标解集的分布性,尝试解决网格任务调度中多目标协同优化问题。实验结果证明,该算法能够有效地平衡时间维度和费用维度目标,提高了资源的利用率和任务的执行效率,与min-min和max-min算法相比具有较好的性能。
关键词:网格任务调度算法;多目标进化算法;自适应邻域;任务调度
multi-objective evolutionary algorithm for
grid job scheduling based on adaptive neighborhood
英文作者名yang ming1,2*, xue sheng-jun2, chen liang1, liu yong-sheng1
英文地址(1.zhejiang meteorological information network center, hangzhou zhejiang 310017, china;
2.college of computer and software, nanjing university of information science and technology, nanjing jiangsu 210044, china)
abstract: a new adaptive neighborhood multi-objective grid task scheduling algorithm (anmo-gtsa) was proposed in this paper for the multi-objective job scheduling collaborative optimization problem in grid computing. in the
anmo-gtsa, an adaptive neighborhood method was applied to find the
non-inferior set of solutions and maintain the diversity of the multi-objective job scheduling population. the experimental results indicate that the algorithm proposed in this paper can not only balance the multi-objective job scheduling, but also improve the resource utilization and efficiency of task execution. moreover, the proposed algorithm can achieve better performance on
time-dimension and cost-dimension than the traditional min-min and max-min algorithms.
key words: grid job scheduling algorithm; multi-objective evolutionary algorithm; adaptive neighborhood; job scheduling
0引言
在资源异构高效的网格计算中,网格环境涉及网格用户、网格资源管理者、虚拟组织管理者等多个实体,不同实体间对管理机制、安全策略、调度时间和费用等目标都不同,有的甚至相互冲突。因此,如何通过资源管理与调度算法协调这些不同实体间和同类实体内部的不同目标要求是当前网格计算中的热点问题[1]。
近年来,国内外研究人员提出了不少高效的网格任务调度算法,其中比较典型的有min-min、max-min和sufferage等[2-5],这些调度算法主要以任务完成时间作为单一调度目标。针对多目标任务的调度算法有min-min启发式调度算法[6]和多目标冲突度遗传算法[7]等,这些算法主要采用权重法将多个目标函数聚合成单一的目标函数,进行单目标求解。权重法具有时间复杂度低、便于实现的特点。但是,这些算法主要通过调整权重来平衡多个目标,而权重的取值具有随意性,影响了调度算法的性能,这些算法自身也存在一些固有
的缺陷,很难满足网格环境用户同时对多个目标的需求。另外,单目标优化算法仅能根据聚合函数来得到决策空间中一个可行解,降低了最终解的质量,缺乏灵活性与可扩展性。而多目标优化问题的解并非唯一的,它存在一个最优解集或非支配解集(non-dominated solutions set, ndset),集合中元素称为pareto最优解或非劣最优解[8-9]。因此,更为合理的途径是采用多目标最优化算法来解决多目标网格调度问题。
鉴于此,本文通过网格任务调度的多个效用函数指标,运用多目标最优化理论及其算法来解决网格任务调度中多目标协同问题,提出了一种基于自适应邻域的多目标网格任务调度算法(a new adaptive neighborhood multi-objective grid task scheduling algorithm, anmo-gtsa)。该算法采用一种新的基于自适应邻域修剪策略,不仅可以获得多个相互冲突的调度目标的最优解,还可以改善负载均衡的问题。在通常情况下,最短任务完成时间目标和最低费用目标在一般情况下是冲突的,无法在这两个目标上同时获得最优的调度结果,通过该算法可以平衡这两个目标,使得计算节点的分配更均匀,并且将其与传统算法min-min和max-min进行了对比实验,实验结果验证了新算法的优越性。
1调度模型和问题定义
从用户的角度来说,总是希望分配到的资源能够用最少的时间、最小的费用完成所有提交的任务;而从资源提供者角度看,完成时间越少、资源性能越高,定价费用自然也会越高。资源的可用性越高,它完成单位计算量的费用越高;请求资源的用户数量越多,资源的价格越高。资源的价格和任务完成时间对网格用户的成本起决定作用,都是评估模型中重要的指标。
网格任务调度相关定义如下:
1)用集合r={r1,r2,…,rm}表示m个计算资源,其中rj表示第j个资源。
2)用集合t={t1,t2,…,tn}表示n个任务,其中ti表示第i个任务。
3)任务的执行时间用m×n阶矩阵et表示;eti j表示任务ti在处理节点rj上的预期执行时间,eti j=∞表示任务ti不能在处理节点rj上执行。
下面给出网格任务调度方面的最优跨度和费用效能这两个问题的描述。
最优跨度问题假设不考虑计算任务的跨节点执行,用户向系统提交的任务就是网格调度单元进行任务分配的最小单位,大型计算任务的分解由用户来完成,并且任务之间是的。
任务调度问题是将n个任务集t以合理的方式调度到m个处理节点集r上执行,以尽可能地达到预定目标。任务调度的结果用n×m的二维矩阵w来表示,当wi j=1(wi j∈w)表示将任务将ti调度到处理节点rj上执行;否则wi j=0。
为了便于描述,定义以下参数和符号:makespan表示最优跨度;bj表示处理节点rj的最早可用时间;cti j表示任务ti在处理节点rj上的预期完成时间。
一般有cti j=bj+eti j。当任务ti被调度到处理节点rj上执行时,令cti=cti j,表示任务ti执行完成的时间,则任务集t的执行完成时间makespan(t)= maxti∈t(cti),调度目标是要获得尽量小的makespan,即min(makespan)。
第3期 杨明等:自适应邻域的多目标网格任务调度算法计算机应用 第32卷费用效能
问题当需要缩短运行时间时,需要牺牲更多的cpu使用费用来补偿,即处理能力越高的cpu,其使用费用通常越高。因此,如何能使cpu的使用费用和运行时间同时达到最小值,是一个复杂的问题。
假设cost表示应该执行完所有任务所需的总费用;uj表示资源rj在单位时间内的价格;ci j表示任务ti在资源rj上的费用,则任务ti的执行费用ci j和总费用cost可表示为:
ci j=eti j×uj(1)
cost=∑ni=1∑mj=1ci j(2)
则调度求解目标是尽量小的cost,即min(cost)。
基于上面提出的最优跨度和费用效能两个问题的模型,多目标网格任务调度的总目标函数可以表示为：
min f(makespan, cost)(3)
式(3)表示任务调度的目标是在执行完所有任务后,取得尽量少的总执行时间和尽量小的总花费,使该两个目标同时达到最优。
2自适应邻域多目标网格任务调度算法
2.1自适应邻域策略
为了避免算法的分布性在进化中受到破坏的现象以及解决邻域半径的取值问题,首先,应使半径变化率的自适应调整曲线在davg处缓慢改变,从而提高距离接**均距离的个体的邻域半径。其次,当davg和dmin相差较大时,确保自适应调整曲线不会趋于直线型。最后,保证种群中较优个体仍具有一定的分布性。同时,为了能尽可能地保留较好的分布性,应更平滑davg处的自适应调整曲线。如图1所示。
图片图1自适应调整曲线
由于sigmoid函数在线性和非线性行为之间显现出较好的平衡[9],所以采用sigmoid函数作为自适应调整曲线。求解邻域半径的自适应调整公式如式(4)所示。
r=rmax-rmin1+expa(r-dmin)davg-dmin+rmin,d≥dmin
rmin,dn,则利用算法3进行修剪操作,降低其大小,直到其规模等于任务数n;若|ndset|第6步结束条件。以进化代数作为终止条件,若满足终止条件,则将ndset中的所有非支配个体作为最终的输出群体;否则,ndset保存到x(g+1)中,令g=g+1,转第3步。3实验分析
为了检验所提自适应邻域多目标网格任务调度算法模型的性能,首先讨论了实验的参数设置,然后通过与其他网格任务调度算法,如max-min和min-min算法进行了比较分析,表明了anmo-gtsa算法的优越性。
3.1实验参数设置
在网格环境中,由于任务到达时间的随机性以及计算资源的动态性,所以网格环境中一般需要动态调度算法[10]。本节在批处理模式下分别针对不同的任务数和处理节点数进行了实验。模拟实验的参数设置如下:
1)anmo-gtsa算法采用实数编码,交叉概率0.85,变异概率0.01,种群规模为100,进化代数为300,适应度评价次数为30000,算法的运行代数为评价个体的数目除以种群规模。
2)每个任务在各个处理节点上的执行时间满足均匀分布;任务的到达时间服从泊松分布。
3)处理节点的失效率在区间1×10-4~1×10-3内均匀选择。
4)在不同数目的任务集进行实验时,处理节点数为10,任务数的范围是100～1000,间隔为100;在不同数目的处理节点进行实验时,任务数为500,处理节点数为10～100,间隔为10。
每个实验都分别选择了不同任务集和计算节点集进行了100 次,将100次实验结果取平均得到最终的实验结果。
3.2实验结果与性能分析
仿真实验分为两部分:1)网格系统是由10个网格资源节点组成,任务数为100～1000的任务集合组成,间隔为100;2)网格系统是由500个任务数组成,网格资源数为10～100的
网格资源节点集合组成,间隔为10。为了使实验数据具有稳定性,每组实验均进行多次,用其平均值进行性能分析。
图3为在不同任务数情况下，各种调度算法得到的执行时间和费用性能比较曲线图。图4为在不同资源节点数情况下，各种调度算法得到的执行时间和费用性能比较曲线图。时间维度定义为调度方案中所有的任务所获得的时间性能效用总和。从图3(a)和图4(a)可看出,anmo-gtsa时间性能效用优于max-min和min-min算法。费用维度定义调度方案中所有的任务所获得的费用性能效用总和。从图3(b)和图4(b)可看出,anmo-gtsa费用性能效用优于max-min和min-min算法。从实验结果数据可看出,由于anmo-gtsa算法综合考虑了执行时间和费用性能效用,所以其执行时间和费用性能效用都优于max-min和min-min算法。
图片图3anmo-gtsa、max-min和min-min在不同任务数下的性能比较
图片图4anmo-gtsa、max-min和min-min在不同网格资源节点数下的性能比较
为了分析算法在负载均衡方面的性能,从第一部分实验中,选择由100个任务数组成,网格资源节点数为10的网格资源节点集合组成的网格系统。图5显示了各种调度算法的映射能力。从图中可看出,anmo-gtsa算法在负载均衡性能方面比max-min和min-min算法有较大改善。主要由于以下原因:anmo-gtsa算法具有解决多个任务调度目标的最优解的能力,能在一定程度上平衡负载。而min-min算法中每个资源的负载极不平衡,主要原因在于该算法将执行时间最短的任务分配在负载最小的资源处理节点上,这导致执行时间长的任务分配到负载较大的资源处理节点上。
综上所述,本文提出的anmo-gtsa算法在不同的网格系统下都表现得较好,在处理执行
时间和费用这两个任务调度目标时,能使这两个目标同时达到最优,验证了anmo-gtsa算法的可行性和有效性。
图片图5anmo-gtsa、max-min和min-min在10个网格资源节点和100个任务数下的映射图
4结语
网格任务调度问题是网格计算中一个至关重要的问题,它的调度算法将直接影响到网格环境中任务执行的效率与结果。另外,传统的单目标任务调度方式无法有效地满足网格环境个体的多目标需求,必须有合理的管理模式和多目标调度算法才能充分地发挥网格的特性。
本文针对网格任务调度的特点提出了一个基于自适应邻域多目标网格任务调度模型;根据当代种群本身的情况,设计了一种基于自适应邻域多目标网格调度算法,该算法采用的自适应邻域的策略,改善了算法的性能;通过与max-min和min-min算法的对比实验表明，该算法在处理网格任务调度的多目标问题,表现出较优秀的效果,使用该算法处理网格任务调度问题,是一个有效的方法。
参考文献:
[1]都志辉, 陈渝, 刘鹏. 网格计算[m].北京:清华大学出版社,2002:3-16.
[2]maheswaran m, ali s, siegel h j, et al. dynamic matching and scheduling of a class of independent tasks onto heterogeneous computing systems [c]// hcw
99:
proceedings of the 8th heterogeneous computing workshop. washington, dc: ieee computer society, 1999:30-44.
[3]maheswaran m, ali s, siegel h j, et al. a comparison of dynamic strategies for mapping a class of independent tasks onto heterogeneous computing systems [r]. west lafayette, indiana: purdue university, school of electrical and computer engineering, 1999.
[4]wu m y, shu w, zhang h. segmented min-min: a static mapping algorithm for meta-tasks on heterogeneous computing systems [c]// proceedings of the 9th ieee heterogeneous computing workshop. washington, dc: ieee computer society, 2000:375-385.
[5]casanova h, legrand a, zagorodnov d, et al. heuristics for scheduling parameter sweep applications in grid environments [c]// proceedings of the 9th heterogeneous computing workshop. washington, dc: ieee computer society, 2000:349-363.
[6]王树鹏, 云晓春, 余翔湛. 基于生存性和makespan的多目标网格任务调度算法研究[j]. 通信学报, 2006, 27(2):43-45.
[7]乔付, 张国印, 刘忠艳. 基于多目标冲突度网格任务调度策略[j]. 计算机应用研究, 2009,26(4):1491-1493.
[8]deb k, pratap a, agarwal s, et al. a fast and elitist multiobjective genetic
algorithm: nsga-ⅱ[j]. ieee transactions on evolutionary computation, 2002, 6(2): 182-197.
[9]薛胜军, 杨明. 一种新的自适应邻域的多目标进化算法[j]. 计算机工程与应用， 2011,47(25):49-53.
[10]maheswaran m, ali s, siegel h j, et al. dynamic mapping of a class of independent tasks onto heterogeneous computing systems [j]. journal of parallel and distributed computing, 1999, 59(2):107-131.
