Research on DAG parallel task scheduling problem based on ?quantum-behaved particle swarm optimization
ZHANG Cong,SHEN Hui-zhang
(Antai College of Economics & Management, Shanghai Jiaotong University, Shanghai 200052, China)
Abstract:Task scheduling is one of the important problems in parallel computing system.This paper proposed a quantum-?behaved particle swarm optimization algorithm for task scheduling based on directed acyclic graph.First redefined the parallel task scheduling problem and its aim.Then discussed the representation of the encoding, the procedure of the decoding, the computational method of position vector, the continuative of the discrete problem and the structure of the algorithm respectively.In the end,presented the algorithm simulation,experiment result analysis and the conclusions.The simulation results show that this algorithm has better global optimizing ability and more rapid convergence, and it is superior to genetic algorithm and particle swarm optimization algorithm.
Key words:task scheduling; quantum-behaved particle swarm optimization(QPSO); directed acyclic graph(DAG)
网络并行计算环境下的任务调度问题是指在一定约束条件下,如何将一组任务分配到多台处理机上执行的组合优化问题,其已被证明是NP完全问题,不可能在多项式时间内找到问题的最优解[1,2]。目前常见的并行任务调度问题按照任务之间有无数据依赖关系可以划分为独立任务调度和依赖关系任务调度。前者在调度任务时不需要考虑任务之间的数据依赖关系;而后者通常用有向无环图(DAG)表示任务之间的数据依赖关系,在调度过程中满足任务之间的数据依赖关系。依赖关系任务调度的求解优化过程比独立任务调度的要复杂许多,且其适用范围也更广。以DAG表示的并行任务模型的研究得到了广泛关注和迅速发展。近年出现的一些启发式算法(如模拟退火算法、遗传算法等)为求解此类NP完全问题提供了新的途径[3~5],但是这些算法有些复杂性太高难以实现,有些实现起来太费时,所以有必要寻求更好的算法来解决此问题。
粒子群优化(PSO)算法是由Kennedy等人[6]提出的一种源于对鸟群捕食行为模拟的进化计算技术,已成为进化计算的一个最吸引人的分支。与遗传算法类似,PSO是一种基于迭代的优化方法,系统初始化为一组随机解,通过迭代搜寻最优值,但是在许多实际应用领域,更胜于遗传算法,尤其是在非线性优化问题上。量子粒子群优化(QPSO)算法是在传统的PSO基础上提出的一种新型的具有高效率全局搜索能力的进化算法[7,8]。它主要是引入量子物理的思想改进了PSO的进化方法,即更新粒子位置的方法;在更新粒子位置时重点考虑各个粒子的当前局部最优位置信息和全局最优位置信息。QPSO具有调整参数少、容易实现、收敛能力强等优势。为适应任务分配问题的求解,本文设计出合适的粒子编码,利用改进的量子粒子群算法求解任务分配问题,并与其他算法相比较。实验结果表明,本文提出的算法可以获得质量更高的解职称论文。
1 问题描述
本模型的计算系统由一系列异构的处理机组成,需要处理的总任务已分解成一系列子任务。模型的约束条件为:任务执行具有非抢占性,即处理机只有在执行完某个任务之后才能处理另外一个任务;另外这些任务之间具有前驱后继的数据依赖关系,某个子任务只有在其所有的前驱任务处理完毕后才能开始执行。该模型的调度目标就是要使得整个DAG图的调度长度最短。
为了便于分析问题,可以用下列五元组表述:
Π=(P,G,Θ,Ψ,Ω)
由表1、2和算法的静态性能曲线可以得出:
a)在任务数较多、处理机较多的情况下,PSO与本文QPSO算法的收敛速度比文献[3]算法快很多,但与文献[4]算法比较时,PSO算法的收敛速度明显比文献[4]算法快,本文QPSO算法则与文献[4]算法相当;而在任务数少的情况下,除文献[3]算法稍慢,其他算法相差不大。
b)本文QPSO算法能找到的最优解比文献[3,4]算法有明显的提高,尤其是子任务数较多、处理机数较多时。
c)PSO与本文QPSO算法比较时,发现QPSO算法的收敛速度比PSO算法慢,但得到的最优解比PSO算法好。
这是因为:首先,本文对问题的编码能够覆盖整个解空间,相对来说文献[3,4]的算法只能从一个相对较小的空间内搜索;其次,本文采用了离散空间到连续空间的转换过程,它不仅满足了QPSO算法对待解问题的取值要求,还在一定程度上能更好地保护与遗传优良的解片段。另外,PSO算法收敛过快,而QPSO的量子搜索方式对传统的PSO算法有了很大的改进,实验证明可防止早熟。
5 结束语
基于DAG的并行任务调度问题是NP难问题,传统的优化算法很难求得全局最优解,虽然已有人将遗传算法应用于此问题,但结果有待进一步改善。本文给出了新的问题定义,对QPSO算法作出调整与改进,编码表示采用了适合于任务调度问题的优先规则与处理机分配相结合的形式,并将离散空间优化问题转换为连续空间优化问题,使得QPSO有较好的搜索能力。最后通过仿真实验得到的一系列数据,表明了本文的改进QPSO算法比遗传算法和PSO算法有更好的性能,并有理由认为,合理的编码表示与高效的搜索策略相结合是任务分配调度问题全局寻优的有效途径。
参考文献:
[1]
GRAY M R,JOHNSON D S.Computers and intractability:a guide to the theory of NP-completeness[M].New York:W.H.Freeman and Co.,1979.
[2]AHMAD I,KWORK Y K.On parallelizing the multiprocessor scheduling problem[J].IEEE Trans on Parallel and Distributed Systems,1999,10(4):414-432.
[3]HOU E S H,ANSARI N,HONG Ren.A genetic algorithm for multiprocessor scheduling[J].IEEE Trans on Parallel and Distributed Syetems,1994,5(2):113-120.
[4]钟求喜,谢涛,陈火旺.基于遗传算法的任务分配与调度[J].计算机研究与发展,2000,37(10):1197-1203.
[5]张聪,马义忠.异构计算系统中基于遗传算法的任务分配与调度[J].微电子学与计算机,2004,21(6): 74-78.
[6]KENNEDY J,EBERHART R C.Particle swarm optimization[C]//Proc of IEEE International Conference on Neural Networks.Pisca-?taway:IEEE Press,1995:1942-1948.
[7]SUN Jun,FENG Bin,XU Wen-bo.Particle swarm optimization with particles having quantum behavior[C]//Proc of Congress on Evolutionary Computation. 2004: 325-331.
[8]SUN Jun,XU Wen-bo,FENG Bin.A global search strategy of quantum behaved particle swarm optimization[C]//Proc of IEEE Conference on Cybernetics and Intelligent Systems. 2004: 111-116.