基于动态关键路径的bnp调度算法

基于动态关键路径的bnp调度算法

1静态调度和bnp调度获得并行系统的性能的关键是对处理机器的有效规划。它将任务集T分布到处理机系统P上求解,满足任务之间的依赖关系,且使得调度长度最短。若并行任务的任务执行时间、任务依赖关系、通信时间和同步时间是预先知道的,则调度可以在编译时进行,称为静态调度。若分布式系统中的处理机数有限,则称为BNP调度问题。由于实际应用中,处理机数多是受限的,所以静态BNP调度问题是调度算法研究中的一个重要分支。2问题模型和相关工作首先对BNP调度模型及一些相关概念进行描述。2.1bnp调度算法的研究目标一个并行任务T由满足一定前趋约束的子任务集{T1,T2,Λ,Tν}组成,它可以用一个有向无环图G=(V,E)表示。其中V(|V|=ν)是节点集,对应着并行任务中的一个子任务,节点权量wi代表了任务Ti的运行时间,表示任务需用的单位执行时间(UnitExecutingTime,UET)数。E(|E|=e)是有向边集,表明了任务之间的偏序?关?系?和?通?信?时?间,即Ti→Tj表示只有在任务Ti完成之后,Tj才能开始,Ti称为Tj的直接前趋,Tj称为Ti的直接后继,或称Ti为有向边的尾,Tj为有向边的头。有向边上的权值ci,j表明了任务Ti传递数据给任务Tj所需的时间。但当Ti,Tj分配到同一个处理机上执行时,ci,j为0。另外,假设分布式系统P由n台同构的处理机P1,P2,Λ,Pn全互连组成,且网络同构。BNP调度算法的研究目标是:将并行任务T分布到P上求解,使得它们满足任务间的约束关系,同时使任务T的执行时间最短。定义1若并行任务T对应的任务图G=(V,E)中存在一条从子任务Ti到子任务Tj的路径,则称Ti为Tj的前趋,Tj为Ti的后继。定义2称任务图G=(V,E)中没有前趋的节点为入节点或就绪任务,没有后继的节点为出节点。定义3任务图的关键路径是图中任务节点和有向边的一个集合,它是任务图中从一个入节点到一个出节点的所有路径中节点计算量和有向边的通信开销之和最大的路径,简记为CP(critialpath),称关键路径上的任务为关键任务。2.2bnp调度算法众所周知,大多数情况下,有前趋约束的任务在多处理机上的调度是NP-完全问题,大多使用启发式算法进行求解,包括遗传调度、队列调度等。但基于算法复杂度和对任务图限制的考虑,其中最通用的是队列调度算法,它主要是重复以下过程直至所有的任务已被调度:①根据所有未调度节点的静态或动态优先级确定调度节点;②根据一定的准则为该调度节点分配处理机及相应的时间槽。现有的BNP队列调度算法有HLFET(highestlevelfirstwithestimatedtimes)、MCP(modifiedcriticalpath)、DLS(dynamic-levelscheduling)等调度算法。其中HLFET和MCP分别以节点的静态b-level值和ALAP(aslateaspossible)值作为节点的优先级,并为调度节点分配可最早执行它的处理机。而DLS采用了一种动态优先级的概念,它定义了任务-处理机对的动态层概念,每次调度时,对其中动态层值最大者进行调度,并将它分配给对应的处理机。由于采用了动态优先级的概念,因而它优于前两者,但其时间复杂度也因此高于HLFET的O(v2)和MCP的O(v2log2v)的时间复杂度,为O(nv3)。对上述3种算法进行分析,发现它们不能保证对影响算法性能的动态关键任务进行最早调度,从而有可能导致整个任务系统的完成时间被拖延(非动态关键任务已占用了时间槽,例子见第3节)。为克服上述算法中的缺点,进一步优化任务的调度长度,本文对BNP调度问题提出了一种新的启发式调度算法。该算法不同于队列调度算法——不需计算所有未调度任务的优先级,它基于任务图的动态关键路径,递归地确定调度任务,是第一个使用递归思想进行调度的算法。同时,它结合调度任务的后继任务,为其选择了最佳时间槽。3任务图12关键路径在调度算法中起着重要作用,任务优先级的确定常受限于它(如b-level值)。但由于任务之间通信开销的不确定性,故随着调度的进行,任务图的关键路径也随之改变。为此,我们提出动态关键路径的概念,它是针对调度过程中的剩余任务子图定义的。3.1动态关键路径的定义首先对任务图的概念进行扩充,允许它没有入节点,可以从一条边进入,相应地称这条没有尾节点的边为该任务图的入边,记作ϕ→Tj。其中ϕ是空节点,Tj是它的头节点。定义4定义任务图G=(V,E)的去掉某个入节点Ti或去掉某条入边的头节点Ti及所有以Ti为头的入边而剩余的G的子图为节点Ti关于G的剩余任务子图,记为GL(Ti,G),即GL(Ti,G)=(VL,EL),其中VL=V-{Ti},EL=E-{ϕ→Ti|ϕ→Ti∈E}。上述剩余任务子图的定义是相对于一个节点而言的,但它也同样适用于对节点集S={Ti1,Ti2,Λ,Til}定义剩余任务子图,即GL(S,G)=GL(Til,ΛGL(Ti2,GL(Ti1,G)))。显然,调度节点只能是任务图的入节点Ti或入边的头节点Ti(它的前趋已被调度),当节点Ti被调度后,我们称它对应的剩余任务子图中的关键路径为当前的关键路径(按定义3计算,但路径可以从一条入边起始,终止于一个出节点),此即提出的动态关键路径的概念。由于任务之间的通信开销也影响着任务的调度长度,因而我们在上述动态关键路径的定义中允许入边的存在。这也是本文的动态关键路径概念与一般定义的关键路径(按定义3计算)的不同之处。定义5对于任务图G=(V,E)来讲,定义其子任务Ti(∈V)的前趋任务子图是由G中Ti的所有前趋及它们之间的有向边组成的一个有向无环图,它是G的一个子图,且其节点权重和边权重与G中的对应节点和边保持一致。若将该前趋任务子图记为GP(Ti,G),则有GP(Ti,G)=(VP,EP),其中VP={Tj|Tj∈V且在G中Tj为Ti的前趋},EP={Tk→Tl|Tk→Tl∈E,Tk,Tl∈VP或Tk=ϕ,Tl∈VP或Tk∈VP,Tl=Ti}。对上述定义,为直观化,下面举一个简单的例子,如图1所示。3.2基于主要动态路径的序列并行规划算法调度算法的研究通常是确定两个准则,即选择调度节点的准则R1和为调度节点确定处理机的准则R2。下面分别对它们进行研究。3.2.1递归调度的思想由于关键路径在调度算法中的重要作用,因而,我们希望对当前动态关键路径上的第一个关键节点(称为动态关键任务)进行调度,但此时存在一个问题:该节点的前趋节点可能未被调度。如图1(b)所示,按关键节点调度的思想,当T1、T3被调度后,剩余任务子图中的第一个关键节点是T5,但此时它的前趋节点T2、T4未被调度。为此,我们提出递归调度的思想,即对该节点的前趋任务子图进行调度,递归地确定调度节点。具体算法描述如下。其中函数调用select-processor(Ti)实现为调度节点Ti选择处理机的功能。对它的算法实现,我们有如下考虑。3.2.2任务ts的最早调度和终止时间常用的处理机选择算法是为调度任务Ti选择可最早执行它的处理机。但对有通信开销的任务系统来讲,它不能有效地减少调度长度。如图2所示。从图2中可以看出,由于在对调度任务进行处理机分配时只考虑了它自身,没有考虑它的通信开销对后继任务的影响,因而有可能拖延整个任务系统。为此我们按如下方法对任务Ti进行调度。假设Tj为当前关键路径中Ti的直接后继节点。(1)若Tj=ϕ,则将Ti调度到可最早执行它的处理机上;(2)若Tj≠ϕ,则从各处理机上可最早开始Ti的n个时间槽内选择一个,使Tj具有最早开始时间(根据已调度直接前趋节点计算得到的开始时间)。显然,这种处理机选择算法避免了通信开销过大,有可能拖延任务完成时间这种情况的发生。对上述第(2)种情况,若逐个进行比较,则它的时间复杂度较高,为O(nv)。为此,本文提出了时间复杂度为O(v)的一个快速算法。为便于算法描述,首先定义如下参数(其中后4个参数是相对于某个任务TS定义的):task-proc[q]——任务Tq分配的处理机(q=1,2,Λ,ν);st-task[q]——任务Tq的开始执行时间(q=1,2,Λ,ν);st-proc[i]——处理机Pi的空闲起始时间(i=1,2,Λ,n);SPT[s]——任务TS的已调度直接前驱任务集,假设SPT[s]={Tm1,Tm2,Λ,Tml};SPP[s]——SPT[s]分配的处理机集,假设SPP[s]={Ps1,Ps2,Λ,Psb}(b≤l);et-task[q]——SPT[s]中任务Tq的包含通信开销cq,s的结束时间,即et-task[q]=st-task[q]+wq+cq,s,q=m1,m2,Λ,ml;et[q]——SPT[s]中分配到处理机Pq上的任务的et-task的最大值,即et[q]=max{et-task[m]|Tm∈SPT[i],且task-proc[m]=Pq}(q=s1,s2,Λ,sb)。实际上,et[q](q=s1,s2,Λ,sb)直接影响着任务TS的开始时间。当TS不被调度到处理机Pq上时,它的开始时间只能是等于或大于et[q]+1,这即是提出的快速算法的依据。首先,假设对调度任务Ti进行最早调度。假设它被调度在处理机Pk上,开始执行时间为st-task[i]。在对Ti进行最早调度后,我们假设对Tj也进行最早调度(由于通信开销的存在,只考虑将Tj调度在SPP[j]中(如式(1)所示)。且若有多个处理机同时取st-task[j],则选择处理机的st-proc最小者)。假设它被调度在处理机PS上,开始执行时间为st-task[j],它对应的et[q](q=j1,j2,Λ,jb)分别为et1[q],其中的第1、2、3个最大值分别为et1[j1],et1[j2],et1[j3],它的前驱任务Ti的包括通信开销ci,j的结束时间为et-task。提出的算法的实质即是在对Ti,Tj进行最早调度后,进一步根据et-task和st-task[j]的取值情况对任务Ti有可能使st-task[j]最小的调度位置进行比较,从中选取最佳者。①Pk≠Ps且et-task+1<st-task[j]这种情况下,对任务Ti的调度保持不变,st-task[j]已达到最小。②Pk≠Ps且et-task+1=st-task[j]此时,若k=j1,则令x=j2;若k=j2,则令x=j1;然后分别将Ti调度到处理机Ps,Px上可最早开始它的时间槽内,计算对应的st-task[j],取3种调度情况对应的st-task[j]最小者作为Ti的调度结果(相同值时,顺序为Pk,Ps,Px,即仍保证最早调度)。③Pk=Ps此种情况下,若k=j1,则令x=j2;若k≠j1,则令x=j1;然后将Ti调度到处理机Px上可最早开始它的时间槽内,计算对应的st-task[j],与已有的st-task[j]比较,取最小者。若值相同,则保持Ti的最早调度。对上述的调度调整过程,可证明如下定理。定理1在对任务Ti,Tj进行最早调度后,若进一步按上述①～③对Ti的调度进行选择,则Tj具有最早的开始时间。定理1的证明如下:证明假设对任务Tj,Tj进行最早调度后,某些参数定义如2.2.2节所述。实际上,st-task[j]可根据(1)式计算。st-task[j]=min{max{st-proc[j1],et[j2]+1},max{st-proc[q],et[j1]+1},q=j2,Λ,jb}(1)st−task[j]=min{max{st−proc[j1],et[j2]+1},max{st−proc[q],et[j1]+1},q=j2,Λ,jb}(1)假设在Ti被调度到处理机Pl(Pl∈SPP[j],Pl≠Pk)上后,对Tj进行最早调度。假设它对应的开始执行时间为st-task′[j],对应的et[q](q=j1,j2,Λ,jb)分别为et2[q],其中的第1、2个最大值分别为et2[j1′],et2[j2′]。同(1)式有st-task′[j]=min{max{st-proc[j1′],et[j2′]+1},max{st-proc[q],et2[j1′]+1},q=j1,j2,Λ,jb‚≠j1′}(2)st−task′[j]=min{max{st−proc[j1′],et[j2′]+1},max{st−proc[q],et2[j1′]+1},q=j1,j2,Λ,jb‚≠j1′}(2)(注:(1)和(2)式中的st-proc的某些值是不同的,即在Tj被调度的处理机Pk,Pl上是不同的,其它情况取值一样。)证明的思路即是比较(1)式和(2)式,证明它们在被调度到3.2.2节①～③中要求的处理机上时,有可能使得st-task′[j]<st-task[j],而在Ti被调度在其它处理机上时,Tj的最早调度的开始时间将大于、等于st-task′[j](或st-task[j])。仍按①～③分情况证明。这里,只以第②种情况为例,其它情况可同理证明。Ps≠Pk且et-task+1=st-task[j]结合(1)式可知有3种情况存在:①st-task[j]=et1[j2]+1=et-task+1(≠et1[j1]+1此时,进一步由(1)式可推得et1[s]=et1[j1],即处理机Ps,Pk上的et值分别等于前两个最大值,且Ps=Pj1。由于Pk是可最早开始任务Ti的处理机,所以当Ti被调度在处理机Pl(Pl∈SPP[j],≠Ps,Pk)时,有et2[j1′]≥et[j1],et2[j2′]≥et[j2](3)且若j1≠j1′,则有et2[j1′]≥et2[j2′]≥et1[j1]≥et1[j2];若j1=j1′,则有et1[j1]=et2[j1′],et2[j2′]≥et1[j2],将其代入(1)式和(2)式可得st-task′[j]≥st-task[j1]。同理分析,当Ti被调度在处理机Ps上时,有et2[j1′]=et2[s]≥et1[j1],et2[j2′]≤et1[j2](4)因此,当et2[j2′]<et1[j2],且此时的st-proc[j1′]=st-proc[s]≤et2[j2′]+1时,有st-task′[j]=et2[j2′]+1<st-proc[j]即当Ti被调度在处理机Ps上时,有可能使得st-task[j]更小。②st-task[j]=et1[j1]+1=et-task+1(≠et1[j2]+1)同①的分析,当Ti被调度在处理机Ps上时,有et2[j1′]=et2[s]≥et1[j1],et2[j2′]≤et1[j1](5)故根据(2)式可知,若此时的st-proc[s](假设为st-proc)≤et1[j1]+1,则有st-task[j′]≤st-task[j]。假设在Ti被调度到处理机Pl(Pl∈SPP[j],Pl≠Pk,Ps)上后,类似地定义st-task″[j],et3[j1″],et3[j2″]。显?然?,当Pl≠Px时,由于Ps是满足(1)式的st-proc最小者,所以有et3[j1″]=et3[l]≥et2[j1′],et3[j2″]≤et2[j2′](6)由于此时的st-proc[l]≥st-proc,故可推得st-task″[j]≥st-proc′[j]。同理,当Pl=Px时,有et3[j1″]=et3[x]≥et2[j1′],et3[j2″]≤et2[j2′],故可推得st-task″[j]有可能小于st-task′[j]。所以,这种情况下,Ti只有被调度在处理机Ps,Pk,Px上,st-task[j]才具有最小值。③st-task[j]=et1[j]+1=et1[j2]+1=et-task+1同理可证,若et1[j3]=et1[j1],则当Ti被调度在处理机Pl(Pl∈SPP[j],Pl≠Pk)上时,st-task′[j]≥st-task[j];若et1[j3]≠et1[j1],则当Ti只有被调度在处理机Pl(Pk=Pj1,则为Pj2;否则,为Pj1)上时,st-task′[j]才有可能小于st-task[j]上述即为提出的处理机选择算法,它的具体算法描述见第3.2.3节。3.2.3键路径的递归并行调度算法对上述调度节点选择和处理机选择算法进行综合,我们得到如下并行调度算法。算法1基于动态关键路径的递归并行调度算法定义G,st-task,st-proc,task-proc,q为全局变量;初始化:st-task[i]=-1(i=1,2,Λ,ν);st-proc[i]=0(i=1,2,Λ,n);task-proc[i]=-1(i=1,2,Λ,v);3.3最早调度的时间复杂度下面分析提出的算法在最坏情况下的时间复杂度。算法的复杂度依赖于使用的数据结构,由于算法中需计算前驱任务子图,所以我们用包含两个指针的链表表示任务图(一个指向它的直接前驱节点,一个指向它的直接后继节点)。首先对select-processor()进行复杂度分析。显然,若对Ti(Tj)进行最早调度,则需计算SPT,SPP,et-task和et,然后类似于式(1)计算,其中前4个可