同构计算环境中DAG任务图的调度算法

Task scheduling algorithm for DAG graphs in homogenous computing environments

在并行多处理机系统中,任务调度算法是保证整个系统性能的关键。通常用有向无环图(DAG)表示任务间的依赖关系。将粒子群算法应用于组合优化领域,构造了求解任务调度问题的离散粒子群算法。算法采用基于分组的思想对粒子进行直接编码,借鉴遗传算法的思想,将粒子个体最优及全局最优解分别采用交叉操作作用到当前粒子位置上,使粒子不断向最优位置逼近;同时在每次迭代过程中引入变异操作以提高粒子群体多样性。实验结果表明,算法在不同规模的任务调度问题中均取得了良好的效果。

The task scheduling algorithm has been the key to guarantee system performance in parallel multiprocessor systems. The directed acyclic graph （DAG） is always used for presenting the dependence relationship between tasks. A new task scheduling algorithm based on discrete particle swarm optimization （DPSO） is proposed, which brings another way in solving combinatorial optimization problems. The particles are represented as a vector by using direct coding method. With the illumination of genetic algorithms, the crossover operation is applied to change current situation of each particle with the local best and the global best solutions so that the particle flies towards the optimal solution quickly, while a mutation operation is also bring forward to improve the groups＇ diversity during each iteration. The experimental results show that the DPSO algorithm always obtains better performance in different-scaled task scheduling problems.