[發(fā)明專(zhuān)利]一種基于自動(dòng)選擇副本因子模型的圖計(jì)算方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201710533444.5
• 申請(qǐng)日: 2017-07-03
• 公開(kāi)（公告）號(hào): CN109213592B
• 公開(kāi)（公告）日: 2023-07-18
• 發(fā)明（設(shè)計(jì)）人: 陳瀚;馬凌霄;楊智;薛繼龍;代亞非
• 申請(qǐng)（專(zhuān)利權(quán)）人: 北京大學(xué)
• 主分類(lèi)號(hào): G06F9/50
• 分類(lèi)號(hào): G06F9/50
• 代理公司: 北京君尚知識(shí)產(chǎn)權(quán)代理有限公司 11200
• 代理人: 余功勛

1.一種基于自動(dòng)選擇副本因子模型的圖計(jì)算方法，其步驟包括：

將圖數(shù)據(jù)切分得到若干個(gè)切片；

根據(jù)自動(dòng)選擇副本因子模型為上述每個(gè)切片選擇最優(yōu)的副本因子R_i，其中所述副本因子R_i是指為第i個(gè)切片S_i選擇的副本個(gè)數(shù)；

初始化上述每個(gè)切片的所有節(jié)點(diǎn)值，計(jì)算每個(gè)切片的每一條邊，并根據(jù)上述每個(gè)切片的副本因子R_i將計(jì)算得到的目標(biāo)節(jié)點(diǎn)的副本值存放在R_i個(gè)副本中；

合并上述每一條邊的R_i個(gè)副本的目標(biāo)節(jié)點(diǎn)的副本值，并將合并后得到的目標(biāo)節(jié)點(diǎn)的更新值更新至GlobalVertices數(shù)組；其中所述GlobalVertices數(shù)組用于存放圖數(shù)據(jù)的所有節(jié)點(diǎn)值；

所述自動(dòng)選擇副本因子模型的輸入是一個(gè)切片的平均度數(shù)和GPU的存儲(chǔ)限制，輸出為該切片最優(yōu)的副本因子R_i；其中所述切片最優(yōu)的副本因子R_i的計(jì)算公式為：

其中R_i代表第i個(gè)切片的副本因子；u和E分別代表第i個(gè)切片S_i中的目標(biāo)節(jié)點(diǎn)和邊。

2.如權(quán)利要求1所述的方法，其特征在于，該方法步驟還包括：將GlobalVertices數(shù)組中存放的圖數(shù)據(jù)的所有節(jié)點(diǎn)值傳輸至內(nèi)存中進(jìn)行同步。

3.如權(quán)利要求1所述的方法，其特征在于，所述將圖數(shù)據(jù)切分得到若干個(gè)切片是指：根據(jù)GPU顯存大小將圖數(shù)據(jù)切分成若干個(gè)頁(yè)，并根據(jù)每個(gè)頁(yè)的大小確定每個(gè)頁(yè)中包含的若干個(gè)切片的尺寸以及根據(jù)共享內(nèi)存大小確定每個(gè)切片中最大節(jié)點(diǎn)個(gè)數(shù)。

4.如權(quán)利要求1所述的方法，其特征在于，所述切片采用CSC和CSR壓縮格式保存。

5.如權(quán)利要求1所述的方法，其特征在于，CPU將切片以批量發(fā)送的方式發(fā)送給GPU進(jìn)行計(jì)算。

6.如權(quán)利要求1所述的方法，其特征在于，采用sum方法合并上述每一條邊的R_i個(gè)副本的目標(biāo)節(jié)點(diǎn)的副本值。

7.如權(quán)利要求6所述的方法，其特征在于，所述sum方法是指利用兩路歸并策略將R_i個(gè)副本的目標(biāo)節(jié)點(diǎn)的副本值進(jìn)行合并。

8.如權(quán)利要求1所述的方法，其特征在于，采用apply方法將合并后得到的目標(biāo)節(jié)點(diǎn)的更新值更新至GlobalVertices數(shù)組。

9.如權(quán)利要求8所述的方法，其特征在于，所述apply方法如果采用異步模式，則目標(biāo)節(jié)點(diǎn)的更新值將直接提交到GlobalVertices數(shù)組；如果采用同步模式，則先將目標(biāo)節(jié)點(diǎn)的更新值存儲(chǔ)到一暫時(shí)的數(shù)組中，在所有切片計(jì)算結(jié)束后再更新到GlobalVertices數(shù)組中。