馮佳穎 張小旺 馮志勇

1(天津大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 天津 300350) 2(天津大學(xué)軟件學(xué)院 天津 300350) 3 (天津市認(rèn)知計(jì)算與應(yīng)用重點(diǎn)實(shí)驗(yàn)室 天津 300350) (fengjiaying@tju.edu.cn)

語(yǔ)義網(wǎng)(semantic Web)是一種新型的智能網(wǎng)絡(luò)，它旨在解決當(dāng)前Web上信息爆炸導(dǎo)致人們獲取目標(biāo)信息十分困難的問(wèn)題.資源描述框架(resource description framework， RDF)和SPARQL查詢語(yǔ)言是W3C(World Wide Web Consortium)組織推薦的用來(lái)描述語(yǔ)義網(wǎng)中的數(shù)據(jù)資源及其之間關(guān)系的語(yǔ)言規(guī)范和數(shù)據(jù)查詢語(yǔ)言.隨著RDF數(shù)據(jù)量的不斷增大，如何在大規(guī)模RDF數(shù)據(jù)集上進(jìn)行高效的查詢檢索是當(dāng)今面對(duì)的一個(gè)重大挑戰(zhàn).

傳統(tǒng)RDF數(shù)據(jù)集的查詢方法使用CPU作為處理器，諸如Jena[1]，RDF-3X[2]，gStore[3]等集中式查詢引擎系統(tǒng)，它們已將CPU的計(jì)算能力發(fā)揮到了極致.近年來(lái)，圖形處理單元(graph processing unit, GPU)計(jì)算性能不斷增強(qiáng).由于GPU具有浮點(diǎn)計(jì)算能力強(qiáng)、帶寬高、性價(jià)比高、能耗低等優(yōu)勢(shì)，可以極大地補(bǔ)充CPU的計(jì)算能力.利用GPU的并行處理能力實(shí)現(xiàn)算法和操作，可以大大降低CPU的負(fù)載.

在RDF數(shù)據(jù)集上的SPARQL(Simple Protocol and RDF Query Language)查詢過(guò)程就是一個(gè)子圖同構(gòu)的過(guò)程.子圖同構(gòu)問(wèn)題是圖處理問(wèn)題中一個(gè)最基本的研究?jī)?nèi)容，屬于NP完全問(wèn)題.類型同構(gòu)是一種不精確的子圖同構(gòu).通過(guò)頂點(diǎn)和邊的標(biāo)簽約束，將部分查詢轉(zhuǎn)化為類型同構(gòu)問(wèn)題.并結(jié)合GPU數(shù)據(jù)處理方面高效的的計(jì)算性能，本文提出了使用并行硬件GPU實(shí)現(xiàn)對(duì)RDF類型同構(gòu)查詢的算法，從而提高RDF數(shù)據(jù)集的查詢性能.

本文主要貢獻(xiàn)如下：結(jié)合RDF數(shù)據(jù)的特征和GPU極高的計(jì)算能力，提出一種基于GPU的匹配算法，使GPU多處理器調(diào)度更簡(jiǎn)便；在GPU的硬件加速下，對(duì)本算法進(jìn)行大量的性能實(shí)驗(yàn).實(shí)驗(yàn)結(jié)果表明:基于GPU的類型匹配算法性能對(duì)于現(xiàn)有方法有了顯著的提高.

1 背景知識(shí)

1.1 RDF和SPARQL

資源描述框架RDF是W3C組織提出的語(yǔ)義Web標(biāo)準(zhǔn)數(shù)據(jù)模型.它是用于形式化描述Web資源的元數(shù)據(jù).RDF通過(guò)語(yǔ)法符號(hào)和序列化數(shù)據(jù)格式的方法來(lái)描述概念并對(duì)信息進(jìn)行建模.RDF三元組(S，P，O)是RDF數(shù)據(jù)集的基本單元，一個(gè)RDF數(shù)據(jù)集中包含了許多RDF三元組，這些三元組表示了資源和資源之間的聯(lián)系，其中S代表主語(yǔ)(subject),是被描述的資源，P代表謂語(yǔ)(predicate),表示資源的一個(gè)屬性或關(guān)系，O代表賓語(yǔ)(object),表示屬性值.

由許多RDF三元組組成的數(shù)據(jù)集將語(yǔ)義Web的信息表示成為一個(gè)帶標(biāo)注的有向圖，稱為RDF圖.

定義1. RDF圖.一個(gè)RDF圖可以表示成為給定一個(gè)帶標(biāo)簽的有向圖G=(V，E，μ，σ).V表示頂點(diǎn)的有限集，E表示邊的有限集.μ：V→LV表示頂點(diǎn)到頂點(diǎn)標(biāo)簽類型的映射函數(shù).σ：E→LE表示邊到邊標(biāo)簽類型的映射函數(shù).LV和LE是按標(biāo)簽排列的離散符號(hào)集合，表示了聯(lián)系2個(gè)帶標(biāo)簽的頂點(diǎn)或邊的標(biāo)簽值向量.

Fig. 1 RDF graph圖1 RDF圖

如圖1展示了一個(gè)RDF圖，其中，橢圓節(jié)點(diǎn)表示資源，有向邊表示屬性，矩形節(jié)點(diǎn)表示字符值.例如，對(duì)于資源“me”，其“fullName”屬性的值是一個(gè)字符值“Enic Miller”.

SPARQL查詢語(yǔ)言是W3C組織推薦的RDF標(biāo)準(zhǔn)查詢語(yǔ)言，由一組三元組模式(triple pattern)組成.大多數(shù)SPARQL查詢都是由若干個(gè)基本圖模式(basic graph pattern, BGP)組成.SPARQL查詢即為圖模式匹配，其查詢的過(guò)程為找到與每個(gè)三元組模式匹配的三元組，再連接(join)具有共享變量的三元組模式的局部結(jié)果.結(jié)合圖1，如果我們想獲得某個(gè)具有屬性“type”，同時(shí)具有屬性“fullName”其值為“Eric Miller”的資源時(shí)，我們可以通過(guò)如下的SPARQL查詢獲得，其對(duì)應(yīng)的查詢圖如圖2所示.

SELECT ?xWHERE{

?xtype ?y.

?xfullName “Eric Miller”.}

Fig. 2 SPARQL query graph圖2 SPARQL查詢圖

本工作通過(guò)研究SPARQL語(yǔ)法細(xì)節(jié)和語(yǔ)義的形式化定義[4]并使用GPU上的類型同構(gòu)算法來(lái)提高特定基本圖模式中查詢處理的性能.

1.2 RDF中的子圖同構(gòu)與類型同構(gòu)

依據(jù)RDF圖是帶標(biāo)簽的有向圖的特征，本文的研究重點(diǎn)僅關(guān)注帶標(biāo)簽的有向圖.在已知的RDF數(shù)據(jù)中進(jìn)行SPARQL查詢的過(guò)程也就是一個(gè)模式圖(即圖2所示查詢圖)與RDF圖的子圖同構(gòu)匹配過(guò)程.

定義2. 子圖同構(gòu).給定一個(gè)RDF圖G和一個(gè)模式圖P，P包含n個(gè)頂點(diǎn)(v0，v1，v2，…，vn-1).如果G中包含n個(gè)頂點(diǎn)(u0，u1，u2，…，un-1)，與P之間存在一個(gè)單射函數(shù)f:P→G，使G的頂點(diǎn)和邊與P的頂點(diǎn)和邊一一匹配，則認(rèn)為模式圖P子圖同構(gòu)于有向圖G.

尋找子圖同構(gòu)就是將模式圖Gp嵌入RDF圖G的過(guò)程.當(dāng)子圖的所有頂點(diǎn)、邊都與模式圖的排列順序相同，并且對(duì)應(yīng)的頂點(diǎn)和邊符合各自的標(biāo)簽時(shí)，匹配過(guò)程結(jié)束.

定義3.k邊游走.假設(shè)一個(gè)圖中的非空有限序列W=(v0，e0，v1，e1，v2，…，ek-1，vk)，其中邊ei連接頂點(diǎn)vi和vi+1.這個(gè)序列的長(zhǎng)度為2k+1，被稱為k邊游走(k-edge walk).

定義4. 類型同構(gòu).給定一個(gè)RDF圖G=(VG，EG，μ，σ)，和相關(guān)聯(lián)的模式圖P=(VP，EP，μ，σ)，它們之間存在標(biāo)簽函數(shù)的映射關(guān)系，μ:V→LV和σ:E→LE分別定義了頂點(diǎn)和邊與標(biāo)簽之間的映射關(guān)系，其中LV和LE為標(biāo)簽集合，即LVP?LVG和LEP?LEG.定義P的k邊游走為

類型同構(gòu)通過(guò)k邊游走算法，計(jì)算出RDF有向圖中與模式圖的類型相匹配的部分.如圖3(b)和圖4(b)中虛線框內(nèi)G的子圖均為滿足P的類型同構(gòu).不同之處在于圖3(b)是對(duì)P的頂點(diǎn)不加約束的類型同構(gòu)，圖4(b)是對(duì)P的頂點(diǎn)增加約束的類型同構(gòu)，說(shuō)明類型同構(gòu)只是匹配滿足映射的頂點(diǎn)與邊，并不要求同構(gòu).

Fig. 3 Without constrained type-isomorphism of P vertexes 圖3 P的頂點(diǎn)不加約束的類型同構(gòu)

類型同構(gòu)是一種不精確的子圖匹配，不同于子圖同構(gòu)問(wèn)題的是類型同構(gòu)不需要找到同構(gòu)結(jié)構(gòu).如圖3(a)和圖4(a)所示的G對(duì)應(yīng)了相同的類型同構(gòu)，但對(duì)應(yīng)了不同的子圖同構(gòu)，如圖3(c)和圖4(c)所示.通過(guò)對(duì)類型同構(gòu)的k邊游走序列增加標(biāo)簽的限制，從而得到更精確的結(jié)果,如圖3所示.IRSMG[5]中提出子圖同構(gòu)問(wèn)題的解可以簡(jiǎn)化為約束的類型同構(gòu)的解.因此，本文將在RDF圖與基本圖模式之間的匹配問(wèn)題，轉(zhuǎn)化為RDF圖與相應(yīng)的關(guān)聯(lián)模式圖的附加約束的類型同構(gòu)匹配問(wèn)題.

Fig. 4 Constrained type-isomorphism of P vertexes圖4 P的頂點(diǎn)增加約束的類型同構(gòu)

Fig. 6 Concurrent threads of GPU圖6 GPU的并發(fā)線程

1.3 GPU架構(gòu)和CUDA編程模型

圖5所示為CPU與GPU架構(gòu)示意圖.與CPU相比，GPU增多了算術(shù)邏輯單元(arithmetic and logic unit, ALU)，使其更適用于規(guī)則結(jié)構(gòu)、算法單一的數(shù)據(jù)處理.基于GPU的特征，本文設(shè)計(jì)了GPU多處理器的調(diào)度模型，以提高其計(jì)算性能.

Fig. 5 Architecture of CPU and GPU圖5 CPU與GPU架構(gòu)示意圖

GPU由許多單指令多數(shù)據(jù)流(single instruction multiple data, SIMD)處理器組成，支持?jǐn)?shù)千個(gè)并發(fā)線程，如圖6所示為擁有GPU設(shè)備，Host為CPU控制端，Device為GPU設(shè)備端.Host端程序的執(zhí)行按照串行代碼(serial code)運(yùn)行，圖6左端箭頭指示了程序串行執(zhí)行的時(shí)間順序.當(dāng)內(nèi)核(kernel)程序運(yùn)行時(shí)，調(diào)用GPU進(jìn)行計(jì)算，數(shù)以千計(jì)的GPU將同時(shí)進(jìn)行計(jì)算，其組織形式如圖6所示.GPU線程具有低上下文切換和低創(chuàng)建線程時(shí)間的特點(diǎn).GPU的線程被組織為線程組(thread group).同一個(gè)線程組中的所有線程共享計(jì)算資源，例如寄存器、緩存等.線程組被分為多個(gè)調(diào)度單元方便在多處理器上動(dòng)態(tài)調(diào)度.GPU內(nèi)存具有高帶寬和高訪問(wèn)延遲等特點(diǎn)，這些優(yōu)勢(shì)使GPU更適合于大規(guī)模RDF數(shù)據(jù)的并行計(jì)算.

CUDA(compute unified device architecture)是顯卡廠商N(yùn)VIDIA推出的一款用于GPU并行編程的編程模型API(application programming interface).在CUDA中，并行工作負(fù)載以計(jì)算內(nèi)核(kernel)的形式表示并提交到設(shè)備上執(zhí)行.內(nèi)核的構(gòu)造方式提供了細(xì)粒度并行性.通常在主機(jī)的CPU上控制內(nèi)核的提交和執(zhí)行.每個(gè)線程被分配唯一標(biāo)識(shí)符，并為它們安排調(diào)度順序.線程標(biāo)識(shí)符常用于加載和存儲(chǔ)的內(nèi)存偏移量的計(jì)算.主進(jìn)程和計(jì)算單元之間的數(shù)據(jù)傳輸通過(guò)全局存儲(chǔ)器來(lái)完成，并且所有線程都有全局存儲(chǔ)器訪問(wèn)權(quán)限.但是CUDA編程模型不提供計(jì)算單元的內(nèi)存分配方法.這意味著在執(zhí)行內(nèi)核之前，主進(jìn)程需要分配好所需的輸出緩沖區(qū).

結(jié)合RDF數(shù)據(jù)和GPU計(jì)算能力的特征，本文主要涉及的是為內(nèi)核計(jì)算的編碼和執(zhí)行設(shè)計(jì)一個(gè)完善的GPU調(diào)度策略，并提出一種基于GPU的類型算法來(lái)提高部分基本圖模式的查詢效率.

2 相關(guān)工作

子圖同構(gòu)是精確的圖匹配，是圖數(shù)據(jù)研究中的一個(gè)NP-完全(NP-complete)問(wèn)題.近年來(lái)，子圖同構(gòu)問(wèn)題得到了廣泛的關(guān)注,很多研究人員嘗試了許多方法來(lái)解決通用圖中的子圖同構(gòu)問(wèn)題.1976年，Ullmann[6]第1次提出了實(shí)用的子圖同構(gòu)的搜索算法.該算法基于回溯的思想，當(dāng)部分解決方案可行時(shí)對(duì)其進(jìn)行迭代直到找出完整的解決方案；如果發(fā)現(xiàn)部分解決方案不可行，則及時(shí)終止.目前，已有一些方法對(duì)Ullmann算法進(jìn)行改進(jìn)，例如VF2[7]，QuickSI[8]，GraphQL[9]，GADDI[10]，SPath[11]等.這些算法利用不同的連接順序、剪枝規(guī)則或輔助信息對(duì)候選集進(jìn)行及時(shí)有效的剪枝篩選，從而減少連接操作的運(yùn)算量，提高算法性能.但是，由于時(shí)間復(fù)雜度較高，這些算法不適用于大規(guī)模圖數(shù)據(jù)的應(yīng)用場(chǎng)景.

為了加速在大規(guī)模圖或者多數(shù)量圖上的子圖同構(gòu)操作，STwig算法[12]將查詢圖分解成一系列結(jié)構(gòu)簡(jiǎn)單的基本單元，這些基本單元能夠非常容易地在數(shù)據(jù)圖中完成匹配，但是將產(chǎn)生的局部結(jié)果組合在一起則需要高效的連接策略.呂雪棟等人[13]設(shè)計(jì)的FFD-Inde是建立一種新穎的索引算法來(lái)加速星形圖的查詢處理.在星形查詢中，這種方法在數(shù)據(jù)量巨大的情況下顯著地提高了查詢效率，但是星形查詢只是查詢圖的一部分，無(wú)法推廣到查詢圖的一般情況.基于類型同構(gòu)的非精確子圖同構(gòu)是由精確子圖同構(gòu)問(wèn)題的泛化引入的.這種方法比較新穎并且可以擴(kuò)展到子圖同構(gòu)問(wèn)題.Berry等人[14]提出了基于類型同構(gòu)的不精確的子圖同構(gòu)問(wèn)題.類型同構(gòu)不需要像子圖同構(gòu)一樣結(jié)構(gòu)完全相同.根據(jù)RDF數(shù)據(jù)的特征，考慮利用頂點(diǎn)和邊的標(biāo)簽的類型信息，將子圖同構(gòu)問(wèn)題轉(zhuǎn)化成為帶約束的不精確的類型同構(gòu)問(wèn)題.

近些年，圖形處理器GPU在并行處理方面取得了十分顯著的成績(jī).由于計(jì)算能力強(qiáng)和便于編程，GPU已經(jīng)逐漸發(fā)展成為用于通用計(jì)算中常用的協(xié)處理器[15].基于GPU的大規(guī)模并行處理框架已經(jīng)成功應(yīng)用于處理大規(guī)模圖上的基本圖操作，包括廣度優(yōu)先搜索[16]、最短路徑[17]和最小生成樹(shù)[18].在RDF數(shù)據(jù)管理領(lǐng)域，Pan等人[19]率先在RDFS中明確提出計(jì)算量的工作負(fù)載的概念從而允許利用GPU的細(xì)粒度并行，并以此獲得性能的提高.該工作僅關(guān)注了RDFS推理的并行，沒(méi)有關(guān)注在底層數(shù)據(jù)查詢查詢處理的優(yōu)化.Choksuchat等人[20-22]提出一種基于Jena的RDF處理系統(tǒng)，存儲(chǔ)結(jié)構(gòu)使用基于Cassandra的Key-value結(jié)構(gòu)和基于HDT的二進(jìn)制三元組模式(binary triple pattern)，并實(shí)現(xiàn)了基于JCuda語(yǔ)義查詢.Chantrapornchai等人[23]提出基于Bitstructure的修剪算法處理查詢并使用概要信息以減少數(shù)據(jù)讀取量的方法，以保證可擴(kuò)展性和優(yōu)化內(nèi)存使用狀況.TripleID[24]是用于RDF查詢和推導(dǎo)處理的并行框架，它提供了一種新穎的壓縮RDF數(shù)據(jù)的文件格式，以通過(guò)GPU并行加速數(shù)據(jù)處理.Fu等人在2014年提出的MapGraph[25]是基于對(duì)PowerGraph’s Gather-Apply-Scatter(GAS)模型的修改而實(shí)現(xiàn)的.他們使用MapGraph實(shí)現(xiàn)了4種常見(jiàn)的圖形分析操作：寬度優(yōu)先搜索(BFS)，單源最短路徑(SSSP)，連接組件(CC)和PageRank(PR).2015年，Yang等人[26]提出了在普通圖上進(jìn)行并行處理子圖同構(gòu)的GPU算法，但普通圖的規(guī)模有很大的局限性[27]，例如語(yǔ)義信息含量少、節(jié)點(diǎn)數(shù)量少等[28]，所以此方法并不適用于大規(guī)模的RDF數(shù)據(jù)[29].同樣，對(duì)于處理大規(guī)模的RDF數(shù)據(jù)的類型同構(gòu)問(wèn)題也沒(méi)有高效的基于GPU的求解方式.

這些方法的共同之處在于將RDF三元組進(jìn)行編碼壓縮，并對(duì)其建立索引，以加速存儲(chǔ)查詢的過(guò)程.本文依據(jù)RDF圖數(shù)據(jù)的特性，提出一種基于類型同構(gòu)的子圖匹配算法，以使GPU并行計(jì)算應(yīng)用于在RDF圖處理，并提高子圖匹配的性能.

3 RDF類型同構(gòu)算法

3.1 字典構(gòu)建

本文選擇以串行的方式解析文件和預(yù)處理數(shù)據(jù).依據(jù)RDF數(shù)據(jù)的特性，每個(gè)三元組元素都由主語(yǔ)、謂語(yǔ)和賓語(yǔ)3部分組成，并且每個(gè)元素都是字符串(string)值，例如URI(uniform resource identifier)或字符值.程序在內(nèi)存中構(gòu)造字典將所有字符串值轉(zhuǎn)化為整數(shù)值.這樣保證了每個(gè)值都是固定長(zhǎng)度，方便后續(xù)程序?qū)?shù)據(jù)進(jìn)行處理.同時(shí)，由于緩沖區(qū)需要在數(shù)據(jù)傳輸前進(jìn)行分配，固定長(zhǎng)度可以降低GPU調(diào)用的的復(fù)雜度，提高算法的性能.

字典是在CPU中動(dòng)態(tài)構(gòu)建的.本算法使用散列映射(Hash map)建造字典.散列映射是一個(gè)關(guān)聯(lián)容器，用于關(guān)聯(lián)Key類型的對(duì)象與Data類型的對(duì)象.散列映射中可以高速查找Key值元素，本算法利用這一優(yōu)勢(shì)來(lái)查找字典中的無(wú)序三元組.字典可以簡(jiǎn)便地加載到內(nèi)存或存儲(chǔ)在磁盤(pán)文件中.在解析三元組時(shí)，主語(yǔ)和賓語(yǔ)均描述的是資源，算法對(duì)其進(jìn)行相同的處理.謂詞作為資源的連接關(guān)系需要單獨(dú)處理，并將三元組擴(kuò)展成了五元組G=(S，P，O，μ，σ).μ映射表示標(biāo)簽值與每個(gè)頂點(diǎn)(即主語(yǔ)和賓語(yǔ))的關(guān)系，σ映射表示標(biāo)簽值與每個(gè)邊(即謂語(yǔ))的關(guān)系.

3.2 基于GPU的類型同構(gòu)算法

基本圖模式查詢是SPARQL查詢的基本形式和主要子集[19].SPARQL中的其他圖模式，如聯(lián)合模式(union graph pattern)、可選模式(optional graph pattern)等，都可以通過(guò)額外的代數(shù)運(yùn)算轉(zhuǎn)換為基本圖模式.

由2.2節(jié)中描述的概念，類型同構(gòu)根據(jù)已形成的游走路徑WP來(lái)訪問(wèn)RDF中頂點(diǎn)和邊.理想情況下，查詢包含用作最小游走長(zhǎng)度的歐拉路徑.如果查詢是可以由歐拉路徑構(gòu)造的基本圖模式查詢，并且在頂點(diǎn)和邊添加標(biāo)簽約束，那么類型同構(gòu)的解就是基本圖模式查詢的解.但是在實(shí)際情況中，基本圖模式查詢都是有向無(wú)環(huán)圖.因此，查詢可能無(wú)法追蹤任何的滿足歐拉路徑的游走路徑而導(dǎo)致失敗.

1) 基于GPU的并行映射算法.第2節(jié)中討論過(guò)GPU和CUDA編程模型的特性.由于GPU在代碼的執(zhí)行期間不支持在設(shè)備上動(dòng)態(tài)分配內(nèi)存.所以需要利用設(shè)計(jì)好的數(shù)組結(jié)構(gòu)在執(zhí)行GPU程序之前為輸入數(shù)據(jù)和輸出結(jié)果分配空間.當(dāng)GPU執(zhí)行映射操作時(shí)，如果三元組滿足映射條件，則將候選三元組Etp放置在輸出緩沖器中；如果不滿足映射條件，則需要為輸出緩沖器設(shè)置額外的空間以存儲(chǔ)中間結(jié)果.因此，將所有數(shù)組結(jié)構(gòu)中的元素初始設(shè)置為0，在緩沖區(qū)根據(jù)主語(yǔ)ID排序，以減少三元組主語(yǔ)ID的重復(fù).

2) 基于GPU的連接算法.連接是將多個(gè)已匹配的局部匹配圖合并為完整匹配圖的操作.如果基本圖模式包含共享變量，那么就將映射的輸出直接傳遞到連接中.如果基本圖模式?jīng)]有共享變量，則無(wú)法進(jìn)行接下來(lái)的連接操作.那么對(duì)于類型同構(gòu)來(lái)說(shuō)，如果2個(gè)匹配的三元組有1個(gè)共享變量，那么它們可以被合并成1個(gè)通路.

為了充分利用GPU并行的優(yōu)點(diǎn)，連接過(guò)程包含3個(gè)階段：①并行映射;②按ID排序;③去重.在并行映射階段中，本算法根據(jù)共享變量在三元組中的位置設(shè)置標(biāo)志以減少去重階段的冗余操作,而GPU的單指令多數(shù)據(jù)的體系架構(gòu)特點(diǎn)也有助于加速笛卡兒乘積的平行化.

本文提出的算法請(qǐng)見(jiàn)算法1，是以初始化游走列表InitWalks開(kāi)始，以選擇RDF數(shù)據(jù)圖中第1個(gè)可以與WP模式匹配的分段.從行②開(kāi)始的循環(huán)，每次迭代都會(huì)通過(guò)匹配分段，進(jìn)一步擴(kuò)大候選集的游走長(zhǎng)度的范圍.映射操作輸出分段并以頂點(diǎn)ID作為關(guān)鍵字(Key).行③說(shuō)明了匹配的實(shí)現(xiàn)，并且本算法使用雙調(diào)排序法(bitonic sort)對(duì)映射操作的結(jié)果進(jìn)行并行排序.其作用是通過(guò)共享變量頂點(diǎn)的關(guān)鍵字對(duì)游走的候選集進(jìn)行排序.算法1的其余部分是通過(guò)對(duì)計(jì)算笛卡兒積而實(shí)現(xiàn)去重操作.算法1通過(guò)1次迭代WP的一個(gè)分段以構(gòu)建與該分段匹配的所有游走的候選集.顯然，生成結(jié)果中完整長(zhǎng)度的有向路徑的集合即是所有類型同構(gòu)游走的結(jié)果集合，也就是在RDF數(shù)據(jù)圖中完成了類型同構(gòu)的匹配過(guò)程.

算法1. 基于GPU的類型同構(gòu)算法.

輸入：RDF數(shù)據(jù)圖中所有三元組模式的集合S、將圖分段成k個(gè)有序列表TP；

輸出：在RDF中完成匹配的集合R.

① InitWalks：接收S和TP從S中讀取分段s；

② ifs能夠匹配WP中的第1個(gè)分段(S1，P1，O1)

③ 將S添加入candidate walk為1的候選集中；

④ ExtendWalks：

⑤ for每一個(gè)Key值小于k的記錄do

⑥ 從S中讀取另一個(gè)分段s.如果它能夠匹配WP中的第1個(gè)分段(St,Pt,Ot)，將s添加入游走長(zhǎng)度為t的候選集中，并從最近訪問(wèn)的候選集中讀取candidate walk；

⑦ end for

⑧ 使用雙調(diào)排序發(fā)對(duì)candidate walk進(jìn)行并行排序；

⑨ for每個(gè)定點(diǎn)do

⑩ whileCandWalkList的每個(gè)成員

4 實(shí)驗(yàn)設(shè)計(jì)和性能分析

本節(jié)在GPU架構(gòu)上實(shí)現(xiàn)了RDF圖上的類型同構(gòu)算法，并對(duì)其進(jìn)行了性能測(cè)試.經(jīng)過(guò)與CPU架構(gòu)下的類型同構(gòu)算法的效率對(duì)比，并將gStore中基于子圖同構(gòu)的方法與本文中的算法進(jìn)行比較，證明了GPU架構(gòu)解決類型同構(gòu)問(wèn)題的效率優(yōu)于CPU架構(gòu)，進(jìn)一步說(shuō)明GPU在解決RDF數(shù)據(jù)查詢問(wèn)題上具有突出的性能.

4.1 CPU與GPU的比較實(shí)驗(yàn)

1) 實(shí)驗(yàn)環(huán)境和數(shù)據(jù)集

本實(shí)驗(yàn)平臺(tái)的配置為NVIDIA GTX590 1.35 GHz GPU的顯卡和運(yùn)行英特爾?Core(i)i7-26 001.35 GHz的4核處理器.操作系統(tǒng)版本為L(zhǎng)inux Ubuntu 14.04，內(nèi)存大小為2 GB，GPU的設(shè)備內(nèi)存為1 536 MB.GPU使用PCI-E3.0總線在主存儲(chǔ)器和設(shè)備存儲(chǔ)器之間進(jìn)行數(shù)據(jù)傳輸數(shù)據(jù)，其傳輸帶寬為4 GB/s.

實(shí)驗(yàn)采用LUBM(Lehigh University Bench-mark)數(shù)據(jù)集.LUBM是一個(gè)采用大學(xué)領(lǐng)域內(nèi)本體的基準(zhǔn)，可以生成任意大小的OWL數(shù)據(jù)類型.這些數(shù)據(jù)中包含了教師、學(xué)生、課程等信息之間的關(guān)聯(lián)信息.由于本算法關(guān)注的是RDF數(shù)據(jù)的圖匹配問(wèn)題，需要對(duì)產(chǎn)生的OWL數(shù)據(jù)進(jìn)行預(yù)處理，將其轉(zhuǎn)化為系統(tǒng)處理所需的RDF三元組格式.本實(shí)驗(yàn)選取了7個(gè)不同規(guī)模的LUBM數(shù)據(jù)集來(lái)測(cè)試算法的性能.表1詳細(xì)描述了這7個(gè)數(shù)據(jù)集的數(shù)據(jù)特征和規(guī)模.為了對(duì)本文提出的算法進(jìn)行測(cè)試與分析，本實(shí)驗(yàn)選取了2種查詢方案，如表2所示.

Table 1 LUBM Datasets of Experiment表1 實(shí)驗(yàn)使用LUBM數(shù)據(jù)集

Table 2 Benchmark Test Queries表2 基準(zhǔn)測(cè)試查詢語(yǔ)句

2) CPU與GPU實(shí)驗(yàn)結(jié)果和分析

本文選取了LUBM查詢中具有代表性的查詢語(yǔ)句作為實(shí)驗(yàn)的基準(zhǔn)測(cè)試查詢，分別對(duì)7個(gè)不同規(guī)模的數(shù)據(jù)集上進(jìn)行測(cè)試，以比較相同環(huán)境下CPU和GPU的性能.表3和表4中分別記錄了每個(gè)查詢僅使用CPU計(jì)算單元計(jì)算類型同構(gòu)匹配算法的響應(yīng)時(shí)間、使用基于GPU計(jì)算單元加速類型同構(gòu)匹配算法的查詢響應(yīng)時(shí)間、以及它們之間的加速比.表3和表4中的查詢響應(yīng)時(shí)間均為多次測(cè)試后的平均響應(yīng)時(shí)間.本實(shí)驗(yàn)所測(cè)試的算法查詢響應(yīng)時(shí)間僅包括從用戶提交查詢到查詢結(jié)束之間的時(shí)間，不包括數(shù)據(jù)的載入時(shí)間和數(shù)據(jù)IO的傳輸時(shí)間.

Table 3 Query Response Time of Q1 over LUBM Datasets表3 Q1在LUBM數(shù)據(jù)集上的查詢響應(yīng)時(shí)間 ms

Table 4 Query Response Time of Q2 over LUBM Datasets表4 Q2在LUBM數(shù)據(jù)集上的查詢響應(yīng)時(shí)間 ms

圖7(a)為查詢Q1在不同規(guī)模LUBM數(shù)據(jù)集上的查詢響應(yīng)時(shí)間，圖7(b)為基于CPU的查詢響應(yīng)時(shí)間與基于GPU查詢的加速比.圖8則分別為查詢Q2在不同規(guī)模LUBM數(shù)據(jù)集上的查詢響應(yīng)時(shí)間和基于CPU的查詢響應(yīng)時(shí)間與基于GPU的加速比.

由實(shí)驗(yàn)結(jié)果分析，在數(shù)據(jù)量較少的情況下，例如LUBM1，本算法的查詢響應(yīng)時(shí)間與基于CPU的算法的時(shí)間近似.原因是在初始化時(shí)CPU調(diào)用GPU進(jìn)行數(shù)據(jù)分配調(diào)用的過(guò)程需要額外耗費(fèi)一定通信代價(jià).但是隨著數(shù)據(jù)集的不斷增大，由于GPU并行計(jì)算能力強(qiáng)，GPU的查詢響應(yīng)時(shí)間遠(yuǎn)遠(yuǎn)低于CPU的運(yùn)行時(shí)間.圖7和圖8所示，隨著數(shù)據(jù)量的不斷增大，GPU的查詢響應(yīng)時(shí)間明顯低于CPU.且CPU和GPU的加速比隨著數(shù)據(jù)量的增大而逐漸上升，最后穩(wěn)定在3倍左右.說(shuō)明在類型同構(gòu)并行算法中，GPU的查詢效率遠(yuǎn)高于CPU.

Fig. 7 Query response time and speedup between CPU and GPU of Q1圖7 Q1的查詢響應(yīng)時(shí)間及CPU與GPU運(yùn)算的加速比

Fig. 8 Query response time and speedup between CPU and GPU of Q2圖8 Q2的查詢響應(yīng)時(shí)間及CPU與GPU運(yùn)算的加速比

對(duì)比實(shí)驗(yàn)結(jié)果數(shù)據(jù)，本文提出的基于GPU的RDF類型同構(gòu)的并行算法性能顯著高于CPU處理的性能.

4.2 類型同構(gòu)與子圖同構(gòu)算法比較結(jié)果和分析

1) 實(shí)驗(yàn)環(huán)境和數(shù)據(jù)集

本實(shí)驗(yàn)平臺(tái)的配置有NVIDIA Tesla M40 GPU的顯卡和運(yùn)行英?Xeon?E5-2603 v4 1.7 GHz的6核處理器.操作系統(tǒng)版本為L(zhǎng)inux Ubuntu 14.04 Server，內(nèi)存大小為8 GB，GPU的設(shè)備內(nèi)存為24 GB.本實(shí)驗(yàn)使用數(shù)據(jù)集及查詢語(yǔ)句如表5和表6所示.

Fig. 9 Query response time and speedup between CPU and GPU of Q3圖9 Q3的查詢響應(yīng)時(shí)間及CPU與GPU運(yùn)算的加速比

DatasetsTripleNumberDatasetsSize∕MBEntityLUBM101316700160．56207443LUBM202782126341．41437572LUBM304109002505．10645971LUBM405495742676．19864239LUBM506890640848．32137216LUBM100138799701711．102179783

Table 6 Benchmark Test Queries表6 基準(zhǔn)測(cè)試查詢語(yǔ)句

為了與4.1節(jié)中實(shí)驗(yàn)區(qū)分，本文選取了LUBM查詢中的較為復(fù)雜的查詢語(yǔ)句(作為實(shí)驗(yàn)的基準(zhǔn)測(cè)試查詢，分別對(duì)8個(gè)不同規(guī)模的數(shù)據(jù)集上進(jìn)行測(cè)試.比較相同環(huán)境下基于子圖同構(gòu)的RDF數(shù)據(jù)查詢引擎與本文所提算法性能.

2) CPU與GPU實(shí)驗(yàn)結(jié)果和分析

本文選取了LUBM查詢中具有代表性的查詢語(yǔ)句作為實(shí)驗(yàn)的基準(zhǔn)測(cè)試查詢，分別對(duì)7個(gè)不同規(guī)模的數(shù)據(jù)集上進(jìn)行測(cè)試.

表7和表8中的記錄了Q3和Q4的查詢響應(yīng)時(shí)間與加速比.并在圖9和圖10中以圖表形式分別進(jìn)行展示.

Table 7 Query Response Time of Q3 over LUBM Datasets表7 Q3在LUBM數(shù)據(jù)集上的查詢響應(yīng)時(shí) ms

Table 8 Query Response Time of Q4 over LUBM Datasets表8 Q4在LUBM數(shù)據(jù)集上的查詢響應(yīng)時(shí)間 ms

Fig. 10 Query response time and speedup between CPU and GPU of Q4圖10 Q4的查詢響應(yīng)時(shí)間及CPU與GPU運(yùn)算的加速比

由圖表分析所得，本實(shí)驗(yàn)所提方案與目前性能較好的集中式查詢引擎gStore進(jìn)行比較.與gStore相比，Q3的加速比約在1.4～1.9倍，本算法查詢響應(yīng)時(shí)間僅為其響應(yīng)時(shí)間的1/2左右.Q4的加速比約在2.1～2.7倍，本算法查詢響應(yīng)時(shí)間僅為其響應(yīng)時(shí)間的1/3左右.本算法總體性能提高了1.4～2.7倍.隨著數(shù)據(jù)量的增大，本實(shí)驗(yàn)所提方案提升的性能顯著.

經(jīng)過(guò)查詢對(duì)比發(fā)現(xiàn)，本算法在包含鏈狀的查詢(如Q1和Q4)，展現(xiàn)了良好的性能.但是在只含有星狀查詢(如Q3)中，其查詢性能則略低于包含鏈狀的查詢.結(jié)合本文的理論基礎(chǔ)分析，算法在星狀查詢中展開(kāi)成k邊游走的過(guò)程中可能導(dǎo)致邊的重復(fù)遍歷，因而導(dǎo)致了算法的性能有所下降.

通過(guò)對(duì)比實(shí)驗(yàn)，本文提出的基于GPU的RDF類型同構(gòu)的并行算法性能顯著高于基于CPU的RDF子圖同構(gòu)的處理方法.

5 總 結(jié)

依據(jù)RDF圖本身的數(shù)據(jù)特征，傳統(tǒng)的子圖同構(gòu)的問(wèn)題可以用來(lái)解決SPAQRL中基本圖模式查詢問(wèn)題.本文基于IRSMG的方法和理論，提出了一種基于GPU的RDF類型同構(gòu)并行算法，以高效地完成基本圖模式查詢，減少查詢響應(yīng)時(shí)間.本文通過(guò)研究約束的類型同構(gòu)問(wèn)題，將問(wèn)題引申至RDF圖的模式匹配和查詢.通過(guò)設(shè)置游走等級(jí)的方法，對(duì)滿足查詢圖標(biāo)簽的頂點(diǎn)進(jìn)行遍歷檢查，確定后續(xù)查找范圍.最后得到每個(gè)三元組模式的局部解，使用GPU并行的進(jìn)行連接操作.因此最大程度利用了GPU的計(jì)算能力，使基本圖模式查詢性能有了顯著的提高.

盡管本工作研究的問(wèn)題僅限于基本圖模式查詢，但是其性能優(yōu)于CPU的處理方式.這為以后RDF數(shù)據(jù)處理的發(fā)展提供了新的思路.由于現(xiàn)在本文所提出的算法僅能支持部分基本圖模式，例如涉及星狀和鏈狀的查詢，對(duì)于包含環(huán)狀的查詢則體現(xiàn)了較為一般的性能.因此如何將本算法的思想推廣到基本圖模式一般情況將是本文后續(xù)工作.

[1] Mcbride B. Jena: Implementing the RDF model and syntax specification[C] //Proc of the 5th ISWC’01. New York: ACM, 2001: 23-28

[2] Neumann T, Weikum G. RDF-3X: A RISC-style engine for RDF[J]. VLDB Journal, 2008, 1(1): 647-659

[3] Zou Lei, ?zsu M, Chen Lei, et al. gStore: Answering SPARQL queries via subgraph matching[J]. VLDB Journal, 2014, 23(4): 565-590

[4] Pérez J, Arenas M, Gutierrez C. Semantics and Complexity of SPARQL[M]. Berlin: Springer, 2006: 1-45

[5] Zhang Junzhao, Zhang Bingyi, Zhang Xiaowang, et al. IRSMG: Accelerating inexact RDF subgraph matching on the GPU[C] //Proc of ISWC’16. Berlin: Springer, 2016

[6] Ullmann J. An algorithm for subgraph isomorphism[J]. Journal of the ACM, 1976, 23(1): 31-42

[7] Cordella L, Foggia P, Sansone C, et al. A (sub) graph isomorphism algorithm for matching large graphs[J]. IEEE Trans on Pattern Analysis and Machine Intelligence, 2004, 26(10): 1367-1372

[8] Shang Haichuan, Zhang Ying, Lin Xuemin, et al. Taming verification hardness: An efficient algorithm for testing subgraph isomorphism[J]. VLDB Journal, 2008, 1(1): 364-375

[9] He Huahai, Singh A. Graphs-at-a-time: Query language and access methods for graph databases[C] //Proc of ICDM’08. New York: ACM, 2008: 405-418

[10] Zhang Shijie, Li Shirong, Yang Jiong. GADDI: Distance index based subgraph matching in biological networks[C] //Proc of EDBT’09. New York: ACM, 2008: 405-418

[11] Zhao Peixiang, Han Jiawei. On graph query optimization in large networks[J]. VLDB Journal, 2010, 3(1-2): 340-351

[12] Sun Zhao, Wang Hongzhi, Wang Haixun, et al. Efficient subgraph matching on billion node graphs[J]. VLDB Journal, 2012, 5(9): 788-799

[13] Lyu Xuedong, Wang Xin, Li Yuanfang, et al. FFD-Index: An efficient indexing scheme for star subgraph matching on large RDF graphs[G] //LNCS 9052: Proc of Database Systems for Advanced Applications. Berlin: Springer, 2015: 240-245

[14] Berry J, Hendrickson B, Kahan S, et al. Software and algorithms for graph queries on multithreaded architectures[C] //Proc of IPDPS’07. Los Alamitos, CA: IEEE Computer Society, 2007: 1-14

[15] Xu Xinhai, Lin Yufei, Yi Wei. A survey of techniques of CPU-GPGPU heterogeneous architecture[J]. Computer Engineering & Science, 2009, 31(S1): 24-26 (in Chiness)

(徐新海, 林宇斐, 易偉. CPU-GPGPU異構(gòu)體系結(jié)構(gòu)相關(guān)技術(shù)綜述[J]. 計(jì)算機(jī)工程與科學(xué), 2009, 31(S1): 24-26)

[16] Merrill D, Garland M, Grimshaw A. Scalable GPU graph traversal[J]. ACM Sigplan Notices, 2012, 47(8): 117-128

[17] Katz G, Kider J. All-pairs shortest-paths for large graphs on the GPU[C] //Proc of GH’08. New York: ACM, 2008: 47-55

[18] Vineet V, Harish P, Patidar S, et al. Fast minimum spanning tree for large graphs on the GPU[C] //Proc of HPG’09. New York: ACM, 2009: 167-171

[19] Heino N, Pan J. RDFS Reasoning on massively parallel hardware[G] //LNCS 7649: Proc of ISWC’12. Berlin: Springer, 2012: 133-148

[20] Choksuchat C, Chantrapornchai C. Large RDF representa-tion framework for GPUs case study key-value storage and binary triple pattern[C] //Proc of ICSEC’2013. Piscataway, NJ: IEEE, 2013: 13-18

[21] Choksuchat C, Chantrapornchai C. Experimental framework for searching large RDF on GPUs based on key-value storage[C] //Proc of JCSSE’13. Piscataway, NJ: IEEE, 2013: 171-176

[22] Choksuchat C, Chantrapornchai C. On the HDT with the tree representation for large RDFs on GPU[C] //Proc of the 19th ICPADS’13. Los Alamitos, CA: IEEE Computer Society, 2013: 651-656

[23] Chantrapornchai C, Choksuchat C, Haidl M, et al. Entailment processing for large RDF data sets using GPU[C] //Proc of SoMeT’16. Clifton, NJ: IOS, 2016: 333-345

[24] Haidl M, Gorlatch S. TripleID: A low-overhead represen-tation and querying using GPU for large RDFs[C] //Proc of BDAS’16. Berlin: Springer, 2016: 400-415

[25] Fu Zhisong, Personick M, Thompson B. MapGraph: A high level API for fast development of high performance graph analytics on GPUs[C] //Proc of GRADES’14. New York: ACM, 2014: 1-6

[26] Yang Bo, Lu Kai, Gao Yinghui, et al. GPU acceleration of subgraph isomorphism search in large scale graph[J]. Journal of Central South University, 2015, 22(6): 2238-2249

[27] Fu Lizhen, Meng Xiaofeng. Reachability indexing for large-scale graphs: Studies and forcasts[J]. Journal of Computer Research and Development,2015, 52(1): 116-129 (in Chiness)

(富麗貞, 孟小峰. 大規(guī)模圖數(shù)據(jù)可達(dá)性索引技術(shù)：現(xiàn)狀與展望[J]. 計(jì)算機(jī)研究與發(fā)展, 2015, 52(1): 116-129)

[28] Zou Lei, Peng Peng. A survey of distributed RDF data management[J]. Journal of Computer Research and Development, 2017, 54(6): 1213-1224 (in Chiness)

(鄒磊, 彭鵬. 分布式RDF數(shù)據(jù)管理綜述[J]. 計(jì)算機(jī)研究與發(fā)展, 2017, 54(6): 1213-1224)

[29] Li Jianhui, Shen Zhihong, Meng Xiaofeng. Scientific big data management: Concepts, technologies and system[J]. Journal of Computer Research and Development, 2017, 54(2): 235-247 (in Chiness)

(黎建輝, 沈志宏, 孟小峰. 科學(xué)大數(shù)據(jù)管理: 概念、技術(shù)與系統(tǒng)[J]. 計(jì)算機(jī)研究與發(fā)展, 2017, 54(2): 235-247)