李安騰，崔鵬杰，袁野，王國仁

(1.北京理工大學(xué) 計(jì)算機(jī)學(xué)院，北京 100081；2.東北大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，遼寧 沈陽 110169)

圖作為重要的數(shù)據(jù)結(jié)構(gòu)，能清晰地表示系統(tǒng)內(nèi)各部分之間的復(fù)雜聯(lián)系.子圖匹配是基礎(chǔ)的圖數(shù)據(jù)挖掘算法，目的是在數(shù)據(jù)圖中找到與查詢圖結(jié)構(gòu)相同的子圖，在社交網(wǎng)絡(luò)分析[1-2]、知識圖譜檢索[3-5]，化合物發(fā)現(xiàn)[6]、生物事件提取[7]等領(lǐng)域都有重要應(yīng)用.子圖匹配被證明是NP-hard問題[8]，傳統(tǒng)的解決方法通常基于樹的搜索和回溯實(shí)現(xiàn)[9].隨著信息時(shí)代的發(fā)展，圖數(shù)據(jù)規(guī)模急劇增大，上百萬條邊的圖已十分常見[10]，傳統(tǒng)的串行子圖匹配算法難以應(yīng)對.以圖形處理器(graphic processing unit, GPU)為中心的中央處理器(center processing unit, CPU)-GPU異構(gòu)圖處理系統(tǒng)不斷涌現(xiàn)[11-12]，英偉達(dá)推出的計(jì)算機(jī)統(tǒng)一設(shè)備架構(gòu)（computer unified device architecture，CUDA）編程模型進(jìn)一步方便了GPU的使用.相比于以CPU為主的圖計(jì)算系統(tǒng)，GPU有更高的帶寬和并發(fā)度，為子圖匹配問題的解決帶來了新的思路.

根據(jù)算法的執(zhí)行環(huán)境，對子圖匹配算法的研究可以分為2個類別：基于CPU和基于GPU.基于CPU的串行算法由Ullmann[13]提出，使用基于深度優(yōu)先搜索的策略，VF2[14]在此基礎(chǔ)上利用結(jié)點(diǎn)間的連接性進(jìn)行剪枝，VF3[15]改進(jìn)VF2，由此出現(xiàn)更多的剪枝策略，如啟發(fā)式確定匹配順序、結(jié)點(diǎn)分類.為了降低候選集的規(guī)模，減少冗余的匹配，TurboISO[16]提出鄰居等價(jià)類的概念.還有許多算法預(yù)先建立關(guān)于圖的結(jié)構(gòu)索引，以減少搜索空間和優(yōu)化匹配順序，如QuickSI[17]、GraphQL[18]、GADDI[19]等，這些算法的優(yōu)化細(xì)節(jié)[20-21]各有不同，但基本思路都是通過增強(qiáng)候選集的過濾能力來提升算法的執(zhí)行效率[22].

隨著GPU相關(guān)技術(shù)的發(fā)展，研究者開始嘗試尋求子圖匹配在GPU上的并行解決方案.Tran等[23]提出GpSM，采用基于邊的連接策略，利用生成樹和非樹結(jié)構(gòu)2次過濾候選集以提升匹配效率.同樣是以候選邊為連接單元，GunrockSM[24]基于Gunrock[25]圖計(jì)算平臺, 采用廣度優(yōu)先的并行處理方式.不同于基于邊的連接實(shí)現(xiàn)，Zeng等[26]提出的GPU友好子圖匹配算法（GPU-friendly subgraph isomorphism algorithm，GSI）采用基于點(diǎn)的連接策略，并針對圖的邊標(biāo)簽設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)以提升訪存效率.Bonnici等[27]提出GRASS算法，采用混合廣度優(yōu)先和深度優(yōu)先的方式，通過 GPU并行過濾候選集.汪洋等[28]提出多編碼樹結(jié)構(gòu)，使生成的搜索空間樹的尺寸減小.當(dāng)前子圖匹配算法在GPU上的實(shí)現(xiàn)主要由過濾和連接2個階段組成.在過濾階段，為每個查詢圖中的結(jié)點(diǎn)確定在數(shù)據(jù)圖中可供匹配的候選集，GpSM利用生成樹且分2步過濾候選集，并行性不高；GSI將鄰邊和鄰接點(diǎn)的標(biāo)簽數(shù)量編碼為簽名以方便并行驗(yàn)證，但忽略了結(jié)點(diǎn)的所處局部的結(jié)構(gòu)特征，過濾能力不強(qiáng).在連接階段，GpSM由候選點(diǎn)生成候選邊，再基于候選邊進(jìn)行連接運(yùn)算，但這樣不能確定中間結(jié)果表的大小和寫入地址，需要進(jìn)行重復(fù)連接[23，26]，占用大量線程資源且在時(shí)間上帶來額外開銷.

針對以上挑戰(zhàn)和已有算法的不足，本研究提出基于GPU的子圖匹配算法GpSI，對過濾和連接的2階段模型進(jìn)行優(yōu)化.過濾階段，綜合考慮結(jié)點(diǎn)局部的數(shù)量特征和結(jié)構(gòu)特征，將這些特征編碼生成結(jié)點(diǎn)簽名，利用GPU并行驗(yàn)證，高效過濾候選集；連接階段，采用基于候選點(diǎn)的連接策略[26]，預(yù)分配空間并設(shè)計(jì)高效的集合運(yùn)算以避免邊連接策略因重復(fù)連接帶來的額外時(shí)空開銷.通過在真實(shí)數(shù)據(jù)集與合成數(shù)據(jù)集上的多個算法對比實(shí)驗(yàn)來證明GpSI的優(yōu)越性.

1 預(yù)備知識

1.1 子圖匹配

定義：子圖匹配.給定查詢圖Q={Vq,Eq,Lq}，數(shù)據(jù)圖G={Vg,Eg,Lg}，其中Vq、Vg為圖的結(jié)點(diǎn)集合，Eq、Eg為邊集合，Lq、Lg為結(jié)點(diǎn)到標(biāo)簽的映射函數(shù).在Q、G間存在單射函數(shù)f:Vq→Vg，使得

子圖匹配算法要求枚舉所有映射f.如圖1所示，在查詢圖和數(shù)據(jù)圖之間可以找到2個符合定義的匹配，分別為m0={(u0,v0),(u1,v2),(u2,v5)}、m1={(u0,v0),(u1,v3),(u2,v5)} ，其中A、B、C均為結(jié)點(diǎn)標(biāo)簽，ui、vi均為結(jié)點(diǎn).

圖1 子圖匹配示例Fig.1 Example of subgraph matching

1.2 CUDA模型和GPU架構(gòu)

CUDA由NVIDIA在2007年推出[29].在CUDA模型下，GPU的線程按組織粒度由大到小分為線程格(grid)、線程塊(block)以及線程(thread)，同一個線程塊內(nèi)每32個線程組織成線程束(warp)，工作在單指令多線程(single instruction multiple threads, SIMT)模式下，是GPU最小的調(diào)度單元.GPU內(nèi)部包含一組固定的流式多處理器(streaming multiprocessor, SM)，線程塊按一定策略被調(diào)度到處理器上執(zhí)行.GPU內(nèi)存被劃分為多個層次和類型，各部分容量和訪問延遲均有較大差異.其中最外層為全局內(nèi)存(global memory)，可供所有的線程訪問，大小通常為GB級別，訪問延遲在400～600個時(shí)間片；其次為每個線程塊內(nèi)的共享內(nèi)存(shared memory)，只能由塊內(nèi)線程訪問，大小通常為48 KB，訪問延遲為32個時(shí)間片；線程塊內(nèi)還設(shè)有L1緩存，特性與共享內(nèi)存類似.GPU上內(nèi)存總線讀寫全局內(nèi)存和L1緩存每次都傳輸連續(xù)的128 B[30]，因此對同一個線程束內(nèi)的線程而言，訪問一段連續(xù)的內(nèi)存可以進(jìn)行合并訪存優(yōu)化，顯著降低訪存頻率從而降低訪存延遲.

2 算法處理框架

如圖2所示為GpSI的整體處理框架.GpSI按執(zhí)行順序可以大致分為過濾和連接2個階段.過濾階段，利用簽名確定每個查詢點(diǎn)的候選集；連接階段，基于這些候選集迭代完成查詢點(diǎn)的匹配，最后得出匹配結(jié)果.

圖2 GpSI的框架Fig.2 Framework of GpSI

GpSI先進(jìn)行過濾階段的處理: 1）為輸入的數(shù)據(jù)圖和查詢圖中的每個結(jié)點(diǎn)生成簽名，即一串編碼結(jié)點(diǎn)局部特征的比特序列.2）利用簽名進(jìn)行候選集過濾，對每個查詢點(diǎn)并行與所有數(shù)據(jù)點(diǎn)按一定規(guī)則進(jìn)行簽名驗(yàn)證.對某個查詢點(diǎn)而言，在這一步可以剔除不可能匹配的數(shù)據(jù)點(diǎn).過濾階段完成即可確定每個查詢點(diǎn)的候選集，以圖1 (a)中u1為例，在經(jīng)過過濾階段的處理后，得到它在數(shù)據(jù)圖中的候選集C(u1)={v2,v3}.在連接階段，按一定順序連接獲得的候選集.采用基于候選點(diǎn)的連接策略，預(yù)分配空間，再在這些臨時(shí)空間上進(jìn)行集合運(yùn)算，完成連接過程.連接階段會產(chǎn)生一系列形如圖1 (c)所示的匹配表，由于每次增量匹配1個查詢點(diǎn)，新匹配表每次擴(kuò)充1列，行數(shù)與集合運(yùn)算后產(chǎn)生的結(jié)果數(shù)有關(guān).當(dāng)連接階段完成，最后輸出的匹配表即為結(jié)果，算法執(zhí)行完畢.

3 過濾階段

3.1 復(fù)合簽名

假設(shè)在某個正確匹配中，數(shù)據(jù)點(diǎn)v是查詢點(diǎn)u的匹配點(diǎn)，則除了結(jié)點(diǎn)標(biāo)簽一致外，u的局部特征也一定復(fù)現(xiàn)于v的局部特征中，這些特征包括局部的數(shù)量特征（如鄰居數(shù)量）和結(jié)構(gòu)特征.GpSI提出結(jié)點(diǎn)的復(fù)合簽名對這些特征進(jìn)行描述.結(jié)點(diǎn)的復(fù)合簽名由數(shù)量簽名和結(jié)構(gòu)簽名2個部分組成.先對結(jié)點(diǎn)的鄰居按標(biāo)簽進(jìn)行分類計(jì)數(shù)以生成數(shù)量簽名.為了方便驗(yàn)證，采用哈希算法將鄰居標(biāo)簽映射到不同的桶(buckets)進(jìn)行統(tǒng)計(jì)：數(shù)量簽名表現(xiàn)為比特序列，它被均分成若干個桶，鄰居標(biāo)簽將被分別映射到這些桶內(nèi)并編碼計(jì)數(shù).如圖3所示為圖1(b)中v0的數(shù)量簽名.若桶大小為4，對于某個桶，無標(biāo)簽映射編碼為0000，有1個映射編碼為0001，2個映射編碼為0011，3個映射編碼為0111，4個及以上映射編碼為1111.在具體實(shí)現(xiàn)中，桶的長度可依據(jù)輸入的圖數(shù)據(jù)信息進(jìn)行調(diào)整.

圖3 數(shù)量簽名Fig.3 Quantity signature

僅利用數(shù)量簽名不能反映結(jié)點(diǎn)的局部特征以及有效過濾候選集.結(jié)點(diǎn)和它不超過2跳區(qū)域的鄰近點(diǎn)可能構(gòu)成多種結(jié)構(gòu)，如路徑和三角形，使用結(jié)構(gòu)簽名記錄這些結(jié)構(gòu)，可以顯著增強(qiáng)候選集的過濾能力.以圖1(b)中的v0為例，圖4中從v0出發(fā)，不超過2跳可以找到由標(biāo)簽組成的1條(A,B,A)路徑，2條(A,C,B)路徑，3條(A,B,C)路徑以及2個標(biāo)簽三角形(A,B,C).如圖5所示，結(jié)構(gòu)簽名包含若干個桶，被均分為路徑簽名和三角簽名2個部分，對獲得的標(biāo)簽序列進(jìn)行與生成數(shù)量簽名類似的操作，即對這些序列進(jìn)行哈希，使之映射到相應(yīng)的桶中進(jìn)行編碼計(jì)數(shù).在結(jié)構(gòu)簽名中，各個桶內(nèi)的編碼方式和數(shù)量簽名一致，如從v0出發(fā)的路徑序列(A,B,C)出現(xiàn)3次，則對應(yīng)桶內(nèi)編碼為0111.觀察到序列的首位都是出發(fā)點(diǎn)的標(biāo)簽，這部分將單獨(dú)驗(yàn)證，因此實(shí)現(xiàn)中可將首位省略，只對序列的后2位組合進(jìn)行哈希計(jì)數(shù)即可.在標(biāo)簽三角形序列中，為了避免重復(fù)計(jì)數(shù)，同一個三角形序列嚴(yán)格按標(biāo)簽的次序只計(jì)數(shù)一次，例如圖4中已記錄三角形序列(A,B,C)則不再記錄序列(A,C,B).算法1為某個結(jié)點(diǎn)u的復(fù)合簽名生成過程.行2～3遍歷結(jié)點(diǎn)u的鄰居，生成數(shù)量簽名；行4～8從點(diǎn)u出發(fā)進(jìn)行1次不超過2跳的廣度優(yōu)先遍歷，得到三角形和路徑序列，生成對應(yīng)的結(jié)構(gòu)簽名.

圖4 結(jié)點(diǎn)的局部路徑Fig.4 Local paths of vertex

圖5 結(jié)構(gòu)簽名Fig.5 Structure signature

算法1生成復(fù)合簽名

輸入：結(jié)點(diǎn)u∈G輸出：結(jié)點(diǎn)簽名S(u)

1init(S(u));

2 for eachvinN(u):

3GenQuantitySig(v,S(u));

4 for eachvinN(u):

5 for eachwinN(v):

6 ifw∈N(u):

7GenTriangleSig(v,w,S(u));

8GenPathSig(v,w,S(u));

9 returnS(u);

如圖6所示，復(fù)合簽名由數(shù)量簽名和結(jié)構(gòu)簽名2部分拼接而成.簽名的空間占用小不僅能節(jié)省GPU的內(nèi)存，使GPU處理更大規(guī)模的圖，也能減少后續(xù)驗(yàn)證簽名的用時(shí).通常情況下，查詢圖中的結(jié)點(diǎn)標(biāo)簽均來自數(shù)據(jù)圖，有|Lg|＞|Lq|.為了保證統(tǒng)計(jì)的準(zhǔn)確性，數(shù)量簽名的桶數(shù)量應(yīng)為|Lg|；結(jié)構(gòu)簽名中的路徑和三角形序列都可由2個標(biāo)簽組成，考慮可能構(gòu)成的組合數(shù)，桶數(shù)量應(yīng)該分別為|Lg|2.當(dāng)|Lg|＞＞|Lq|時(shí)，由于|Lq|一般不超過10，增加桶的個數(shù)帶來的過濾能力增益有限，此時(shí)可以犧牲一定的準(zhǔn)確性，基于|Lq|分配桶數(shù)量.一般來講，數(shù)量簽名的桶所占比特序列較長，偏向于記錄數(shù)量；結(jié)構(gòu)簽名中桶的長度較短，偏向于記錄種類.為了節(jié)省空間，以上所有類型的桶大小均支持依據(jù)圖數(shù)據(jù)的統(tǒng)計(jì)信息進(jìn)行動態(tài)調(diào)整.

圖6 復(fù)合簽名Fig.6 Composite signature

3.2 候選集過濾

數(shù)據(jù)圖和查詢圖的每個點(diǎn)的簽名生成后，便可以利用這些簽名進(jìn)行候選集過濾.雖然復(fù)合簽名分為若干部分，但過濾候選集采用統(tǒng)一的驗(yàn)證方法：比較各個桶內(nèi)編碼的數(shù)值大小，若v∈C(u)，則S(u)的各個桶內(nèi)數(shù)值應(yīng)不大于S(v).為了方便GPU并行處理，采用按位與運(yùn)算完成驗(yàn)證.可以推出，?u∈Vq,v∈Vg；若v∈C(u)，則

換言之，作為必要條件，若式（3）不成立，則v?C(u)，以此剔除無關(guān)的數(shù)據(jù)點(diǎn)，使得候選集的規(guī)?？s小.相較只考慮數(shù)量特征[26]，綜合利用結(jié)點(diǎn)局部的結(jié)構(gòu)和數(shù)量特征的復(fù)合簽名具有更強(qiáng)的過濾能力.以圖1(a)中的u1為例，若只采用數(shù)量簽名，則過濾階段后C(u1)={v2,v3,v4}，只有繼續(xù)進(jìn)行連接才能發(fā)現(xiàn)v4?C(u1)；若采用復(fù)合簽名，則過濾階段后即可確定C(u1)={v2,v3}，后續(xù)連接階段的任務(wù)量可以認(rèn)為是各候選集大小的乘積.復(fù)合簽名能有效地降低候選集規(guī)模，減少連接階段任務(wù)量、提升整體性能，在面對大規(guī)模的圖時(shí)優(yōu)勢明顯.利用簽名驗(yàn)證進(jìn)行候選集過濾適于GPU并行處理，使用并行前綴和算法[30]，時(shí)間復(fù)雜度為O(|Vq|lb|Vg|)，其中|Vq|通常不超過10，時(shí)間開銷較為理想.

4 連接階段

按一定順序連接查詢點(diǎn)的候選集，便可得到最終的匹配結(jié)果，算法2為連接階段的總流程.優(yōu)先選取候選集規(guī)模|C(u)|最小的查詢點(diǎn)加入部分匹配集Qp，M初始設(shè)為起始查詢點(diǎn)的候選集；每輪選擇與Qp相連且|C(u)|最小的未匹配點(diǎn)u′，調(diào)用join函數(shù)對M、C(u)進(jìn)行連接以生成新匹配表M′；每次連接結(jié)束，更新M、Qp；當(dāng)查詢圖結(jié)點(diǎn)全部匹配完成，返回M為結(jié)果，連接過程結(jié)束.

算法2基于候選點(diǎn)的連接

輸入：查詢圖Q，數(shù)據(jù)圖G

輸出：匹配結(jié)果表M

1 partial matching query graphQp=?;

2 fori=1 to |Vq|:

3 ifi==1:

4u′=argminu|C(u)|;

5M=C(u′),Qp.add(u′);

6 else:

7u′=argminu{|C(u)||u?Qp∧N(u)∩Qp!=?};

8 new matching tableM′=join(M,C(u′));

9M=M′,Qp.add(u′);

10 returnM;

如圖7所示，新匹配表的生成是連接階段的關(guān)鍵步驟.假定Qp={u0,u1}且部分匹配表為M1，須進(jìn)行u2匹配，已知C(u2)={v5}.1）獲得Qm=N(u2)∩Qp，即與u2相鄰且已匹配的查詢點(diǎn)集，為M1的每一行分配1個線程束(warp)，在warpi中查詢Qm在該行對應(yīng)匹配的數(shù)據(jù)點(diǎn)，求得這些數(shù)據(jù)點(diǎn)鄰居數(shù)量的最小值并記錄下來，即sizei=min{|N(vj)||vj=mi[u′],u′∈Qm}.2）以sizei為粒度給warpi在全局預(yù)分配空間bufi.例如m0中符合條件的匹配點(diǎn)有m?0={v0,v2}，鄰居集合中N(v2)規(guī)模最小，故以|N(v2)|預(yù)分配空間并將N(v2)載入buf0.在這些臨時(shí)空間bufi上，warpi并行地進(jìn)行集合運(yùn)算.以warp0為例，進(jìn)行N(v2)-m0（排除本行中已匹配數(shù)據(jù)點(diǎn)）、N(v2)∩C(u2)和N(v2)∩N(v0)等運(yùn)算.3）將bufi中的結(jié)果和M1對應(yīng)拼接，寫入新匹配表M2，完成u2的匹配.重復(fù)上述過程直到所有查詢點(diǎn)都完成匹配.

圖7 生成新匹配表Fig.7 Generating new matching table

算法3為join 函數(shù)的執(zhí)行過程，由于涉及的集合運(yùn)算多，優(yōu)化這些運(yùn)算將加速整個算法的執(zhí)行.行7中，由于mi的規(guī)模一般不超過10，可以考慮將其緩存至共享內(nèi)存，直接遍歷bufi去除mi中結(jié)點(diǎn)即可.行8中，由于C(u)一般規(guī)模較大且對所有線程共享，可以將其轉(zhuǎn)換成位圖，存于GPU的全局內(nèi)存或常量內(nèi)存中，這樣不僅空間開銷低，且O(1)時(shí)間即可判斷某個結(jié)點(diǎn)是否屬于C(u).行9～10是對m?i中每個數(shù)據(jù)點(diǎn)的鄰居求交集，該部分執(zhí)行次數(shù)多且運(yùn)算中涉及的集合規(guī)模通常比較大，暴力算法時(shí)間開銷大，有必要進(jìn)行優(yōu)化.考慮到圖在GPU上的存儲結(jié)構(gòu).采用CSR（compressed sparse row）格式[31]進(jìn)行存儲.不同于傳統(tǒng)的鄰接表和鄰接矩陣的圖數(shù)據(jù)表現(xiàn)形式，CSR具有節(jié)省空間、存儲結(jié)構(gòu)對GPU友好的優(yōu)點(diǎn).使用CSR，O(1)時(shí)間即可定位到結(jié)點(diǎn)的鄰接表，且鄰接表都連續(xù)存儲在一塊區(qū)域，方便了線程的合并訪存.

算法3join(M,C(u))

輸入：匹配表M，候選集C(u)

輸出：新匹配表M′

1Qm=N(u)∩Qp；

2 parallel allocate memory:

3m?i={mi[u′]|u′∈Qm}；

4vs=minargv{|N(v)||v∈m?i}；

5bufi=N(vs)；

6 parallel set operation:

7bufi=bufi-mi；

8bufi=bufi∩C(u)；

9 for eachvjinm?iexceptvs:

10bufi=bufi∩N(vj)；

11 allocate memory for new matching tableM′；

12 parallel link process:

13 linkmiwith bufi，write toM′；

14 returnM′；

為了優(yōu)化交集運(yùn)算，生成CSR時(shí)對鄰接表進(jìn)行預(yù)處理，將每個鄰接表內(nèi)結(jié)點(diǎn)按編號從小到大的順序進(jìn)行排列，以便二分查找使交集運(yùn)算時(shí)間復(fù)雜度顯著降低.如圖8所示，N(vs)被初始加載到bufi中，在所有交集運(yùn)算的鄰居集合中，N(vs)的規(guī)模最小.在線程束并行處理下，即匹配表中的每一行各分配1個warp處理時(shí)，和1個鄰居集合N(vj)求交集，迭代|N(vs)|/|warp|輪，其中|warp|=32.在每輪迭代中，同個warp內(nèi)線程ti在N(vj)中進(jìn)行二分查找，驗(yàn)證N(vs)中的結(jié)點(diǎn)是否在N(vj)出現(xiàn).由于所有鄰居集合的結(jié)點(diǎn)都是按編號有序存放的，當(dāng)warp中相鄰線程在進(jìn)行二分查找時(shí)，訪問過的結(jié)點(diǎn)在物理內(nèi)存上有一定程度的鄰近性，避免了隨機(jī)訪存，提升了訪存效率.

圖8 交集運(yùn)算Fig.8 Intersection operation

引理：給定整數(shù)序列3≤N1≤N2,N3,···,Nk(k≥2)，給出整數(shù)序列1～k的排列π，那么?π，僅當(dāng)π[1]=1時(shí)取得最小值且最小值與無關(guān).

證明：序列N1,N2,···,Nk已給定，則定值，對原式進(jìn)行轉(zhuǎn)化：Nπ[1]lb(F/Nπ[1])，其中N1≤Nπ[1]≤F/3.當(dāng)Nπ[1]=N1即π[1]=1時(shí)，Nπ[1]lb(F/Nπ[1])取得最小值，且該最小值與π[2～k]無關(guān)，證畢.

時(shí)間復(fù)雜度的相關(guān)推導(dǎo)和證明過程中假定的是臨時(shí)結(jié)果bufi不變，在具體實(shí)現(xiàn)中，算法3的行6～10每完成一次集合運(yùn)算都會即時(shí)把不符合要求的數(shù)據(jù)點(diǎn)從bufi剔除，以降低臨時(shí)結(jié)果規(guī)模，因此實(shí)際的時(shí)空復(fù)雜度都會更低.

負(fù)載不均衡不但會導(dǎo)致線程資源的浪費(fèi)，而且會影響整體執(zhí)行耗時(shí).為此，結(jié)合GPU的線程模型，采用線程的三級調(diào)度策略[32]，即在并行場景下，當(dāng)任務(wù)量較大時(shí)，優(yōu)先采用線程塊執(zhí)行；任務(wù)量中等時(shí)，使用線程束；若仍有剩余則使用線程并行處理.如算法3的行6～10，若32≤|N(vs)|＜1024；優(yōu)先采用線程束并行處理；1024≤|N(vs)|，優(yōu)先采用線程塊并行處理.行12～13也可以采用類似調(diào)度策略并行將結(jié)果寫入新匹配表.

5 實(shí)驗(yàn)結(jié)果

對本研究提出的算法GpSI進(jìn)行實(shí)驗(yàn)，并對比GPU上先進(jìn)的算法GSI、基于邊連接的算法GpSM和CPU上廣泛使用的串行算法VF3.實(shí)驗(yàn)采用真實(shí)數(shù)據(jù)集和合成數(shù)據(jù)集進(jìn)行測試.真實(shí)數(shù)據(jù)集來自斯坦福大規(guī)模網(wǎng)絡(luò)數(shù)據(jù)集SNAP[33]，包括臉書社交圈網(wǎng)絡(luò)(facebook)、聯(lián)邦能源委員會郵件通信網(wǎng)絡(luò)(enron)、地理位置社交網(wǎng)絡(luò)(gowalla)、DBLP協(xié)作網(wǎng)絡(luò)(dblp)以及美國得州道路網(wǎng)(road)，各數(shù)據(jù)集詳細(xì)信息如表1所示.表中，MD為最大結(jié)點(diǎn)度數(shù)，NV為結(jié)點(diǎn)數(shù)，NE為邊數(shù).設(shè)置相關(guān)研究中普遍使用的3個查詢圖[34]進(jìn)行實(shí)驗(yàn)，如圖9所示.穩(wěn)定性測試中，采用模型生成或隨機(jī)游走的方式生成數(shù)據(jù)圖、查詢圖以驗(yàn)證算法的魯棒性.真實(shí)數(shù)據(jù)集上結(jié)點(diǎn)一般不帶標(biāo)簽，因此預(yù)處理階段進(jìn)行隨機(jī)設(shè)置，下文若不作特殊說明，數(shù)據(jù)圖中結(jié)點(diǎn)標(biāo)簽種類均設(shè)定為5.算法代碼均采用C++編寫，使用CUDA Toolkit 10.9，操作系統(tǒng)為Ubuntu20.04.CPU為Intel i5-9400，GPU為NVIDIA GTX1650，顯存4 GB，擁有896個流處理器，內(nèi)存為DDR4 16 GB，SSD大小為512 GB.所有實(shí)驗(yàn)均重復(fù)10次，以平均值作為實(shí)驗(yàn)結(jié)果.算法輸出經(jīng)過Boost-VF2lib[35]提供的子圖匹配算法程序的正確性驗(yàn)證.

表1 子圖匹配實(shí)驗(yàn)的數(shù)據(jù)集信息Tab.1 Data set information of subgraph matching

圖9 查詢圖Fig.9 Query graph

5.1 過濾能力測試

在GPU算法中只有GSI基于候選點(diǎn)進(jìn)行連接，將GpSI與GSI進(jìn)行候選集過濾能力的對比測試.連接階段總是從候選集最小的查詢點(diǎn)開始，因此以最小候選集的規(guī)模衡量過濾能力.使用查詢圖Q0作為輸入，結(jié)果如表2所示.可以看出，復(fù)合簽名過濾能力顯著優(yōu)于GSI，候選集規(guī)模更小.在過濾用時(shí)上GpSI也略占優(yōu)勢，主要原因是簽名經(jīng)過精心設(shè)計(jì)，空間占用比GSI少，減少了每個線程驗(yàn)證過程的循環(huán)次數(shù).

表2 2種算法在不同數(shù)據(jù)集上的過濾能力測試結(jié)果Tab.2 Filtering ability test results of two algorithms on different datasets

5.2 執(zhí)行用時(shí)測試

如圖10所示為GpSI與GSI、GpSM和VF3在各數(shù)據(jù)集和查詢圖下的總執(zhí)行用時(shí)比較.VF3在查詢圖Q1、Q2下用時(shí)已遠(yuǎn)超GPU版本算法，故不再記錄；Q2在數(shù)據(jù)圖road中找不到匹配，也不作用時(shí)統(tǒng)計(jì).實(shí)驗(yàn)結(jié)果表明，在總執(zhí)行用時(shí)上，GpSI在所有測試數(shù)據(jù)集上均優(yōu)于同類算法，其中比GSI加速了2～10倍，比GpSM加速了最高100倍.在查詢圖為Q0、Q1時(shí)，查詢圖的邊數(shù)比較稀疏，復(fù)合簽名充分挖掘查詢點(diǎn)局部的數(shù)量和結(jié)構(gòu)特征，使得GpSI相比GSI和GpSM加速明顯.查詢圖Q2中的邊比較稠密，基于候選邊連接的GpSM性能有所提升，由于結(jié)點(diǎn)局部數(shù)量信息的增加，GSI的過濾能力也得到增強(qiáng)，但GpSI在執(zhí)行用時(shí)上依然優(yōu)勢明顯.得益于高效集合運(yùn)算和三級調(diào)度策略，GpSI在真實(shí)世界的冪律圖下表現(xiàn)出色.圖10(a)中，當(dāng)面對稀疏網(wǎng)格圖(road)時(shí)，結(jié)點(diǎn)局部特征缺乏導(dǎo)致GpSM和GSI候選集過濾能力下降，總用時(shí)表現(xiàn)不如VF3，但GpSI的復(fù)合簽名過濾策略使得候選集規(guī)模遠(yuǎn)小于同類算法，在總執(zhí)行用時(shí)上仍然保持巨大優(yōu)勢.

圖10 算法的執(zhí)行用時(shí)對比Fig.10 Comparison of execution time for algorithms

5.3 GPU內(nèi)存占用測試

為了測試算法的內(nèi)存開銷，進(jìn)行GPU內(nèi)存占用MGPU測試.以Q2作為查詢圖，記錄各算法運(yùn)行時(shí)的最大GPU內(nèi)存占用，結(jié)果如圖11所示.可以看出，GpSI的整體內(nèi)存占用優(yōu)于GSI、GpSM.得益于復(fù)合簽名的高效過濾能力，GpSI的候選集與匹配表的規(guī)模比GSI和GpSM的?。粡?fù)合簽名經(jīng)過精心設(shè)計(jì)，自身空間占用優(yōu)于GSI；GpSI連接階段以最小鄰居數(shù)預(yù)分配空間的策略，使得生成新匹配表時(shí)產(chǎn)生的額外空間占用小于GSI.

圖11 算法的圖形處理器內(nèi)存占用對比Fig.11 Comparison of graphic processing unit memory consumption for algorithms

5.4 穩(wěn)定性測試

為了測試GpSI的穩(wěn)定性，記錄算法隨數(shù)據(jù)圖和查詢圖規(guī)模增長時(shí)的總執(zhí)行用時(shí).數(shù)據(jù)圖規(guī)模增長測試中，采用Erd?s-Rényi模型[36]生成隨機(jī)的數(shù)據(jù)圖進(jìn)行實(shí)驗(yàn)，初始時(shí)NV=5.0×104、NE=2.0×105，之后數(shù)據(jù)圖規(guī)模線性遞增直到NV=2.5×105、NE=1.0×106，查詢圖為Q0.在查詢圖規(guī)模增長測試中，使用Erd?s-Rényi模型生成NV=1.0×105、NE=4.0×105的數(shù)據(jù)圖，另隨機(jī)生成若干查詢圖，限定查詢圖結(jié)點(diǎn)的平均度數(shù)為3，結(jié)點(diǎn)數(shù)由6遞增到10，實(shí)驗(yàn)結(jié)果如圖12所示，圖中，NV,D為數(shù)據(jù)圖結(jié)點(diǎn)數(shù)，NV,Q為查詢圖結(jié)點(diǎn)數(shù).由于候選集和匹配表規(guī)模龐大，隨著數(shù)據(jù)圖規(guī)模的增長，GpSM耗時(shí)急劇增加，GpSI和GSI的執(zhí)行用時(shí)都維持著線性增長.GpSI有高強(qiáng)的候選集過濾能力和高效的連接策略，在執(zhí)行用時(shí)上始終優(yōu)于GpSM和GSI，且對圖數(shù)據(jù)規(guī)模的增長不敏感，穩(wěn)定性最好.

圖12 3種算法的穩(wěn)定性測試Fig.12 Scalability test of three algorithms

6 結(jié) 語

本研究提出GPU上的子圖匹配算法GpSI，該算法采用過濾和連接的2階段處理模型.在過濾階段，充分利用結(jié)點(diǎn)的局部數(shù)量特征和結(jié)構(gòu)特征設(shè)計(jì)復(fù)合簽名，增強(qiáng)了候選集過濾能力.在連接階段，采用基于候選點(diǎn)的連接策略，提出以最小鄰居數(shù)為粒度的空間預(yù)分配方法，設(shè)計(jì)高效的集合運(yùn)算，避免了傳統(tǒng)方法帶來的額外開銷，提升了連接效率.針對圖數(shù)據(jù)的不規(guī)則性，在實(shí)現(xiàn)上使用多種方式降低訪存延遲和均衡線程負(fù)載.在未來研究中，計(jì)劃面對更大規(guī)模的圖開展基于多GPU的子圖匹配算法的相關(guān)研究.