基于0-1互换算法的网格同构平台任务调度

姚东铌

(陕西学前师范学院 实验室与设备管理处， 陕西 西安　710100)



基于0-1互换算法的网格同构平台任务调度

姚东铌

(陕西学前师范学院 实验室与设备管理处， 陕西 西安710100)

摘要：网格计算及其衍生的云计算是近年来兴起的新技术，能够给人们提供一个高级、强大的计算服务和信息数据资源管理平台.网格的核心是资源共享，其核心问题之一就是任务调度，它直接决定了资源的有效利用.针对网格计算中同构计算平台下的独立任务的调度问题,采用局部搜索策略设计了一种基于0-1互换的调度算法，并使用MATLAB编写程序，对算法进行测试，结果表明该算法具有迭代次数少、调度效果好等优点.

关键词：网格计算； 同构平台； 任务调度； 0-1互换算法

0引言

网格是一种计算和数据管理的基础设施，能为各种社会活动提供信息化支持，它是一个高级、强大的计算服务和信息数据资源管理平台.网格中的资源具有分布性、共享性、自相似性、动态性、多样性、自治性与管理的多重性等特点.网格计算及其衍生的云计算是近年来兴起的新技术[1-3]，网格的核心是资源共享，其任务调度直接决定了资源的有效利用而成为网格计算最核心的问题之一[4].

网格任务调度负责引导用户提交任务并按照任务类型、所需资源及可用资源等情况安排运行日程和策略.任务调度根据任务的需求，首先发现满足条件的计算资源，然后从满足条件的计算资源中根据特定的算法策略选择一个合适的资源分配给任务.在网格环境中，任务和资源的数目都比较大，任务和资源之间的关系也相对复杂，因此任务调度问题[5,6]是一项繁复而困难的工作.研究人员常常会对任务模型、资源模型等进行若干假设的化繁为简.本文中将对同构计算平台下独立任务的调度算法进行研究与分析.

1算法思想

1.1问题定义

与同构相对的是异构，异构体现在网格中的计算资源是由若干处理机通过网络连接起来的，其处理机之间的类型和处理速度各不相同.类型异构的处理机结构过于复杂，现实的需求也不是很高，并且通过虚拟机制(比如Java虚拟机)可以在一定程度上解决处理机类型异构的问题，因此通常的任务调度不考虑类型异构.在此基础上，如果再假设任一独立任务在所有处理机上具有相同的计算时间，那么问题就简化为平台同构.

1.2基于0-1互换算法的任务调度

实际的调度中通常难以达到最优化结果，即任务调度的下界.然而从一个初始解开始，每一步通过最小化各个处理机上的任务负载，在当前邻域内寻找到一个更优解，使得各个处理机负载基本相同，从而得到更短的调度长度，实现目标函数逐步优化，直到不能进一步改进为止.上述过程是可以通过算法实现的.

图1　0-1互换算法的任务调度流程图

本文采用局部搜索[8-10]的策略，构建0-1互换算法(IC)对同构平台的独立任务调度问题进行研究，其流程图如图1所示.具体地，先利用LS算法[11,12]进行初始调度，将独立任务调度到处理机；然后寻找负载最大和最小的处理机并计算其负载的差值；如果负载最大的处理机上和负载最小的处理机上存在任务满足特定的交换条件：交换这两个任务能够减少调度长度，则将这两个任务交换；按照这样的策略对当前已调度的任务进行不断的调整以得到一个更优化的调度结果，直到处理机的负载平衡或者找不到满足交换条件的任务为止.完整的算法描述如下：

输入：

任务集T={t1,t2,…,tn};处理机P={p1,p2,…,pm};

输出：

Initial_LS(P,T); //利用LS算法进行初始调度.

While(1)

{

//寻找负载最大和最小的处理机pmax和pmin

Lpmax=Lpmin=L(p1);pmax= pmin=p1;

For(i=2;i<=n;i++)

{

If(Lpmax

If(Lpmin>L(pi))then{Lpmin=L(pi);pmin=pi;}

}

//计算最大负载Lpmax与最小负载Lpmin差值

Diff=Lpmax-Lpmin;

If(Diff>Limit) then //预设阈值Limit

{

Flag=0；

//搜索负载最大的处理机pmax上的任务

For(i=1;i<= Num(pmax);i++)

{

Ti= pmax[i]; //pmax上的第i个任务

//搜索负载最小的处理机pmin上的任务

For(j=1;j<=Num(pmin);j++)

{

Tj= pmin[j]; //pmin上的第j个任务

Delta=Ti-Tj;

If(Delta>0 AND Delta

{

Flag=1; //满足交换条件

//将Ti和Tj交换，并修改相应的负载

pmax[i]=Tj;pmin[j]= Ti;

Break; //结束本轮循环搜索

}

}

}

//不满足交换条件，返回结果1

If(Flag==0) then Exit(1);

}

else

{

Exit(0); //负载已经平衡，返回结果0

}

}

在初始化阶段使用常见的LS算法进行初始化调度，由于后续任务调整阶段的存在，初始调度算法选择的基本思想是简单有效.

在任务调整阶段首先需要的问题是选择哪些处理机进行任务交换.这里采用选择负载最大和最小的处理机的策略；其次是选择哪些任务进行交换，这是算法的关键，基本原则是仅在两个任务的交换能够减少应用的完成时间时才对两个任务进行交换.算法中采用的条件是0

在循环过程中不断搜索负载最大和最小的处理机并比较其负载差值，若小于预先设定的阈值Limit则认为已经负载平衡.在上述的交换条件约束下，每次交换都会使得应用的完成时间严格缩短.通过多次循环，直到处理机的负载已经平衡或者不存在满足交换条件的任务时，算法终止.

2仿真结果

实验先通过一个例子说明算法的运行效果，然后通过比较对算法的调度质量进行分析，最后对算法时间性能进行分析.实验使用MATLAB编写程序进行仿真，运行环境为处理器Intel Core2 Duo T6500主频2.1 GHz，内存2 GB，操作系统Windows XP.

例子：任务数n为50，处理机数m为5，任务集合 {56,23,62,8,46,92,14,44,84,79,41,96,16,40,76,27,93,58,92,58,25,99,61,12,63,50,25,11,9,91,46,89,55,17,59,70,59,47,15,19,13,40,59,48,71,56,80,56,56,43}.使用LS算法进行初始化调度，结果如表1所示，任务的初始调度长度为522.LS的初始调度负载很不均衡，最大的负载差值为39.

表1　LS的初始调度

表2　调整后的调度

基于IC算法的调度过程：第一次负载最重的处理机p3的负载为522，负载最轻的处理机p2的负载为483，差值为39.依次检查p2和p3的任务，发现任务t2=23和任务t11=41满足交换条件，将它们交换.第二次负载最重的处理机p1和负载最轻的处理机p2的负载差值为18，交换其上的任务t1=56和任务t11=41.第三次负载交换p1的任务t11=41和p4的任务t31=46.依照算法经过8次交换后得到的任务调度结果如表2所示，最大的负载差值已经降低至1，可见该算法是有效的.

我们再通过对比0-1互换算法(IC)和LS算法、BF(Bacterial Foraging)算法[13,14]的调度长度，可以评价算法的调度质量.这里使用平均负载作为参考值对算法得到的调度长度做归一化处理.归一化的结果值越小则表明算法得到的结果越接近平均负载，调度长度越小[15].对于正态分布的执行时间，其均值Lmin=100，方差为10，处理机数m=16，任务数为100到1 000，步长为100.结果如图2所示，可见相比于LS算法和BF算法， 0-1互换算法(IC) 在不同的任务个数下的调度长度最短，非常接近最优值，具有很好的调度质量.

图2　不同算法调度长度的比较

图3　IC算法迭代次数随处理机数的变化

图4　IC算法迭代次数随任务数的变化

迭代次数直接反应了算法的运行时间，可以用来分析算法的时间性能.下面对满足正态分布(均值为100，方差为10)的任务执行时间在不同任务数n和处理机数m下进行仿真实验并记录相应迭代次数.首先，当n分别为1 000、2 000和3 000时，随着m由4增加到24(步长为4)迭代次数逐步增加，如图3所示.其次，当m分别为4、12和24时，随着n由100增加到3 000(步长为100)迭代次数略有增加，且当任务数比较多时稳定在一个固定的迭代次数水平附近，如图4所示.对比图3和图4可以看出，本文中的IC算法迭代次数随处理器数增加而增长的较快，但随任务数增加而增长的不明显.因此对于需要在相对固定的硬件处理设备上执行大量计算任务时该算法是非常适用的.最后，在不同任务数n和处理机数m下进行了180次仿真实验，记录相应迭代次数，如图5所示，结果表明即使对于较大的任务数和处理器数，迭代次数都很少超过180，可见算法具有非常好的时间性能.

图5　IC算法迭代次数的变化

3结论

网格计算及其衍生的云计算是近年来兴起的新技术，其核心问题之一的任务调度决定了资源是否有效利用.0-1互换算法作为一种局部搜索调度算法，具有迭代次数少、调度效果好等优点.本文就网格计算中同构计算平台下的独立任务的调度问题设计了基于0-1互换的优化算法，并使用MATLAB编写了算法程序.仿真结果表明，该算法是可行的，并收到了良好的效果.

参考文献

[1] 都志辉,陈渝,刘鹏.网格计算[M].北京:清华大学出版社,2002.

[2] 胡引翠.网格计算技术的应用及其发展趋势[J].测绘通报,2005(3):23-26.

[3] 王义立,陈晓江,冯健,等.网格计算:现状与进展[J].微电子学与计算机,2006,23(10):181-183,186.

[4] 罗作民,张景,李军怀,等.网格计算及其关键技术综述[J].计算机工程与应用,2003,39(30):18-22.

[5] 许元飞.网格计算中任务调度算法的仿真研究[J].计算机仿真,2011,28(8):134-137.

[6] 崔玉宝,贾振华,侯志国,等.网格任务调度算法研究[J].微计算机信息,2006,22(15):109-111.

[7] 康一梅,郑应平.同等并行处理机上独立任务的调度[J].自动化学报,1997,23(1):81-84.

[8] 邹恒明.算法之道[M].北京:机械工业出版社,2010.

[9] 唐晋韬,王挺,王戟.适合复杂网络分析的最短路径近似算法[J].软件学报,2011,22(10):2 279-2 290.

[10] 陈涛.基于加速遗传算法的选择性支持向量机集成[J].计算机应用研究,2011,28(1):139-141.

[11] 李红英.机器有使用限制的两台同类机排序的在线LS 算法[J].华东理工大学学报(自然科学版),2006,32(9):1 134-1 137.

[12] 丁伟.速度相同的具有m-2台通用机的两组工件的LS算法分析[J].中山大学学报(自然科学版),2010,49(6):1-5.

[13] 周雅兰.细菌觅食优化算法的研究与应用[J].计算机工程与应用,2010,46(20):16-21.

[14] 朱云龙,陈瀚宁,申海.生物启发计算[M].北京:清华大学出版社,2013.

[15] 刘宴兵,尚明生,肖云鹏.网格高性能调度及资源管理技术[M].北京:科学出版社,2010.

Analysis of 0-1 interchange algorithm for task scheduling

in isomorphic platform of grid computing

YAO Dong-ni

( Department of Laboratory and Equipment Management, Shaanxi Xueqian Normal University, Xi′an 710100, China)

Abstract:Grid computing and cloud computing is booming at present,providing advanced and powerful computing services and information management platforms to the whole society.Task scheduling is one of the most important technologies of grid computing.The paper is to analyze the 0-1 interchange algorithm for task scheduling in isomorphic platform of grid computing.It contains choiceness of algorithm steps based on local search principle and building up test program in MATLAB for performance estimation,etc.Results of simulation show that the algorithm is effective and reliable.

Key words:grid computing； isomorphic platform； task scheduling； 0-1 interchange algorithm

中图分类号：TP393

文献标志码：A

文章编号：1000-5811(2015)02-0169-04

作者简介:姚东铌(1982-)，女，陕西西安人，工程师，研究方向：计算机数据挖掘技术、实验室管理

收稿日期:*2014-11-12 *2014-12-23