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

有效

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

本發(fā)明提出一種基于GPU加速的優(yōu)化線程調(diào)度與分區(qū)的強(qiáng)連通圖檢測(cè)方法，為使用異構(gòu)系統(tǒng)進(jìn)行強(qiáng)連通圖檢測(cè)的方法，通過(guò)將每個(gè)warp分成多個(gè)虛擬warp并分配多個(gè)頂點(diǎn)任務(wù)、使用著色分區(qū)替換傳統(tǒng)的WCC分區(qū)等方法平衡了線程分配、增加了每次迭代產(chǎn)生的強(qiáng)連通圖數(shù)目，從而達(dá)到提升算法運(yùn)行效率的目的。

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

本發(fā)明涉及使用異構(gòu)系統(tǒng)進(jìn)行強(qiáng)連通圖檢測(cè)的方法，具體的說(shuō)是一種GPU上的基于warp重用與著色分區(qū)的強(qiáng)連通圖檢測(cè)算法。

背景技術(shù)

圖數(shù)據(jù)是數(shù)據(jù)處理中一類(lèi)基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)，它能夠很好地表達(dá)出數(shù)據(jù)之間的關(guān)聯(lián)性，因此在生物、化學(xué)、人工智能、社交網(wǎng)絡(luò)等多個(gè)領(lǐng)域得到廣泛地應(yīng)用。強(qiáng)連通圖(Strongly Connected Components,SCC)是一種基礎(chǔ)的圖結(jié)構(gòu)，是指有向圖中所有頂點(diǎn)兩兩有向連接的最大子集。雖然強(qiáng)連通圖檢測(cè)是一個(gè)很早就開(kāi)始研究的問(wèn)題，并且已經(jīng)有Tarjan算法、Kosaraju算法、Dijkstra算法等優(yōu)秀的檢測(cè)方法。但是，這些算法大多是基于深度優(yōu)先遍歷(depth-first search,DFS)的串行算法，其運(yùn)行時(shí)間隨著圖數(shù)據(jù)規(guī)模的擴(kuò)大而急劇增加，并且很難并行化。隨著通用型的GPU等并行計(jì)算設(shè)備被廣泛應(yīng)用到高性能計(jì)算的應(yīng)用中，研究人員提出了一些基于GPU的并行強(qiáng)連通圖檢測(cè)算法，這些算法大多基于對(duì)中心點(diǎn)的前向遍歷與后向遍歷所形成區(qū)域求交集的方法，并通過(guò)分區(qū)來(lái)增加每次迭代檢測(cè)的并行性。然而在遍歷的過(guò)程中，這些算法會(huì)為所有未完成檢測(cè)的頂點(diǎn)中每個(gè)頂點(diǎn)分配一個(gè)線程或一個(gè)warp(包括32個(gè)線程的線程組)，這些頂點(diǎn)中很多頂點(diǎn)不需要被處理，則分配的線程直接被釋放掉，而其他頂點(diǎn)的鄰接頂點(diǎn)數(shù)目相差很大，導(dǎo)致不同的線程或線程組間嚴(yán)重地負(fù)載不均衡。另外，現(xiàn)有的分區(qū)方法只是將和其它頂點(diǎn)沒(méi)有任何連接的頂點(diǎn)分到同一個(gè)分區(qū)當(dāng)中，產(chǎn)生的分區(qū)數(shù)目不是很多。每次迭代檢測(cè)之后，所有未完成檢測(cè)的頂點(diǎn)狀態(tài)全部歸零，使得每次檢測(cè)后的計(jì)算結(jié)果不能被充分利用。因此，對(duì)于當(dāng)前基于GPU的并行強(qiáng)連通圖檢測(cè)算法中的線程任務(wù)分配與分區(qū)方法進(jìn)行優(yōu)化改進(jìn)是提升并行強(qiáng)連通圖檢測(cè)算法效率的關(guān)鍵。

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

本發(fā)明提出一種基于GPU加速的優(yōu)化線程調(diào)度與分區(qū)的強(qiáng)連通圖檢測(cè)方法，通過(guò)將每個(gè)warp分成多個(gè)虛擬warp并分配多個(gè)頂點(diǎn)任務(wù)、使用著色分區(qū)替換傳統(tǒng)的WCC分區(qū)等方法平衡了線程分配、增加了每次迭代產(chǎn)生的強(qiáng)連通圖數(shù)目，從而達(dá)到提升算法運(yùn)行效率的目的。

本發(fā)明的技術(shù)方案如下：

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

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

對(duì)圖數(shù)據(jù)進(jìn)行第一類(lèi)剪枝操作，檢測(cè)出只由一個(gè)頂點(diǎn)組成的強(qiáng)連通圖1-SCC；

進(jìn)行第一類(lèi)中心點(diǎn)選取操作，使用入度和出度的積最大的頂點(diǎn)做為中心點(diǎn)；

使用warp重用方法從中心點(diǎn)開(kāi)始并行地前向和后向遍歷，得到強(qiáng)連通圖和三個(gè)分區(qū)，其中強(qiáng)連通圖為前向和后向均遍歷到的頂點(diǎn)與中心點(diǎn)形成的連通圖，三個(gè)分區(qū)為前向遍歷到后向未遍歷到的頂點(diǎn)，前向未遍歷到后向遍歷到的頂點(diǎn)，以及前向和后向均未遍歷到的頂點(diǎn)所形成的分區(qū)；

判斷是否需要進(jìn)行第二類(lèi)剪枝操作，若需要，則進(jìn)行第二類(lèi)剪枝操作，檢測(cè)出由一個(gè)頂點(diǎn)組成的強(qiáng)連通圖1-SCC和由兩個(gè)頂點(diǎn)組成的強(qiáng)連通圖2-SCC；

使用著色分區(qū)方法對(duì)所述三個(gè)分區(qū)進(jìn)行進(jìn)一步分區(qū)，得到更多更小的分區(qū)；

在所形成的小分區(qū)中進(jìn)行第二類(lèi)中心點(diǎn)選取操作，選取每個(gè)分區(qū)中初始顏色值與分區(qū)顏色值相同的頂點(diǎn)做為中心點(diǎn)，從中心點(diǎn)開(kāi)始前向遍歷，將遍歷到的頂點(diǎn)與中心點(diǎn)組成一個(gè)強(qiáng)連通圖，未被遍歷到的頂點(diǎn)形成新的分區(qū)；

進(jìn)行第三類(lèi)中心點(diǎn)選取操作，直接在每個(gè)分區(qū)中隨機(jī)選取一個(gè)頂點(diǎn)做為中心點(diǎn)，從中心點(diǎn)開(kāi)始并行地前向和后向遍歷；

再次進(jìn)行第一類(lèi)剪枝操作，并更新強(qiáng)連通圖和分區(qū)；