1、基于量子粒子群优化的 DAG 并行任务调度探讨摘 要:任务调度是网络并行计算系统的核心问题之一。在有向无环图(DAG)描述问题的基础上,提出了一种进行并行任务调度的量子粒子群优化算法。首先对 DAG 并行任务调度问题作出定义,并给出了优化问题的目标;然后分别探讨了问题的编码表示、解码方案、位置向量的计算方法、离散问题连续化、算法的总体流程等;最后给出算法的仿真实验情况与研究,实验结果表明,该算法有良好的全局寻优性能和快捷的收敛速度,调度效果优于遗传算法和粒子群优化算法。 关键词:任务调度;量子粒子群优化;有向无环图?Research on DAG parallel task schedulin
2、g 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
3、-?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 cont
4、inuative 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 sup
5、erior 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。目前常见的并行任务调度问题按照任务之间有无数据依赖关系可以划分为独立
6、任务调度和依赖关系任务调度。前者在调度任务时不需要考虑任务之间的数据依赖关系;而后者通常用有向无环图(DAG)表示任务之间的数据依赖关系,在调度过程中满足任务之间的数据依赖关系。依赖关系任务调度的求解优化过程比独立任务调度的要复杂许多,且其适用范围也更广。以 DAG 表示的并行任务模型的研究得到了广泛关注和迅速发展。近年出现的一些启发式算法(如模拟退火算法、遗传算法等)为求解此类 NP 完全问题提供了新的途径35,但是这些算法有些复杂性太高难以实现,有些实现起来太费时,所以有必要寻求更好的算法来解决此问题。 粒子群优化(PSO)算法是由 Kennedy 等人6提出的一种源于对鸟群捕食行为模拟的
7、进化计算技术,已成为进化计算的一个最吸引人的分支。与遗传算法类似,PSO 是一种基于迭代的优化方法,系统初始化为一组随机解,通过迭代搜寻最优值,但是在许多实际应用领域,更胜于遗传算法,尤其是在非线性优化问题上。量子粒子群优化(QPSO)算法是在传统的 PSO基础上提出的一种新型的具有高效率全局搜索能力的进化算法7,8。它主要是引入量子物理的思想改进了 PSO 的进化方法,即更新粒子位置的方法;在更新粒子位置时重点考虑各个粒子的当前局部最优位置信息和全局最优位置信息。QPSO 具有调整参数少、容易实现、收敛能力强等优势。为适应任务分配问题的求解,本文设计出合适的粒子编码,利用改进的量子粒子群算法
8、求解任务分配问题,并与其他算法相比较。实验结果表明,本文提出的算法可以获得质量更高的解职称论文。 1 问题描述 本模型的计算系统由一系列异构的处理机组成,需要处理的总任务已分解成一系列子任务。模型的约束条件为:任务执行具有非抢占性,即处理机只有在执行完某个任务之后才能处理另外一个任务;另外这些任务之间具有前驱后继的数据依赖关系,某个子任务只有在其所有的前驱任务处理完毕后才能开始执行。该模型的调度目标就是要使得整个 DAG 图的调度长度最短。 为了便于分析问题,可以用下列五元组表述: =(P,G,) 其中: P=P?1,P?2,P?n为 n 个处理机的集合。 G 是子任务集 T 的依赖关系图,它
9、通过 DAG 来表示各个子任务间的调度约束关系。G=(T,E),其中 T=T?1,T?2,T?m为 m 个子任务的集合,一个子任务 T?i 就是图 G 中的一个节点,E 是任务依赖关系图中的有向边集。T?i,T?jE(i,j=1,2,m),则表示在子任务 T?i 没有完成之前,任务 T?j 不能执行。这时称 T?i 为 T?j 的一个前驱,T?j 为 T?i 的一个后继,E 可用邻接矩阵存储。 是一个 mn 矩阵,其元素 ij 表示任务 T?i 在处理机 P?j 上的执行时间,假设每个任务的执行时间预知(i=1,2,m;?j=1,2,n)。 是一个 mm 矩阵,其元素 ij 表示任务 T?i
10、与 T?j 之间的数据传输延时(i,j=1,2,m),同时假设各处理机间的通信能力是相同的,且忽略网络拥塞,即传输的数据量是惟一影响 ij 大小的因素。 是一个 mn 的任务分配矩阵,其中 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 上执行,
11、那么子任务 T?i 在处理机 P?j 上的执行时间满足以下两式: St(T?i,P?j)=maxT?kPred(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?kPred(T?i)被分配到处理机?P?r 上。 根据式(1)(2)迭代计算,可得到所有子任务的结束执行时刻。设 (S)为在调度策略
12、 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),其飞行速度记
13、为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
14、是惯性权重,动态调整惯性权重以平衡收敛的全局性和收敛速度;c?1 和 c?2 为加速常数,通常在 02 取值,c?1 调节粒子飞向自身最好位置方向的步长,c?2 调节粒子飞向全局最好位置方向的步长;r1,d(t),r2,d(t)U(0,1),且 d =1,2,n。为了减少在进化过程中粒子离开搜索空间的可能性,粒子的每一维速度被限定在-Vmax,Vmax内。 2.2 QPSO 算法 Sun 等人从量子力学的角度,通过对粒子收敛行为的研究,基于粒子群算法提出了一种新的算法模型量子粒子群(QPSO)算法。在该算法中,由于粒子满足聚集态的性质完全不同,使粒子在整个可行解空间中进行搜索寻求全局最优解,因
15、而 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=PPija|mbest?j-xij|ln(1/u),u=rand(7) 其中:mbest 是粒子群 pbest 的中间位置;Pij 为粒子本身所找到的最优解 pbest;Pgj 为整个粒子群目前找到的最优解 gbest; PP
16、ij 为 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)(以一定
17、的概率取加或减)更新每个粒子的新位置。 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消除。本文
18、选择了五种优先规则,包括最短执行时间(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=
19、1,PS 为空,TS 由所有无前驱的子任务构成。 b)由 TS 中所有子任务编码,在处理机分配向量(M?1,?M?2,M?m)中找到分配给每个子任务的处理机,并在 中找到具体执行时间。 c)依据约束条件和执行时间,得到 TS 中每个子任务对应的指标时间(开工、完工或执行时间),由编码 R?t 所对应的优先规则选出一个子任务(如优先规则为最短执行时间,则选 TS 中执行时间最短的子任务,如果有多个子任务符合优先规则,则任选一个),该子任务就是 PS?t,从 TS 中删除它,并将其加入 PS 的尾部。 d)逐个考察 PS?t 的后继子任务,如果该子任务无其他前驱,或其他前驱都已被调度执行,则将其加
20、入 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) 处理时间指 16 号子任务在对应处理机上的执行时间。 根据示例数据得到的调度列表 PS 为(T?1 T?2 T?4 T?6 T?3 T?5),甘特图如图 2 所示。 由上述编码方式和解码过程可知,本文编码能保证调度的可行性,且码长较短,无冗余,解码复杂性不高。 3
21、.2 QPSO 中向量的计算方法 对每个粒子,它的优先规则向量和处理机分配向量可以表示为Xpriority(1.m)和 Xmachine(1.m),按式(5)(7)计算这两个向量。由于前面所述的 QPSO 为连续空间算法,而 DAG 并行任务调度问题为整数规划问题,将离散优化转变成对实数向量的连续优化,具体过程如下:a)将每个向量切断分成若干个子串,各段子串的长度可以相等,也可以不相等,子串形如(q?1,q?2,q?k)。 b)从整数组成的子串到实数作一个映射,可表示为 r=c?ki=1q?ib?k-i(9) 其中:r 为映射的实数;c 是常数,一般取足够小的实数,本文取值为0.01;b 为基数,对于 Xpriority,b 取值为 5,对于 Xmachine,b 取值为 n。 c)在计算任务执行总时间前,需将 r 转换为子串,即式(9)的逆映射: q?i=(rc-?i-1j=1q?jb?k-j)div b?k-i(10) 其中:div 为整除,得到的商 q?i 为整数,在实际运算时,可用一个循环,i从 1k 得到子串中所有分量。
