返回首页
当前位置: 主页 > 互联网技术 > 网格计算 >

网格计算中一种改进的启发式任务调度算法

时间:2014-10-04 00:08来源:电脑教程学习网 www.etwiki.cn 编辑:admin

摘要:网格计算技术是上个世纪90年代出现的新兴研究领域。网格系统由异构的资源组成。网格计算中,一个好的任务调度算法不但要考虑所有任务的makespan,使其值尽量小,同样要考虑到整个系统机器间的负载平衡问题。文章对异构计算环境下的元任务调度算法进行了分析,针对Min-min算法可能引发的负载不平衡问题,结合网格计算环境的特点,提出了一种适用于网格计算环境中的任务调度算法。

关键词:网格计算;任务调度;映射;完成时间;负载平衡

 

 


1 引言

 

互联网技术的发展,硬件技术和通信技术的进步共同加快了计算机领域的进步。20世纪80年代出现了并行计算,支持同步的算法、程序和体系结构的开发。随后出现了分布计算,它要求各个处理机之间能够协同计算,通过处理机间的通信共同解决问题。网格计算[1]技术的发展则迎合了21世纪并行与分布计算技术的发展趋势,它是以资源共享为目的,支持对可计算资源的远程和并发的访问,用高速网络连接的地理上分布的可计算资源所组成的一个具有单一系统映像的高性能计算和信息服务环境[2]。

网格资源包括计算资源、存储资源和通信资源。如何使用这些资源高效的完成计算任务是网格系统的研究重点之一。对于网格用户而言,它向网格系统提交任务,由网格调度程序按照某种调度策略把用户提交的任务分配给网格系统中的可用资源。

任务调度包括任务映射和调度两个方面。任务映射是逻辑地为每个任务匹配一个最合适的机器,以便最小化应用程序的执行时间或完成时间。任务调度则将任务传输到其映射的机器上运行。本文所讲的任务调度强调的是前者即任务到资源的映射。以最大完成时间(makespan)为优化目标的任务——资源映射一直以来都是NP完全问题[3],解决这类问题常用启发式算法。针对于异构计算环境中元任务的调度,动态启发式算法又分在在线模式和批模式启发。经典的算法如在线模式中的MET[4]、MCT[4]、SA[4,6]、OLB[4];批模式中的Min-min[4,5,6]、Max-min [4,5,6]、Suffrage[4]。

 

2 调度模型的建立

 

为了较好的描述网格计算中的任务调度问题,我们采用数学模型的方法进行形式化的描述。网格环境中资源的范围很广泛,它指加入到网格系统中、所有可被共享的资源。所到达的任务可能是计算型也可能是数据存储型。为了描述问题的简单,本文所指的任务包括两类子任务:计算子任务和数据传输子任务。计算子任务是该任务中需要消耗计算资源的部分;传输子任务代表获得计算所需输入的数据通信即该任务中需要消耗存储资源和通信资源的部分。不考虑任务之间的依赖性。有如下定义:

(1)参与调度的任务集合为T={t1,t2…tn},其中ti代表的是任务i。

(2)参与调度的异构机器集合为H={h1,h2…hm},其中hj代表的是机器j。

(3)定义任务ti在机器hj上的期望执行时间eij为机器hj在不考虑其它负载情况下执行任务ti所需要的时间。

(4)定义任务ti在机器hj上的期望完成时间cij为任务ti映射到机器hj上执行完的时间。

(5)定义机器hj的期望就绪时间为rj,则向量r存储了所有机器的期望就绪时间。

(6)据(3)(4)(5)的定义有cij=rj+eij。

(7)定义系统中有f个文件服务器或者数据仓库,S={s1,s2……sf}。

(8)定义矩阵data,dataij表示子任务vi向文件服务器或数据仓库sj存取数据所需要的数据传输时间。

 

3 算法描述

3.1 Min-min

Min-min算法是一种实现起来很简单的算法,算法的执行时间也很快,具有较好的makespan。该算法的目的是将大量的任务指派给不仅完成它最早,而且执行它最快的机器。算法的思想是首先映射小的任务,并且映射到执行快的机器上。执行过程为:计算要参与映射事件的任务集中每个任务在各个机器上的期望完成时间,找到每个任务的最早完成时间及其对应的机器;从中找出具有最小最早完成时间的任务,将该任务指派给获得它的机器;指派完成后,更新机器期望就绪时间并将已完成映射的任务从任务集合中删除。重复上面的过程,直到所有的任务都被映射完。该算法形式化描述如下:

T为所有未调度的任务的集合

① 判断任务集合T是否为空,不为空,执行②;否则跳到步骤⑦;

② 对于任务集中的所有任务,求出它们映射到所有可用机器上的最早完成时间cij;

③ 根据②的结果,找出最早完成时间最小的那个任务ti和所对应的机器hj;

④ 将任务ti映射到机器hj上;并将该任务从任务集合中删除;

⑤ 更新机器hj的期望就绪时间rj;

⑥ 更新其他任务在机器hj上的最早完成时间;回到①。

⑦ 此次映射事件结束,退出程序。

Min-min算法完成一次映射事件的时间复杂度为O(n2m),其中n为一次映射事件需要完成映射的任务总数,m为可用的机器总数。

3.2 Max-min

Max-min启发算法非常类似于上面提到的Min-min启发算法。同样要计算每一任务在任一可用机器上的最早完成时间。不同的是Max-max算法首先调度大任务。任务到资源的映射是选择最早完成时间最大的任务映射到所对应的机器上。时间复杂度同Min-min一样也为O(n2m),其中n为一次映射事件需要完成映射的任务总数,m为可用的机器总数。

在Min-min算法中,每次都是选择小任务映射到执行快的机器上,这种映射会使得更多的任务映射到某一台或几台机器上,从而使得整个网格系统中可用机器的负载不平衡。而Max-min算法同Min-min相反,它首先调度大的任务,一定程度上平衡负载。因此综合这两种算法的思想提出一种新的算法,该算法在对任务集合执行一次映射事件的过程中,会根据当前系统的负载平衡情况,动态的选择Min-min算法和Max-min算法中的一种来进行任务——资源的映射。在本文中,称这种改进的新算法为MM算法。

3.3 MM算法

MM算法的思想借鉴于SA(Switching Algorithm)算法,SA是异构计算环境下,用来对任务进行在线模式映射的一种启发式算法。

网格计算环境中,任一资源mi的期望就绪时间为ri,设所有机器的最大期望就绪时间为rmax,最小的期望就绪时间为rmin;设变量µ表示系统中机器间的负载平衡指数,µ=rmin/rmax,显然µ∈[0,1]。rmin=rmax=0,表明当前系统中所有机器都处于空闲状态,等待着任务的映射;µ=0,表明当前系统中存在处于空闲状态的机器;µ=1,表明当前系统中任务的分配基本处于平均状态。在算法中,为了轮回的调用Min-min和Max-min算法,设定了两个边界值rlow和rhigh。映射事件开始时,初始化变量µ=1。首先使用Min-min算法,当变量µ的值下降到rlow时,改用Max-min算法;当变量µ的值上升到rhigh时,在改用Min-min算法。如此轮回调用这两个启发式算法,直到此次映射事件结束。

------分隔线----------------------------
标签(Tag):网格计算
------分隔线----------------------------
推荐内容
猜你感兴趣