任務(wù)間相互依賴的并行作業(yè)調(diào)度算法研究.pdf

1、以工作站機群為代表的并行計算模式無疑是并行分布式計算的重點研究領(lǐng)域，同時，隨著網(wǎng)絡(luò)互聯(lián)技術(shù)的發(fā)展，并行計算環(huán)境也從局域網(wǎng)范疇向廣域網(wǎng)范疇拓展，在機群計算的基礎(chǔ)上出現(xiàn)了新的基于因特網(wǎng)的并行分布式計算模式即網(wǎng)格計算。而無論在機群計算還是網(wǎng)格計算的實現(xiàn)中，如何對并行作業(yè)的任務(wù)進行調(diào)度是影響整個系統(tǒng)成敗和性能的關(guān)鍵因素，因而研究多處理器或多計算機的任務(wù)調(diào)度算法對于機群計算和網(wǎng)格計算都具有十分重要的理論和實際意義。
　　 隨著并行處理和并

2、行計算概念的出現(xiàn)，對并行作業(yè)任務(wù)調(diào)度問題的研究就由來已久。前人的研究已經(jīng)證明，即使在簡化模型的情形下，絕大多數(shù)的并行作業(yè)任務(wù)調(diào)度問題也是NP完全問題，所以在計算復雜度可以接受的前提下獲取并行作業(yè)任務(wù)調(diào)度問題最優(yōu)解的努力無疑是不現(xiàn)實的。而啟發(fā)式算法由于在更接近實際情況下具有算法實現(xiàn)容易、性能較好以及時間復雜度較低的優(yōu)點被普遍采用，在研究相應(yīng)的已有任務(wù)調(diào)度算法的基礎(chǔ)上，針對靜態(tài)編譯時調(diào)度、動態(tài)運行時調(diào)度和實時調(diào)度的不同要求提出了一系列并行作

3、業(yè)任務(wù)調(diào)度的啟發(fā)式算法。
　　 在涉及到的所有啟發(fā)式調(diào)度算法都采用DAG(Directed Acyclic Graph)模型來描述并行作業(yè)的狀況，因為DAG模型更能真實地反映并行作業(yè)的實際情況。同時所有算法都考慮了處理器異構(gòu)的因素。
　　 在研究和分析兩個異構(gòu)環(huán)境下典型的靜態(tài)調(diào)度算法HEFT和CPOP的基礎(chǔ)上提出了基于層次和分支優(yōu)先性的調(diào)度算法LBP。目前絕大多數(shù)靜態(tài)啟發(fā)式調(diào)度算法是關(guān)鍵路徑的表調(diào)度算法，算法HEFT和C

4、POP亦不例外，但是在異構(gòu)計算環(huán)境下關(guān)鍵路徑已失去表達最迫切需要調(diào)度任務(wù)的意義，算法LBP摒棄了傳統(tǒng)的以關(guān)鍵路徑作為優(yōu)先性首要考慮的思想，而以任務(wù)的層次性和分支數(shù)來考慮任務(wù)的優(yōu)先性，理論證明和試驗分析說明，在異構(gòu)計算環(huán)境中算法LBP和算法HEFT、CPOP具有相同的時間復雜度，但算法LBP比上述兩算法的調(diào)度性能相比較有較大的改進。
　　 除此之外，算法LBP本身具有天然較好的并行性。并行作業(yè)任務(wù)調(diào)度算法的并行化研究并不是很多，因

5、為調(diào)度算法本身固有的串行性。盡管靜態(tài)啟發(fā)式調(diào)度算法的時間復雜度較低，但在任務(wù)規(guī)模過大的情況下算法所花費的時間也可能很可觀。根據(jù)串行算法LBP各步驟中數(shù)據(jù)和操作的相關(guān)性，提出了算法LBP的并行算法PLBP，理論證明算法PLBP與LBP具有相同的調(diào)度性能，與文獻中已有的并行化調(diào)度算法HPMCP及PBSA相比，算法PLBP的時間復雜度更低。
　　 靜態(tài)調(diào)度算法受限于DAG中各參數(shù)必須在調(diào)度之前完全獲取的前提條件，而在實際科學計算中這一

6、前提并不能得到滿足，DAG中任務(wù)參數(shù)一般是在其父任務(wù)執(zhí)行完成時才能實例化，即DAG中各任務(wù)是邊調(diào)度邊執(zhí)行的。在分析已有幾種典型的動態(tài)調(diào)度算法基礎(chǔ)上，采用DAG的參數(shù)化模型PTG(Parameterized Task Graph)，并對建立在PTG模型上的動態(tài)調(diào)度算法PTGDS進行研究，在任務(wù)調(diào)度的同步性和調(diào)度策略等方面對其進行改善，并把靜態(tài)調(diào)度算法LBP的思想融入其中，提出了改進的并行作業(yè)動態(tài)調(diào)度算法IPTGDS。并在理論上分析算法IP

7、TGDS是可行的，同時試驗結(jié)果說明算法IPTGDS與PTGDS相比調(diào)度性能更優(yōu)。
　　 把研究的基于DAG的靜態(tài)調(diào)度算法和動態(tài)調(diào)度算法的成果引入到實時系統(tǒng)中，建立了異構(gòu)環(huán)境下的動態(tài)實時調(diào)度模型，在此模型上提出了動態(tài)最早完成優(yōu)先算法DEFF；同時，對實時環(huán)境下的動態(tài)調(diào)度經(jīng)典算法――近視算法進行分析，借鑒近視算法中的回溯思想，提出了基于有限回溯的動態(tài)調(diào)度算法BBDS，算法BBDS與近視算法的不同在于：近視算法針對元任務(wù)集而算法BBD