[發(fā)明專利]一種面向異構(gòu)服務(wù)器結(jié)構(gòu)的圖計(jì)算負(fù)載均衡方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201711274503.8
• 申請(qǐng)日: 2017-12-06
• 公開（公告）號(hào): CN108089918B
• 公開（公告）日: 2020-07-14
• 發(fā)明（設(shè)計(jì)）人: 曹強(qiáng);盛豐
• 申請(qǐng)（專利權(quán)）人: 華中科技大學(xué)
• 主分類號(hào): G06F9/48
• 分類號(hào): G06F9/48;G06F9/50
• 代理公司: 華中科技大學(xué)專利中心 42201
• 代理人: 張建偉;曹葆青

1.一種面向異構(gòu)服務(wù)器結(jié)構(gòu)的圖計(jì)算負(fù)載均衡方法，其特征在于，包括如下階段：

檢測(cè)不均衡階段：在圖計(jì)算任務(wù)運(yùn)行時(shí)，主控節(jié)點(diǎn)監(jiān)測(cè)每次超級(jí)步中各計(jì)算節(jié)點(diǎn)的處理時(shí)間，并根據(jù)本次超級(jí)步中所有計(jì)算節(jié)點(diǎn)處理時(shí)間的變異系數(shù)和用戶預(yù)設(shè)的閾值，判斷各計(jì)算節(jié)點(diǎn)上的圖計(jì)算負(fù)載是否均衡；所述變異系數(shù)為反映一組數(shù)據(jù)值離散程度的參數(shù)；

擬定遷移計(jì)劃階段：各計(jì)算節(jié)點(diǎn)確定各自需要遷移的頂點(diǎn)，主控節(jié)點(diǎn)確定這些頂點(diǎn)對(duì)應(yīng)的遷入節(jié)點(diǎn)；

實(shí)施遷移階段：所有遷出節(jié)點(diǎn)采用延遲遷移的方式傳輸頂點(diǎn)信息到對(duì)應(yīng)的遷入節(jié)點(diǎn)上，主控節(jié)點(diǎn)更新頂點(diǎn)遷移后的位置信息；

其中，所述檢測(cè)不均衡階段中，根據(jù)本次超級(jí)步中所有計(jì)算節(jié)點(diǎn)處理時(shí)間的變異系數(shù)和用戶預(yù)設(shè)的閾值，判斷各計(jì)算節(jié)點(diǎn)上的圖計(jì)算負(fù)載是否均衡，包括：

各計(jì)算節(jié)點(diǎn)將本次超級(jí)步中監(jiān)測(cè)的處理時(shí)間發(fā)送給主控節(jié)點(diǎn)；

主控節(jié)點(diǎn)計(jì)算本次超級(jí)步中所有處理時(shí)間的變異系數(shù)CV：

其中u為本次超級(jí)步中所有計(jì)算節(jié)點(diǎn)的平均處理時(shí)間，N為計(jì)算節(jié)點(diǎn)的總個(gè)數(shù)，t_i為計(jì)算節(jié)點(diǎn)i在本次超級(jí)步中監(jiān)測(cè)的處理時(shí)間；

若上次和本次超級(jí)步中計(jì)算所得的變異系數(shù)CV都大于用戶預(yù)設(shè)的閾值CV_thr，則主控節(jié)點(diǎn)判定各計(jì)算節(jié)點(diǎn)上的圖計(jì)算負(fù)載不均衡；否則，認(rèn)定各計(jì)算節(jié)點(diǎn)上的圖計(jì)算負(fù)載為是均衡的；

主控節(jié)點(diǎn)將判定的結(jié)果發(fā)送給所有計(jì)算節(jié)點(diǎn)。

2.如權(quán)利要求1所述的面向異構(gòu)服務(wù)器結(jié)構(gòu)的圖計(jì)算負(fù)載均衡方法，其特征在于，包括以下步驟：

步驟1所有計(jì)算節(jié)點(diǎn)導(dǎo)入圖算法和圖數(shù)據(jù)集；

步驟2所有計(jì)算節(jié)點(diǎn)執(zhí)行圖算法的一次超級(jí)步；

步驟3主控節(jié)點(diǎn)判斷各計(jì)算節(jié)點(diǎn)上的圖計(jì)算負(fù)載是否均衡；

步驟4若步驟3中判定結(jié)果為負(fù)載不均衡，則進(jìn)入擬定遷移計(jì)劃階段，轉(zhuǎn)步驟5；否則，轉(zhuǎn)步驟7，所有計(jì)算節(jié)點(diǎn)進(jìn)入下一次超級(jí)步；

步驟5各計(jì)算節(jié)點(diǎn)確定各自需要遷移的頂點(diǎn)，主控節(jié)點(diǎn)確定這些頂點(diǎn)對(duì)應(yīng)的遷入節(jié)點(diǎn)；

步驟6所有計(jì)算節(jié)點(diǎn)采用延遲遷移的方式，傳輸頂點(diǎn)信息到對(duì)應(yīng)的遷入節(jié)點(diǎn)上，主控節(jié)點(diǎn)更新并匯總頂點(diǎn)遷移后的位置信息；

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

3.如權(quán)利要求2所述的面向異構(gòu)服務(wù)器結(jié)構(gòu)的圖計(jì)算負(fù)載均衡方法，其特征在于，步驟5中擬定遷移計(jì)劃階段包括以下子步驟：

步驟5-1主控節(jié)點(diǎn)將本次超級(jí)步中平均處理時(shí)間u發(fā)送給各計(jì)算節(jié)點(diǎn)；

步驟5-2各計(jì)算節(jié)點(diǎn)根據(jù)平均處理時(shí)間u，判定自身是遷出節(jié)點(diǎn)還是遷入節(jié)點(diǎn)；

若是遷出節(jié)點(diǎn)，則計(jì)算其需要遷出的邊數(shù)E_out，并進(jìn)一步根據(jù)E_out確定需要遷出的頂點(diǎn)；

若是遷入節(jié)點(diǎn)，則計(jì)算其需要遷入的邊數(shù)E_in；

步驟5-3計(jì)算節(jié)點(diǎn)將各自需要遷出或遷入的邊數(shù)發(fā)送給主控節(jié)點(diǎn)；

步驟5-4主控節(jié)點(diǎn)根據(jù)各計(jì)算節(jié)點(diǎn)需要遷出或遷入的邊數(shù)，確定遷移頂點(diǎn)對(duì)應(yīng)的遷入節(jié)點(diǎn)；

步驟5-5主控節(jié)點(diǎn)將遷移頂點(diǎn)對(duì)應(yīng)的遷入節(jié)點(diǎn)信息發(fā)送給相應(yīng)的遷出節(jié)點(diǎn)。

4.如權(quán)利要求3所述的面向異構(gòu)服務(wù)器結(jié)構(gòu)的圖計(jì)算負(fù)載均衡方法，其特征在于，步驟5-2中各遷出節(jié)點(diǎn)確定各自需要遷出的頂點(diǎn)時(shí)操作如下：

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

當(dāng)Δt為負(fù)時(shí)，表示計(jì)算節(jié)點(diǎn)i的圖計(jì)算負(fù)載低于平均負(fù)載水平，該節(jié)點(diǎn)需要遷入的邊數(shù)為E_in＝(μ-t_i)*EPS_i；

遷出節(jié)點(diǎn)需要遷出的邊數(shù)E_out確定后，則需要遷出的頂點(diǎn)可以從該遷出節(jié)點(diǎn)所維護(hù)的頂點(diǎn)中按照所連接的邊數(shù)降序選出，直至選出頂點(diǎn)的邊數(shù)總和達(dá)到E_out。