[發明專利]一種面向異構服務器結構的圖計算負載均衡方法

有效

• 申請號: 201711274503.8
• 申請日: 2017-12-06
• 公開（公告）號: CN108089918B
• 公開（公告）日: 2020-07-14
• 發明（設計）人: 曹強;盛豐
• 申請（專利權）人: 華中科技大學
• 主分類號: G06F9/48
• 分類號: G06F9/48;G06F9/50
• 代理公司: 華中科技大學專利中心 42201
• 代理人: 張建偉;曹葆青

1.一種面向異構服務器結構的圖計算負載均衡方法，其特征在于，包括如下階段：

檢測不均衡階段：在圖計算任務運行時，主控節點監測每次超級步中各計算節點的處理時間，并根據本次超級步中所有計算節點處理時間的變異系數和用戶預設的閾值，判斷各計算節點上的圖計算負載是否均衡；所述變異系數為反映一組數據值離散程度的參數；

擬定遷移計劃階段：各計算節點確定各自需要遷移的頂點，主控節點確定這些頂點對應的遷入節點；

實施遷移階段：所有遷出節點采用延遲遷移的方式傳輸頂點信息到對應的遷入節點上，主控節點更新頂點遷移后的位置信息；

其中，所述檢測不均衡階段中，根據本次超級步中所有計算節點處理時間的變異系數和用戶預設的閾值，判斷各計算節點上的圖計算負載是否均衡，包括：

各計算節點將本次超級步中監測的處理時間發送給主控節點；

主控節點計算本次超級步中所有處理時間的變異系數CV：

其中u為本次超級步中所有計算節點的平均處理時間，N為計算節點的總個數，t_i為計算節點i在本次超級步中監測的處理時間；

若上次和本次超級步中計算所得的變異系數CV都大于用戶預設的閾值CV_thr，則主控節點判定各計算節點上的圖計算負載不均衡；否則，認定各計算節點上的圖計算負載為是均衡的；

主控節點將判定的結果發送給所有計算節點。

2.如權利要求1所述的面向異構服務器結構的圖計算負載均衡方法，其特征在于，包括以下步驟：

步驟1所有計算節點導入圖算法和圖數據集；

步驟2所有計算節點執行圖算法的一次超級步；

步驟3主控節點判斷各計算節點上的圖計算負載是否均衡；

步驟4若步驟3中判定結果為負載不均衡，則進入擬定遷移計劃階段，轉步驟5；否則，轉步驟7，所有計算節點進入下一次超級步；

步驟5各計算節點確定各自需要遷移的頂點，主控節點確定這些頂點對應的遷入節點；

步驟6所有計算節點采用延遲遷移的方式，傳輸頂點信息到對應的遷入節點上，主控節點更新并匯總頂點遷移后的位置信息；

步驟7重復步驟2至步驟6，直至圖算法收斂。

3.如權利要求2所述的面向異構服務器結構的圖計算負載均衡方法，其特征在于，步驟5中擬定遷移計劃階段包括以下子步驟：

步驟5-1主控節點將本次超級步中平均處理時間u發送給各計算節點；

步驟5-2各計算節點根據平均處理時間u，判定自身是遷出節點還是遷入節點；

若是遷出節點，則計算其需要遷出的邊數E_out，并進一步根據E_out確定需要遷出的頂點；

若是遷入節點，則計算其需要遷入的邊數E_in；

步驟5-3計算節點將各自需要遷出或遷入的邊數發送給主控節點；

步驟5-4主控節點根據各計算節點需要遷出或遷入的邊數，確定遷移頂點對應的遷入節點；

步驟5-5主控節點將遷移頂點對應的遷入節點信息發送給相應的遷出節點。

4.如權利要求3所述的面向異構服務器結構的圖計算負載均衡方法，其特征在于，步驟5-2中各遷出節點確定各自需要遷出的頂點時操作如下：

各計算節點按照頂點所連接的邊數，對其所維護的頂點降序排列；當計算節點i接收到主控節點發來的平均處理時間u后，計算本次超級步中其處理時間t_i與平均處理時間u的差值Δt＝t_i-u；當Δt為正時，表示計算節點i的圖計算負載高于平均負載水平，該節點需要遷出的邊數為E_out＝(t_i-μ)*EPS_i，其中EPS_i為計算節點i在本次超級步中平均每秒所處理的邊數；

當Δt為負時，表示計算節點i的圖計算負載低于平均負載水平，該節點需要遷入的邊數為E_in＝(μ-t_i)*EPS_i；

遷出節點需要遷出的邊數E_out確定后，則需要遷出的頂點可以從該遷出節點所維護的頂點中按照所連接的邊數降序選出，直至選出頂點的邊數總和達到E_out。