[發明專利]隨機擴散動態負載均衡方法

有效

• 申請號: 201510467927.0
• 申請日: 2015-07-31
• 公開（公告）號: CN105117292B
• 公開（公告）日: 2018-09-14
• 發明（設計）人: 張平健;嚴善楷;王世緯;詹治海
• 申請（專利權）人: 華南理工大學
• 主分類號: G06F9/50
• 分類號: G06F9/50
• 代理公司: 廣州市華學知識產權代理有限公司 44245
• 代理人: 羅觀祥

本發明公開了一種隨機擴散動態負載均衡方法，包括以下步驟：步驟1、把計算任務隨時間的遷移而位于哪個進程這一狀態變量看作是一個隨機過程，每次迭代通過隨機擴散信息交換協議以及基于概率圖模型的參數學習過程；步驟2、計算出任務量隨機遷移矩陣，據此進行任務遷移來達到負載均衡。具有良好的擴展性和良好的全局均衡效果等優點。

技術領域

本發明涉及一種在多核集群上進行并行計算的動態負載均衡技術，特別涉 及一種隨機擴散動態負載均衡方法，該均衡方法主要是針對異構集群系統。

背景技術

由于芯片制造工藝以及存儲帶寬的制約，一味地追求單機性能顯得越來越 不現實。并行計算自提出以來一直是解決大規模計算問題的主要手段，近幾十 年來更是被廣泛關注和研究，并行計算系統主要的硬件模型主要有對稱多處理 機系統(Symmetric MultiProcessing，SMP)和大規模并行處理系統(Massively Parallel Processing，MPP)等，其對應的計算模式分別是多核計算和集群計 算。多核集群并行計算是當今計算的主流模式已成為工業界和學術界的共識， 尤其是在高性能計算(High Performance Computing，HPC)領域。隨著應用復 雜性和處理數據量的增長，以及要求提供計算服務的用戶數量的增多，集群系 統的單機核數與計算結點數目將不斷增加，甚至通過安裝具有高吞吐率的加速卡，如圖形處理器(GPU)、現場可編程門陣列(FPGA)以及眾核集成協處理器 (MIC)，來增強單機計算性能。

業務數據的累積使得各個行業對數據處理和計算性能的需求從來沒有如此 迫切，為了有效地利用集群系統的計算資源，工業界和學術界一直致力于研究 影響并行計算應用性能的因素。除了計算系統本身的規模、各個結點的計算能 力、互聯網絡、存儲系統以及并行算法本身的設計以外，負載均衡往往是一個 被忽視的重要因素。負載不均衡帶來的壞處只有在處理大規模數據的時候才會 比較突出，在一般的并行計算應用中，因為進程的數量較少或者任務量不多， 負載不均衡現象并不明顯，如果不是有對比實驗數據或者專門測試負載均衡情 況那么是很難識別出來的，這種程序一旦遇上數據量或者運行規模翻幾倍的情 況則很可能無法勝任。

對于一些簡單應用，例如結構化的網格計算、稠密矩陣運算，負載容易被 預測，而且不會動態地改變。這類應用并不需要復雜的負載均衡技術，只需要 簡單的靜態負載均衡(Static Load Balancing，SLB)，在運行之前把計算任務 盡可能平均地分配到各個計算進程便可以滿足需要。然而，隨著復雜應用的出 現，計算負載隨時間而變化并且其變化趨勢較難預測的現象已經變得十分普遍。 例如，在分子動力學模擬應用里，如果分子是按數量靜態分配給各個進程，分 子的移動就不會引起負載不均衡；如果一些復雜的模擬算法為了更好地進行作 用力的計算而把分子按空間坐標分配給各個進程，分子的移動將帶來負載不均 衡并嚴重地影響到算法整體的性能。在科學計算軟件中，計算流體動力學、氣 候模擬中的降雨和云層等都是經常會引起負載不均衡的大型復雜應用。

動態負載均衡(Dynamic Load Balancing，DLB)技術通過在運行時間隔性 地在進程之間遷移計算任務來減少應用的總體運行時間，這種技術能有效地解 決以上所說的復雜應用所產生的負載不均衡現象，帶來應用整體性能的提升。 不但如此，當應用是運行在一個結點間或者進程間計算性能不一致的集群上時， 即使每個進程的負載能均衡分配，負載不均衡的現象依然存在，因為這時候各 個計算進程的有效運行時間并不一致，也就是說進程之間的等待會帶來計算資 源的浪費。出現進程間計算性能不一致的原因有很多，例如異構系統中部分結 點的配置差異，部分結點安裝了加速卡可以為運行其上的進程提供加速服務， 溫度、濕度的變化可能會使機器的計算性能出現波動，這些情況一般很難進行 統計或預測，所以動態負載均衡技術更加顯得重要。