孟 軻 林志恒 譚光明

(*中國(guó)科學(xué)院計(jì)算技術(shù)研究所高性能計(jì)算研究中心 北京 100190)

(**中國(guó)科學(xué)院大學(xué) 北京 100049)

0 引言

子圖匹配算法在多個(gè)領(lǐng)域有著廣泛的應(yīng)用,例如從蛋白質(zhì)相互作用網(wǎng)絡(luò)中提取重要子圖結(jié)構(gòu)來(lái)揭示其三維結(jié)構(gòu),在語(yǔ)義數(shù)據(jù)上挖掘推理模式,從資源描述框架(resource description framework,RDF)[1]數(shù)據(jù)中挖掘關(guān)聯(lián)信息,在社交媒體數(shù)據(jù)中挖掘有價(jià)值的用戶關(guān)系等。子圖匹配算法通常將帶標(biāo)簽的模式圖(pattern graph)作為輸入,并通過(guò)在數(shù)據(jù)圖(data graph)中查找這些模式的所有實(shí)例來(lái)提取出用戶感興趣的子圖。這類算法通常圍繞著數(shù)據(jù)圖中的子圖展開搜索和匹配,而傳統(tǒng)的圖計(jì)算應(yīng)用(例如寬度優(yōu)先搜索和佩奇排名)則是圍繞著頂點(diǎn)狀態(tài)展開計(jì)算[2-4],一些基于圖的學(xué)習(xí)模型也不會(huì)涉及到圖的拓?fù)?而是在每個(gè)節(jié)點(diǎn)上有更大計(jì)算量[5-7]。與之相比,子圖匹配算法內(nèi)存消耗更大,更容易受到數(shù)據(jù)非規(guī)則性的影響。隨著應(yīng)用領(lǐng)域不斷擴(kuò)大,需要處理的圖數(shù)據(jù)的大小也逐年增加,目前圖數(shù)據(jù)的邊數(shù)已達(dá)到百億級(jí)別[8]。遍歷這些邊帶來(lái)的大量數(shù)據(jù)移動(dòng)和計(jì)算量對(duì)當(dāng)下的計(jì)算機(jī)構(gòu)成了不小的挑戰(zhàn)。圖應(yīng)用作為一種典型的非規(guī)則負(fù)載,其極低時(shí)空局部性使其很難在當(dāng)前的體系結(jié)構(gòu)平臺(tái)上獲得令人滿意的并行效率,對(duì)數(shù)據(jù)結(jié)構(gòu)和負(fù)載均衡算法的設(shè)計(jì)也一直是圖算法的研究熱點(diǎn)。

近些年來(lái),以圖形處理單元(graphic processing unit,GPU) 為中心的異構(gòu)圖處理系統(tǒng)不斷涌現(xiàn)[9-10]。相比于以中央處理器(center processing unit,CPU)為主的圖計(jì)算系統(tǒng)而言,GPU 有著更高的帶寬和并發(fā)度,這使得GPU 能夠更快地遍歷圖中所有的邊并能同時(shí)處理更多的請(qǐng)求。而以子圖匹配為代表的圖挖掘算法恰恰需要極高的并發(fā)度和帶寬來(lái)保證性能。異構(gòu)計(jì)算平臺(tái)越來(lái)越普遍,尤其是在E 級(jí)[8]超算的研發(fā)上,異構(gòu)架構(gòu)正逐漸成為主流。許多數(shù)據(jù)中心也開始利用GPU 來(lái)加速各類應(yīng)用。因此如何利用GPU 加速子圖匹配算法是非常有意義而且重要的。然而在GPU 上部署子圖匹配算法仍然有著巨大的挑戰(zhàn),是因?yàn)閳D數(shù)據(jù)結(jié)構(gòu)非常稀疏,且不同的圖數(shù)據(jù)訪存模式差異巨大,采用單一的靜態(tài)優(yōu)化方法往往顧此失彼[10],如何設(shè)計(jì)對(duì)GPU 友好的圖數(shù)據(jù)結(jié)構(gòu),針對(duì)不同情況選擇合適的GPU 優(yōu)化策略顯得至關(guān)重要。

雖然關(guān)于子圖匹配算法的研究有很多,但大多數(shù)都是針對(duì)CPU 算法的研究。解決子圖匹配問(wèn)題最簡(jiǎn)單的方法是窮舉搜索法,但搜索空間隨著圖的節(jié)點(diǎn)規(guī)模呈指數(shù)型增長(zhǎng),即使圖規(guī)模很小,計(jì)算時(shí)間也是不可接受的。文獻(xiàn)[11]提出了一種回溯算法,可以大幅減少搜索空間。后來(lái),其他研究者在此基礎(chǔ)上提出了VF2[12]、QuickSI[13]、GraphQL[14]、GADDI[15]等算法。Ullmann 算法[11]并未定義查詢頂點(diǎn)的匹配順序。VF2[12]從一個(gè)隨機(jī)頂點(diǎn)開始,選擇與已經(jīng)匹配的查詢頂點(diǎn)相連的下一個(gè)頂點(diǎn)。通過(guò)利用頂點(diǎn)標(biāo)簽頻率的全局統(tǒng)計(jì),QuickSI[13]提出了一種匹配順序,該順序?qū)⒈M可能早地訪問(wèn)具有低頻率頂點(diǎn)標(biāo)簽。TurboIso[16]將查詢圖重寫為NEC 樹,該樹將與同時(shí)具有相同鄰居結(jié)構(gòu)的查詢頂點(diǎn)匹配,在一定程度上提高了匹配效率。Spath[17]則提出了一種并行子圖匹配算法,將查詢子圖分解為兩層高的樹,稱之為twig。這些算法用不同的剪枝規(guī)則和匹配順序來(lái)提升性能,但是這些算法仍然太慢,且只能處理具有數(shù)千個(gè)頂點(diǎn)的圖。

近些年來(lái),利用GPU 處理稀疏問(wèn)題逐漸成為一種充滿潛力的方案,因此也有一些研究者試圖在GPU 上部署子圖匹配任務(wù)。GpSense[18]根據(jù)GPU的特點(diǎn)設(shè)計(jì)了對(duì)GPU 友好的數(shù)據(jù)結(jié)構(gòu)和優(yōu)化策略來(lái)加速子圖匹配。GpSM[19]則基于圖拆分的方法,設(shè)計(jì)了一些剪枝算法減少搜索空間,但是其算法依賴人工指定的參數(shù)。GSM[20]是一個(gè)基于Gunrock[9]框架的子圖匹配算法,它將傳統(tǒng)圖計(jì)算的原語(yǔ)擴(kuò)展到圖挖掘的領(lǐng)域。本文提出一種基于GPU 的頂點(diǎn)預(yù)剪枝子圖匹配算法(GPU-based vertex-pruning subgraph matching,GVSM),GVSM 基于圖拆分的子圖匹配算法,利用高效的剪枝規(guī)則和GPU 的高并發(fā)來(lái)提升性能。和現(xiàn)有的子圖匹配算法進(jìn)行性能對(duì)比,GVSM 顯示了顯著的性能優(yōu)勢(shì)。在已有研究的基礎(chǔ)上,本文的主要貢獻(xiàn)有以下3 個(gè)方面。

(1)提出了黑名單算法以及調(diào)度順序決定算法。通過(guò)快速的預(yù)處理,提前大幅減少搜索空間,平衡了并發(fā)度和搜索效率。

(2)GVSM 將高并發(fā)的匹配過(guò)程卸載到GPU 上執(zhí)行,而回溯和連接過(guò)程則放在CPU 上執(zhí)行。設(shè)計(jì)了流水線處理方案讓CPU 和GPU 協(xié)同處理子圖匹配任務(wù),并能夠動(dòng)態(tài)地負(fù)載均衡。

(3)和現(xiàn)有的子圖匹配算法進(jìn)行了性能對(duì)比,詳細(xì)分析了優(yōu)化的有效性,優(yōu)化后的算法顯示出顯著的性能優(yōu)勢(shì)。

1 子圖匹配算法概述

1.1 算法定義

給定一個(gè)數(shù)據(jù)圖D(Vd,Ed,Ld)和模式圖P(Vp,Ep,Lp),其中V 指圖中的點(diǎn)集,E 指圖中的邊集,L 指節(jié)點(diǎn)的標(biāo)簽。子圖匹配算法指在D 中查找所有P 的實(shí)例。即對(duì)vp∈Vq,存在vd與之對(duì)應(yīng)。因此子圖匹配任務(wù)通常接受兩份輸入數(shù)據(jù),一個(gè)是數(shù)據(jù)圖,另一個(gè)是模式圖,一般數(shù)據(jù)圖較大而模式圖較小。例如,如圖1 所示,在給定的數(shù)據(jù)圖中,要查找的模式圖為由標(biāo)簽{A,B,C,D}構(gòu)成的子圖。

圖1 子圖匹配算法與并行化

子圖匹配算法的兩大挑戰(zhàn)是:(1) 產(chǎn)生大量的中間結(jié)果,對(duì)存儲(chǔ)和檢索的壓力巨大;(2) 由于圖數(shù)據(jù)本身的非規(guī)則性,負(fù)載不均衡問(wèn)題十分嚴(yán)重,這對(duì)GPU 這類核數(shù)多但是單核弱的平臺(tái)帶來(lái)了巨大挑戰(zhàn)。

而目前國(guó)內(nèi)外針對(duì)子圖匹配問(wèn)題的解決方案沒(méi)有很好地注意到匹配過(guò)程可以剪枝的地方,導(dǎo)致做了許多冗余的搜索,浪費(fèi)了算力,同時(shí)缺少針對(duì)GPU 這類平臺(tái)進(jìn)行系統(tǒng)性的優(yōu)化。

1.2 查詢圖拆分優(yōu)化

Spath[17]是對(duì)查詢圖進(jìn)行拆分的子圖匹配算法,它將查詢子圖分解為twig(一個(gè)兩層高的樹),如圖1 所示。在拆分完模式圖之后,算法執(zhí)行擴(kuò)展-連接過(guò)程。在擴(kuò)展階段,算法按一定順序匹配每一個(gè)拆分出來(lái)的twig,即遍歷數(shù)據(jù)圖中每個(gè)點(diǎn)及其一階鄰居,查詢其是否能匹配當(dāng)前twig。在連接階段,將每個(gè)twig 匹配到的待選點(diǎn)集進(jìn)行笛卡爾積操作,將這些分割開來(lái)的待選點(diǎn)組合成完整的子圖?；趫D拆分子圖匹配算法過(guò)程可以抽象成2 個(gè)步驟。第1 步驟只匹配單獨(dú)的twig (本文中稱為擴(kuò)展操作,expand),它只檢查單個(gè)點(diǎn)在數(shù)據(jù)圖中的匹配關(guān)系,而不檢查子圖的拓?fù)潢P(guān)系;第2 步驟檢查生成的子圖的拓?fù)潢P(guān)系是否滿足模式圖的拓?fù)潢P(guān)系(本文中稱為連接操作,join),它需要對(duì)子圖的整體連通性進(jìn)行檢查。

1.3 基于前綴樹的壓縮優(yōu)化

為了存儲(chǔ)產(chǎn)生的大量的中間結(jié)果,必須要對(duì)其進(jìn)行數(shù)據(jù)壓縮,來(lái)減少其消耗的存儲(chǔ)空間。由于產(chǎn)生的中間結(jié)果有許多的重合部分,因此可以采用前綴樹的方式來(lái)壓縮中間結(jié)果的共同部分,如圖2 所示。產(chǎn)生的2 個(gè)中間結(jié)果{A,B,C}和{A,B,D}有著相同的部分{A,B},因此可以存儲(chǔ)到同一個(gè)根上。將這些中間結(jié)果稱為圖的一個(gè)嵌入。

圖2 前綴樹存儲(chǔ)子圖

前綴樹的每一部分保存2 個(gè)值{vid,idx}。其中idx 表示該嵌入的前序點(diǎn)的索引,vid 表示該嵌入的當(dāng)前節(jié)點(diǎn)的標(biāo)簽。而前綴樹的每一層所存儲(chǔ)的節(jié)點(diǎn)的標(biāo)簽都是相同的。前綴樹將隨著子圖匹配算法的過(guò)程進(jìn)行構(gòu)建,子圖匹配過(guò)程中每匹配一個(gè)twig就會(huì)增加前綴樹的一層,由于相同的前綴總是只需保存一份,相比于直接存儲(chǔ)子圖可以節(jié)省大量的存儲(chǔ)空間。但是在連接過(guò)程中,整個(gè)子圖需要還原到原始的結(jié)構(gòu)。此時(shí)可以從前綴樹的葉子節(jié)點(diǎn)開始沿著idx 指針進(jìn)行遍歷直到抵達(dá)根節(jié)點(diǎn),此時(shí)路徑上的節(jié)點(diǎn)就構(gòu)成了當(dāng)前迭代下已經(jīng)匹配的子圖。

2 子圖匹配算法優(yōu)化

本節(jié)將詳細(xì)介紹子圖匹配的算法優(yōu)化,包括縮小搜索空間、搜索時(shí)剪枝優(yōu)化、調(diào)度順序優(yōu)化,這些算法能夠顯著減少搜索空間,并減少需要存儲(chǔ)的子圖的數(shù)目。

2.1 縮小搜索空間

為了減少子圖匹配過(guò)程中產(chǎn)生的中間結(jié)果,本文設(shè)計(jì)了黑名單算法來(lái)提前排除數(shù)據(jù)圖G 中的部分點(diǎn)和邊。如圖1 所示,頂點(diǎn)v1雖然有著和模式圖匹配的標(biāo)簽B,但是它沒(méi)有標(biāo)簽為D 的孩子節(jié)點(diǎn),因此在后序的匹配中必然不能形成有效匹配。如果將這個(gè)子圖拖到最后才排除,那么勢(shì)必會(huì)浪費(fèi)優(yōu)先的計(jì)算資源和存儲(chǔ)空間。因此在開始子圖匹配算法之前,先對(duì)子圖的部分節(jié)點(diǎn)進(jìn)行標(biāo)記,使其不參與后序的匹配過(guò)程。對(duì)子圖的標(biāo)記通過(guò)位圖(Bitmap)來(lái)完成,每一位代表該節(jié)點(diǎn)是否被標(biāo)記為被排除的點(diǎn)。這一部分可以在預(yù)處理完成。GPU 在執(zhí)行匹配的過(guò)程中,首先讀取該位圖中的信息,如果某個(gè)線程發(fā)現(xiàn)當(dāng)前節(jié)點(diǎn)被位圖標(biāo)記為應(yīng)當(dāng)排除的節(jié)點(diǎn),那么就直接跳過(guò)該節(jié)點(diǎn)的匹配,從而減少搜索時(shí)間。

最初位圖中所有位全部初始化為0,此時(shí)所有的頂點(diǎn)都是合法的。黑名單算法將迭代進(jìn)行篩選,在上一輪被加入黑名單的節(jié)點(diǎn)在本輪迭代中不會(huì)參與統(tǒng)計(jì),因此會(huì)影響它的鄰居節(jié)點(diǎn),使得更多的節(jié)點(diǎn)被加入黑名單。該算法將遍歷模式圖P 中的每個(gè)頂點(diǎn),同時(shí)也將其鄰居節(jié)點(diǎn)的標(biāo)簽進(jìn)行遍歷,記錄其鄰居標(biāo)簽的種類和數(shù)量,并將這些信息單獨(dú)存入數(shù)組中。之后循環(huán)遍歷數(shù)據(jù)圖D 中的每個(gè)節(jié)點(diǎn),記錄當(dāng)前節(jié)點(diǎn)v 的鄰居節(jié)點(diǎn)的標(biāo)簽數(shù)目和種類。隨后查詢P 中是否存在頂點(diǎn)u,其鄰居節(jié)點(diǎn)的狀態(tài)能夠匹配節(jié)點(diǎn)v。若不能匹配,則將v 加入黑名單。這說(shuō)明節(jié)點(diǎn)v 無(wú)論如何都無(wú)法和模式圖中的某個(gè)節(jié)點(diǎn)進(jìn)行匹配,故可以提前剪枝。這個(gè)算法由于不需要存儲(chǔ)中間結(jié)果,每次只需要遍歷一次邊集即可完成標(biāo)記,因此開銷非常低,第4 節(jié)將詳細(xì)分析該算法的開銷。

在1.2 節(jié)中,介紹了基于圖拆分的子圖匹配算法,它將模式圖P 拆成兩層高的樹(twig)來(lái)和數(shù)據(jù)圖中的節(jié)點(diǎn)進(jìn)行匹配,這意味著在匹配過(guò)程中不僅要匹配節(jié)點(diǎn)自己的標(biāo)簽,也要匹配節(jié)點(diǎn)的一階鄰居的標(biāo)簽。黑名單算法也基于類似的規(guī)則,如果數(shù)據(jù)圖中的某個(gè)節(jié)點(diǎn)v 不能匹配模式圖中拆分出來(lái)的任意一個(gè)twig,那么這個(gè)節(jié)點(diǎn)就是不合法的,可以提前篩除。而且篩除節(jié)點(diǎn)v 將影響到它的所有鄰居節(jié)點(diǎn),這將導(dǎo)致它的某個(gè)鄰居u 從合法狀態(tài)變?yōu)椴缓戏顟B(tài),是因?yàn)閡 的合法性可能依賴于v。例如節(jié)點(diǎn)u 必須借助鄰居v 才能和模式圖P 中拆出來(lái)的twig 進(jìn)行匹配。若v 變?yōu)椴缓戏?那么u 也不合法。因此黑名單算法是一個(gè)遞歸的過(guò)程,在每一輪迭代中,不斷篩除不合法的節(jié)點(diǎn)。在最初的幾輪迭代中,會(huì)標(biāo)記大量的節(jié)點(diǎn)到黑名單中,但隨著迭代的推進(jìn),標(biāo)記的效率會(huì)大幅下降。因此黑名單算法可以只執(zhí)行最初幾輪迭代就停止,來(lái)平衡算法開銷和剪枝效率。

2.2 剪枝優(yōu)化

在搜索之前執(zhí)行黑名單算法可以有效減少搜索空間。在搜索的過(guò)程中,也可以進(jìn)行一些剪枝操作來(lái)提前終止搜索分支以減少內(nèi)存和算力的開銷。最基礎(chǔ)的剪枝條件就是數(shù)據(jù)圖中當(dāng)前節(jié)點(diǎn)的標(biāo)簽和正在匹配的twig 的根節(jié)點(diǎn)標(biāo)簽要保持一致。而進(jìn)一步嚴(yán)格的檢查則需要對(duì)它們的鄰居節(jié)點(diǎn)進(jìn)行一一匹配,這是一個(gè)耗時(shí)的步驟,它需要檢索大量的邊。由于輸入數(shù)據(jù)常常存在著擁有大量邊集的“超級(jí)節(jié)點(diǎn)”,因此數(shù)據(jù)圖D 中常常存在蘊(yùn)含關(guān)系,即對(duì)于D中2 個(gè)頂點(diǎn)v 和u,它們具有相同的標(biāo)簽且u 的鄰居集合是v 鄰居集合的子集,記做v?u。形式化表達(dá)如下,如果v ?u,當(dāng)且僅當(dāng)L(v)=L(u) 且Adj(u)?Adj(v),其中L(v)表示v 的標(biāo)簽,Adj(v)是v 的鄰居頂點(diǎn)集。根據(jù)蘊(yùn)含關(guān)系可以得知,當(dāng)v?u時(shí),如果v 匹配失敗,那么此時(shí)u 的匹配也必然失敗。如圖3 所示,節(jié)點(diǎn)v1、v2、v3都能匹配當(dāng)前標(biāo)簽B,且節(jié)點(diǎn)v2、v3的鄰域是v1的鄰域的子集,因此v1?v2且v1?v3。由于v1沒(méi)有標(biāo)簽為E 的鄰居,因此v1匹配失敗,根據(jù)蘊(yùn)含關(guān)系,不需要進(jìn)行數(shù)據(jù)比對(duì)也可以推出v2、v3匹配將失敗,因此之后的匹配可以跳過(guò)v2、v3?？梢岳迷撘蕾囮P(guān)系對(duì)子圖匹配的搜索過(guò)程進(jìn)行剪枝。因此對(duì)于數(shù)據(jù)圖中某一節(jié)點(diǎn)u和其在模式圖中的匹配節(jié)點(diǎn)u′設(shè)立3 條規(guī)則來(lái)實(shí)現(xiàn)該剪枝過(guò)程。

圖3 蘊(yùn)含關(guān)系剪枝優(yōu)化

(1) 頂點(diǎn)u′和u 標(biāo)簽必須相同,且deg(u) >=deg(u′)(deg(u)表示頂點(diǎn)u 的度)。

(2) 頂點(diǎn)u 的鄰居頂點(diǎn)擁有的標(biāo)簽種類必須比頂點(diǎn)u′多。

(3) 若D 中存在v?u,則要求v 必須能匹配u′。

其中前兩條規(guī)則可以簡(jiǎn)單地判斷當(dāng)前頂點(diǎn)u 是否有足夠的鄰居節(jié)點(diǎn)來(lái)完成后續(xù)的匹配,最后一條規(guī)則利用了蘊(yùn)含關(guān)系來(lái)進(jìn)行提前剪枝,其實(shí)現(xiàn)方式如圖3 所示。通過(guò)提前對(duì)數(shù)據(jù)圖進(jìn)行預(yù)處理可以得到一個(gè)依賴數(shù)組Deps,表示節(jié)點(diǎn)Deps[i]蘊(yùn)含節(jié)點(diǎn)i,即Deps[i]?i。在匹配過(guò)程中,維護(hù)一個(gè)匹配數(shù)組Match,其中Match[i]表示節(jié)點(diǎn)i 可以在模式圖中得到一個(gè)合法的匹配,其中0 表示不合法,1 表示合法,-1 表示尚未處理。通過(guò)查詢Match[Deps[i]]即可得知節(jié)點(diǎn)i 是否需要被剪枝處理。為了減少開銷,在本文中,只關(guān)注一層蘊(yùn)含關(guān)系,即不關(guān)注嵌套的蘊(yùn)含關(guān)系。即便如此,實(shí)驗(yàn)證明該剪枝規(guī)則能減少大量的不必要的搜索。

另一方面,蘊(yùn)含關(guān)系也能夠減少內(nèi)存消耗,在1.3 節(jié)中介紹了利用前綴樹的方式存儲(chǔ)子圖匹配的中間結(jié)果的方法,前綴樹需要存儲(chǔ)在GPU 的顯存中,而這一部分的存儲(chǔ)空間往往較少,即使使用了前綴樹的方式進(jìn)行了壓縮,子圖匹配產(chǎn)生的大量的中間結(jié)果仍然是一個(gè)巨大的壓力。特殊地,若v?u且u?v,即v 和u 的鄰居節(jié)點(diǎn)相同,但是占據(jù)著前綴樹不同的空間,可以把這些節(jié)點(diǎn)合并到一起,以鏈表的方式存儲(chǔ)到一個(gè)前綴樹分支里,在遍歷該前綴樹的時(shí)候只需處理一次,來(lái)代替被合并的鏈表里的所有節(jié)點(diǎn)。在匹配結(jié)束后,可以將這些節(jié)點(diǎn)依次替換,將其還原,可以節(jié)省前綴樹存儲(chǔ)的空間。

2.3 最優(yōu)調(diào)度順序

在搜索過(guò)程中存在著大量的冗余搜索。這是因?yàn)橐恍┧阉鞣种ё罱K無(wú)法匹配模式圖,但是在搜索過(guò)程中由于無(wú)法判斷是否能夠形成匹配,不得不將其存儲(chǔ)到接下來(lái)的迭代中。事實(shí)上在數(shù)據(jù)圖中頂點(diǎn)的信息量存在著差別,信息量越大的節(jié)點(diǎn)匹配越嚴(yán)格,可以更早地排除沒(méi)有潛力的節(jié)點(diǎn)[21]。如圖1 所示,查詢圖P 和數(shù)據(jù)圖D 中,如果不考慮任何剪枝優(yōu)化,假設(shè)匹配順序?yàn)閧C,A,B,D},那么在第一輪迭代中數(shù)據(jù)圖有3 個(gè)C 符合標(biāo)簽,因此將需要存儲(chǔ)3 個(gè)中間結(jié)果,而若匹配順序?yàn)閧D,B,A,C},那么第一輪迭代只需存儲(chǔ)一個(gè)中間結(jié)果。因此,對(duì)于數(shù)據(jù)圖里頂點(diǎn)的匹配順序?qū)⒂绊懰阉餍?。為了減少中間結(jié)果的產(chǎn)生,盡量將較難匹配的節(jié)點(diǎn)或者匹配結(jié)果較少的節(jié)點(diǎn)提前進(jìn)行匹配,來(lái)減少匹配過(guò)程中產(chǎn)生的中間結(jié)果。對(duì)于一個(gè)模式圖中的節(jié)點(diǎn),它的鄰居節(jié)點(diǎn)數(shù)目和標(biāo)簽的種類越多,其匹配的難度越高。同時(shí)它在數(shù)據(jù)圖中的直接匹配越少,則預(yù)期產(chǎn)生的中間結(jié)果數(shù)目就越少,采用g(v)來(lái)衡量模式圖中節(jié)點(diǎn)v 的預(yù)期產(chǎn)生中間結(jié)果的多少,可設(shè)g(v)=(freq(v) -blacklist(v))/(deg(v) × labels(Adj(v)))。其中freq(v)表示v 的標(biāo)簽在數(shù)據(jù)圖中出現(xiàn)的頻度,blacklist(v)表示v 的標(biāo)簽在黑名單中出現(xiàn)的頻度,deg(v)表示v 的節(jié)點(diǎn)度數(shù),labels(Adj(v))表示v 的鄰居節(jié)點(diǎn)標(biāo)簽的種類數(shù)目。當(dāng)g(v)越高時(shí),匹配v 產(chǎn)生的中間結(jié)果就可能越多。因此調(diào)度順序可以通過(guò)利用g(v)來(lái)啟發(fā)式地決定。

最優(yōu)調(diào)度順序生成算法實(shí)際上是最小生成樹prime 算法的變體。在最開始的一輪迭代里選擇g(v)值最小的節(jié)點(diǎn),將其加入到已挑選集合O 中。隨后的每一輪迭代里,在剩下的節(jié)點(diǎn)里挑選一個(gè)與O 聯(lián)通且g(v)最小的節(jié)點(diǎn),在GVSM 的實(shí)現(xiàn)中,可以通過(guò)優(yōu)先隊(duì)列來(lái)維護(hù)當(dāng)前g(v)最小的節(jié)點(diǎn)。對(duì)于子圖匹配而言,實(shí)際上其搜索空間并不是整個(gè)數(shù)據(jù)圖,而是受限于查詢圖的特征。通過(guò)選擇最優(yōu)的調(diào)度順序,將每一輪迭代可能產(chǎn)生的中間結(jié)果控制在最小,該算法可以在預(yù)處理階段進(jìn)行。若模式圖P 中有n 個(gè)節(jié)點(diǎn),計(jì)算出每個(gè)節(jié)點(diǎn)的g(v)值并以此為據(jù)排序,需要O(n log n)代價(jià),故生成調(diào)度順序的算法需要O(n2log n)的代價(jià)。由于n 的數(shù)值一般很小,因此該算法帶來(lái)的預(yù)處理開銷可以忽略不計(jì)。

3 基于GPU 的子圖匹配系統(tǒng)的設(shè)計(jì)

針對(duì)GPU 高并發(fā)、高帶寬的特點(diǎn),在第2 節(jié)的基礎(chǔ)上,實(shí)現(xiàn)了基于GPU 的子圖匹配系統(tǒng)GVSM。GVSM 能充分利用異構(gòu)架構(gòu)的特點(diǎn),協(xié)同完成匹配任務(wù)。3.1 節(jié)將介紹CPU-GPU 的流水線設(shè)計(jì),3.2 節(jié)將提出GPU 和CPU 之間的自適應(yīng)負(fù)載均衡優(yōu)化。

3.1 流水線設(shè)計(jì)

如第1 節(jié)所述,子圖匹配算法是一個(gè)需要大量搜索的算法,如果能利用GPU 大量的線程進(jìn)行搜索將能夠極大地提升搜索效率。但GPU 更適合做規(guī)則的運(yùn)算,如果將整個(gè)子圖匹配算法都放到GPU上,可能會(huì)導(dǎo)致嚴(yán)重的負(fù)載均衡問(wèn)題,使得系統(tǒng)無(wú)法充分發(fā)揮GPU 的高并發(fā)性。另外,由于GPU 的顯存大小限制,子圖匹配的搜索過(guò)程產(chǎn)生的大量中間結(jié)果如果保存在GPU 顯存內(nèi),則可能面臨顯存溢出的問(wèn)題。因此,本文采用CPU 和GPU 協(xié)同計(jì)算的模式進(jìn)行子圖匹配,利用GPU 執(zhí)行每輪的計(jì)算任務(wù),將GPU 計(jì)算時(shí)產(chǎn)生的大量中間結(jié)果和候選子圖保存至CPU 主存上克服GPU 的內(nèi)存溢出問(wèn)題,同時(shí)CPU 的多線程技術(shù)也能為GPU 分擔(dān)一些簡(jiǎn)單的計(jì)算任務(wù),使得兩者能夠協(xié)同計(jì)算。

在第1 節(jié)中,本文介紹了基于擴(kuò)展-連接的子圖匹配算法。如圖4 所示,在GPU 的實(shí)現(xiàn)中,擴(kuò)展過(guò)程考慮的是子圖和頂點(diǎn)/邊的關(guān)系,它在已經(jīng)找到的中間結(jié)果上,通過(guò)遍歷邊界點(diǎn)的鄰居節(jié)點(diǎn)來(lái)產(chǎn)生新的待選子圖,因此邏輯比較簡(jiǎn)單。而GPU 擅長(zhǎng)利用大量線程做一些簡(jiǎn)單的任務(wù),這樣的特性適合用來(lái)執(zhí)行擴(kuò)展操作,GPU 只需要輸入前綴樹的一部分?jǐn)?shù)據(jù)就可以進(jìn)行擴(kuò)展操作。由于GPU 的內(nèi)存容量小,而CPU 端的內(nèi)存容量往往遠(yuǎn)大于GPU 內(nèi)存,因此本文通過(guò)借助CPU 內(nèi)存來(lái)保存中間結(jié)果。對(duì)于連接操作而言,其處理的是子圖內(nèi)部的關(guān)系,這相比于擴(kuò)展操作往往更加復(fù)雜,它需要按照前綴樹的索引將整個(gè)待選子圖還原,這不僅需要復(fù)雜的邏輯也需要大量的非連續(xù)內(nèi)存訪問(wèn)。而CPU 擅長(zhǎng)處理邏輯復(fù)雜的操作,因此本文利用CPU 的多線程技術(shù)來(lái)處理連接過(guò)程。這就需要CPU 和GPU 進(jìn)行協(xié)同計(jì)算,利用數(shù)據(jù)移動(dòng)解決內(nèi)存空間不足的問(wèn)題。

圖4 GPU-CPU 協(xié)同處理的Expand-Join 操作

為了充分發(fā)揮GPU 和CPU 各自的優(yōu)勢(shì),本文設(shè)計(jì)了流水線方案來(lái)隱藏CPU 和GPU 之間數(shù)據(jù)傳輸。在迭代開始時(shí),CPU 端生成初始待匹配的集合。為了讓GPU 執(zhí)行擴(kuò)展操作,系統(tǒng)需要將數(shù)據(jù)通過(guò)高速串行計(jì)算機(jī)擴(kuò)展總線(peripheral component interconnect express,PCI-E)傳輸?shù)紾PU 顯存。GPU在接收到數(shù)據(jù)之后,對(duì)當(dāng)前的子圖進(jìn)行搜索,生成候選匹配的中間結(jié)果集合。接著需要將這些中間結(jié)果從GPU 設(shè)備端拷貝到CPU 主存,讓CPU 執(zhí)行連接操作檢查這些子圖,CPU 將合格的子圖保存在主存上。在下一輪迭代中,將部分?jǐn)?shù)據(jù)繼續(xù)拷貝到GPU上重復(fù)執(zhí)行上述步驟。當(dāng)?shù)Y(jié)束時(shí),所有挖掘到的子圖將保存在CPU 主存上。整個(gè)流程簡(jiǎn)化后可以分為以下4 個(gè)步驟。

(1) 數(shù)據(jù)拷貝到GPU。

(2) GPU 執(zhí)行擴(kuò)展操作。

(3) 數(shù)據(jù)拷貝回CPU。

(4) CPU 執(zhí)行連接操作。

按這樣的4 個(gè)步驟,系統(tǒng)可以依次串行執(zhí)行整個(gè)圖挖掘過(guò)程,在第i 輪時(shí),按串行思路需要依次做完步驟(1)～(4)之后才會(huì)執(zhí)行第i +1 輪迭代。但這樣的方式使得當(dāng)GPU 在執(zhí)行擴(kuò)展操作時(shí),由于CPU 還沒(méi)有接收到數(shù)據(jù)無(wú)法處理而處于等待狀態(tài)。GVSM 通過(guò)流水線的方式,讓GPU 和CPU 可以同時(shí)進(jìn)行計(jì)算,同時(shí)重疊數(shù)據(jù)傳輸和計(jì)算,如圖5 所示。

為防止內(nèi)存溢出,系統(tǒng)每次僅拷貝本輪的一部分?jǐn)?shù)據(jù)至GPU 進(jìn)行擴(kuò)展操作,因此本文對(duì)前綴樹進(jìn)行了切分,每次計(jì)算時(shí)只傳輸前綴樹中一層的一部分?jǐn)?shù)據(jù)到GPU 中參與擴(kuò)展,這是因?yàn)镚PU 執(zhí)行擴(kuò)展操作時(shí)會(huì)消耗大量?jī)?nèi)存。由于采用了流水線設(shè)計(jì),GPU 中需要同時(shí)保存第i-1、i、i+1 輪迭代的數(shù)據(jù),與之對(duì)應(yīng)CPU 也需要同時(shí)保存第i -1、i、i +1輪迭代的數(shù)據(jù),因此需要將存儲(chǔ)空間分為3 個(gè)緩沖區(qū),用來(lái)保存3 個(gè)相鄰迭代的數(shù)據(jù)。對(duì)于GPU 來(lái)說(shuō),同一時(shí)刻,除了正在處理第i 輪的數(shù)據(jù)以外,還可以同時(shí)保存下行的i +1 輪的數(shù)據(jù)和上行的i -1 輪迭代的數(shù)據(jù)。如圖5 所示,在數(shù)據(jù)交換的過(guò)程中,需要依據(jù)對(duì)應(yīng)的內(nèi)存緩沖區(qū)拷貝數(shù)據(jù),得益于英偉達(dá)GPU 的雙拷貝(dual-copy)引擎,第i-1 份擴(kuò)展后的候選數(shù)據(jù)的設(shè)備到主存?zhèn)鬏?device to host,D2H)(步驟(3))和第i +1 份待擴(kuò)展數(shù)據(jù)的主存到設(shè)備傳輸(host to device,H2D)(步驟(1))可以進(jìn)行數(shù)據(jù)傳輸重疊,與此同時(shí)GPU 上第i 輪的擴(kuò)展操作和CPU 第i+2 輪的連接操作也可以同時(shí)進(jìn)行。利用這樣的流水線模式,系統(tǒng)能夠充分利用CPU 和GPU的計(jì)算能力,重疊了計(jì)算也節(jié)省了數(shù)據(jù)的傳輸時(shí)間。

圖5 基于流水線的子圖匹配算法流程

3.2 自適應(yīng)負(fù)載均衡

由于子圖匹配在擴(kuò)展操作過(guò)程中會(huì)產(chǎn)生不可控?cái)?shù)量的中間結(jié)果,同時(shí)產(chǎn)生的中間結(jié)果隨著迭代的深入而逐漸增多,如果每次流水線固定拷貝一整層數(shù)量的節(jié)點(diǎn)到GPU,可能會(huì)導(dǎo)致實(shí)際需要處理的邊集相差較大。在子圖匹配的早期階段,需要的內(nèi)存量很小,整個(gè)擴(kuò)展-連接過(guò)程都可以在GPU 上直接完成,此時(shí)拷貝到CPU 上反而導(dǎo)致了額外的開銷。由于不是所有的情況下使用GPU 都能起到加速效果,比如在數(shù)據(jù)量較少的時(shí)候?qū)?shù)據(jù)拷貝到GPU 上反而會(huì)使性能下降。因此本文設(shè)計(jì)一種動(dòng)態(tài)負(fù)載均衡方法,通過(guò)設(shè)置一個(gè)閾值th,當(dāng)前綴樹的某一層數(shù)量超過(guò)這個(gè)閾值時(shí),才將連接操作通過(guò)流水線的方式交由CPU 處理,否則所有的流程都在GPU 上處理。

為了保證流水線能更好地重疊計(jì)算,需要GPU和CPU 的負(fù)載盡可能相同,否則會(huì)導(dǎo)致算力的浪費(fèi)。在算法的前期,子圖匹配過(guò)程將產(chǎn)生大量的中間結(jié)果,而且增長(zhǎng)速度非?？?。GVSM 采用分塊的方法進(jìn)行處理,每次從前綴樹中拷貝chunk_size 個(gè)頂點(diǎn)到GPU 中去,但是其個(gè)數(shù)將隨著CPU 的負(fù)載變動(dòng)。由圖5 可知,為了保證重疊率,其塊大小chunk_size 需要保證GPU 處理第i 輪擴(kuò)展操作的時(shí)間要盡可能和CPU 處理第i -2 輪的連接操作時(shí)間相同。但是由于不同的節(jié)點(diǎn)的鄰居節(jié)點(diǎn)數(shù)量不一樣,有的節(jié)點(diǎn)可能連接著數(shù)百萬(wàn)的節(jié)點(diǎn),而有的節(jié)點(diǎn)可能只有數(shù)個(gè)節(jié)點(diǎn)。那么每次拷貝固定大小的塊到GPU 上仍然會(huì)導(dǎo)致嚴(yán)重的負(fù)載不均衡問(wèn)題,從而影響流水線的運(yùn)行。因此根據(jù)出度數(shù)作為每個(gè)節(jié)點(diǎn)的權(quán)重,通過(guò)提前保存當(dāng)前層節(jié)點(diǎn)權(quán)重的前綴和來(lái)進(jìn)行任務(wù)塊的劃分,通過(guò)二分的方法確定當(dāng)前塊的大小,保證每次拷貝到GPU 上的任務(wù)塊需要處理的邊的數(shù)目和連接操作需要處理的邊的數(shù)目滿足線性關(guān)系,即chunk_size×avg_degree=k×subgraph_size。其中subgraph_size 是第i -2 次迭代需要連接操作的子圖的數(shù)量,avg_degree 表示當(dāng)前塊的平均出度數(shù)。而k 值需要通過(guò)多次實(shí)驗(yàn)采用回歸訓(xùn)練確定。通過(guò)這種方法能夠以幾乎忽略不計(jì)的開銷保證每次迭代需要處理的任務(wù)塊有相近的處理時(shí)間。

另一方面,擴(kuò)展操作通過(guò)接受前綴樹中的一段節(jié)點(diǎn),以及模式圖中的一個(gè)twig,在數(shù)據(jù)圖中尋找對(duì)應(yīng)的匹配,這一過(guò)程通常在GPU 上進(jìn)行。而在之后的連接操作,則將新匹配出的節(jié)點(diǎn)和之前匹配出來(lái)的中間結(jié)果進(jìn)行笛卡爾積操作,來(lái)判斷所形成的新的子圖是否符合要求。在此過(guò)程中,每次只添加一個(gè)節(jié)點(diǎn)。事實(shí)上,子圖匹配也可以在一次內(nèi)核調(diào)用中處理2 個(gè)twig,即同時(shí)匹配2 個(gè)節(jié)點(diǎn),相當(dāng)于增加了搜索的步長(zhǎng)。尤其在算法后期,節(jié)點(diǎn)數(shù)目較少時(shí),可以增加搜索的步長(zhǎng),加快優(yōu)化。

4 實(shí)驗(yàn)評(píng)測(cè)

4.1 實(shí)驗(yàn)環(huán)境和基準(zhǔn)測(cè)試程序

在本節(jié)中,使用本文提出的技術(shù)構(gòu)建了一個(gè)完整的子圖匹配算法GVSM,并選擇6 個(gè)真實(shí)數(shù)據(jù)集作為數(shù)據(jù)圖。如表1 所示,這6 個(gè)數(shù)據(jù)集的頂點(diǎn)規(guī)模在十萬(wàn)至百萬(wàn)級(jí)別,邊規(guī)模在百萬(wàn)至千萬(wàn)級(jí)別。其中nv 表示對(duì)應(yīng)數(shù)據(jù)集中頂點(diǎn)的數(shù)量,ne 表示對(duì)應(yīng)數(shù)據(jù)集中邊的數(shù)量。Ave-degree 為數(shù)據(jù)圖中每個(gè)頂點(diǎn)的度的平均數(shù)。它在一定程度上反映了圖的稠密程度,一般來(lái)說(shuō),平均度數(shù)越高說(shuō)明圖越稠密,反之則說(shuō)明圖越稀疏。這些真實(shí)數(shù)據(jù)集普遍具有無(wú)尺度(scale-free)的特點(diǎn),即每個(gè)頂點(diǎn)擁有的邊的數(shù)量呈冪律分布,這導(dǎo)致部分節(jié)點(diǎn)擁有大量的邊與之相連,而絕大數(shù)頂點(diǎn)只有少數(shù)邊相連。通過(guò)預(yù)處理,對(duì)實(shí)驗(yàn)數(shù)據(jù)分配隨機(jī)數(shù)量的標(biāo)簽,并選擇各種不同規(guī)模的模式圖進(jìn)行子圖匹配任務(wù)。

表1 GVSM 測(cè)試的數(shù)據(jù)集

實(shí)驗(yàn)運(yùn)行平臺(tái)的服務(wù)器為搭載架構(gòu)為Intel Xeon 的處理器并裝有Nvidia 的tesla P100 顯卡,配備16 GB 顯存。操作系統(tǒng)為ubuntu 16.04,內(nèi)存為94 GB,CUDA 版本為CUDA 10.0。每次測(cè)試時(shí)間為10 次運(yùn)行的平均時(shí)間。選擇近些年發(fā)布的開源的基于GPU 的子圖匹配算法GpSM[19]和GSM[20]作為參考對(duì)象。GpSM 針對(duì)GPU 結(jié)構(gòu)做了優(yōu)化,加速了子圖匹配算法的計(jì)算流程。GSM 則是基于Gunrock[9]的基礎(chǔ)上所構(gòu)建的子圖匹配算法。其實(shí)現(xiàn)也都是基于圖拆分的子圖匹配,分為擴(kuò)展和連接兩步。而Gunrock 是GPU 上非常流行的圖算法庫(kù),有著優(yōu)化良好的庫(kù)函數(shù)來(lái)處理GPU 上的稀疏數(shù)據(jù)。

4.2 性能對(duì)比

為了驗(yàn)證算法的高效性,在6 個(gè)真實(shí)圖數(shù)據(jù)上,通過(guò)和開源的已發(fā)表的工作GpSM 和GSM 進(jìn)行單節(jié)點(diǎn)的性能對(duì)比,以測(cè)試算法執(zhí)行時(shí)間與查詢圖中頂點(diǎn)數(shù)量之間的關(guān)系,結(jié)果如圖6 所示,從圖6 可以發(fā)現(xiàn),GpSM、GSM 和GVSM 的處理時(shí)間均隨著查詢圖節(jié)點(diǎn)的上升而上升。因?yàn)槟Ｊ綀D節(jié)點(diǎn)的增加將導(dǎo)致需要匹配的邊集呈指數(shù)上升。但是相比于GSM和GpSM,GVSM 有著更快的處理時(shí)間以及更平滑的曲線。這說(shuō)明GVSM 更有潛力處理規(guī)模更大的查詢。由于GVSM 有高效的剪枝優(yōu)化手段,去掉許多冗余的沒(méi)有必要的搜索分支,這使得整個(gè)匹配過(guò)程中需要載入的數(shù)據(jù)和需要的計(jì)算量大大縮小。

圖6 實(shí)驗(yàn)結(jié)果對(duì)比

在查詢圖頂點(diǎn)較少的時(shí)候,GVSM 的性能略低于GSM 和GpSM,這是因?yàn)镚VSM 有額外的預(yù)處理時(shí)間,黑名單算法的額外開銷以及流水線的在啟動(dòng)階段沒(méi)有辦法重疊PCI-E 總線拷貝導(dǎo)致的。由于查詢圖較少的時(shí)候再需要進(jìn)行的搜索并不多,優(yōu)化帶來(lái)的性能提升不足以完全掩蓋其帶來(lái)的開銷。因此GVM 更適合處理查詢圖較大的子圖匹配任務(wù),不適合處理查詢圖較小的子圖匹配任務(wù)。但隨著查詢規(guī)模的增長(zhǎng),GVSM 性能很快就超過(guò)了GSM 并逐漸拉開了差距。除此之外,如圖6(f)所示,GSM 和GpSM在邊數(shù)較多的大圖orkut 上無(wú)法處理較大的查詢圖,GSM 在查詢圖的頂點(diǎn)數(shù)量超過(guò)8 個(gè)時(shí),會(huì)導(dǎo)致需要存儲(chǔ)的中間結(jié)果數(shù)量超過(guò)GPU 的顯存而導(dǎo)致程序異常退出。但是GVSM 由于采用了前綴樹對(duì)中間結(jié)果進(jìn)行了壓縮,并采用流水線的方式,將中間結(jié)果轉(zhuǎn)存到CPU 上,并利用CPU 分擔(dān)了一部分不適合并行處理的計(jì)算工作,這使得GVSM 能處理的問(wèn)題規(guī)模大幅增加。

4.3 算法剪枝優(yōu)化性能分析

在第2 節(jié)中,介紹了3 種縮小搜索空間的剪枝優(yōu)化手段,分別是黑名單算法、蘊(yùn)含關(guān)系剪枝、以及調(diào)度順序優(yōu)化。在GPU 上實(shí)現(xiàn)這3 種優(yōu)化,并和沒(méi)有開啟這3 種優(yōu)化的原始程序在6 個(gè)真實(shí)的圖數(shù)據(jù)上進(jìn)行性能上的對(duì)比,來(lái)驗(yàn)證本文優(yōu)化工作的有效性。

圖7 展示了黑名單算法的有效性及其帶來(lái)的預(yù)處理的開銷。黑名單算法通過(guò)提前的預(yù)處理操作剔除掉一些不可能發(fā)展為最終子圖的節(jié)點(diǎn),并將它們提前標(biāo)記,這種篩除并不是基于簡(jiǎn)單的標(biāo)簽匹配而是依賴更深層次的拓?fù)潢P(guān)系。從圖7 左圖可以看出,利用該算法在多個(gè)數(shù)據(jù)集上能提升15%～50%的性能,對(duì)于標(biāo)簽數(shù)量相對(duì)較多的圖性能提升更顯著。圖7 右圖則展示了該算法在不同數(shù)據(jù)集上的預(yù)處理開銷占總運(yùn)行時(shí)間的比例,從中可知在所有的數(shù)據(jù)集上開銷都少于總運(yùn)行時(shí)間的17%。對(duì)于規(guī)模較小的數(shù)據(jù)集enron、gowalla、mico 而言,由于總運(yùn)行時(shí)間較短,因而黑名單算法開銷占比較高,而對(duì)于規(guī)模較大的數(shù)據(jù)集patents、road-central 和orkut 而言,其開銷低于7%?？梢酝茰y(cè)在更大的數(shù)據(jù)規(guī)模下,黑名單算法的開銷會(huì)更低。因此黑名單算法更適合規(guī)模較大的數(shù)據(jù)集而不適合小規(guī)模數(shù)據(jù)集?？紤]到其帶來(lái)的性能提升,該算法的額外開銷是可接受的。

圖7 黑名單算法的效果和開銷

圖8 展示了搜索中利用蘊(yùn)含關(guān)系剪枝在6 個(gè)數(shù)據(jù)集上的優(yōu)化效果。通過(guò)蘊(yùn)含關(guān)系剪枝,GVSM 維護(hù)一個(gè)額外的數(shù)據(jù)結(jié)構(gòu)來(lái)記錄節(jié)點(diǎn)間的蘊(yùn)含關(guān)系,并據(jù)此對(duì)搜索過(guò)程進(jìn)行提前剪枝。尤其是在進(jìn)行黑名單算法篩除了大量邊和頂點(diǎn)以后,將產(chǎn)生更多的蘊(yùn)含關(guān)系,這進(jìn)一步提升了剪枝效率。該優(yōu)化對(duì)中小規(guī)模的圖能提供約20%的性能提升。而對(duì)部分大圖數(shù)據(jù)性能提升不高,這是因?yàn)楣?jié)點(diǎn)數(shù)目增多,邊的連接方式變多,這導(dǎo)致蘊(yùn)含關(guān)系較少,同時(shí)需要維護(hù)的數(shù)據(jù)結(jié)構(gòu)開銷也逐漸增大,因此帶來(lái)的性能提升無(wú)法掩蓋需要維護(hù)額外數(shù)據(jù)結(jié)構(gòu)帶來(lái)的開銷。

圖8 剪枝優(yōu)化效果

圖9 展示了不同的調(diào)度順序?qū)π阅艿挠绊?在這里顯示了mico 圖數(shù)據(jù)在進(jìn)行一個(gè)4 節(jié)點(diǎn)的查詢圖的子圖匹配任務(wù)時(shí)采用不同的匹配順序而導(dǎo)致的性能差異。在全部的6 種順序中,以C-A-B-D 的順序進(jìn)行匹配性能最好,比最壞的情況B-A-D-C 性能要高出1 倍。這是因?yàn)樘崆斑M(jìn)行嚴(yán)格的匹配有助于控制子圖匹配過(guò)程中產(chǎn)生的中間結(jié)果,GVSM 采用啟發(fā)式方法對(duì)匹配順序進(jìn)行排序,在這種情況下找到順序也是C-A-B-D,與枚舉出來(lái)的最優(yōu)調(diào)度順序相符合。在6 個(gè)真實(shí)圖數(shù)據(jù)的測(cè)試中,在87%的情況下,GVSM 能夠根據(jù)啟發(fā)式算法選中最優(yōu)的調(diào)度順序。

圖9 不同調(diào)度順序?qū)π阅艿挠绊?/p>

4.4 系統(tǒng)實(shí)現(xiàn)優(yōu)化性能分析

第3 節(jié)介紹了2 種針對(duì)GPU 的子圖匹配算法在實(shí)現(xiàn)上的設(shè)計(jì),分別是利用流水線重疊計(jì)算和數(shù)據(jù)移動(dòng),以及負(fù)載均衡任務(wù)劃分。在GPU 上實(shí)現(xiàn)這2 種優(yōu)化,將沒(méi)有和開啟這2 種優(yōu)化的原始程序在6個(gè)真實(shí)的圖數(shù)據(jù)上進(jìn)行性能對(duì)比,來(lái)驗(yàn)證本文設(shè)計(jì)的有效性。

圖10 展示了流水線優(yōu)化在6 個(gè)真實(shí)圖數(shù)據(jù)中的性能。從圖中可以發(fā)現(xiàn),對(duì)數(shù)據(jù)規(guī)模較小的圖而言,使用流水線的方式與不使用流水線進(jìn)行重疊差別不大。這是因?yàn)樵诖藭r(shí)圖的數(shù)據(jù)可以直接在GPU 中存下,因此流水線優(yōu)化更適合較大規(guī)模的圖數(shù)據(jù)。GVSM 在處理小規(guī)模數(shù)據(jù)時(shí),根據(jù)設(shè)立的閾值th,所有的計(jì)算都在GPU 內(nèi)完成,因此不需要通過(guò)PCI-E 總線來(lái)交換數(shù)據(jù)。而對(duì)數(shù)據(jù)規(guī)模較大的圖而言,不進(jìn)行流水線的重疊會(huì)導(dǎo)致GPU 因等待數(shù)據(jù)而空轉(zhuǎn),所以執(zhí)行時(shí)間較長(zhǎng)。在這種情況下開啟流水線優(yōu)化可以將性能提升2～2.8 倍。而直接在GPU 上處理這個(gè)規(guī)模的數(shù)據(jù),可能會(huì)由于查詢圖節(jié)點(diǎn)過(guò)多而導(dǎo)致無(wú)法在GPU 中存下大量的中間數(shù)據(jù)而任務(wù)失敗。利用流水線將GPU 和CPU 結(jié)合起來(lái)可以高效地處理更大的數(shù)據(jù)集,性能也不低于基于純GPU 的實(shí)現(xiàn)GSM。

圖10 流水線優(yōu)化效果

圖11 展示了采用動(dòng)態(tài)塊大小方法的負(fù)載均衡優(yōu)化在Mico 圖數(shù)據(jù)上執(zhí)行的每層迭代的時(shí)間。由于每次迭代只處理一塊數(shù)據(jù),采用靜態(tài)的方法每次選取固定數(shù)量的節(jié)點(diǎn),而采用動(dòng)態(tài)方法每次選擇和CPU 上相近的負(fù)載?？梢园l(fā)現(xiàn),在算法初期,采用靜態(tài)方法的版本有大量的中間結(jié)果需要確定,因此會(huì)出現(xiàn)一些關(guān)鍵迭代層,在這些迭代中,會(huì)搜索到大量的邊集,從而決定了整個(gè)算法的運(yùn)行時(shí)間。由于負(fù)載不均衡,導(dǎo)致在關(guān)鍵迭代層計(jì)算和負(fù)載不匹配,無(wú)法和前后兩層的任務(wù)進(jìn)行有效的重疊,而采用動(dòng)態(tài)方法,對(duì)每次拷貝進(jìn)GPU 的數(shù)據(jù)進(jìn)行控制,保證前后兩次迭代的任務(wù)差距不會(huì)過(guò)大,因此重疊效果更好。另一方面,從圖中可以發(fā)現(xiàn),在算法后期,由于中間結(jié)果變少,需要搜索的邊也逐漸變少,導(dǎo)致后面的迭代需要處理的節(jié)點(diǎn)數(shù)量變少,此時(shí)數(shù)據(jù)通過(guò)PCI-E 總線傳輸?shù)难舆t逐漸成為性能的瓶頸。因此采用一次處理2 條邊而不是1 條邊的方法可以大幅減少迭代層數(shù),從而減少額外的數(shù)據(jù)傳輸開銷。

圖11 負(fù)載均衡優(yōu)化效果

5 結(jié)論

本文對(duì)單節(jié)點(diǎn)的子圖匹配算法及其優(yōu)化技術(shù)進(jìn)行了介紹,并在查詢圖拆分的算法上提出了一種基于GPU 的子圖匹配方法GVSM。在該算法上設(shè)計(jì)了黑名單算法,通過(guò)提前篩除不可能構(gòu)成最終子圖的節(jié)點(diǎn),減少了搜索需要的計(jì)算量和內(nèi)存空間,同時(shí)通過(guò)蘊(yùn)含關(guān)系進(jìn)行剪枝,并通過(guò)決策匹配順序,大幅減少了冗余的搜索分支。在系統(tǒng)優(yōu)化上,采用GPU與CPU 協(xié)同計(jì)算的方式,利用流水線優(yōu)化技術(shù),重疊了計(jì)算與數(shù)據(jù)移動(dòng),并利用GPU 的高帶寬高并發(fā)來(lái)完成待選點(diǎn)集的發(fā)掘。同時(shí)采用了動(dòng)態(tài)負(fù)載均衡算法,保證GPU 與CPU 之間的工作量的平衡,保證了流水線的穩(wěn)定。最終的實(shí)驗(yàn)結(jié)果表明,本文方法能顯著提升子圖挖掘任務(wù)的性能,相比同類型的實(shí)現(xiàn),可將處理性能提升2 倍,并能應(yīng)對(duì)更大規(guī)模的數(shù)據(jù)集。本文方法具有一定的通用性,這些優(yōu)化技術(shù)也能在其他的圖挖掘應(yīng)用上使用。在未來(lái)的工作當(dāng)中,將會(huì)把本文的優(yōu)化方法擴(kuò)展到其他類型的圖挖掘算法中,并把GVSM 擴(kuò)展到大規(guī)模GPU 集群上,以處理更大規(guī)模圖挖掘任務(wù)。