并行設(shè)計(jì)中的任務(wù)調(diào)度問(wèn)題

1基于任務(wù)優(yōu)化調(diào)度算法的并行設(shè)計(jì)同時(shí)設(shè)計(jì)是一種系統(tǒng)的工作方法，用于同時(shí)設(shè)計(jì)產(chǎn)品及其相關(guān)過(guò)程。由于在同時(shí)設(shè)計(jì)工程中占主導(dǎo)地位，全行工程的核心是并行設(shè)計(jì)。在這里，對(duì)分解的設(shè)計(jì)任務(wù)的分配（完成設(shè)計(jì)任務(wù)的個(gè)人或群體）是并行設(shè)計(jì)的重要內(nèi)容之一。同時(shí)設(shè)計(jì)任務(wù)的規(guī)劃方法是在不同的匹配方法中找到最合理的子任務(wù)分配方法。文獻(xiàn)針對(duì)任務(wù)調(diào)度問(wèn)題分別給出了相應(yīng)的實(shí)現(xiàn)算法,但是這些算法都沒(méi)有考慮任務(wù)間的時(shí)序關(guān)系,而這在設(shè)計(jì)任務(wù)集的分布并行求解中經(jīng)常出現(xiàn).文獻(xiàn)提出了一種基于任務(wù)時(shí)序關(guān)系的“均衡-適度”算法,但不是求解問(wèn)題的最短時(shí)間解.文獻(xiàn)提出了一種任務(wù)優(yōu)化調(diào)度算法,但重點(diǎn)考慮任務(wù)均衡問(wèn)題.特別地,當(dāng)子任務(wù)數(shù)量較多以及子任務(wù)之間的時(shí)序關(guān)系較復(fù)雜時(shí),任務(wù)調(diào)度問(wèn)題是一個(gè)NP難問(wèn)題,也是一個(gè)組合優(yōu)化問(wèn)題,如果利用隨機(jī)搜索法、爬山法等傳統(tǒng)算法難以解決這類問(wèn)題.為解決此類任務(wù)調(diào)度問(wèn)題,本文給出了一個(gè)基于任務(wù)偏序圖和子任務(wù)深度值的遺傳算法,并介紹了該算法的總體框架、關(guān)鍵要素設(shè)計(jì)及其實(shí)現(xiàn).2設(shè)計(jì)任務(wù)調(diào)度在研究并行設(shè)計(jì)環(huán)境下設(shè)計(jì)子任務(wù)的調(diào)度問(wèn)題時(shí),針對(duì)該問(wèn)題的描述所給出的假設(shè)往往各不相同.不失一般性,我們假設(shè)一個(gè)大的總?cè)蝿?wù)已經(jīng)按照某種分解規(guī)則被分解為若干個(gè)子任務(wù),這些子任務(wù)的求解存在有序性和可并行性,并且各子任務(wù)將由不同的設(shè)計(jì)單元來(lái)承擔(dān),而不同的設(shè)計(jì)單元對(duì)各子任務(wù)的求解效率是不盡相同的.同時(shí),假定需調(diào)度的子任務(wù)數(shù)多于可提供的設(shè)計(jì)單元數(shù),并且各設(shè)計(jì)單元中的子任務(wù)之間的關(guān)系是非搶先式的,即在同一設(shè)計(jì)單元中的一個(gè)子任務(wù)沒(méi)有完成之前,其他分配在該節(jié)點(diǎn)上的子任務(wù)不能開(kāi)始執(zhí)行.并行設(shè)計(jì)環(huán)境下的設(shè)計(jì)子任務(wù)之間的這種偏序關(guān)系我們可以用一個(gè)任務(wù)偏序圖來(lái)描述,它是一個(gè)用有向非循環(huán)圖(DirectedAcylicGraph,DAG)表示的各子任務(wù)之間的依賴關(guān)系和時(shí)序約束關(guān)系的子任務(wù)關(guān)系圖.如圖1所示為7個(gè)子任務(wù)的偏序關(guān)系圖.根據(jù)任務(wù)偏序圖,我們將設(shè)計(jì)任務(wù)調(diào)度問(wèn)題模式化為DAG:G=(N,P,T,A).其中,N={NSi|1≤i≤m}是設(shè)計(jì)單元集,m為設(shè)計(jì)單元總數(shù),NSi表示第i個(gè)設(shè)計(jì)單元;P={STi|1≤i≤n}是子任務(wù)集,n(n≥m)為子任務(wù)的總數(shù),STi表示第i個(gè)子任務(wù);T={Tij|1≤i≤m,1≤j≤n}是各子任務(wù)的執(zhí)行時(shí)間集,Tij表示設(shè)計(jì)單元NSi執(zhí)行子任務(wù)STj的效率(可以用時(shí)間表示);A={Aij|1≤i≤n,1≤j≤n,i≠j}是有向邊集,Aij(STi→STj)表示子任務(wù)STi與子任務(wù)STj執(zhí)行上的時(shí)序關(guān)系,即任務(wù)STj在任務(wù)STi執(zhí)行完成之后才能開(kāi)始.基于以上描述,并行設(shè)計(jì)環(huán)境下的設(shè)計(jì)任務(wù)調(diào)度的目標(biāo)可以表述為:在滿足任務(wù)偏序圖中各子任務(wù)間時(shí)序約束關(guān)系的條件下尋找一個(gè)任務(wù)調(diào)度策略,將子任務(wù)集中的n個(gè)子任務(wù)分別調(diào)度到設(shè)計(jì)單元集中的m個(gè)設(shè)計(jì)單元中去執(zhí)行,并使得整個(gè)任務(wù)(總?cè)蝿?wù))的總的執(zhí)行效率最高,即總的完成時(shí)間最短.3不同子任務(wù)的調(diào)度策略定義1.子任務(wù)相關(guān)性表示一個(gè)子任務(wù)的開(kāi)始需依賴于另一個(gè)或多個(gè)子任務(wù)的結(jié)束,可表示為{STi,STi+1,…,STi+k;k≥0}→STj.其中,{STi,STi+1,…,STi+k}中的各子任務(wù)稱為子任務(wù)STj的前趨任務(wù),子任務(wù)STj稱為{STi,STi+1,…,STi+k}中各子任務(wù)的后繼任務(wù).定義2.用任務(wù)關(guān)聯(lián)矩陣An×n={Aij|1≤i≤n,1≤j≤n}來(lái)表示子任務(wù)之間的相關(guān)性.如果子任務(wù)STi完成后才能進(jìn)行子任務(wù)STj,即STi→STj,則Aij=1;否則,Aij=0.定義3.通過(guò)定義子任務(wù)的深度值來(lái)描述任務(wù)偏序圖中各子任務(wù)間的相對(duì)層次關(guān)系.子任務(wù)STi的深度值Η(SΤi)={0?若pred(SΤi)=?1+maxSΤj∈pred(SΤi)(Η(SΤj))?否則?其中,pred(STi)為子任務(wù)STi的前趨任務(wù)集.定義4.“單元-任務(wù)”匹配矩陣NPMm×n={cij|1≤i≤m,1≤j≤n}描述了子任務(wù)與設(shè)計(jì)單元之間的調(diào)度關(guān)系.其中,cij=1,表示子任務(wù)STj調(diào)度給了設(shè)計(jì)單元NSi;cij=0,表示子任務(wù)STj沒(méi)有調(diào)度給設(shè)計(jì)單元NSi,并且調(diào)度在同一設(shè)計(jì)單元中的所有子任務(wù)是按其深度值大小升序排列的.一個(gè)“單元-任務(wù)”匹配矩陣實(shí)際上描述了滿足任務(wù)偏序圖中各子任務(wù)間時(shí)序約束關(guān)系條件的一個(gè)任務(wù)調(diào)度策略.定義5.“單元-任務(wù)”效率矩陣NPTm×n={tij|1≤i≤m,1≤j≤n}描述了各設(shè)計(jì)單元對(duì)各子任務(wù)的執(zhí)行效率.其中,tij表示設(shè)計(jì)單元NSi執(zhí)行子任務(wù)STj所需執(zhí)行時(shí)間.定義6.調(diào)度在某一設(shè)計(jì)單元上的子任務(wù)的開(kāi)始時(shí)間既與任務(wù)偏序圖中它的前趨任務(wù)集中各子任務(wù)的結(jié)束時(shí)間有關(guān),也與其在該設(shè)計(jì)單元中的前趨任務(wù)的結(jié)束時(shí)間有關(guān),因此子任務(wù)的開(kāi)始時(shí)間Τb(SΤj)={0?若pred(SΤj)=?maxSΤi∈pred(SΤj)(Ηe(SΤi))?否則?其中,pred(STj)為子任務(wù)STj在任務(wù)偏序圖及其所在設(shè)計(jì)單元NSi任務(wù)集中的所有前趨任務(wù)的集合;設(shè)Te(STj)為結(jié)束時(shí)間,有Τe(SΤj)=Τb(SΤj)+tij.設(shè)對(duì)于一個(gè)設(shè)計(jì)子任務(wù)調(diào)度策略S,ts(NSi)為策略S中設(shè)計(jì)單元NSi任務(wù)列表中的最后一個(gè)子任務(wù)的結(jié)束時(shí)間.設(shè)t(S)為整個(gè)任務(wù)調(diào)度策略S的完成時(shí)間,t(S)=max1≤i≤m(ts(ΝSi))(1)我們可以將并行設(shè)計(jì)環(huán)境下的設(shè)計(jì)子任務(wù)調(diào)度問(wèn)題的目標(biāo)模型描述為尋找一個(gè)設(shè)計(jì)子任務(wù)調(diào)度策略S,使得t(S)最小,即優(yōu)化目標(biāo)函數(shù)為minS(t(S)).此外,為了充分利用所有設(shè)計(jì)資源,一般每個(gè)設(shè)計(jì)單元至少應(yīng)分配一個(gè)子任務(wù),并且一個(gè)子任務(wù)只能調(diào)度給一個(gè)設(shè)計(jì)單元.根據(jù)這些邊界約束條件,一個(gè)合法的、能夠準(zhǔn)確描述子任務(wù)調(diào)度的任務(wù)調(diào)度策略還應(yīng)滿足以下條件:n∑j=1cij≥1;m∑i=1cij=1.因此,一個(gè)基于任務(wù)之間時(shí)序關(guān)系的調(diào)度策略必須表示出兩方面的信息:(1)各個(gè)子任務(wù)被映射到哪個(gè)設(shè)計(jì)單元中去執(zhí)行,即對(duì)?STi∈P,要給出所在的設(shè)計(jì)單元NSi∈N;(2)每個(gè)子任務(wù)在其所映射的設(shè)計(jì)單元上的開(kāi)始時(shí)間,即對(duì)?STi∈P,要給出其所在的設(shè)計(jì)單元NSi上的開(kāi)始時(shí)間Tb(STi).4自適應(yīng)全局優(yōu)化概率搜索算法的基本法遺傳算法是模擬生物在自然環(huán)境中的遺傳和進(jìn)化過(guò)程的一種自適應(yīng)全局優(yōu)化概率搜索算法,其基本要素主要有染色體結(jié)構(gòu)設(shè)計(jì)、個(gè)體適應(yīng)度評(píng)價(jià)、遺傳算子設(shè)計(jì)以及運(yùn)行參數(shù)設(shè)定等.4.1始種群文化檢索設(shè)計(jì)子任務(wù)調(diào)度問(wèn)題的遺傳算法的框架如下:Step1.讀入一個(gè)任務(wù)偏序圖,構(gòu)造相應(yīng)的任務(wù)關(guān)聯(lián)矩陣,計(jì)算矩陣中各子任務(wù)的深度值H(STi).Step2.生成初始種群POP(t),t=0.Step3.如果不滿足算法的終止條件,執(zhí)行Step4;否則,轉(zhuǎn)Step9.Step4.計(jì)算種群中每個(gè)染色體的適應(yīng)度.Step5.執(zhí)行選擇運(yùn)算,形成下一代種群POP(t+1).Step6.以概率pci和pco分別執(zhí)行內(nèi)部交叉運(yùn)算和外部交叉運(yùn)算.Step7.以概率pm執(zhí)行變異運(yùn)算.Step8.計(jì)算種群中的每個(gè)染色體的調(diào)度時(shí)間t(S(i)),保存最好(t(S)最小)的染色體,t=t+1,轉(zhuǎn)Step3.Step9.輸出最好解,算法結(jié)束.4.2單元匹配矩陣遺傳算法中染色體結(jié)構(gòu)主要有一維串結(jié)構(gòu)、多參數(shù)的映射結(jié)構(gòu)、變長(zhǎng)串編碼結(jié)構(gòu)以及樹(shù)結(jié)構(gòu)編碼等.由于在任務(wù)調(diào)度問(wèn)題中,被調(diào)度的子任務(wù)之間以及同一設(shè)計(jì)單元的子任務(wù)之間存在一些關(guān)聯(lián)信息,一維的數(shù)據(jù)結(jié)構(gòu)難以表達(dá)這些信息,而樹(shù)結(jié)構(gòu)的特性又不能用來(lái)適應(yīng)度評(píng)估,因此我們采用第3節(jié)定義的二維矩陣——“單元-任務(wù)”匹配矩陣NPMm×n來(lái)描述.矩陣中的每一行可稱為基因行,如{cij|1≤j≤n}反映了調(diào)度在某個(gè)設(shè)計(jì)單元中的任務(wù)列表及其執(zhí)行順序;矩陣中的每一列稱為基因列,如{cij|1≤i≤n}反映了某一設(shè)計(jì)子任務(wù)與設(shè)計(jì)單元之間的映射關(guān)系.一個(gè)用二維矩陣描述的染色體,也就是設(shè)計(jì)子任務(wù)調(diào)度問(wèn)題的一個(gè)解.4.3初始種群的生成初始種群的生成方法是,將任務(wù)偏序圖中的所有子任務(wù)按其深度值劃分為h+1個(gè)子集DAG(i),其中0≤i≤h,h為DAG中所有子任務(wù)深度值中的最大值.對(duì)每個(gè)子集DAG(i),隨機(jī)地將子集中的所有子任務(wù)指派到m個(gè)設(shè)計(jì)單元中去,然后將所有調(diào)度到同一設(shè)計(jì)單元中的子任務(wù)按照其深度值作升序排列,從而得到一個(gè)子任務(wù)調(diào)度策略,即種群中的一個(gè)個(gè)體,也就是如前所述的一個(gè)用二維矩陣描述的染色體.重復(fù)執(zhí)行以上過(guò)程就可以生成具有一定規(guī)模的初始種群.初始種群的規(guī)模是初始種群生成的一個(gè)關(guān)鍵因素,它對(duì)遺傳算法具有直接的影響.初始種群的規(guī)模越大,其適應(yīng)度函數(shù)評(píng)估次數(shù)越多,算法陷入局部解的危險(xiǎn)性越小;但另一方面,初始種群規(guī)模越大,計(jì)算量相應(yīng)增加,從而會(huì)影響算法的效能.所以一般應(yīng)根據(jù)具體問(wèn)題,依靠經(jīng)驗(yàn)來(lái)確定初始種群的規(guī)模.4.4適應(yīng)度函數(shù)的確定在遺傳算法中,以個(gè)體適應(yīng)度的大小來(lái)確定該個(gè)體被遺傳到下一代群體中的概率.為正確計(jì)算不同情況下各個(gè)體的遺傳概率,要求所有個(gè)體的適應(yīng)度必須為正數(shù)或零,不能為負(fù)數(shù).在設(shè)計(jì)子任務(wù)的調(diào)度問(wèn)題中,可以使用任務(wù)調(diào)度策略S的完成時(shí)間t(S)作為評(píng)價(jià)該策略優(yōu)劣的標(biāo)準(zhǔn).遺傳算法按概率機(jī)制進(jìn)行選擇操作時(shí),適應(yīng)度值應(yīng)滿足非負(fù)性要求,使用如下適應(yīng)度函數(shù)f(S)=Tmax-t(S).其中,Tmax=n∑j=1max1≤i≤m(tij)為常數(shù),表示所有子任務(wù)在各設(shè)計(jì)單元中執(zhí)行所需時(shí)間最大值的總和,顯然f(S)≥0.4.5遺傳算子設(shè)計(jì)4.5.1個(gè)任務(wù)調(diào)度策略選擇算子的算法很多,本文采用適應(yīng)度比例方法.適應(yīng)度比例方法按個(gè)體適應(yīng)度的大小計(jì)算選擇概率.設(shè)群體大小為k,對(duì)于一個(gè)任務(wù)調(diào)度策略S(i),即一個(gè)個(gè)體相應(yīng)的遺傳選擇概率Ρsi=f(S(i))/k∑i=1f(S(i)).其中,Psi反映個(gè)體S(i)的適應(yīng)度在整個(gè)群體中的個(gè)體適應(yīng)度總和所占的比例,個(gè)體的適應(yīng)度越高,其被選擇的概率也越大;此外,為了使進(jìn)化過(guò)程中優(yōu)良的個(gè)體不被交叉和變異操作所破壞,對(duì)于選擇概率較高的個(gè)體不參與交叉變異操作,而直接進(jìn)入下一代群體.4.5.2應(yīng)基因列之間的外部交叉運(yùn)算本文提出兩種交叉算子:兩個(gè)染色體部分對(duì)應(yīng)基因列之間的外部交叉運(yùn)算,即外部交叉算子;同一染色體內(nèi)部的兩個(gè)基因行對(duì)應(yīng)基因片段之間的內(nèi)部交叉運(yùn)算,即內(nèi)部交叉算子.(1)q在si和s兩基本型基因列中,交叉點(diǎn)選擇,把si和s對(duì)于子任務(wù)調(diào)度策略(個(gè)體)S(i)和S(j)的外部交叉算子的操作過(guò)程如下:Step1.隨機(jī)生成一個(gè)數(shù)q(0≤q≤h),根據(jù)q在S(i)和S(j)的基因列中選擇交叉點(diǎn),把S(i)和S(j)按基因列分成前后兩部分;Step2.相互交換S(i)和S(j)對(duì)應(yīng)交叉點(diǎn)后的所有基因列,生成新的個(gè)體S′(i)和S′(j).顯然,這種染色體間對(duì)應(yīng)基因列交叉運(yùn)算不會(huì)破壞各設(shè)計(jì)單元(基因行)中各子任務(wù)深度值的升序排列順序.因此,新生成的個(gè)體S′(i)和S′(j)仍然是滿足定義4的.(2)兩qt0qh、交叉點(diǎn)和交叉點(diǎn)的形成我們交換同一染色體中不同基因行之間對(duì)應(yīng)的基因片段也可能產(chǎn)生新的個(gè)體.個(gè)體S(i)的內(nèi)部交叉過(guò)程如下:Step1.隨機(jī)生成一個(gè)數(shù)q(0≤q≤h),從S(i)中隨機(jī)選擇兩個(gè)基因行,根據(jù)q在這兩個(gè)基因行中選擇交叉點(diǎn),把它們分成前后兩部分;Step2.將這兩個(gè)基因行的后半部分所有任務(wù)相互交換,生成新的個(gè)體S′(i).容易證明,這兩個(gè)基因行在經(jīng)過(guò)內(nèi)部交叉運(yùn)算后,它們中的各基因(子任務(wù))仍然是按照其深度值升序排列的.因此,新生成的個(gè)體S′(i)也仍然是能夠滿足定義4的.4.5.3si中各基因行中深度值的計(jì)算在子任務(wù)調(diào)度問(wèn)題中,個(gè)體S(i)中的變異操作實(shí)質(zhì)是子任務(wù)遷徙的過(guò)程,即某個(gè)設(shè)計(jì)單元中的一個(gè)子任務(wù)被重新調(diào)度到另一個(gè)設(shè)計(jì)單元中的過(guò)程,具體操作過(guò)程如下:Step1.隨機(jī)生成一個(gè)數(shù)q(0≤q≤h),計(jì)算個(gè)體S(i)中各基因行中深度值等于q的子任務(wù)數(shù)Ni,0≤i≤n;Step2.從Ni最大的基因行中隨機(jī)選擇一個(gè)深度值等于q的基因(子任務(wù)),將其遷徙到Ni最小的基因行中,從而生成一個(gè)新的個(gè)體S′(i).顯然子任務(wù)經(jīng)遷徙后,這兩個(gè)基因行中的各基因仍然是按基因(子任務(wù))深度值升序排列的.因此,新生成的個(gè)體S′(i)也是滿足定義4的.5任務(wù)3.3調(diào)度策略下面以圖1所示的7個(gè)任務(wù)的調(diào)度過(guò)程為例,說(shuō)明本文提出的遺傳算法的實(shí)現(xiàn)過(guò)程.(1)從圖1中我們可以得到這7個(gè)任務(wù)的任務(wù)關(guān)聯(lián)矩陣、前趨任務(wù)集和深度值,如表1所示.(2)設(shè)有3個(gè)設(shè)計(jì)單元NS1,NS2和NS3,我們將這7個(gè)子任務(wù)按其深度值升序排列(H(ST1)≤H(ST2)≤H(ST3)≤H(ST4)≤H(ST5)≤H(ST6)≤H(ST7))及邊界約束條件調(diào)度到這3個(gè)設(shè)計(jì)單元中去,表2所示為一種可能的調(diào)度策略,即初始種群中的一個(gè)個(gè)體S,顯然該調(diào)度策略是滿足定義4的.(3)設(shè)各設(shè)計(jì)單元對(duì)各子任務(wù)的完成時(shí)間,即“單元-任務(wù)”效率矩陣如表3所示.(4)由表1～3,我們可以得到各子任務(wù)的所有前趨任務(wù)集,各任務(wù)的開(kāi)始時(shí)間和結(jié)束時(shí)間,如表4所示.從表4中我們可以得到各設(shè)計(jì)單元最后一個(gè)子任務(wù)的結(jié)束時(shí)間ts(NSi)分別為16,11和12.因此,由式(1)可得該任務(wù)調(diào)度策略S的完成時(shí)間t(S)=16.這樣我們就可以得到種群中每個(gè)個(gè)體的t(S),通過(guò)計(jì)算它們的適應(yīng)度以及選擇合適的交叉概率和變異概率,進(jìn)行選擇、交叉和變異等操作,最終生成新一代種群,計(jì)算并保存種群中t(S)最小的染色體.重復(fù)以上過(guò)程,當(dāng)滿足算法終止條件,如達(dá)到最多迭代代數(shù)或種群連續(xù)一定代數(shù)沒(méi)有進(jìn)化時(shí),即可得到該子任務(wù)調(diào)度問(wèn)題的最好解,即子任務(wù)的最優(yōu)調(diào)度策略.我們?cè)赑Ⅳ上用VC++編程實(shí)現(xiàn)了本文算法.針對(duì)文中實(shí)例,設(shè)定相同的算法參數(shù),種群規(guī)模設(shè)為100,計(jì)算速度約為每分