[發(fā)明專利]一種基于GPU的多分區(qū)強(qiáng)連通圖檢測(cè)方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201910371230.1
• 申請(qǐng)日: 2019-05-06
• 公開(kāi)（公告）號(hào): CN110288507B
• 公開(kāi)（公告）日: 2021-03-09
• 發(fā)明（設(shè)計(jì)）人: 侯駿騰;王樹(shù)鵬;吳廣君;王振宇;張建宇
• 申請(qǐng)（專利權(quán)）人: 中國(guó)科學(xué)院信息工程研究所
• 主分類號(hào): G06T1/20
• 分類號(hào): G06T1/20;G06F16/901
• 代理公司: 北京君尚知識(shí)產(chǎn)權(quán)代理有限公司 11200
• 代理人: 陳艷

本發(fā)明提出一種基于GPU的多分區(qū)強(qiáng)連通圖檢測(cè)方法，包括以下步驟：加載圖數(shù)據(jù)并統(tǒng)一存儲(chǔ)格式；在圖數(shù)據(jù)上基于GPU進(jìn)行第一剪枝操作，檢測(cè)出1?SCC；在除1?SCC外的部分上選取中心點(diǎn)，從中心點(diǎn)開(kāi)始并行地前向和后向遍歷，更新?tīng)顟B(tài)得到SCC和多個(gè)分區(qū)；在未被檢測(cè)的圖數(shù)據(jù)上基于GPU進(jìn)行第二剪枝操作，檢測(cè)出2?SCC；在未被檢測(cè)的圖數(shù)據(jù)上檢測(cè)弱連通區(qū)域，并在弱連通區(qū)域上每個(gè)選取中心點(diǎn)，從中心點(diǎn)開(kāi)始前向遍歷；在弱連通區(qū)域的中未被前向遍歷到的區(qū)域隨機(jī)選取保存的最后一個(gè)頂點(diǎn)做為副中心點(diǎn)，從中心點(diǎn)與副中心點(diǎn)開(kāi)始后向遍歷，再進(jìn)行第一剪枝操作，再次更新?tīng)顟B(tài)得到SCC和分區(qū)；通過(guò)上述步驟獲得全部的SCC。

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

本發(fā)明屬于異構(gòu)系統(tǒng)上的圖計(jì)算領(lǐng)域，具體涉及一種在配置GPU設(shè)備的異構(gòu)系統(tǒng)上進(jìn)行多分區(qū)的強(qiáng)連通圖檢測(cè)的方法。

背景技術(shù)

隨著大數(shù)據(jù)、物聯(lián)網(wǎng)等技術(shù)的蓬勃發(fā)展，所能獲取的數(shù)據(jù)越來(lái)越多，并且這些數(shù)據(jù)之間存在著錯(cuò)綜復(fù)雜的聯(lián)系。圖計(jì)算可以對(duì)這些復(fù)雜的信息進(jìn)行簡(jiǎn)化研究，而強(qiáng)連通圖(Strongly Connected Components，SCC)檢測(cè)是圖計(jì)算中的一個(gè)重要的基礎(chǔ)算法。早期的強(qiáng)連通圖檢測(cè)的研究中有很多經(jīng)典的并且效果很好的強(qiáng)連通圖檢測(cè)方案，這些方案大多為串行算法。然而隨著圖數(shù)據(jù)規(guī)模的不斷增大，串行算法的檢測(cè)時(shí)間會(huì)呈現(xiàn)線性上升的趨勢(shì)。隨著GPU技術(shù)的成熟，在GPU上進(jìn)行強(qiáng)連通圖檢測(cè)的并行算法得到廣泛研究，并且這些算法在大圖上的檢測(cè)效果明顯優(yōu)于經(jīng)典的串行算法。

基于GPU的并行強(qiáng)連通圖檢測(cè)方案可以分類FB算法、Colouring算法、OBF算法這三類，其中效果最好并且研究較多的是FB算法。研究人員在FB算法上提出了多種的改進(jìn)方案，但是這些算法并沒(méi)有改變FB算法整體的算法思路，即：選取中心點(diǎn)并對(duì)其進(jìn)行前向和后向的廣度優(yōu)先遍歷，根據(jù)所有頂點(diǎn)被遍歷到的情況得到一個(gè)強(qiáng)連通圖和三個(gè)分區(qū)，然后在每個(gè)分區(qū)中繼續(xù)迭代檢測(cè)。這一方案結(jié)合剪枝與弱連通區(qū)域檢測(cè)等方法能夠在生成圖中能取得很好的檢測(cè)效果，但是在真實(shí)圖中存在很多的中等大小的強(qiáng)連通圖，這些強(qiáng)連通圖在數(shù)目上小于由一個(gè)頂點(diǎn)組成的強(qiáng)連通圖(1-SCC)和由兩個(gè)頂點(diǎn)組成的強(qiáng)連通圖(2-SCC)，在強(qiáng)連通圖所包含頂點(diǎn)數(shù)目上遠(yuǎn)小于最大強(qiáng)連通圖的頂點(diǎn)個(gè)數(shù)，然而由于FB算法的整體思路只能保證每次檢測(cè)出的強(qiáng)連通圖個(gè)數(shù)是上一次檢測(cè)的3倍，所以需要很多次檢測(cè)才能將這些中等大小的強(qiáng)連通圖全部檢測(cè)出來(lái)。因此，如何加速中等大小的強(qiáng)連通圖的檢測(cè)速度成為提高真實(shí)圖上強(qiáng)連通圖檢測(cè)效率的關(guān)鍵。此外，傳統(tǒng)的FB算法中的中心點(diǎn)選取與弱連通區(qū)域檢測(cè)的過(guò)程都有提速的空間。

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

本發(fā)明提出了一種基于GPU的多分區(qū)強(qiáng)連通圖檢測(cè)方法，在配備GPU的異構(gòu)系統(tǒng)上進(jìn)行多分區(qū)的強(qiáng)連通圖檢測(cè)，通過(guò)增加每次檢測(cè)產(chǎn)生的分區(qū)個(gè)數(shù)減少算法的檢測(cè)次數(shù)，從而達(dá)到提升算法執(zhí)行效率的目的。

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

一種基于GPU的多分區(qū)強(qiáng)連通圖檢測(cè)方法，包括以下步驟：

加載圖數(shù)據(jù)并統(tǒng)一存儲(chǔ)格式；

在圖數(shù)據(jù)上基于GPU進(jìn)行第一剪枝操作，檢測(cè)出由單個(gè)頂點(diǎn)組成的強(qiáng)連通圖1-SCC；

在除1-SCC外的部分上選取中心點(diǎn)，從中心點(diǎn)開(kāi)始并行地前向和后向遍歷，更新?tīng)顟B(tài)得到強(qiáng)連通圖SCC和多個(gè)分區(qū)；

在未被檢測(cè)的圖數(shù)據(jù)上基于GPU進(jìn)行第二剪枝操作，檢測(cè)出由兩個(gè)頂點(diǎn)組成的強(qiáng)連通圖2-SCC；

在未被檢測(cè)的圖數(shù)據(jù)上檢測(cè)弱連通區(qū)域，并在弱連通區(qū)域上每個(gè)選取中心點(diǎn)，從中心點(diǎn)開(kāi)始前向遍歷；

在弱連通區(qū)域的中未被前向遍歷到的區(qū)域隨機(jī)選取保存的最后一個(gè)頂點(diǎn)做為副中心點(diǎn)，從中心點(diǎn)與副中心點(diǎn)開(kāi)始后向遍歷，再進(jìn)行第一剪枝操作，再次更新?tīng)顟B(tài)得到SCC和分區(qū)；

通過(guò)上述步驟獲得全部的SCC。

進(jìn)一步地，加載圖數(shù)據(jù)并統(tǒng)一存儲(chǔ)格式具體包括以下步驟：