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

有效

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

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

2.如權利要求1所述方法，其特征在于，所述初始劃分階段具體包括以下步驟：

步驟1-1)采用空間填充曲線法對多維空間分布的數據元素進行排序，對處理器編號；設N個數據元素從多維空間映射到一維空間，映射后的N個數據元素排列記為x₁,x₂,…,x_N；設參與運算的處理器有M個，M<<N，將M個處理器編號，記為p₁,p₂,…,p_M；

步驟1-2)對數據元素平均劃分的條件下，測量各處理器一個時間步的計算時間和責任通信時間；對平均劃分的數據元素進行微調后，測量各處理器一個時間步的責任通信時間；具體包括：

第一次劃分，將x₁,x₂,…,x_N平均分成M塊，分配到各處理器并啟動運行一個時間步，得到各處理器計算時間T_Cj，責任通信時間T_Rj1；第二次劃分，對第一次劃分的各數據塊進行微調，依次將第一次劃分的數據塊的后面k個元素移到下一個數據塊，最后一個數據塊只接收前一個數據塊；將微調后的數據塊分配到各處理器并啟動運行一個時間步，得到各處理器責任通信時間T_Rj2；

步驟1-3)根據實測的各處理器的計算時間，利用插值法求解計算量累加函數；具體實現為：

設在x₁,x₂,…,x_N排列下，數據元素x的計算量密度函數為f(t,x)，t為時間參數；在n個時間步內，n≤3，假設f保持不變，則計算量密度函數表示為與時間無關的函數f(x)；

(x_j1,x_j2)為處理器p_j負責的數據塊，則處理器的計算時間為T_Cj表示為

全部處理器的計算時間為：

$\left\{\begin{array}{c}{\&Integral;}_{x_{11}}^{x_{12}}f\left(x\right)=T_{C1}\\ {\&Integral;}_{x_{21}}^{x_{22}}f\left(x\right)=T_{C2}\\ \mathrm{...}\\ {\&Integral;}_{x_{M1}}^{x_{M2}}f\left(x\right)=T_{C3}\end{array}\right.---\left(1\right)$

假設函數f(x)在x₁,x₂,…,x_N排列中選取的M個點X₁,X₂,…,X_M上有值；

對于X_i<x<X_i+1，得到f(x)的插值近似函數：

$f\left(x\right)=\frac{(x-X_i)f\left(X_{i+1}\right)+(X_{i+1}-x)f\left(X_i\right)}{X_{i+1}-X_i}---\left(2\right)$

將(2)式代入方程組(1)，得到以f(X₁),f(X₂),…,f(X_M)為未知數的線性方程組，求解可得f(x)在X₁,X₂,…,X_M處的值；利用插值算法求得計算量的累加函數F(x)，F(x)表示為X₁,X₂,…,X_M之間的分段形式；

步驟1-4)根據實測的各處理器的計算時間，利用插值法求解責任通信時間函數的導函數；具體實現為：

處理器p_j的責任通信時間函數為g(t,x_j1,x_j2)，x_j1,x_j2為處理器所負責的數據元素的起點和終點；在較少的n個時間步內，n≤3，假設g保持不變，則處理器p_j的責任通信時間函數表示為g(x_j1,x_j2)；

假設g(x)為連續函數且在x點有導數，求解g(x)在指定點的導數G'(x)；

g(x_j1,x_j2)代表某時間步處理器p_j的責任通信時間，元素x_j1+Δx為x_j1的右鄰點，得到：

g(x_j1+Δx,x_j2)＝-G'(x_j1)Δx+g(x_j1,x_j2) (3)

g(x_j1,x_j2+Δx)＝G'(x_j2)Δx+g(x_j1,x_j2) (4)

(x_j1,x_j2)和(x_j3,x_j4)分別為處理器p_j在兩次劃分中所負責的數據塊，兩個數據塊劃分的大部分數據元素重疊，利用式(3)、(4)分別對處理器負責的數據塊的左右兩端做近似處理得：

$g(x_{j3},x_{j4})-g(x_{j1},x_{j2})=-G^{\&prime;}\left(\frac{x_{j1}+x_{j3}}{2}\right)(x_{j3}-x_{j1})+G^{\&prime;}\left(\frac{x_{j2}+x_{j4}}{2}\right)(x_{j4}-x_{j2})---\left(5\right)$

為計算通信時間函數，測試兩次不同劃分的責任通信時間；處理器p_j兩次劃分的責任通信時間分別為T_Rj1，T_Rj2，則，

$G^{\&prime;}\left(\frac{x_{j2}+x_{j4}}{2}\right)(x_{j4}-x_{j2})-G^{\&prime;}\left(\frac{x_{j1}+x_{j3}}{2}\right)(x_{j3}-x_{j1})=T_{Rj2}-T_{Rj1}---\left(6\right)$

假設函數G'(x)在x₁,x₂,…,x_N排列中選取的M個點X₁,X₂,…,X_M上有值；

對于X_i<x<X_i+1，得到G'(x)的插值近似函數：

$G^{\&prime;}\left(x\right)=\frac{(x-X_i)G^{\&prime;}\left(X_{i+1}\right)+(X_{i+1}-x)G^{\&prime;}\left(X_i\right)}{X_{i+1}-x_i}---\left(7\right)$

將式(7)代入形如式(6)的所有處理器的方程組，得到以G'(X₁),G'(X₂),…,G'(X_M)為未知數的線性方程組，求解得到G'(x)在X₁,X₂,…,X_M處的值，利用插值法求得G'(x)的近似函數，G'(x)表示為X₁,X₂,…,X_M之間的分段形式；

步驟1-5)根據計算量密度函數和責任通信時間函數，以及根據指定的數據塊的平均計算量和通信量，為每個數據塊分配數據元素；當分配不平均時，修改為數據塊指定的平均計算量和通信量，迭代求解數據塊劃分方案；具體實現為：

根據已知的F(x)、G'(x)，在x₁,x₂,…,x_N上求一組X'₀,X'₁,…,X'_M其中X'₀＝x₁，X'₀＝x_N，使式(8)最小：

MAX(F(X'_j)-F(X'_j-1)+g(X'_j,X'_j-1)) (8)

F(X'_j)-F(X'_j-1)表示以X'_j-1和X'_j分別為起點和終點的數據塊的計算量，g(X'_j,X'_j-1)則表示這個數據塊的責任通信量；

步驟1-5-1)設為各處理器計算時間的平均值；g₀為各處理器責任通信時間的平均值；

步驟1-5-2)使用累加法求X'₁在數據元素x₁,x₂,…,x_N中使式(9)成立的最右的元素x_i；

$F\left({X^{\&prime;}}_1\right)-F\left({X^{\&prime;}}_0\right)+g(x_1,{X^{\&prime;}}_1)\&le;\stackrel{\&OverBar;}{F}+\frac{g_0}{2}---\left(9\right)$

其中F(X'₀)＝0，x₁₁,x₁₂分別為第一個數據塊的起點和終點；

由式(9)得到的X'₁，則(x₁,X'₁)為第一個處理器p₁的預分配數據塊，表示為(X'₀,X'₁)；

步驟1-5-3)根據已求得的X'₁，結合式(10)利用遞推法依次求得剩余的數據塊；

$F\left({X^{\&prime;}}_j\right)-F\left({X^{\&prime;}}_{j-1}\right)+g({X^{\&prime;}}_{j-1},{X^{\&prime;}}_j)\&le;\stackrel{\&OverBar;}{F}+\frac{g_0}{2}---\left(10\right)$

其中，

$g({X^{\&prime;}}_{j-1},{X^{\&prime;}}_j)=g(x_{i1},x_{i2})-G^{\&prime;}\left(\frac{{X^{\&prime;}}_{j-1}+x_{i1}}{2}\right)({X^{\&prime;}}_{j-1}-x_{i1})+G^{\&prime;}\left(\frac{{X^{\&prime;}}_j+x_{i2}}{2}\right)({X^{\&prime;}}_j-x_{i2})---\left(11\right)$

式(11)中，g(x_i1,x_i2)為測試值；

步驟1-5-4)根據具體情況，對參數g₀調整后重新進行數據塊劃分；

第一種情況，當遞推法計算到第i步(i<M)，x₁,x₂,…,x_N中元素已經取盡，這時計算終止；新的g₀設為回到步驟1-5-2)，將g'₀代入式(9)重新開始迭代計算；

第二種情況，計算進行了M步，但x₁,x₂,…,x_N中的元素還沒有取盡，設X_M＝x_k，新的g₀設定為回到步驟1-5-2)，將g'₀代入式(9)重新開始迭代計算；

第三種情況，當計算到第M步，X_M取值為x₁,x₂,…,x_N集合的最后一個元素，且小于一定的值(如)時，迭代停止，轉步驟1-5-5)；

第四種情況，迭代達到設定的次數，說明計算量和通信量無法達到相對均衡，此時迭代停止，轉步驟1-5-5)；

步驟1-5-5)當迭代停止時，求得一組X'₀,X'₁,…,X'_M，以X'₀,X'₁,…,X'_M作為分割點將數據元素排列x₁,x₂,…,x_N分成M個數據塊，由此得到數據劃分方案；

步驟1-6)將劃分的數據塊分配給所有的處理器，啟動運行n個時間步，收集的計算時間和通信時間分析負載均衡的效率；如果負載均衡效率低于要求門限，收集最近一個時間步各處理器計算時間T_Cj，責任通信時間T_Rj1；對現有劃分進行微調后，運行一個時間步，得到各處理器的責任通信時間T_Rj2；進入步驟1-3)重新進行數據塊劃分；如果負載均衡效率達到要求門限，則繼續運行，進入第二階段進行動態調整；

所述動態調整階段，具體包括以下步驟：

步驟2-1)根據設定的時間間隔，定時查看負載均衡效率，收集n個時間步各處理器的計算時間和責任通信時間，n≤20，如果預測未來m個時間步的負載均衡效率平均值高于設定的閾值，則繼續運行，等待下個時間間隔再繼續檢測，否則啟動負載動態調整，執行步驟2-2)；

步驟2-2)收集最近一個時間步收集的各處理器計算時間T_Cj，責任通信時間T_Rj1；在不同劃分情況下的通信時間的測試值；求解計算量密度函數f和通信量函數的導數G'；采用步驟1-2)相同的數據塊劃分微調方法對現有劃分微調后，運行一個時間步，得到各處理器的責任通信時間T_Rj2；轉入步驟1-3)繼續運行，重新進行數據塊劃分。