摘 要:任务调度是网络并行计算系统的核心问题之一。在有向无环图(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),重新计算,直到终止条件满足。
3 基于QPSO的DAG并行任务调度
3.1 编码与解码
任务调度的常见编码包括基于任务的编码、基于操作的编码和基于优先规则的编码等。由于DAG并行任务调度的复杂性,采用任一种上述编码形式均无法保证所有解的合法性,这将浪费大量的求解时间。本文设计了一种复合的编码方案:编码长度为2 m,可描述为两个向量,第一个向量采用基于优先规则的编码方式,为一个包含m维的向量(R?1,R?2,…,R?m)。其中R?i表示在算法迭代过程中第i次迭代时发生的冲突利用优先规则R?i消除。本文选择了五种优先规则,包括最短执行时间(SPT)、最长执行时间(LPT)、最早开工时间(EST)、最早完工时间(EFT)、最晚完工时间(LFT),数字0、1、2、3、4分别对应优先规则SPT、LPT、EST、EFT、LFT。第二个向量是处理机分配向量,即一个包含m维的向量(M?1,M?2,…,M?m)。其中M?i表示编号为i的子任务被分配到编号为(M?i)的处理机上执行(所有处理机编号为0,1,…,n-1)。
在解码过程中,设t为调度的时间步,PS为调度列表。其中PS?t为第t步调度执行的子任务;TS为所有前驱已经被调度的子任务所构成的集合。解码算法如下:
a)令t=1,PS为空,TS由所有无前驱的子任务构成。
b)由TS中所有子任务编码,在处理机分配向量(M?1,?M?2,…,M?m)中找到分配给每个子任务的处理机,并在Θ中找到具体执行时间。
c)依据约束条件和执行时间,得到TS中每个子任务对应的指标时间(开工、完工或执行时间),由编码R?t所对应的优先规则选出一个子任务(如优先规则为最短执行时间,则选TS中执行时间最短的子任务,如果有多个子任务符合优先规则,则任选一个),该子任务就是PS?t,从TS中删除它,并将其加入PS的尾部。
d)逐个考察PS?t的后继子任务,如果该子任务无其他前驱,或其他前驱都已被调度执行,则将其加入TS中。
e)令t=t+1,若t 通过下面示例说明解码过程:
任务的DAG如图1所示。
优先规则向量:
(032140)
即:(SPT EFT EST LPT LFT SPT)
处理机分配向量:
(0 1 1 0 1 0)
即(P1 P2 P2 P1 P2 P1)
在Θ中查到的处理时间:
(2 4 6 5 3 7)
处理时间指1～6号子任务在对应处理机上的执行时间。
根据示例数据得到的调度列表PS为(T?1 T?2 T?4 T?6 T?3 T?5),甘特图如图2所示。
由上述编码方式和解码过程可知,本文编码能保证调度的可行性,且码长较短,无冗余,解码复杂性不高。
3.2 QPSO中向量的计算方法
对每个粒子,它的优先规则向量和处理机分配向量可以表示为Xpriority(1..m)和Xmachine(1..m),按式(5)~(7)计算这两个向量。由于前面所述的QPSO为连续空间算法,而DAG并行任务调度问题为整数规划问题,将离散优化转变成对实数向量的连续优化,具体过程如下:
a)将每个向量切断分成若干个子串,各段子串的长度可以相等,也可以不相等,子串形如(q?1,q?2,…,q?k)。
b)从整数组成的子串到实数作一个映射,可表示为
r=c×?ki=1q?i×b??k-i(9)
其中:r为映射的实数;c是常数,一般取足够小的实数,本文取值为0.01;b为基数,对于Xpriority,b取值为5,对于Xmachine,b取值为n。
c)在计算任务执行总时间前,需将r转换为子串,即式(9)的逆映射:
q?i=(rc-?i-1j=1q?j×b??k-j)div b??k-i(10)
其中:div为整除,得到的商q?i为整数,在实际运算时,可用一个循环,i从1~k得到子串中所有分量。
例如9个子任务的情况,Xpriority=(2 4 2 1 4 3 4 1 0),分为三段,各子串长度均为3。
子串 (242); (143); (410)
变换后得到
r0.720.481.05
经过迭代后的情况:
逆变换后得到
r0.531.120.91
子串(203)(422)(331)
在初始化时,可省掉式(9)的转换过程,直接给粒子位置赋实数。
解决了连续化问题之后,还有一个边界问题,如上例r的取值为[0,1.24],如迭代过程中z的运算结果超出范围时,将r值取在边界上。若r<0,取值0;r>1.24,取值1.24。
通过上述映射和逆映射,整数规划问题转换为连续优化问题,从而可以利用QPSO优化获得高质量的解。
3.3 算法流程
a)初始化粒子群,根据编码方案设定各粒子的随机位置。
b)根据式(10)将每个粒子的实数向量转换为整数向量。
c)对每个粒子的整数向量解码后,计算每个粒子的目标函数值。
d)更新每个粒子的局部最优值P?i。
e)更新粒子群的全局最优值P?g。
f)根据式(5)计算mbest。
g)根据式(6)计算每个粒子随机点PP?i。
h)根据式(7)更新每个粒子的新位置。
i)返回b)步,直到满足迭代的次数。
4 仿真实验与结果分析
4.1 实验参数选取
本文的仿真实验是在MATLAB软件上实现的。实验所用DAG图随机生成,每个任务节点有1～4个前驱与后继,估计运行时间θij为1～50 s的随机数。实验计算了文献[3,4]的算法、PSO与本文的QPSO共四种情况,算法中主要参数:种群大小为80,终止代数为1 500,amax取值1,amin取值0.5;PSO的惯性权重w与QPSO中的收缩扩张系数a取值相同,c?1和c?2均为2,编码、解码、连续化与边界问题均使用本文的方案;文献[3]算法的杂交概率为1.0,变异概率为0.05;文献[4]算法的内部杂交概率为0.8,迁移概率为0.2,演化策略中的参数为μ/λ=5。
4.2 计算结果与分析
对于随机生成的同一个DAG图,分别用上述四种算法进行计算,记录各算法收敛时得到的最优解的完成时间和收敛时的进化代数。计算结果如表1所示。为了消除数据随机性的影响,更好地反映算法的性能,表1中的进化代数是100次进化的平均收敛代数,完成时间是所有100次进化中得到的最优解的平均完成时间。图3为四个处理机100个子任务情况下四种算法分别进化的静态性能曲线,列出了各算法在不同进化代数时所找到的最优解。表2为四种算法在进化中能收敛到其最优解的次数占实验总次数的百分比。
表1 仿真实验结果
处理机?个数子任务?个数
完成时间/s
文献[3]?算法文献[4]?算法PSO?算法本文?算法
收敛时的进化代数
2528527127926539312529
250565543551538166131108125
1001 5481 4291 4271 416418339285323
2519318618817953463338
450457429428417194168135157
1001 1981 1361 1391 073516468323339
2515214113813473544952
850341297292281336217163212
1001 106911923875727621538601
表2 收敛到其已知最优解的次数占进化总次数的百分比%
各算法子任务个数25子任务个数50子任务个数100
文献[3]算法876448
文献[4]算法969281
PSO算法928967
本文算法1009996
由表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.
