基于赋权有向超图的云计算依赖任务调度研究  

Research of dependent task schedule of cloud computing based on weighted directed hypergraph

作　　者：孙凌宇[1] 冷明[1,2] 朱平[1] 李金忠[1] 

机构地区：[1]井冈山大学计算机科学系,江西吉安343009 [2]加州大学洛杉矶分校电子工程系,美国加利福尼亚州90095

出　　处：《计算机工程与应用》2015年第24期34-39,共6页Computer Engineering and Applications

基　　金：国家自然科学基金(No.61363014;No.61163062;No.61063007);江西省青年科学家培养对象计划(No.20153BCB23003);江西省科技厅支撑项目(No.20132BBE50048);江西省自然科学基金(No.20132BAB201035);江西省教育厅科学技术研究项目(No.GJJ13540;No.GJJ12474);流域生态与地理环境监测国家测绘地理信息局重点实验室资助课题

摘　　要：如何对依赖任务进行高效合理的调度是云计算急需解决的关键问题之一。对云计算环境下的依赖任务调度系统进行了形式化描述。采用赋权有向无环超图来构造依赖任务调度问题的数学模型,结点对应于依赖任务,有向超边对应于任务之间的执行先后依赖关系。将云计算依赖任务调度问题转换为赋权有向超图的优化划分问题,提出了基于多水平方法和赋权有向超图的依赖任务划分优化算法。设计并实现了基于多水平方法的云计算依赖任务调度原型系统。在Cloud Sim云计算仿真实验平台下,与Min-Min算法、Max-Min算法进行了对比实验,实验数据对比表明该算法在减少依赖任务执行时间的同时,优化了资源负载均衡性能。How to schedule dependent task efficiently is the key issue in cloud computing environment. The formal description of dependent task scheduler in cloud computing is presented. This paper adopts the weighted directed acyclic hypergraph as the mathematical model of the dependent task scheduling problem in cloud computing, whose vertex can be considered as the dependent task and directed hyperedge can be represented as the priority dependency among the tasks.Furthermore, it transforms the dependent task scheduling problem to the hypergraph partition problem and proposes the task partitioning algorithm based on the multilevel method and the weighted directed hypergraph. It also designs and implements the prototype system of the cloud computing dependent tasks schedule based on the multilevel method. It carries out the comparative experiments among the Min-Min algorithm, Max-Min algorithm and the proposed algorithm based on Cloud Sim simulation platform of cloud computing. The experiment and analysis show the proposed algorithm has better performance in terms of decreasing the task completing time and the improvement of resource load balancing.

关 键 词：云计算 任务调度 赋权有向超图 多水平方法 优化算法 

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