基于量子粒子群优化的DAG并行任务调度探讨

  对于每个即将毕业的人来说,毕业论文是不断找资料,然后不断修改的时光。下面YJBYS小编为大家整理了一篇计算机网络毕业论文,同时也希望毕业生们能够顺利写完毕业论文哦!

  摘 要:任务调度是网络并行计算系统的核心问题之一。在有向无环图(DAG)描述问题的基础上,提出了一种进行并行任务调度的量子粒子群优化算法。首先对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)步,直到满足迭代的次数。

相关推荐