[發明專利]一種基于插值算法面向計算通信聯合優化的負載均衡方法

有效

• 申請號: 201410503520.4
• 申請日: 2014-09-26
• 公開（公告）號: CN104281494B
• 公開（公告）日: 2017-05-10
• 發明（設計）人: 楊廣文;劉圣卓;張志遠;陳宇澍;姜進磊;韓寶玲
• 申請（專利權）人: 清華大學
• 主分類號: G06F9/50
• 分類號: G06F9/50
• 代理公司: 北京清亦華知識產權代理事務所(普通合伙)11201
• 代理人: 廖元秋

技術領域

本發明屬于高性能可擴展并行數值模擬應用領域，特別涉及一種基于插值算法的面向計算通信聯合優化的負載均衡方法。

背景技術

在高性能可擴展并行數值模擬應用領域，如流體動力、高溫高壓物理過程模擬計算等，常常需要使用成百上千的處理器并行執行運算任務。這些計算通常具有如下特點：(1)數據元素通常可以被映射到靜態且均勻的多維網格上；(2)不同數據元素的運算時間可能不同；(3)數據元素的運算量隨計算的時間步發生變化且相近時間步的變化很小；(4)計算的通信通常只與相鄰數據元素相關。為提高計算效率，需使每個處理器在相同時間步的計算時間和通信時間(不含等待時間)之和基本相當，并盡可能降低通信延遲。動態負載均衡機制通過合理劃分數據元素使得每個處理器承擔的計算任務相對均衡，并能根據處理器的負載變化對其進行動態調整。

負載均衡問題可定義為：設需要處理的N個數據元素分布在一個多維空間定義為V_d表示d維空間(d＝1,2,3,4)，用來執行并行運算的處理器共M個定義為{(p_i)|1≤i≤M}，通常M<<N；N個數據元素被依據一定規則劃分為M個數據塊，每個處理器負責一個數據塊。在某個時間步處理器的有效運算時間(包括有效的計算時間和通信時間)分別為{(C_i)|1≤i≤M}，則該時間步的負載均衡效率E可以定義為：

顯然E≤1，E越大負載越均衡，而動態負載均衡的目的是使E的值在運算過程中大部分時間保持在一定的閾值以上且越大越好。負載均衡通常在兩個時機發揮作用：第一，是計算開始之前，這時需要對數據元素的計算量等進行估計，并對多維空間分布的數據元素進行劃分；第二，在計算階段發現處理器負載不均衡(即負載均衡效率低于設定的閾值)時，對數據劃分進行動態調整。

已有的一種已有的針對并行計算的負載均衡方法通常可以分為初始劃分和動態調整兩個階段：

具體實現步驟包括兩個階段。

初始劃分階段包括：

步驟1-1)采用空間填充曲線法對多維空間分布的數據元素進行排序；

步驟1-2)平均劃分(使每個數據塊的數據元素個數相當)條件下，測量一個時間步各處理器的計算時間；

步驟1-3)假定位于同一處理器的數據元素均攤該處理器的計算時間(包括計算時間和通信時間)，根據處理器的計算時間可以得到每個數據元素近似的計算時間；

步驟1-4)根據數據元素的近似計算時間，重新劃分數據塊，使每個數據的計算時間相當；

步驟1-5)根據數據塊的新劃分在處理器之間調整數據元素；繼續運行一個時間步，并測量各處理器的有效計算時間；

步驟1-6)計算負載均衡效率，如果負載均衡效率沒有達到要求，則轉到步驟1-3)，重新進行劃分數據塊；如果負載均衡效率達到要求，則繼續運行，進入動態調整階段；

階段2：動態調整階段

步驟2-1)根據設定的時間間隔，定時查看各處理器的負載均衡效率，收集n個時間步各處理器的計算時間，如果n個時間步的負載均衡的效率均低于設定的閾值(如80％)，則轉入步驟2-2)，否則繼續運行，等待下一個時間間隔；

步驟2-2)收集最近一個時間步的計算時間；轉入步驟1-3)繼續執行。

以上方法存在兩點不足：

第一，該方法在對數據元素的計算時間進行估計時，沒有將計算時間和通信時間分開考慮，計算量估計不精確、調整次數多；

第二，簡單假設同一處理器的數據元素計算量相同，數據元素的計算量估計誤差較大，收斂周期長。

發明內容

本發明的目的是為克服已有技術的不足，提出一種基于插值算法的面向計算通信聯合優化的負載均衡方法，旨在流體動力、高溫高壓物理過程模擬計算等技術領域提升參與運算的各處理器任務的均衡性，提高運行效率，節約計算資源。

本發明提出的一種基于插值算法的面向計算通信聯合優化的負載均衡方法，該方法分初始劃分和動態調整兩個階段，其特征在于，初始劃分階段包括以運算的實測計算量和責任通信量作為基礎值，利用插值算法推算計算量累加函數和通信量變化率函數的近似函數，然后以這兩個函數為參照通過多次迭代獲得最佳的數據劃分方案；動態調整階段包括并行程序運行過程，監視每次運算的計算量和通信量變化，分析處理器的負載均衡狀況并預測負載均衡的趨勢，當負載均衡的效率或預測值低于設定的閾值時，根據當前的計算量和通信量的實測值再次計算量累加函數和通信量變化率函數的近似函數，并對數據塊的劃分進行動態調整。