基于DAG模型的高效并行任務調度算法研究.pdf

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

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