基于粒子群优化算法的异构多处理器任务调度  

Heterogeneous multiprocessor task scheduling based on PSO algorithm

作　　者：李静梅[1] 张博 

机构地区：[1]哈尔滨工程大学计算机科学与技术学院,黑龙江哈尔滨150001

出　　处：《计算机工程与设计》2013年第2期627-631,共5页Computer Engineering and Design

基　　金：国家自然科学基金项目(61003036;60873138);黑龙江省教育厅科学技术研究基金项目(12513048);黑龙江省自然科学基金项目(F201124)

摘　　要：为提高异构多处理器任务调度的执行效率,充分发挥多处理器并行性能,提出一种基于粒子群优化的异构多处理器任务调度算法—PSOASA算法。PSOASA算法以求得任务最短完成时间为目标,首先通过建立新的编码方式和粒子更新公式实现粒子搜索空间到离散空间的映射,使连续的粒子群优化算法适用于离散的异构多处理器任务调度问题,同时通过引入模拟退火算法,克服粒子群算法的"早熟"收敛现象,避免求得的解陷入局部最优。实验结果表明,PSOASA算法的执行效率优于目前广泛采用的遗传算法,有效地降低任务的执行时间,减少了迭代次数,适用于异构多处理器环境大规模任务调度。To improve efficiency implementation heterogeneous multiprocessor task scheduling, parallel performance multi pro cessors, a task scheduling method is proposed, which is based on particle swarm optimization algorithm named PSOASA. The aim of The scheduling algorithm is to achieve shortest activation time. First, particle search space is mapped to discrete space through the establishment of a new coding method and particle update formula, so the continuous particle swarm optimization al gorithm is applied to the discrete heterogeneous multiprocessor task scheduling problem, to overcome the particle swarm algo rithm ＂ premature＂ convergence phenomenon, simulated annealing algorithm is integrated to avoid the obtained solution into a local optimum. The experimental results show that the efficiency of PSOASA is superior to the genetic algorithm and reduce the task execution time and the number of iterations. It is suitable for heterogeneous multiprocessor environment.

关 键 词：异构多处理器 任务调度 PSO算法 模拟退火 遗传算法 

分 类 号：TP303[自动化与计算机技术—计算机系统结构]