费用-时间优化的网格有向无环图调度算法  

A Grid DAG Scheduling Algorithm for Cost-Time Optimization

作　　者：陈宏伟[1] 王汝传[1] 

机构地区：[1]南京邮电大学计算机科学与技术系,江苏南京210003

出　　处：《电子学报》2005年第8期1375-1380,共6页Acta Electronica Sinica

基　　金：国家自然科学基金(No.60173037;No.70271050);江苏省自然科学基金和江苏省自然科学基金预研项目(No.BK2004218);江苏省高技术研究计划(No.BG2004004);江苏省计算机信息处理技术重点实验室基金(No.kjs04)

摘　　要：网格环境下,基于时间限制和费用最小的有向无环图(DAG)调度算法运用经济规律把网格用户中的任务映射到网格资源中运行,弥补了BuyyaR提出的算法中未考虑任务运行的优先关系.该算法有两个关键技术:DAG中有效路径的提取能够定位任务何时在资源上运行;DAG中在作业运行时间尽可能允许的情况下,把任务映射到价格便宜的资源上运行.通过仿真实例,论证了该算法的优越性.The Directed Acychc Graph（DAG） scheduling algorithm, based on time-constrained and minimum-cost in grid environment, applies economic law to map the running tasks of grid users into grid resources. The proposed algorithm overcomes the deficiency of Buyya R＇s algorithm, which is not concerned with priority relationship between running tasks. It is highlighted in two key techniques ： one is that the extraction of valid paths from DAG can effectively locate tasks in specific resources during specific periods; the other one is that tasks should be mapped into cheap resources so that they can be run as much as possible with the restriction of job-running time. A simulative example based on the algorithm is also provided to analyse the characteristics of the algorithm.

关 键 词：网格调度 有向无环图 费用-时间优化 

分 类 号：TP393.02[自动化与计算机技术—计算机应用技术]