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

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

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

3、業(yè)任務(wù)調(diào)度的啟發(fā)式算法。
　　 在涉及到的所有啟發(fā)式調(diào)度算法都采用DAG(Directed Acyclic Graph)模型來(lái)描述并行作業(yè)的狀況，因?yàn)镈AG模型更能真實(shí)地反映并行作業(yè)的實(shí)際情況。同時(shí)所有算法都考慮了處理器異構(gòu)的因素。
　　 在研究和分析兩個(gè)異構(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)計(jì)算環(huán)境下關(guān)鍵路徑已失去表達(dá)最迫切需要調(diào)度任務(wù)的意義，算法LBP摒棄了傳統(tǒng)的以關(guān)鍵路徑作為優(yōu)先性首要考慮的思想，而以任務(wù)的層次性和分支數(shù)來(lái)考慮任務(wù)的優(yōu)先性，理論證明和試驗(yàn)分析說(shuō)明，在異構(gòu)計(jì)算環(huán)境中算法LBP和算法HEFT、CPOP具有相同的時(shí)間復(fù)雜度，但算法LBP比上述兩算法的調(diào)度性能相比較有較大的改進(jìn)。
　　 除此之外，算法LBP本身具有天然較好的并行性。并行作業(yè)任務(wù)調(diào)度算法的并行化研究并不是很多，因

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

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

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