基于安全聚集策略的異構(gòu)機(jī)群調(diào)度算法研究.pdf

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

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

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