基于GPU的子圖匹配優(yōu)化技術(shù)

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

(1.北京理工大學 計算機學院，北京 100081；2.東北大學 計算機科學與工程學院，遼寧 沈陽 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)的解決方法通?；跇涞乃阉骱突厮輰崿F(xiàn)[9].隨著信息時代的發(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]，英偉達推出的計算機統(tǒng)一設(shè)備架構(gòu)（computer unified device architecture，CUDA）編程模型進一步方便了GPU的使用.相比于以CPU為主的圖計算系統(tǒng)，GPU有更高的帶寬和并發(fā)度，為子圖匹配問題的解決帶來了新的思路.

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

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

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

1 預(yù)備知識

1.1 子圖匹配

定義：子圖匹配.給定查詢圖Q={Vq,Eq,Lq}，數(shù)據(jù)圖G={Vg,Eg,Lg}，其中Vq、Vg為圖的結(jié)點集合，Eq、Eg為邊集合，Lq、Lg為結(jié)點到標簽的映射函數(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é)點標簽，ui、vi均為結(jié)點.

圖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個時間片；其次為每個線程塊內(nèi)的共享內(nèi)存(shared memory)，只能由塊內(nèi)線程訪問，大小通常為48 KB，訪問延遲為32個時間片；線程塊內(nèi)還設(shè)有L1緩存，特性與共享內(nèi)存類似.GPU上內(nèi)存總線讀寫全局內(nèi)存和L1緩存每次都傳輸連續(xù)的128 B[30]，因此對同一個線程束內(nèi)的線程而言，訪問一段連續(xù)的內(nèi)存可以進行合并訪存優(yōu)化，顯著降低訪存頻率從而降低訪存延遲.

2 算法處理框架

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

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

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

3 過濾階段

3.1 復(fù)合簽名

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

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

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

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

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

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

輸入：結(jié)點u∈G輸出：結(jié)點簽名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ù)驗證簽名的用時.通常情況下，查詢圖中的結(jié)點標簽均來自數(shù)據(jù)圖，有|Lg|＞|Lq|.為了保證統(tǒng)計的準確性，數(shù)量簽名的桶數(shù)量應(yīng)為|Lg|；結(jié)構(gòu)簽名中的路徑和三角形序列都可由2個標簽組成，考慮可能構(gòu)成的組合數(shù)，桶數(shù)量應(yīng)該分別為|Lg|2.當|Lg|＞＞|Lq|時，由于|Lq|一般不超過10，增加桶的個數(shù)帶來的過濾能力增益有限，此時可以犧牲一定的準確性，基于|Lq|分配桶數(shù)量.一般來講，數(shù)量簽名的桶所占比特序列較長，偏向于記錄數(shù)量；結(jié)構(gòu)簽名中桶的長度較短，偏向于記錄種類.為了節(jié)省空間，以上所有類型的桶大小均支持依據(jù)圖數(shù)據(jù)的統(tǒng)計信息進行動態(tài)調(diào)整.

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

3.2 候選集過濾

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

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

4 連接階段

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

算法2基于候選點的連接

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

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

算法3為join 函數(shù)的執(zhí)行過程，由于涉及的集合運算多，優(yōu)化這些運算將加速整個算法的執(zhí)行.行7中，由于mi的規(guī)模一般不超過10，可以考慮將其緩存至共享內(nèi)存，直接遍歷bufi去除mi中結(jié)點即可.行8中，由于C(u)一般規(guī)模較大且對所有線程共享，可以將其轉(zhuǎn)換成位圖，存于GPU的全局內(nèi)存或常量內(nèi)存中，這樣不僅空間開銷低，且O(1)時間即可判斷某個結(jié)點是否屬于C(u).行9～10是對m?i中每個數(shù)據(jù)點的鄰居求交集，該部分執(zhí)行次數(shù)多且運算中涉及的集合規(guī)模通常比較大，暴力算法時間開銷大，有必要進行優(yōu)化.考慮到圖在GPU上的存儲結(jié)構(gòu).采用CSR（compressed sparse row）格式[31]進行存儲.不同于傳統(tǒng)的鄰接表和鄰接矩陣的圖數(shù)據(jù)表現(xiàn)形式，CSR具有節(jié)省空間、存儲結(jié)構(gòu)對GPU友好的優(yōu)點.使用CSR，O(1)時間即可定位到結(jié)點的鄰接表，且鄰接表都連續(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)化交集運算，生成CSR時對鄰接表進行預(yù)處理，將每個鄰接表內(nèi)結(jié)點按編號從小到大的順序進行排列，以便二分查找使交集運算時間復(fù)雜度顯著降低.如圖8所示，N(vs)被初始加載到bufi中，在所有交集運算的鄰居集合中，N(vs)的規(guī)模最小.在線程束并行處理下，即匹配表中的每一行各分配1個warp處理時，和1個鄰居集合N(vj)求交集，迭代|N(vs)|/|warp|輪，其中|warp|=32.在每輪迭代中，同個warp內(nèi)線程ti在N(vj)中進行二分查找，驗證N(vs)中的結(jié)點是否在N(vj)出現(xiàn).由于所有鄰居集合的結(jié)點都是按編號有序存放的，當warp中相鄰線程在進行二分查找時，訪問過的結(jié)點在物理內(nèi)存上有一定程度的鄰近性，避免了隨機訪存，提升了訪存效率.

圖8 交集運算Fig.8 Intersection operation

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

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

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

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

5 實驗結(jié)果

對本研究提出的算法GpSI進行實驗，并對比GPU上先進的算法GSI、基于邊連接的算法GpSM和CPU上廣泛使用的串行算法VF3.實驗采用真實數(shù)據(jù)集和合成數(shù)據(jù)集進行測試.真實數(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ù)集詳細信息如表1所示.表中，MD為最大結(jié)點度數(shù)，NV為結(jié)點數(shù)，NE為邊數(shù).設(shè)置相關(guān)研究中普遍使用的3個查詢圖[34]進行實驗，如圖9所示.穩(wěn)定性測試中，采用模型生成或隨機游走的方式生成數(shù)據(jù)圖、查詢圖以驗證算法的魯棒性.真實數(shù)據(jù)集上結(jié)點一般不帶標簽，因此預(yù)處理階段進行隨機設(shè)置，下文若不作特殊說明，數(shù)據(jù)圖中結(jié)點標簽種類均設(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.所有實驗均重復(fù)10次，以平均值作為實驗結(jié)果.算法輸出經(jīng)過Boost-VF2lib[35]提供的子圖匹配算法程序的正確性驗證.

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

圖9 查詢圖Fig.9 Query graph

5.1 過濾能力測試

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

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

5.2 執(zhí)行用時測試

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

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

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

為了測試算法的內(nèi)存開銷，進行GPU內(nèi)存占用MGPU測試.以Q2作為查詢圖，記錄各算法運行時的最大GPU內(nèi)存占用，結(jié)果如圖11所示.可以看出，GpSI的整體內(nèi)存占用優(yōu)于GSI、GpSM.得益于復(fù)合簽名的高效過濾能力，GpSI的候選集與匹配表的規(guī)模比GSI和GpSM的?。粡?fù)合簽名經(jīng)過精心設(shè)計，自身空間占用優(yōu)于GSI；GpSI連接階段以最小鄰居數(shù)預(yù)分配空間的策略，使得生成新匹配表時產(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ī)模增長時的總執(zhí)行用時.數(shù)據(jù)圖規(guī)模增長測試中，采用Erd?s-Rényi模型[36]生成隨機的數(shù)據(jù)圖進行實驗，初始時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ù)圖，另隨機生成若干查詢圖，限定查詢圖結(jié)點的平均度數(shù)為3，結(jié)點數(shù)由6遞增到10，實驗結(jié)果如圖12所示，圖中，NV,D為數(shù)據(jù)圖結(jié)點數(shù)，NV,Q為查詢圖結(jié)點數(shù).由于候選集和匹配表規(guī)模龐大，隨著數(shù)據(jù)圖規(guī)模的增長，GpSM耗時急劇增加，GpSI和GSI的執(zhí)行用時都維持著線性增長.GpSI有高強的候選集過濾能力和高效的連接策略，在執(zhí)行用時上始終優(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é)點的局部數(shù)量特征和結(jié)構(gòu)特征設(shè)計復(fù)合簽名，增強了候選集過濾能力.在連接階段，采用基于候選點的連接策略，提出以最小鄰居數(shù)為粒度的空間預(yù)分配方法，設(shè)計高效的集合運算，避免了傳統(tǒng)方法帶來的額外開銷，提升了連接效率.針對圖數(shù)據(jù)的不規(guī)則性，在實現(xiàn)上使用多種方式降低訪存延遲和均衡線程負載.在未來研究中，計劃面對更大規(guī)模的圖開展基于多GPU的子圖匹配算法的相關(guān)研究.