树型网格下独立任务的实用调度算法

Practical Scheduling Algorithm of Independent Tasks on Tree-Based Grid

讨论了节点计算能力和网络通信速度异构的树型网格下独立任务的调度问题.与最小化任务总执行时间不同,文中提出了树型网格平台任务调度问题的一种修正的整数线性规划模型,为解决多层树通过线性规划模型求解最优任务分配数时时间复杂性大的问题,引入推拉方法,将多层树线性规划求解归结为单层树求解,使得求解过程的复杂性大大降低.基于求出的近似最优任务分配数,提出一个静态分布式的启发式任务调度算法.分析和实验表明,在异构的树型网格下进行大量的独立任务调度时,算法性能优于同类算法.

In this paper, the scheduling of independent tasks on the tree-based grid where resources have different computation and communication speeds is discussed. In contrast to minimizing the total execution time of tasks, this paper proposes an improved integral linear planning model. In order to overcome the time complexity when calculating the optimal number of tasks assigned to each node of the multi-level tree, the Push-Pull method is adopted to transform the linear planning of multi-level tree into a single-level one, thus greatly reducing the time complexity. Moreover, according to the calculated approximate number of the assigned optimal tasks, a static distributed heuristic task scheduling algorithm is put forward. Analytical and experimental results show that the proposed algorithm has better performance than other ones in the condition of scheduling lots of independent tasks on heterogeneous tree-based grid.