[發明專利]一種基于時間的大規模圖均衡k劃分的禁忌搜索方法

在審

• 申請號: 201811024190.5
• 申請日: 2018-09-04
• 公開（公告）號: CN109388772A
• 公開（公告）日: 2019-02-26
• 發明（設計）人: 許國艷;石水倩;朱進;周星熠;孫潔
• 申請（專利權）人: 河海大學
• 主分類號: G06F17/10
• 分類號: G06F17/10
• 代理公司: 南京蘇高專利商標事務所(普通合伙) 32204
• 代理人: 李玉平

1.一種基于時間的大規模圖均衡k劃分的禁忌搜索方法，其特征在于：該方法通過監測BSP模型中每個超步的運行時間，根據運行時間與平均時間的差值大小，找出運行時間不平衡的原因，選擇相應的頂點轉移策略。

2.如權利要求1所述的基于時間的大規模圖均衡k劃分的禁忌搜索方法，其特征在于：監測超步的運行時間，找出運行時間不平衡的原因，選擇相應的頂點轉移策略；如果分區計算過長，此時通過頂點轉移策略，計算均衡因子使得分區內頂點數均衡，從而縮短分區計算時間；如果通信時間過長，通過頂點轉移策略，計算頂點收益值，選擇頂點收益值最大的分區，將頂點轉移進該分區。

3.如權利要求1所述的基于時間的大規模圖均衡k劃分的禁忌搜索方法，其特征在于：計算并統計各分區運行時間

圖計算的運行時間等于每個超步的運行時間T_si之和，每個超步的運行時間等于所有分區運行時間T_Di的最大值如公式(3-2)所示：

T_si＝max(T_Di) (3-2)

每個分區的運行時間T_Di等于分區計算時間cpT與通信時間ccT之和，如公式(3-3)所示：

T_Di＝cpT+ccT (3-3)。

4.如權利要求1所述的基于時間的大規模圖均衡k劃分的禁忌搜索方法，其特征在于，選擇相應的頂點轉移策略過程為：

步驟1，計算分區運行時間T_Di與平均運行時間的差值，如果差值小于閾值，說明分區運行時間是在可以接受的范圍內，如果差值大于閾值，則跳轉步驟2；

步驟2：差值大于閾值，說明需要轉移頂點，來減少本地計算時間或者通信時間，從而減少分區運行時間；下面分為兩種情況：一是分區計算時間cpT過長跳轉步驟3，二是通信時間ccT過長跳轉步驟5；

步驟3：分區計算過長，需要選擇與目標分區鄰居數最多的頂點v進行轉移，計算頂點v轉移到目標分區后的均衡因子e，均衡因子e可以將圖的均衡狀況通過數值體現，如公式3-5所示：

其中，V_oi是轉移頂點v之后子區的頂點數，V_Di是整個超步內分區頂點數的總和，k是分區的個數，是理想狀態下，每個分區的頂點個數；

如果轉移頂點后的均衡因子小于轉移前的均衡因子，那么更新禁忌列表，執行下一個超步，否則跳轉步驟4；

步驟4：選擇其他目標分區，并且更新桶列表，跳轉步驟3；

步驟5：通信時間過長，計算頂點v在原來分區相連的頂點的邊的權值之和，計算目標分區相連的頂點的邊的權值之和；

步驟6：計算頂點v的收益值，頂點v的收益函數如公式3-6所示：

G(v)＝W_de-W_oe (3-6)

其中，G(v)是頂點v從原來所在子區去目標轉移子區的收益函數，W_de是頂點v與目標轉移子區內連接的所有頂點的邊的權值之和，W_oe是頂點v與原來所在子區內連接的所有頂點的邊的權值之和；

步驟7：選擇收益值最大的子區，將頂點v轉移；

步驟8：更新禁忌列表，執行下一個超步。

5.如權利要求1所述的基于時間的大規模圖均衡k劃分的禁忌搜索方法，其特征在于，圖劃分算法的根本目的就是減少圖計算的運行時間，本方法通過監測系統運行期間每個超步的運行時間，當超步的運行時間與平均運行時間相差很大時，找出運行時間過長的原因，根據本地計算時間或通信時間來轉移頂點，實現分區間的負載均衡，同時降低分區間通信來減少等待時間。