[發(fā)明專利]一種基于自動(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)（專利權(quán)）人: 北京大學(xué)
• 主分類號(hào): G06F9/50
• 分類號(hào): G06F9/50
• 代理公司: 北京君尚知識(shí)產(chǎn)權(quán)代理有限公司 11200
• 代理人: 余功勛

本發(fā)明提供一種基于自動(dòng)選擇副本因子模型的圖計(jì)算方法，其步驟為：將圖數(shù)據(jù)切分得到若干個(gè)切片；根據(jù)自動(dòng)選擇副本因子模型為上述每個(gè)切片選擇最優(yōu)的副本因子Rsubgt;i/subgt;，其中所述副本因子Rsubgt;i/subgt;是指為第i個(gè)切片Ssubgt;i/subgt;選擇的副本個(gè)數(shù)；初始化上述每個(gè)切片的所有節(jié)點(diǎn)值，計(jì)算每個(gè)切片的每一條邊，并根據(jù)上述每個(gè)切片的副本因子Rsubgt;i/subgt;將計(jì)算得到的目標(biāo)節(jié)點(diǎn)的副本值存放在Rsubgt;i/subgt;個(gè)副本中；合并上述每一條邊的Rsubgt;i/subgt;個(gè)副本的目標(biāo)節(jié)點(diǎn)的副本值，并將合并后得到的目標(biāo)節(jié)點(diǎn)的更新值更新至GlobalVertices數(shù)組；其中所述GlobalVertices數(shù)組用于存放圖數(shù)據(jù)的所有節(jié)點(diǎn)值。該方法不僅解決了計(jì)算資源被浪費(fèi)的問(wèn)題，而且提高了圖計(jì)算系統(tǒng)的速度。

技術(shù)領(lǐng)域

本發(fā)明涉及云計(jì)算領(lǐng)域，具體涉及一種基于自動(dòng)選擇副本因子模型的圖計(jì)算方法。

背景技術(shù)

近年來(lái)，隨著社交網(wǎng)絡(luò)、基因和各種商業(yè)領(lǐng)域中的圖結(jié)構(gòu)數(shù)據(jù)數(shù)量和規(guī)模快速的增長(zhǎng)，對(duì)于處理大規(guī)模圖數(shù)據(jù)的需求也在隨之增加。越來(lái)越多的公司需要圖計(jì)算系統(tǒng)來(lái)對(duì)圖數(shù)據(jù)進(jìn)行分析和計(jì)算。許多分布式圖計(jì)算系統(tǒng)應(yīng)運(yùn)而生，其中包括Pregel、Giraph、GraphX、GraphLab、PowerGraph、PowerLyra和Gemini。然而現(xiàn)有的圖計(jì)算系統(tǒng)節(jié)點(diǎn)之間的大量通信使得網(wǎng)絡(luò)成為瓶頸。分布式圖計(jì)算系統(tǒng)想要達(dá)到很好的性能就需要高速網(wǎng)絡(luò)。

另一種解決方案是不采用分布式架構(gòu)。其中Galois和Ligra就是為共享內(nèi)存/多核機(jī)器設(shè)計(jì)的，GraphChi和X-Stream也是為單機(jī)處理大規(guī)模圖數(shù)據(jù)設(shè)計(jì)的。集中式的圖計(jì)算系統(tǒng)避免了分布式系統(tǒng)中的管理和調(diào)度問(wèn)題。但隨著新的計(jì)算機(jī)硬件的出現(xiàn)(如圖形處理器GPU)，計(jì)算機(jī)硬件性能的不斷提升，這些傳統(tǒng)的圖計(jì)算系統(tǒng)設(shè)計(jì)并不能完全發(fā)揮其計(jì)算能力。使用GPU加速的圖計(jì)算系統(tǒng)似乎是一個(gè)可行的解決方案。盡管已經(jīng)有一些系統(tǒng)進(jìn)行過(guò)一些嘗試，但使用GPU來(lái)支持大規(guī)模圖計(jì)算系統(tǒng)仍然是一個(gè)很大的挑戰(zhàn)。其主要問(wèn)題在于：真實(shí)圖數(shù)據(jù)中存在非常嚴(yán)重的節(jié)點(diǎn)度數(shù)傾斜(圖中小部分的節(jié)點(diǎn)有大量的邊)現(xiàn)象。這會(huì)導(dǎo)致GPU的多個(gè)線程計(jì)算的時(shí)候產(chǎn)生大量的寫沖突。沖突的線程會(huì)被串行化，嚴(yán)重浪費(fèi)并行計(jì)算能力，拖慢系統(tǒng)的計(jì)算速度。

發(fā)明內(nèi)容

針對(duì)上述問(wèn)題，本發(fā)明的目的是提供一種基于自動(dòng)選擇副本因子模型的圖計(jì)算方法，該方法能夠使得GPU多線程并發(fā)計(jì)算時(shí)，不再受圖數(shù)據(jù)中節(jié)點(diǎn)度數(shù)傾斜現(xiàn)象的影響，不僅解決了計(jì)算資源被浪費(fèi)的問(wèn)題，而且提高了圖計(jì)算系統(tǒng)的速度。

為實(shí)現(xiàn)上述目的，本發(fā)明所采用的技術(shù)方案如下：

一種基于自動(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)值。

進(jìn)一步地，該方法步驟還包括：將GlobalVertices數(shù)組中存放的圖數(shù)據(jù)的所有節(jié)點(diǎn)值傳輸至內(nèi)存中進(jìn)行同步。

進(jìn)一步地，所述將圖數(shù)據(jù)切分得到若干個(gè)切片是指：根據(jù)GPU顯存大小將圖數(shù)據(jù)切分成若干個(gè)頁(yè)，并根據(jù)每個(gè)頁(yè)的大小確定每個(gè)頁(yè)中包含的若干個(gè)切片的尺寸以及根據(jù)共享內(nèi)存(shared?memory)大小確定每個(gè)切片中最大節(jié)點(diǎn)個(gè)數(shù)。