DAG任务模型的粒子群优化调度算法  

PSO schedule algorithm for DAG task model

作　　者：陈养平[1] 王来雄[1] 黄士坦[1] 

机构地区：[1]西安微电子技术研究所,陕西西安710075

出　　处：《武汉大学学报（工学版）》2007年第2期129-132,138,共5页Engineering Journal of Wuhan University

基　　金：航天"十五"预研基金资助项目(编号:413160203)

摘　　要：在并行多处理器系统中,通常用有向无环图(DAG)表示任务之间的依赖关系.为了提高该任务模型调度算法的性能,基于粒子群优化算法,提出一种新的调度算法.算法将任务高度和粒子位置作为任务优先级,使用表调度策略生成有效的调度方案,在满足任务间依赖关系的条件下,使所有任务的完成时间最小.仿真实验结果表明,与遗传算法相比,所提出的算法提高了解的质量和收敛速度,特别适合于规模较大的多处理器任务调度.The directed acyclic graph（DAG） is app ied to the parallel multiprocessor system to present the dependence relationship between tasks. A novel task scheduling algorithm is proposed based on particle swarm optimization（PSO）so as to enhance the performance of task scheduling approach in multiprocessor system. It tasks the task height and the particle position as the task priority value, and applies the list scheduling technique to obtain a feasible schedule so that task precedence relationships are satisfied and the total execution time of all tasks is minimized. Simulation results demonstrate that the proposed algorithm, compared with the genetic algorithms, increases both in terms of the the quality of solution and converge speed and especially fits to solve multiprocessor scheduling problem with a number of tasks and processors.

关 键 词：粒子群优化算法 表启发式技术 多处理器系统 任务调度 

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