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

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

现有多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.