基于安全聚集策略的異構機群調度算法研究.pdf

1、近年來，高性能計算呈現(xiàn)加速發(fā)展態(tài)勢，機群是高性能計算的一種重要實現(xiàn)方式。異構機群由于具有高效能特性，在國際上漸受重視。異構機群系統(tǒng)由大量不同機群組成，不同機群中的計算內核有不同的性能與能耗，機群間以及機群內通信帶寬與通信產生的單位能耗也不盡相同。因此，相關研究者面臨巨大挑戰(zhàn)。首先，對于由有向無環(huán)圖(DirectedAcyclicGraph，DAG)建模的大規(guī)模應用程序，如何將其中的眾多任務映射到各異構機群上使得系統(tǒng)能耗達到最小。其次，如

2、何在各個機群上對這些任務進行有效調度，在滿足時間約束的前提下進一步減少系統(tǒng)總能耗。
　　上述的映射與調度問題是NP難的。本文對利用整數(shù)線性規(guī)劃(IntegerLinearProgramming，ILP)技術實現(xiàn)任務映射算法從而實現(xiàn)任務到異構機群的最優(yōu)映射結果進行了探索。由于ILP映射算法的計算時間隨問題規(guī)模增大呈指數(shù)級增長。為了改進ILP映射算法的計算性能，本文首先提出一種安全圖聚集(SafeGraphGrouping，SGG)算

3、法，把通信量大的任務節(jié)點聚集成節(jié)點簇，在減小問題規(guī)模的同時盡可能減少節(jié)點簇間的通信量。然后，使用ILP映射算法解決大規(guī)模應用到異構機群的映射問題。最后，提出時間約束下的局部調度(TimeConstrainedLocalScheduling，TCLS)算法來進一步減少系統(tǒng)總能耗。由于SGG算法可以保證聚集后的圖仍然為有向無環(huán)圖，局部調度過程將不會發(fā)生死鎖。實驗結果表明，SGG算法與現(xiàn)有的圖聚集算法相比，能減少5.14％的系統(tǒng)總能耗。相比較