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

有效

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

本發明公開了一種面向異構服務器結構的圖計算負載均衡方法：根據所有計算節點在一次超級步中處理圖計算負載所用的時間，主控節點計算出本次超級步中所有處理時間的變異系數，若連續兩次超級步中的變異系數大于預設的閾值，則判定各計算節點在運行時的圖計算負載不均衡，需要在本次超級步結束后對計算節點上的圖計算負載重新分配，否則所有計算節點將繼續執行下次超級步。本發明方法利用頂點遷移來平衡每次超級步中計算節點間的處理時間，從而有效地降低每次超級步中所有計算節點的同步開銷，縮短圖計算任務的運行時間，并提高各計算節點運行時的資源利用率。

技術領域

本發明屬于圖計算技術領域，更具體地，涉及一種面向異構服務器結構的圖計算負載均衡方法。

背景技術

分布式圖計算技術被廣泛應用在社交網絡分析、自然語言處理、網頁信息檢索等眾多領域，其組成體系通常包含三個部分：圖算法、圖數據集和圖計算系統。大多數圖計算系統采用BSP(Bulk Synchronization Barrier)計算模型，在此模型下，圖計算過程通常被分為若干次迭代，每一次迭代又稱為一個超級步。在每次超級步中，激活頂點根據在上次超級步中接收的消息更新頂點數值，并將更新后的數值以消息的形式發送給對應的鄰居頂點。相鄰的兩次超級步間設有同步障礙，以保證所有激活頂點在下次超級步開始前已經完成當前超級步中的數值更新操作。

現有的圖計算系統出于負載均衡的考慮，在計算節點導入圖數據集階段為所有計算節點分配數量相當的頂點。然而，當前的數據中心或集群通常采用異構的服務器結構，這使得不同處理能力的計算節點在每次超級步中的處理時間不同，即處理能力強的計算節點在每次超級步中總是比處理能力弱的計算節點優先完成本地計算，并在同步障礙處等待同步。此外，在處理圖計算任務的過程中，分布在各計算節點上的激活頂點數會發生變化，因而各計算節點在每次超級中的負載量也會動態變化。以上兩個原因，導致大多數圖計算系統很難保證各計算節點在每次超級步中的處理時間是均衡的。

針對處理圖計算任務時計算節點間負載不均衡的問題，少數圖計算系統(例如Mizan和GPS)提出采用頂點遷移的方法來均衡每次超級步中各計算節點上的負載。然而，這些圖計算系統通常利用頂點級的參數(例如頂點在一次超級步中接受的消息數)來擬定遷移計劃，從而導致遷移效果不理想，計算節點間的負載在頂點遷移后仍然不均衡。另外，這些圖計算系統通常采用較敏感的遷移策略，即使檢測到輕微的負載不均衡也會執行頂點遷移，導致頂點遷移的開銷(如遷移時間、資源占用等)遠大于負載均衡的收益。

發明內容

針對現有技術的以上缺陷或改進需求，本發明提供一種面向異構服務器結構的圖計算負載均衡方法，用于均衡分布式圖計算系統中所有計算節點在每次超級步中的處理時間，從而降低計算節點在每次超級步中的同步開銷，縮短圖計算任務的運行時間，解決在現有的異構服務器結構下處理圖計算任務時存在的計算節點負載量不均衡和處理時間不同步問題。

本發明提出的一種面向異構服務器結構的圖計算負載均衡方法，包括如下階段：

檢測不均衡階段：在圖計算任務運行時，主控節點監測每次超級步中各計算節點的處理時間，并根據本次超級步中所有計算節點處理時間的變異系數和用戶預設的閾值，判斷各計算節點上的圖計算負載是否均衡；所述變異系數為反映一組數據值離散程度的參數；對于一個圖算法，如果用戶不知道其運行時的特征，即用戶對于運行時激活頂點個數的變化未知，則閾值默認為0.10；而對于穩定的圖算法，即運行時激活頂點的個數不變，則應該設定一個小于0.10的閾值；而對于不穩定的圖算法，即運行時激活頂點的個數持續變化，則應該設定一個大于0.10的閾值；本發明默認閾值可以設為0.10，對于不同圖算法的具體閾值選取則不在本發明的討論范圍內。

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