基于任務(wù)復(fù)制的動態(tài)關(guān)鍵移除調(diào)度算法

基于任務(wù)復(fù)制的動態(tài)關(guān)鍵移除調(diào)度算法

1同構(gòu)同構(gòu)的應(yīng)用以最小完成時間為基礎(chǔ)的文檔任務(wù)是并行分布系統(tǒng)的一個重要問題。相關(guān)任務(wù)可以表示大量的數(shù)值計(jì)算、公式推導(dǎo)、工作流項(xiàng)目、算術(shù)方法等。例如，如快速傅立葉變換和高斯估計(jì)的計(jì)算。即使資源是相同的結(jié)構(gòu)和完整的，任務(wù)也可以重復(fù)使用，這可以顯著提高執(zhí)行效率。同構(gòu)問題是研究異構(gòu)問題的基礎(chǔ)，在解決問題其他單模項(xiàng)目的資源方面具有參考價(jià)值，因此得到了廣泛的研究。本文研究同構(gòu)問題的一個典型模型,即已知一組有優(yōu)先關(guān)系約束的任務(wù)和一組相同數(shù)量的同構(gòu)資源,求一種調(diào)度方案,滿足以下約束:(1)任務(wù)限制(2)限制運(yùn)行(3)任務(wù)調(diào)度tdb目標(biāo)為如何將任務(wù)分配到資源,并給出任務(wù)在資源上的開始時間,使任務(wù)集的最早開始時間與最晚完成時間之間的差盡可能的小,即最小化調(diào)度長度(makespan).此類問題的一個典型應(yīng)用為分布式內(nèi)存機(jī)器中的任務(wù)調(diào)度問題.一般用加權(quán)的有向無回路圖(DirectedAcyclicGraph,DAG)G(V,E,μ,λ)來表示相互依賴的任務(wù)集,如圖2(a)所示,頂點(diǎn)集V={1,2,…,n-1,n}為任務(wù)集,頂點(diǎn)的權(quán)μi表示相應(yīng)任務(wù)的執(zhí)行時間,有向邊集E={eij:i,j∈V;i→j}表示任務(wù)間的優(yōu)先關(guān)系,邊的權(quán)λij表示前后兩任務(wù)不在同一資源上執(zhí)行時的傳輸延遲.目前代表性的調(diào)度方法為啟發(fā)式算法[1,2,3,4,5,6,7,8,9,10],主要包括基于任務(wù)復(fù)制的調(diào)度、基于優(yōu)先級列表的調(diào)度和基于簇的調(diào)度三類.基于任務(wù)復(fù)制(Task-Duplication-Based,TDB)的調(diào)度算法通常要優(yōu)于基于優(yōu)先級列表和基于簇的調(diào)度算法.TDB算法的理論基礎(chǔ)是采取以空間換時間的策略,通過冗余分配任務(wù)到多個資源以減少通信開銷,從而減少總的調(diào)度長度,因此可生成更小的調(diào)度長度.如何準(zhǔn)確地確定應(yīng)被復(fù)制的重要任務(wù)是獲得較短調(diào)度的關(guān)鍵,各種TDB算法的主要區(qū)別也正在于此.近年來發(fā)表的TDB算法包括DSH、BTDH、LCTD、LWB、PY、MJD、CPFD、TDS、ETDS、PPA、IREA等.PY和MJD是其中理論上最優(yōu)的,它們對任意DAG給出了性能保證,而其它僅部分算法對某些特定DAG生成了優(yōu)化調(diào)度.對任意DAG,PY調(diào)度的調(diào)度長度最多為最優(yōu)調(diào)度的2倍,MJD調(diào)度的調(diào)度長度最多為最優(yōu)調(diào)度的1+ε′倍(0<ε′≤1).MJD算法的主要思想是以拓樸順序計(jì)算每個任務(wù)v的開始時間下界ev及其對應(yīng)簇Cv,然后反拓?fù)漤樞蛟L問DAG中的任務(wù)并構(gòu)造調(diào)度.在ev的計(jì)算過程中,數(shù)據(jù)到達(dá)時間c的計(jì)算未到任務(wù)v,而是進(jìn)入簇Cv的第一個任務(wù),可能錯失更小調(diào)度的機(jī)會;且未考慮其祖先得到e值的對應(yīng)簇信息,導(dǎo)致對任務(wù)的實(shí)際最早可能開始時間的估計(jì)不夠準(zhǔn)確.本文提出一種基于任務(wù)復(fù)制的動態(tài)關(guān)鍵前驅(qū)(DynamicCriticalPredecessor,DCP)調(diào)度算法,并證明對任意DAG,DCP調(diào)度的調(diào)度長度最多為最優(yōu)調(diào)度的1+ε倍(0<ε≤1且ε≤ε′).針對實(shí)際應(yīng)用中處理機(jī)數(shù)目受限的情況,算法在不增加調(diào)度長度的同時,盡可能減少占用的資源數(shù)目.實(shí)驗(yàn)表明DCP算法的求解質(zhì)量很高.2sv的初始計(jì)算針對MJD算法的不足,DCP算法主要做了以下改進(jìn):(1)計(jì)算數(shù)據(jù)最早到達(dá)時間時,不是計(jì)算到入簇的第一個任務(wù)的時間,而是計(jì)算v的最早可能開始時間Sv.(2)放寬加入任務(wù)的條件,只要加入該任務(wù)不會使Sv增加,則可以加入簇Cv.(3)計(jì)算Sv時,其祖先任務(wù)含相關(guān)的分簇歷史信息,即在考慮跨簇的任務(wù)時,不僅以任務(wù)為粒度,也以簇為粒度,從而更準(zhǔn)確,并加快了計(jì)算過程.2.1任務(wù)的sv及對應(yīng)簇cv首先按拓?fù)漤樞蛟L問圖G中的任務(wù)v∈V,并計(jì)算其最早可能開始時間Sv及對應(yīng)簇Cv.對任務(wù)v,設(shè)其祖先的S值及對應(yīng)簇已求出,欲求Sv及對應(yīng)簇Cv,只需找到一個包含v及其部分祖先的簇就足夠了,因?yàn)槿绻橙蝿?wù)不是v的祖先,則從簇中移除該任務(wù),不會使Sv增加,只可能使其減小.設(shè)Cv是一個含任務(wù)v及其部分祖先W={w1,w2,…,wl}的簇,U={u1,u2,…,uk}為跨簇Cv的任務(wù).W和U中任務(wù)的S及對應(yīng)簇C已經(jīng)求出.將Si作為任務(wù)i的釋放時間,按就緒任務(wù)釋放時間的先后順序?qū)蟇∪U∪{v}進(jìn)行貪心調(diào)度,得到v的最早可能開始時間Sv,并記下造成Sv不能再下降的關(guān)鍵任務(wù)u,稱u為Cv的關(guān)鍵前驅(qū)cpred(Cv).然后尋找使Sv盡可能小的簇Cv,從只含任務(wù)v的簇開始,每次向簇中并入v的部分祖先集,并檢查Sv是否減小.部分祖先集的選擇,考慮了Cv的關(guān)鍵前驅(qū)u及其對應(yīng)簇Cu,具體過程見圖1.算法1為任務(wù)的Sv及對應(yīng)簇Cv的計(jì)算過程,其中C.s和C.cpred表示當(dāng)前格局貪心調(diào)度后的Sv和簇C的關(guān)鍵前驅(qū),v.s和v.C表示終止格局時的Sv和Cv,w表示最后并入簇C的任務(wù).算法1.COMPUTE_S_VALUE(v,G).2.2任務(wù)2.分簇.進(jìn)行控制得到每個任務(wù)v∈V的最早可能開始時間Sv及對應(yīng)簇Cv后,反拓?fù)漤樞蛟L問G中的任務(wù)并進(jìn)行分簇.算法2.CLUSTERING(G).分簇完成后,將?(G)中的每個簇分配到不同的資源上,它們之間用跨簇的邊集關(guān)聯(lián),然后按任務(wù)的最早可能開始時間非降序排列進(jìn)行貪心調(diào)度,得到最終結(jié)果.3結(jié)果3.1算例2.2算法復(fù)雜度EZ算例是DAG調(diào)度的經(jīng)典算例,如圖2(a)所示,其最優(yōu)調(diào)度的調(diào)度長度一直被認(rèn)為是8.5.圖2(b)為DCP的調(diào)度結(jié)果,調(diào)度長度為8,使用了3個資源.圖2(c)為每個任務(wù)的S值及其對應(yīng)簇,圖2(d)為任務(wù)T6的S和C的計(jì)算過程.DCP與相關(guān)算法的結(jié)果比較見表1,其中EZ、DSC、TDS算法的結(jié)果參見文獻(xiàn),DCP的算法復(fù)雜度說明參見文獻(xiàn).下面證明EZ算例的最優(yōu)調(diào)度的調(diào)度長度為8.事實(shí)1.EZ算例的最優(yōu)調(diào)度的調(diào)度長度為8.證明.因任務(wù)僅當(dāng)其前驅(qū)任務(wù)均已完成才可能執(zhí)行,所以在DCP的調(diào)度結(jié)果中,任務(wù)T1,T2,T3,T4,T5均已在其絕對最早可能開始時間被調(diào)度.由于T1→T2→T7為不考慮邊的權(quán)時的最長路徑,所以T7的最早開始時間不小于6,完成時間不小于7.若T1與T2不在同一簇中,則T2的最早完成時間為11,故T7的最早完成時間為12,不可能為優(yōu)化調(diào)度.故優(yōu)化調(diào)度中,T1與T2必在同一簇中.若T7與T2不在同一簇中,則完成時間不小于9,故優(yōu)化調(diào)度中,T7一定與T2在同一簇中.考慮任務(wù)T6,只有兩種可能:(1)與T2,T7在一個簇中,則T6的最早可能開始時間為6,T7的最早可能完成時間為8;(2)與T2,T7不在一個簇中,則T6的最早可能開始時間為5.5,T7的最早可能完成時間為8.5.可見EZ算例最優(yōu)調(diào)度的調(diào)度長度為8.證畢.3.2算例來源及其它tdb算法的計(jì)算結(jié)果DCP算法與相關(guān)的6個TDB算法比較的結(jié)果見表2,其中算例來源及其它TDB算法的計(jì)算結(jié)果參見文獻(xiàn).可見DCP的解至少與其它TDB算法的最好解一樣好,且若干算例得到了更優(yōu)的解.4標(biāo)識任務(wù)v1+本節(jié)從理論上分析DCP算法的性能,改進(jìn)粒度的定義,并證明DCP對任意DAG可得到優(yōu)于MJD的性能下界.粒度是分析DAG調(diào)度算法性能的一個重要參數(shù).對任務(wù)v∈V,定義g1(v)=min{μu|(u,v)∈E}max{λuv|(u,v)∈E}?g2(v)=min{μw|(v,w)∈E}max{λvw|(v,w)∈E}?g1(v)=min{μu|(u,v)∈E}max{λuv|(u,v)∈E}?g2(v)=min{μw|(v,w)∈E}max{λvw|(v,w)∈E}?則v的粒度g0(v)=min{g1(v),g2(v)},圖G的粒度g0(G)=min{g0(v)|v∈V}.本文改進(jìn)了粒度的定義:(1)只考慮前驅(qū)及輸入邊,不考慮后繼及輸出邊;(2)取前驅(qū)及相應(yīng)輸入邊的比值中的最小值,而不取最小前驅(qū)與最大輸入邊的比值.對任務(wù)v∈V,定義v的粒度為g(v)=min{μu/λuv,(u,v)∈E},圖G的粒度為g(G)=min{g(v)|v∈V}.例如對EZ算例,g(G)=g0(G)=0.2;若修改T1的計(jì)算時間為4,則g0(G′)=0.2,g(G′)=0.25.引理1.對任意DAG圖G(V,E,μ,λ),存在0<ε≤1滿足g(G)=(1-ε)/ε.證明.因μ,λ中元素均為有理數(shù),由粒度的定義,g(G)為有理數(shù)運(yùn)算得到,由有理數(shù)四則運(yùn)算的封閉性,g(G)也為一有理數(shù),故一定可寫為一個分?jǐn)?shù),設(shè)g(G)=a/b,其中a,b∈N={0,1,2,…},且b>0,則0≤g(G)<∞.定義ε=b/(a+b),可推出0<ε≤1,且g(G)=(1-ε)/ε.引理得證.證畢.引理2.設(shè)v為一標(biāo)識任務(wù),且其對應(yīng)簇Cv映射到同一資源,則存在0<ε≤1滿足g(G)=(1-ε)/ε,使stv≤(1+ε)stopt(v).其中stv為v的開始時間,stopt(v)為v在最優(yōu)調(diào)度時的開始時間.證明.由引理1,存在0<ε≤1滿足g(G)=(1-ε)/ε.下面證明stv≤(1+ε)stopt(v),以標(biāo)識任務(wù)v的深度為遞推值,進(jìn)行數(shù)學(xué)歸納證明:(1)若v為開始任務(wù),stv=stopt(v)=0,命題成立;(2)設(shè)命題對v的祖先中的標(biāo)識任務(wù)均成立.設(shè)另一個簇的標(biāo)識任務(wù)u為任務(wù)w∈Cv和簇Cv的關(guān)鍵任務(wù),則u為w的所有前驅(qū)中數(shù)據(jù)到達(dá)最晚的前驅(qū),所以stw=stu+μu+λuw;由于祖先任務(wù)u為一標(biāo)識任務(wù),由假設(shè)stu≤(1+ε)stopt(u),所以stw≤(1+ε)stopt(u)+μu+λuw.因w為u的后繼,stopt(w)≥stopt(u)+μu.因此,stw≤stopt(u)+μu+ε·stopt(u)+λuw,stw≤stopt(w)+ε·stopt(u)+λuw(1)由粒度定義和引理1,μu/λuw≥g(w)≥g(G)=(1-ε)/ε,ε(μu+λuw)≥λuw(2)由式(1)、式(2)得stw≤stopt(w)+ε(stopt(u)+μu+λuw),而stopt(v)≥stopt(u)+μu+λuw,可推出stw≤stopt(w)+εstopt(v)(3)式(3)對任意屬于Cv的任務(wù)成立,所以stv≤(1+ε)stopt(v).引理得證.證畢.定理1.對任意DAG圖G(V,E,μ,λ),存在0<ε≤1滿足g(G)=(1-ε)/ε,且DCP調(diào)度結(jié)果最多為最優(yōu)調(diào)度的1+ε倍.證明.設(shè)Mopt為G的最優(yōu)調(diào)度結(jié)果,對G中所有無后繼的點(diǎn)v,Mopt≥max(stopt(v)+μv).因每個無后繼的點(diǎn)均為標(biāo)識任務(wù),由引理2:makespan(G)≤max{(1+ε)stopt(v)+μv}≤max{(1+ε)[stopt(v)+μv]}≤(1+ε)max{stopt(v)+μv}≤(1+ε)Mopt.調(diào)度結(jié)果最多為最優(yōu)調(diào)度的1+ε倍.證畢.定理2.對任意DAG,DCP算法的性能下界優(yōu)于MJD算法的性能下界.證明.由min{μuλ(u,v),(u,v)∈E}≥min{μu|(u,v)∈E}max{λ(u,v)|(u,v)∈E}min{μuλ(u,v),(u,v)∈E}≥min{μu|(u,v)∈E}max{λ(u,v)|(u,v)∈E},得出g(v)≥g1(v),而g1(v)≥g0(v),故g(v)≥g0(v),因此g(G)≥g0(G).由引理1,存在0<ε≤1滿足g(G)=(1-ε)/ε;由文獻(xiàn),存在0<ε′≤1滿足g0(G)≥(1-ε′)/ε′;可推出(1-ε)/ε≥(1-ε′)/ε′,即ε≤ε′.對任意DAG圖G(V,E,μ,λ),由定理1,DCP算法的makespan(G)≤(1+ε)Mopt;由文獻(xiàn),MJD算法的makespan(G)≤(1+ε′)Mopt.而ε≤ε′,故DCP算法的性能下界優(yōu)于MJD算法的性能下界.因此命題成立.證畢.5不允許復(fù)制時的調(diào)度在實(shí)際應(yīng)用中,某些任務(wù)不允許被復(fù)制,如銀行取款任務(wù),而典型的DAG圖Out-tree和In-tree應(yīng)用非常廣泛,如分而治之(divide-and-conquer)算法、常見的數(shù)值計(jì)算等.本節(jié)討論不允許復(fù)制時DAG的特點(diǎn),并證明存在多項(xiàng)式時間的算法,對Out-tree和In-tree的調(diào)度結(jié)果最多為最優(yōu)調(diào)度的1+ε倍且0<ε≤1.定義1(In-tree).除了唯一的結(jié)束任務(wù),每個任務(wù)只有一個子任務(wù)的DAG.定義2(Out-tree).除了唯一的開始任務(wù),每個任務(wù)只有一個父任務(wù)的DAG.定義3(補(bǔ)圖G′).對任意給定的DAG圖G,其補(bǔ)圖G′與G的唯一不同為G′中每條邊的方向與G中對應(yīng)邊u→w的方向正好相反,為w→u.引理3.不允許復(fù)制時,對任意給定的DAG圖G及其補(bǔ)圖G′,設(shè)S′為G′的一個調(diào)度,可得到G的一個調(diào)度S:S中每個任務(wù)v的匹配資源與S′一致,且開始時間為stv(S)=makespan(S′)-ctv(S′),則G的調(diào)度S為一合理的調(diào)度,且與其補(bǔ)圖G′的調(diào)度S′有相同的調(diào)度長度.證明.首先證明S為一合理的調(diào)度.設(shè)G′開始任務(wù)為v1,結(jié)束任務(wù)為vn,在調(diào)度S′中的開始時間與結(jié)束時間為st′1,ct′1,st′n和ct′n.設(shè)任意w∈V在G′的調(diào)度S′中的開始時間和結(jié)束時間分別為st′w和ct′w.則在G的調(diào)度S中:stn=makespan(S′)-ct′n=ct′n-ct′n=0,ctn=stn+μn=μn,stw-stn=stw=makespan(S′)-ct′w=ct′n-ct′w,ctw-stn=ctw=stw+μw=ct′n-(ct′w-μw)=ct′n-st′w.可見在S中對w的調(diào)度滿足約束關(guān)系,為一合理的調(diào)度.st1=makespan(S′)-ct′1=ct′n-ct′1,makespan(S)=ct1=st1+μ1=ct′n-(ct′1-μ1)=ct′n-st′1=makespan(S′).G的調(diào)度S與補(bǔ)圖G′的調(diào)度S′有相同的調(diào)度長度.引理得證.證畢.定理3.不允許復(fù)制時,存在一多項(xiàng)式時間的算法對Out-tree和In-tree的調(diào)度結(jié)果最多為最優(yōu)調(diào)度的1+ε倍且0<ε≤1.證明.(1)由定理1,算法DCP可對In-tree生成最多為最優(yōu)調(diào)度的1+ε倍的解.而In-tree的每個任務(wù)最多只有一個子任務(wù),由DCP算法,實(shí)際上沒有任務(wù)被復(fù)制.故不允許復(fù)制時,DCP對In-tree的DAG可生成1+ε優(yōu)度的解.(2)任意Out-tree的補(bǔ)圖為In-tree,對補(bǔ)圖G′調(diào)度得到解S′,并定義原圖G的調(diào)度為stv(S)=makespan(S′)-ctv