摘 要:任务调度是网络并行计算系统的核心问题之一。在有向无环图(DAG)描述问题的基础上，提出了一种进行并行任务调度的量子粒子群优化算法。首先对DAG并行任务调度问题作出定义，并给出了优化问题的目标;然后分别探讨了问题的编码表示、解码方案、位置向量的计算方法、离散问题连续化、算法的总体流程等;最后给出算法的仿真实验情况与研究，实验结果表明，该算法有良好的全局寻优性能和快捷的收敛速度，调度效果优于遗传算法和粒子群优化算法。
　　关键词:任务调度;量子粒子群优化;有向无环图?
　　
　　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，Θ，Ψ，Ω)
　　
　　其中:
　　P={P?1，P?2，…，P?n}为n个处理机的集合。
　　
　　G是子任务集T的依赖关系图，它通过DAG来表示各个子任务间的调度约束关系。G=(T，E)，其中T={T?1，T?2，…，T?m}为m个子任务的集合，一个子任务T?i就是图G中的一个节点，E是任务依赖关系图中的有向边集。〈T?i，T?j〉∈E(i，j=1，2，…，m)，则表示在子任务T?i没有完成之前，任务T?j不能执行。这时称T?i为T?j的一个前驱，T?j为T?i的一个后继，E可用邻接矩阵存储。
　　
　　Θ是一个m×n矩阵，其元素θij表示任务T?i在处理机P?j上的执行时间，假设每个任务的执行时间预知(i=1，2，…，m;?j=1，2，…，n)。
　　
　　Ψ是一个m×m矩阵，其元素ψij表示任务T?i与T?j之间的数据传输延时(i，j=1，2，…，m)，同时假设各处理机间的通信能力是相同的，且忽略网络拥塞，即传输的数据量是惟一影响ψij大小的因素。
　　Ω是一个m×n的任务分配矩阵，其中ωij=1表示T?i分配到处理机P?j上执行;否则ωij=0(i=1，2，…，m;j=1，2，…，n)。
　　要实现的目标是寻找一个分配调度策略，将m个子任务分配到n个处理机上，合理调度各个子任务的执行次序，使得各子任务在满足依赖关系图G的约束下，整个任务的完成时间最短。现假设某一合法的分配调度S，将T中的m个子任务分配到n个处理机上，其中子任务T?i被分配到处理机P?j上执行，那么子任务T?i在处理机P?j上的执行时间满足以下两式:
　　St(T?i，P?j)=maxT?k∈Pred(T?i)(Ft(T?k，P?r)+(1-ωkj)ψki)(1)
　　Ft(T?i，P?j)=St(T?i，P?j)+θij;i，k=1，2，…，m;j，r=1，2，…，n
　　(2)
　　
　　其中:St(T?i，P?j)和Ft(T?i，P?j)分别表示子任务T?i在处理机P?j上的开始执行时刻和结束执行时刻;Pred(T?i)表示子任务T?i的前驱节点集合，假设子任务T?k∈Pred(T?i)被分配到处理机?P?r上。
　　根据式(1)(2)迭代计算，可得到所有子任务的结束执行时刻。设Γ(S)为在调度策略S下完成任务所使用的总时间，那么:Γ(S)=max(Ft(T?i，P?j));?i=1，2，…，m;j=1，2，…，n。
　　任务调度目标就是min(Γ(S))?S，即寻找一个分配调度S，使得Γ(S)最小。
　　鉴于本文主要考虑任务调度问题，在不失问题一般性的情况下，可忽略数据传输延时，即在下文中可假设所有的ψij=0。
　　
　　2 算法
　　2.1 PSO算法
　　粒子群优化(PSO)算法是一种进化计算方法，是一种基于迭代的优化工具。该算法通过群体中各粒子间的合作与竞争来搜索全局最优点。
　　系统初始化为一组共n个随机解，通过迭代搜寻整个群体的最优值。粒子i的当前位置为x?i=(xi1，xi2，…，xid)，其飞行速度记为v?i=(vi1，vi2，…，vid)，在解空间中追随适应度最优的粒子进行搜索。在每一次迭代中， 粒子通过跟踪两个“极值”来更新自己:a)每个粒子本身所找到的最优解pbest。如果粒子当前位置对应的适应度小于pbest的适应度，则pbest更新为当前位置。b)整个种群从起始到目前所找到的最优解gbest。每个粒子按以下两个公式进行动态进化，调整粒子的位置:
　　vi，d(t+1)=wvi，d(t)+c?1r1，d(t)(pbest?i，d-xi，d(t))+?c?2r2，d(t)(gbest?d(t)-xi，d(t))(3)
　　x?i(t+1)=x?i(t)+v?i(t+1)(4)
　　
　　其中:w是惯性权重，动态调整惯性权重以平衡收敛的全局性和收敛速度;c?1和c?2为加速常数，通常在0～2取值，c?1调节粒子飞向自身最好位置方向的步长，c?2调节粒子飞向全局最好位置方向的步长;r1，d(t)，r2，d(t)～U(0，1)，且d =1，2，…，n。为了减少在进化过程中粒子离开搜索空间的可能性，粒子的每一维速度被限定在[-Vmax，Vmax]内。
　　2.2 QPSO算法
　　`Sun等人从量子力学的角度，通过对粒子收敛行为的研究，基于粒子群算法提出了一种新的算法模型——量子粒子群(QPSO)算法。在该算法中，由于粒子满足聚集态的性质完全不同，使粒子在整个可行解空间中进行搜索寻求全局最优解，因而QPSO算法在搜索能力上远远优于所有已开发的PSO算法。
　　
　　QPSO算法参数个数少，进化方程的形式更加简单，更容易控制。在QPSO算法中，每一个粒子必须收敛于各自的随机点P?i，粒子按照下面的三式移动:
　　
　　mbest=1m?mi=1P?i=(1m?mi=1Pi1，…，1m?mi=1Pij)(5)
　　PPij=fPij+(1-f)Pgj， f=rand(6)
　　xij=PPij±a|mbest?j-xij|ln(1/u)，u=rand(7)
　　
　　其中:mbest是粒子群pbest的中间位置;Pij为粒子本身所找到的最优解pbest;Pgj为整个粒子群目前找到的最优解gbest; PPij为Pij与Pgj之间的随机点;a为QPSO的收缩扩张系数，它是QPSO收敛的一个重要参数，第t次迭代时一般可取
　　
　　a=amax-t(amax-amin)/tmax(8)
　　
　　其中:tmax是迭代的最大次数，amax与amin分别是最大和最小系数。QPSO的算法流程如下:
　　a)迭代次数t=0，对种群的每个粒子的位置向量进行初始化。
　　b)根据目标函数计算每个粒子的目标函数值。
　　c)更新每个粒子的新局部最优位置P?i。
　　d)更新粒子群的全局最优位置P?g。
　　e)根据式(5)计算mbest。
　　f)根据式(6)计算每个粒子随机点PP?i。
　　g)根据式(7)(以一定的概率取加或减)更新每个粒子的新位置。
　　h)令t=t+1，返回到b)，重新计算，直到终止条件满足。