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

在審

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

本發明公開一種基于時間的大規模圖均衡k劃分的禁忌搜索方法，包含以下步驟：1、計算并統計各分區運行時間；2、計算分區運行時間T_Di與平均運行時間的差值，如果差值小于閾值，說明分區運行時間是在可以接受的范圍內，如果差值大于閾值，則說明需要轉移頂點，來減少本地計算時間或者通信時間，從而減少分區運行時間；3、計算頂點v的收益值，選擇收益值最大的子區，將頂點v轉移，更新禁忌列表，執行下一個超步。本發明將時間這一因素考慮進算法中，能快速的判斷出各個子圖是否負載均衡或者是否子圖間割權近似最小，最終目的是將分布式系統的運行效率得到很大的改善。

技術領域

本發明涉及一種基于時間的大規模圖均衡k劃分的禁忌搜索方法，用于提升分布式系統的運行效率。

背景技術

LGEPTS算法采用轉移頂點的策略將頂點v轉移到目標分區，在迭代過程中選出最優解。然而沒有考慮迭代需要耗費時長，也沒有考慮到在BSP模型中超步的運行時間，會嚴重影響分布式系統的效率。

發明內容

發明目的：針對LGEPTS算法時間開銷較大的問題，引入時間因素，提出了一種基于時間的大規模圖均衡k劃分的禁忌搜索算法。該算法通過監測運行期間每個超步的運行時間，根據運行時間與平均時間的差值大小，找出運行時間不平衡的原因。分區計算過長，此時通過頂點轉移策略，計算均衡因子使得分區內頂點數均衡，從而縮短分區計算時間；通信時間過長，通過頂點轉移策略，計算頂點收益值，選擇頂點收益值最大的分區，將頂點轉移進該分區，最后得到劃分后的子圖。LGEPTS-time算法對LGEPTS算法進行時間上的優化，提升了分布式系統的運行效率，也能提高并行計算的效率。

技術方案：分析原有LGEPTS算法，由于算法每次都需要轉移頂點來保證劃分質量，會消耗大量時間，導致整個超步的運行速度變慢。將時間這一因素加入到大規模圖均衡k劃分的禁忌搜索算法中，提出一種基于時間的大規模圖均衡k劃分的禁忌搜索方法(A TabuSearch Algorithm for Large Scale Equalization K Partition based on Time，簡記為LGEPTS-time)。

一種基于時間的大規模圖均衡k劃分的禁忌搜索方法，該方法通過監測BSP模型中每個超步的運行時間，根據運行時間與平均時間的差值大小，找出運行時間不平衡的原因。如果分區計算過長，此時通過頂點轉移策略，計算均衡因子使得分區內頂點數均衡，從而縮短分區計算時間；如果通信時間過長，通過頂點轉移策略，計算頂點收益值，選擇頂點收益值最大的分區，將頂點轉移進該分區。禁忌搜索方法是一種啟發式方法，該方法可以模仿人類的記憶功能。為了防止頂點重復在子圖間來回移動，該算法使用禁忌表來約束多余重復的操作，盡量避免不必要的循環操作。除此之外，本方法將時間這一因素考慮進算法中，能快速的判斷出各個子圖是否負載均衡或者是否子圖間割權近似最小，最終目的是將分布式系統的運行效率得到很大的改善，對原有的LGEPTS算法進行時間上的優化。

針對BSP模型中，超步的運行時間影響整個系統的分布式效率，從時間方面設計解決思路：監測超步的運行時間，根據本地計算時間和通信時間選擇相應的頂點轉移策略。

步驟一：計算并統計各分區運行時間

系統以每一個頂點為中心進行圖計算，根據BSP模型得出圖計算的運行時間如公式(3-1)所示：

runT＝T_s1+T_s2+...+T_sn＝∑T_si (3-1)

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

T_si＝max(T_Di) (3-2)