基于DAG模型的高效并行任務(wù)調(diào)度算法研究.pdf

1、在當(dāng)今的網(wǎng)絡(luò)并行計(jì)算環(huán)境中,并行任務(wù)調(diào)度已經(jīng)成為并行處理和高性能計(jì)算領(lǐng)域中極其重要的關(guān)鍵技術(shù),不恰當(dāng)?shù)恼{(diào)度甚至?xí)窒蝿?wù)并行化所帶來(lái)的收益.基于此,本文研究了一種以帶節(jié)點(diǎn)權(quán)值和邊權(quán)值的有向無(wú)環(huán)圖來(lái)表示并行任務(wù)的DAG調(diào)度問(wèn)題.一般情況下,這種DAG調(diào)度是個(gè)NP完全問(wèn)題.國(guó)內(nèi)外的研究學(xué)者在該領(lǐng)域進(jìn)行了廣泛而深入的研究.但是隨著網(wǎng)絡(luò)硬件技術(shù)和處理器技術(shù)的飛速發(fā)展,該領(lǐng)域仍然存在不少亟待解決的關(guān)鍵問(wèn)題.在這種新形勢(shì)下,本文主要研究了其中的三個(gè)

2、關(guān)鍵技術(shù),它們是:其一,針對(duì)非線性聚簇下怎樣高效調(diào)度獨(dú)立任務(wù)問(wèn)題,本文提出了一種基于最大并行度的獨(dú)立任務(wù)調(diào)度算法MPD;其二,針對(duì)某些調(diào)度算法雖然性能良好但復(fù)雜度高,或者某些調(diào)度算法雖然復(fù)雜度低但性能不佳的問(wèn)題,本文提出了一種在性能和復(fù)雜度間進(jìn)行折衷的DAG調(diào)度算法EZDCP,從而使得DAG調(diào)度算法更加實(shí)用;最后本文還提出了一個(gè)較為系統(tǒng)性的DAG粒度理論,并且根據(jù)fork和join圖,本文用數(shù)學(xué)方法嚴(yán)格證明了細(xì)粒度下非線性聚簇要優(yōu)于線性