云计算环境下多DAG调度的资源分配进化算法  

Evolutionary algorithm towards resource allocation of concurrent scheduling multiple DAGs in clouds

作　　者：田国忠[1,2] 肖创柏[1] 赵娟娟[2] 

机构地区：[1]北京工业大学计算机学院,北京100124 [2]新疆工程学院计算机工程系,乌鲁木齐830091

出　　处：《计算机应用研究》2014年第9期2798-2802,共5页Application Research of Computers

基　　金：新疆维吾尔自治区自然科学基金资助项目(2013211A031)

摘　　要：现有多DAG调度研究主要在多个DAG共享资源调度的时间最小化、公平性最大化、吞吐量最大化等问题方面提出了相关的解决方案,然而,现有的方法还不能很好地解决云计算环境下多DAG共享资源调度的资源分配优化问题。为此,首先分析讨论了一组多DAG共享云计算资源调度中的多DAG数量、属性结构分布特点与资源需求量之间的关系,并在此基础上提出了基于资源需求强度预测变异方法的进化算法EFRD,有效地解决了云计算环境下多DAG共享资源调度的资源分配优化问题,既保证了多DAG的调度执行时间最小化,也避免了资源的浪费。实验表明,EFRD算法能够有效地收敛到最优解。The existing researches about scheduling multiple DAGs focused on some issues, such as makespan minimization, fairness maximization and throughput maximization, and proposed the related solution. However, there are so far no methods for optimization of resource allocation for scheduling multiple DAGs in clouds. To the problem, this paper analyzed and dis- cussed the relationship among the number of DAGs, characteristics of DAG property, DAG structure and resource demand. And then, it proposed an evolutionary algorithm based on the forecasting of resource demand. The methods not only can mini- mize entire makespan of multiple DAGs, but also can avoid waste of resources. Last experiments demonstrate that, compared with the related method, this algorithm can effectively converges to the optimal solution.

关 键 词：云计算 有向无环图 多DAG调度 资源分配 调度长度 

分 类 号：TP311.5[自动化与计算机技术—计算机软件与理论] TP274[自动化与计算机技术—计算机科学与技术]