基于動態(tài)通信競爭的任意處理機網絡表調度算法.pdf

1、計算技術和網絡技術的飛速發(fā)展，極大地促進了基于網絡環(huán)境的科學應用研究。許多應用領域對計算能力的要求越來越高，單臺計算機已很難滿足計算需求。由多處理機構建的高性能計算系統(tǒng)已成為計算技術發(fā)展的必然，然而在這種系統(tǒng)環(huán)境下調度任意結構并行任務并獲取最優(yōu)解的問題仍然是NP完全難題。表調度算法是解決此類問題的一種經典啟發(fā)式任務調度算法，具有調度性能較好，時間復雜度較低等優(yōu)點。但經典表調度算法假定目標處理機全互連，以及調度節(jié)點時忽略節(jié)點之間的通信，顯

2、然不符合任意處理機網絡計算環(huán)境的需求。因為對于任意處理機網絡拓樸結構的異構系統(tǒng)，各任務之間的通信競爭不可忽略，這種任務通信對整個并行應用程序的執(zhí)行有重要影響。因而，考慮通信競爭的調度算法是提高并行分布式計算系統(tǒng)實際性能的重要途徑之一。 本文研究工作主要方法是在調度算法中考慮通信競爭，即調度任務時同時考慮節(jié)點和通信邊的調度。為了實現(xiàn)調度目標，提出一個基于最短路徑搜索算法的最早通信完成路徑查找算法(EFCS)，采用插入式鏈路實現(xiàn)策略

3、，以達到通信邊的動態(tài)調度；對于任意處理機網絡環(huán)境下的任務優(yōu)先級計算問題，受HEFT算法啟發(fā)提出遞歸優(yōu)先權計算公式，并且按非升序排列獲得各任務優(yōu)先級。同時為了降低算法執(zhí)行時間，采用OpenMP實現(xiàn)算法的并行化，理論分析表明并行算法可達到的加速比為O(PPE)。以隨機產生程序任務圖和現(xiàn)實中的實際應用程序為數(shù)據來源，在兩類不同的任意處理機網絡目標系統(tǒng)上進行了模擬實驗。結果表明本算法明顯優(yōu)于考慮通信競爭的靜態(tài)表調度算法和不考慮通信競爭的表調度算