基于動態(tài)關鍵路徑的bnp調度算法

基于動態(tài)關鍵路徑的bnp調度算法

1靜態(tài)調度和bnp調度獲得并行系統(tǒng)的性能的關鍵是對處理機器的有效規(guī)劃。它將任務集T分布到處理機系統(tǒng)P上求解,滿足任務之間的依賴關系,且使得調度長度最短。若并行任務的任務執(zhí)行時間、任務依賴關系、通信時間和同步時間是預先知道的,則調度可以在編譯時進行,稱為靜態(tài)調度。若分布式系統(tǒng)中的處理機數有限,則稱為BNP調度問題。由于實際應用中,處理機數多是受限的,所以靜態(tài)BNP調度問題是調度算法研究中的一個重要分支。2問題模型和相關工作首先對BNP調度模型及一些相關概念進行描述。2.1bnp調度算法的研究目標一個并行任務T由滿足一定前趨約束的子任務集{T1,T2,Λ,Tν}組成,它可以用一個有向無環(huán)圖G=(V,E)表示。其中V(|V|=ν)是節(jié)點集,對應著并行任務中的一個子任務,節(jié)點權量wi代表了任務Ti的運行時間,表示任務需用的單位執(zhí)行時間(UnitExecutingTime,UET)數。E(|E|=e)是有向邊集,表明了任務之間的偏序?關?系?和?通?信?時?間,即Ti→Tj表示只有在任務Ti完成之后,Tj才能開始,Ti稱為Tj的直接前趨,Tj稱為Ti的直接后繼,或稱Ti為有向邊的尾,Tj為有向邊的頭。有向邊上的權值ci,j表明了任務Ti傳遞數據給任務Tj所需的時間。但當Ti,Tj分配到同一個處理機上執(zhí)行時,ci,j為0。另外,假設分布式系統(tǒng)P由n臺同構的處理機P1,P2,Λ,Pn全互連組成,且網絡同構。BNP調度算法的研究目標是:將并行任務T分布到P上求解,使得它們滿足任務間的約束關系,同時使任務T的執(zhí)行時間最短。定義1若并行任務T對應的任務圖G=(V,E)中存在一條從子任務Ti到子任務Tj的路徑,則稱Ti為Tj的前趨,Tj為Ti的后繼。定義2稱任務圖G=(V,E)中沒有前趨的節(jié)點為入節(jié)點或就緒任務,沒有后繼的節(jié)點為出節(jié)點。定義3任務圖的關鍵路徑是圖中任務節(jié)點和有向邊的一個集合,它是任務圖中從一個入節(jié)點到一個出節(jié)點的所有路徑中節(jié)點計算量和有向邊的通信開銷之和最大的路徑,簡記為CP(critialpath),稱關鍵路徑上的任務為關鍵任務。2.2bnp調度算法眾所周知,大多數情況下,有前趨約束的任務在多處理機上的調度是NP-完全問題,大多使用啟發(fā)式算法進行求解,包括遺傳調度、隊列調度等。但基于算法復雜度和對任務圖限制的考慮,其中最通用的是隊列調度算法,它主要是重復以下過程直至所有的任務已被調度:①根據所有未調度節(jié)點的靜態(tài)或動態(tài)優(yōu)先級確定調度節(jié)點;②根據一定的準則為該調度節(jié)點分配處理機及相應的時間槽?，F有的BNP隊列調度算法有HLFET(highestlevelfirstwithestimatedtimes)、MCP(modifiedcriticalpath)、DLS(dynamic-levelscheduling)等調度算法。其中HLFET和MCP分別以節(jié)點的靜態(tài)b-level值和ALAP(aslateaspossible)值作為節(jié)點的優(yōu)先級,并為調度節(jié)點分配可最早執(zhí)行它的處理機。而DLS采用了一種動態(tài)優(yōu)先級的概念,它定義了任務-處理機對的動態(tài)層概念,每次調度時,對其中動態(tài)層值最大者進行調度,并將它分配給對應的處理機。由于采用了動態(tài)優(yōu)先級的概念,因而它優(yōu)于前兩者,但其時間復雜度也因此高于HLFET的O(v2)和MCP的O(v2log2v)的時間復雜度,為O(nv3)。對上述3種算法進行分析,發(fā)現它們不能保證對影響算法性能的動態(tài)關鍵任務進行最早調度,從而有可能導致整個任務系統(tǒng)的完成時間被拖延(非動態(tài)關鍵任務已占用了時間槽,例子見第3節(jié))。為克服上述算法中的缺點,進一步優(yōu)化任務的調度長度,本文對BNP調度問題提出了一種新的啟發(fā)式調度算法。該算法不同于隊列調度算法——不需計算所有未調度任務的優(yōu)先級,它基于任務圖的動態(tài)關鍵路徑,遞歸地確定調度任務,是第一個使用遞歸思想進行調度的算法。同時,它結合調度任務的后繼任務,為其選擇了最佳時間槽。3任務圖12關鍵路徑在調度算法中起著重要作用,任務優(yōu)先級的確定常受限于它(如b-level值)。但由于任務之間通信開銷的不確定性,故隨著調度的進行,任務圖的關鍵路徑也隨之改變。為此,我們提出動態(tài)關鍵路徑的概念,它是針對調度過程中的剩余任務子圖定義的。3.1動態(tài)關鍵路徑的定義首先對任務圖的概念進行擴充,允許它沒有入節(jié)點,可以從一條邊進入,相應地稱這條沒有尾節(jié)點的邊為該任務圖的入邊,記作?→Tj。其中?是空節(jié)點,Tj是它的頭節(jié)點。定義4定義任務圖G=(V,E)的去掉某個入節(jié)點Ti或去掉某條入邊的頭節(jié)點Ti及所有以Ti為頭的入邊而剩余的G的子圖為節(jié)點Ti關于G的剩余任務子圖,記為GL(Ti,G),即GL(Ti,G)=(VL,EL),其中VL=V-{Ti},EL=E-{?→Ti|?→Ti∈E}。上述剩余任務子圖的定義是相對于一個節(jié)點而言的,但它也同樣適用于對節(jié)點集S={Ti1,Ti2,Λ,Til}定義剩余任務子圖,即GL(S,G)=GL(Til,ΛGL(Ti2,GL(Ti1,G)))。顯然,調度節(jié)點只能是任務圖的入節(jié)點Ti或入邊的頭節(jié)點Ti(它的前趨已被調度),當節(jié)點Ti被調度后,我們稱它對應的剩余任務子圖中的關鍵路徑為當前的關鍵路徑(按定義3計算,但路徑可以從一條入邊起始,終止于一個出節(jié)點),此即提出的動態(tài)關鍵路徑的概念。由于任務之間的通信開銷也影響著任務的調度長度,因而我們在上述動態(tài)關鍵路徑的定義中允許入邊的存在。這也是本文的動態(tài)關鍵路徑概念與一般定義的關鍵路徑(按定義3計算)的不同之處。定義5對于任務圖G=(V,E)來講,定義其子任務Ti(∈V)的前趨任務子圖是由G中Ti的所有前趨及它們之間的有向邊組成的一個有向無環(huán)圖,它是G的一個子圖,且其節(jié)點權重和邊權重與G中的對應節(jié)點和邊保持一致。若將該前趨任務子圖記為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基于主要動態(tài)路徑的序列并行規(guī)劃算法調度算法的研究通常是確定兩個準則,即選擇調度節(jié)點的準則R1和為調度節(jié)點確定處理機的準則R2。下面分別對它們進行研究。3.2.1遞歸調度的思想由于關鍵路徑在調度算法中的重要作用,因而,我們希望對當前動態(tài)關鍵路徑上的第一個關鍵節(jié)點(稱為動態(tài)關鍵任務)進行調度,但此時存在一個問題:該節(jié)點的前趨節(jié)點可能未被調度。如圖1(b)所示,按關鍵節(jié)點調度的思想,當T1、T3被調度后,剩余任務子圖中的第一個關鍵節(jié)點是T5,但此時它的前趨節(jié)點T2、T4未被調度。為此,我們提出遞歸調度的思想,即對該節(jié)點的前趨任務子圖進行調度,遞歸地確定調度節(jié)點。具體算法描述如下。其中函數調用select-processor(Ti)實現為調度節(jié)點Ti選擇處理機的功能。對它的算法實現,我們有如下考慮。3.2.2任務ts的最早調度和終止時間常用的處理機選擇算法是為調度任務Ti選擇可最早執(zhí)行它的處理機。但對有通信開銷的任務系統(tǒng)來講,它不能有效地減少調度長度。如圖2所示。從圖2中可以看出,由于在對調度任務進行處理機分配時只考慮了它自身,沒有考慮它的通信開銷對后繼任務的影響,因而有可能拖延整個任務系統(tǒng)。為此我們按如下方法對任務Ti進行調度。假設Tj為當前關鍵路徑中Ti的直接后繼節(jié)點。(1)若Tj=?,則將Ti調度到可最早執(zhí)行它的處理機上;(2)若Tj≠?,則從各處理機上可最早開始Ti的n個時間槽內選擇一個,使Tj具有最早開始時間(根據已調度直接前趨節(jié)點計算得到的開始時間)。顯然,這種處理機選擇算法避免了通信開銷過大,有可能拖延任務完成時間這種情況的發(fā)生。對上述第(2)種情況,若逐個進行比較,則它的時間復雜度較高,為O(nv)。為此,本文提出了時間復雜度為O(v)的一個快速算法。為便于算法描述,首先定義如下參數(其中后4個參數是相對于某個任務TS定義的):task-proc[q]——任務Tq分配的處理機(q=1,2,Λ,ν);st-task[q]——任務Tq的開始執(zhí)行時間(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上,開始執(zhí)行時間為st-task[i]。在對Ti進行最早調度后,我們假設對Tj也進行最早調度(由于通信開銷的存在,只考慮將Tj調度在SPP[j]中(如式(1)所示)。且若有多個處理機同時取st-task[j],則選擇處理機的st-proc最小者)。假設它被調度在處理機PS上,開始執(zhí)行時間為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節(jié)所述。實際上,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進行最早調度。假設它對應的開始執(zhí)行時間為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節(jié)①～③中要求的處理機上時,有可能使得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節(jié)。3.2.3鍵路徑的遞歸并行調度算法對上述調度節(jié)點選擇和處理機選擇算法進行綜合,我們得到如下并行調度算法。算法1基于動態(tài)關鍵路徑的遞歸并行調度算法定義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最早調度的時間復雜度下面分析提出的算法在最壞情況下的時間復雜度。算法的復雜度依賴于使用的數據結構,由于算法中需計算前驅任務子圖,所以我們用包含兩個指針的鏈表表示任務圖(一個指向它的直接前驅節(jié)點,一個指向它的直接后繼節(jié)點)。首先對select-processor()進行復雜度分析。顯然,若對Ti(Tj)進行最早調度,則需計算SPT,SPP,et-task和et,然后類似于式(1)計算,其中前4個可