基于CPU-GPU異構(gòu)體系結(jié)構(gòu)的并行字符串相似性連接方法

徐坤浩 聶鐵錚 申德榮 寇 月 于 戈

(東北大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院 沈陽(yáng) 110169)

(xukunhao725@163.com)

隨著傳統(tǒng)互聯(lián)網(wǎng)的發(fā)展和移動(dòng)互聯(lián)網(wǎng)的出現(xiàn)，數(shù)據(jù)量迅速變大，“大數(shù)據(jù)”的概念逐漸被人們熟知.但大量的數(shù)據(jù)也對(duì)傳統(tǒng)的數(shù)據(jù)存儲(chǔ)和處理帶來(lái)了新的挑戰(zhàn).為了更快地處理大數(shù)據(jù)，人們采用例如MapReduce和HDFS(Hadoop distributed file system)等分布式的策略來(lái)計(jì)算和存儲(chǔ)大數(shù)據(jù).傳統(tǒng)的CPU性能提升方法已經(jīng)達(dá)到瓶頸，提高主頻和核心數(shù)量等方法對(duì)CPU性能的提升變得越來(lái)越困難，僅由CPU負(fù)責(zé)計(jì)算的傳統(tǒng)相似性連接算法的處理速度已經(jīng)漸漸滿足不了用戶的需求.近年來(lái)，GPU的處理性能和并行處理單元集成度提升迅速，更多的算術(shù)邏輯單元使得GPU的綜合計(jì)算性能遠(yuǎn)超CPU.GPU能夠極大地解決CPU處理能力不足的問(wèn)題，因此基于CPU-GPU異構(gòu)體系結(jié)構(gòu)的處理模式正成為未來(lái)的發(fā)展趨勢(shì).

相似性連接處理技術(shù)是對(duì)來(lái)自不同數(shù)據(jù)集的2個(gè)對(duì)象計(jì)算相似度，并以相似度是否達(dá)到指定閾值作為對(duì)象間的連接條件.目前，相似性連接技術(shù)已經(jīng)被廣泛地應(yīng)用在搜索引擎、數(shù)據(jù)集成以及知識(shí)庫(kù)構(gòu)建等領(lǐng)域.根據(jù)計(jì)算對(duì)象間相似度的算法不同，常見(jiàn)的相似性連接可以分為字符串相似性連接、集合相似性連接、向量相似性連接以及圖相似性連接，其中以字符串相似性連接應(yīng)用最為廣泛.字符串的相似性可以通過(guò)Jaccard相似度等多種相似性度量進(jìn)行計(jì)算.傳統(tǒng)的相似性連接處理技術(shù)一般使用過(guò)濾-驗(yàn)證框架，包含過(guò)濾和驗(yàn)證2個(gè)部分：在過(guò)濾階段設(shè)計(jì)高效的過(guò)濾算法將大量不可能符合相似度要求的數(shù)據(jù)記錄對(duì)過(guò)濾剔除，大幅減少候選對(duì)的數(shù)量；在驗(yàn)證階段，計(jì)算每個(gè)候選對(duì)的相似度，將滿足相似度條件的候選對(duì)添加至最后結(jié)果.

目前，對(duì)相似性連接算法的優(yōu)化主要集中在過(guò)濾階段的優(yōu)化，通過(guò)對(duì)過(guò)濾算法的優(yōu)化來(lái)提升過(guò)濾效果.現(xiàn)有研究工作提出了很多過(guò)濾算法，包括基于倒排索引的計(jì)數(shù)過(guò)濾算法[1]、基于位置的過(guò)濾算法[2]、基于長(zhǎng)度的過(guò)濾算法[3]以及基于前綴的過(guò)濾算法[4].這些算法在一定程度上都提升了過(guò)濾階段的效率，但大部分都是基于串行處理的設(shè)計(jì)思想，處理效率受到了極大的限制.因此，本文主要研究通過(guò)CPU-GPU異構(gòu)體系結(jié)構(gòu)并行處理相似性連接算法，提高相似性連接算法的處理效率.由于CPU與GPU在計(jì)算模型上的巨大區(qū)別，傳統(tǒng)的相似性連接算法無(wú)法直接在GPU上直接運(yùn)行.GPU強(qiáng)大的計(jì)算能力來(lái)源于大量的核心帶來(lái)的高并行度，通過(guò)大量核心并行的執(zhí)行計(jì)算提高任務(wù)處理效率，但GPU存在不適合執(zhí)行復(fù)雜邏輯控制的缺點(diǎn).因此基于GPU實(shí)現(xiàn)相似性連接的加速處理，就必須根據(jù)GPU的處理架構(gòu)特點(diǎn)設(shè)計(jì)相應(yīng)的處理策略和優(yōu)化方法.

本文主要研究基于CPU-GPU異構(gòu)體系結(jié)構(gòu)的并行相似性連接處理方法，通過(guò)將任務(wù)進(jìn)行分解并運(yùn)行在不同處理器架構(gòu)上，提升任務(wù)并行性，從而提高基于過(guò)濾-驗(yàn)證模型的相似性連接處理效率.本文的主要貢獻(xiàn)有4個(gè)方面：

1) 提出了基于CPU-GPU異構(gòu)體系結(jié)構(gòu)的并行相似性連接處理策略，充分利用GPU的并行計(jì)算能力和CPU的邏輯計(jì)算能力.

2) 提出了基于GPU的倒排索引結(jié)構(gòu)和構(gòu)建方法，并采用SoA(struct of arrays)結(jié)構(gòu)提升并行計(jì)算時(shí)倒排索引的構(gòu)建速度.

3) 提出了面向長(zhǎng)度過(guò)濾和前綴過(guò)濾算法的GPU并行過(guò)濾方法，提高記錄對(duì)的過(guò)濾效率.

4) 通過(guò)對(duì)比實(shí)驗(yàn)證明了所提出的并行算法可以有效地提升相似性連接中并行處理的執(zhí)行效率，并分析了不同條件下算法的性能表現(xiàn).

1 相關(guān)工作

目前，關(guān)于相似性連接技術(shù)的研究工作可以分為基于串行技術(shù)的方法和基于并行技術(shù)的方法.

基于串行的相似性連接研究主要集中在對(duì)匹配記錄對(duì)過(guò)濾算法的優(yōu)化以及不同類型數(shù)據(jù)的相似性連接算法2個(gè)方面.Rong等人[4]提出了基于全局指令的多前綴過(guò)濾算法.這篇文章使用了流水線全局指令模式，并且提出適合這種模式的多前綴過(guò)濾算法，有效地減少在驗(yàn)證階段需要計(jì)算的候選對(duì)數(shù)量.Cui等人[5]認(rèn)為隨著數(shù)據(jù)實(shí)時(shí)性要求的提升，動(dòng)態(tài)數(shù)據(jù)流會(huì)成為重要的數(shù)據(jù)來(lái)源，所以對(duì)數(shù)據(jù)流的數(shù)據(jù)相似性連接展開(kāi)了研究，提出基于編輯距離和滑動(dòng)窗口語(yǔ)義驗(yàn)證的相似性連接算法，介紹了數(shù)據(jù)流中滑動(dòng)窗口模型的構(gòu)建以及特征提取等關(guān)鍵步驟.Wang等人[6]研究了局部相似性連接的問(wèn)題，該文首先判斷2個(gè)字符串是否具有一定的局部相似度，然后設(shè)計(jì)算法定位二者的最長(zhǎng)相似子串，基于局部相似子串的長(zhǎng)度進(jìn)行字符串的相似性連接.Zhao等人[7]對(duì)數(shù)組形式的數(shù)據(jù)的相似性連接進(jìn)行研究，文章首先將數(shù)組數(shù)據(jù)抽象成高維向量，然后定義了向量的相似性連接定義與度量標(biāo)準(zhǔn)；在連接的基礎(chǔ)上進(jìn)行了查詢優(yōu)化，提供高效的查詢操作，并且將這種相似性連接與查詢的算法推廣至圖結(jié)構(gòu)的數(shù)據(jù).Patil等人[8]研究不確定字符串的相似性連接和查詢過(guò)程.以上的相關(guān)研究工作都局限在串行的相似性連接算法上，并沒(méi)有突破串行算法的性能瓶頸，而且針對(duì)特定結(jié)構(gòu)數(shù)據(jù)的相似性連接算法并不具備良好的普適性.

在并行的相似性連接算法方面，近些年的研究主要集中在借助已有的并行計(jì)算框架以及利用GPU實(shí)現(xiàn)并行化2個(gè)方面.Chen等人[9]利用MapReduce實(shí)現(xiàn)相似性連接，文章提出基于聚類抽樣和KD樹(shù)(k-dimensional tree)的數(shù)據(jù)劃分方式，保證數(shù)據(jù)被平均地分配到節(jié)點(diǎn)上，然后提出基于順序映射和距離的過(guò)濾方式進(jìn)行數(shù)據(jù)過(guò)濾，提升算法執(zhí)行效率的同時(shí)也使算法具有良好的伸縮性.鄧詩(shī)卓等人[10]利用Spark框架和雙前綴過(guò)濾方法實(shí)現(xiàn)了相似性連接算法.Matsumoto等人[11]提出了并行排序算法，同時(shí)利用并行最大最小堆結(jié)構(gòu)在CPU-GPU異構(gòu)體系上實(shí)現(xiàn)了數(shù)據(jù)相似性連接.Johnson等人[12]利用GPU實(shí)現(xiàn)了k-NN算法以及相似性搜索算法，利用GPU進(jìn)行并行的局部數(shù)據(jù)排序，壓縮數(shù)據(jù)集來(lái)減少數(shù)據(jù)傳輸與通信的代價(jià).Feng等人[13]研究文檔相似性連接，針對(duì)文檔數(shù)據(jù)的特殊性和GPU計(jì)算的特點(diǎn)提出了2階段相似性連接算法，根據(jù)TF-IDF算法進(jìn)行排序后對(duì)低頻詞進(jìn)行過(guò)濾，提出適合并行計(jì)算的倒排索引讀取和相似度計(jì)算方法.

除此以外，GPU也被廣泛地應(yīng)用到其他方面.Alam等人[14]設(shè)計(jì)適合GPU并行計(jì)算的cuPPA算法解決無(wú)標(biāo)度網(wǎng)絡(luò)中遇到的問(wèn)題，算法基于優(yōu)先附著模型，并且可以通過(guò)Hash的方式支持多GPU同時(shí)計(jì)算.Doraiswamy等人[15]使用GPU構(gòu)建索引來(lái)解決時(shí)空數(shù)據(jù)的查詢問(wèn)題，索引覆蓋多個(gè)維度，采用塊存儲(chǔ)的形式加快數(shù)據(jù)查詢速度，并且同時(shí)支持基于異構(gòu)體系結(jié)構(gòu)的查詢請(qǐng)求.

與已有的工作相比，本文的工作將研究基于并行計(jì)算方式的相似性連接處理策略，突破傳統(tǒng)串行算法的性能瓶頸，設(shè)計(jì)面向GPU的數(shù)據(jù)匹配索引結(jié)構(gòu)，以及利用GPU處理架構(gòu)并行計(jì)算模型，提升單處理機(jī)上的并行處理能力，降低分布式環(huán)境的數(shù)據(jù)劃分和網(wǎng)絡(luò)通信代價(jià).

2 基于CPU-GPU的相似性連接處理框架

2.1 相似性連接方法

本文的研究?jī)?nèi)容主要面向以文本為屬性內(nèi)容的記錄集合間的相似性連接方法，其中記錄集合間的相似性度量主要采用基于字符串的相似性匹配方法.字符串相似性匹配方法可以分為2類：基于特征的相似性匹配和基于字符的相似性匹配，其中常用的相似性度量算法有Jaccard相似度、余弦相似度、遺傳相似度和編輯相似度等.本文將針對(duì)基于特征的相似性匹配方法相似性連接進(jìn)行優(yōu)化處理，為此首先給出相似性連接相關(guān)定義：

定義1.相似性連接.給定2個(gè)記錄集合R和S，r和s分別是來(lái)自R和S的記錄，Sim表示相似度計(jì)算函數(shù)；對(duì)于給定相似性閾值τ，相似性連接是指找出所有相似度大于τ的記錄對(duì)r,s，即集合：

{r,s∈R×S|Sim(r,s)≥τ}.

目前相似性連接最常用的處理框架是過(guò)濾-驗(yàn)證框架.過(guò)濾-驗(yàn)證框架分為記錄對(duì)過(guò)濾和相似度驗(yàn)證2個(gè)步驟.過(guò)濾步驟主要的目的是過(guò)濾不相似的候選記錄對(duì)，減少候選記錄匹配集的大小.過(guò)濾算法的設(shè)計(jì)需要同時(shí)平衡過(guò)濾效果與過(guò)濾成本2個(gè)因素：想追求更好的過(guò)濾效果勢(shì)必會(huì)增加過(guò)濾成本；而簡(jiǎn)單的過(guò)濾算法又會(huì)導(dǎo)致過(guò)濾效果不明顯，難以降低驗(yàn)證階段的處理代價(jià).

在過(guò)濾策略中可以使用索引結(jié)構(gòu)提高過(guò)濾效率：例如對(duì)每個(gè)特征建立倒排索引，利用倒排索引的包含項(xiàng)生成候選對(duì).目前，相似性連接在過(guò)濾階段最常用的算法是前綴過(guò)濾算法.前綴過(guò)濾算法的基本思想是利用前綴子串來(lái)衡量整體的相似性[16].其中，首先對(duì)所有的特征進(jìn)行排序，然后對(duì)每一個(gè)字符串進(jìn)行比較，如果其前綴部分的重疊程度小于設(shè)定的閾值，就將候選對(duì)刪除.前綴過(guò)濾常常與長(zhǎng)度過(guò)濾和位置過(guò)濾等方法共同使用來(lái)達(dá)到更好的過(guò)濾效果.

驗(yàn)證階段主要任務(wù)是精確計(jì)算所有候選對(duì)的相似度，如果記錄間的相似度大于給定閾值，那么該記錄對(duì)即可以作為連接結(jié)果輸出.

相似性連接算法不僅可以處理2個(gè)數(shù)據(jù)集合間的記錄相似性匹配，也可以用于在同一個(gè)數(shù)據(jù)集合執(zhí)行自連接操作，從而發(fā)現(xiàn)集合中冗余記錄.

2.2 基于GPU的數(shù)據(jù)處理原理

隨著GPU處理器計(jì)算能力的提高，通用型GPU(general-purpose GPU， GPGPU)被廣泛地應(yīng)用于高性能計(jì)算等領(lǐng)域.相關(guān)研究表明GPU在處理連接、排序、索引構(gòu)建等過(guò)程時(shí)具有更優(yōu)異的表現(xiàn).常用的通用GPU計(jì)算框架包括NVIDIA的CUDA(compute unified device architecture)和非盈利性組織Khronos Group掌管的OpenCL.目前，多數(shù)的研究使用的是CUDA框架處理并行計(jì)算問(wèn)題，該框架使GPU利用SIMT(single instruction multiple threads)體系結(jié)構(gòu)解決復(fù)雜的計(jì)算問(wèn)題.本文將基于CUDA框架在索引處理上的性能特性設(shè)計(jì)相似性連接的算法處理流程.

GPU的優(yōu)勢(shì)在于眾多內(nèi)核帶來(lái)的高并發(fā)度，然而并不是所有的計(jì)算任務(wù)都適合使用GPU計(jì)算.CPU適合處理控制密集型任務(wù)，GPU適合處理包含數(shù)據(jù)并行的計(jì)算密集型任務(wù).因此GPU的并行處理并不是處理完整的計(jì)算流程，而是按照計(jì)算任務(wù)的特性進(jìn)行劃分，GPU處理由計(jì)算任務(wù)主導(dǎo)的且?guī)в泻?jiǎn)單控制流的計(jì)算任務(wù).2種處理器在功能上互補(bǔ)，使CPU-GPU異構(gòu)并行計(jì)算體系結(jié)構(gòu)獲得最佳性能.

2.3 基于異構(gòu)體系的相似性連接處理框架

傳統(tǒng)串行相似性連接方法可以分為數(shù)據(jù)讀取、倒排索引構(gòu)建、原始數(shù)據(jù)過(guò)濾和相似度驗(yàn)證4個(gè)主要步驟，其處理過(guò)程都是基于CPU處理計(jì)算，數(shù)據(jù)在主存中存儲(chǔ).

基于CPU-GPU異構(gòu)體系結(jié)構(gòu)的處理方法將傳統(tǒng)方法的4個(gè)步驟分開(kāi)處理，其中適合并行計(jì)算的部分由GPU負(fù)責(zé)，數(shù)據(jù)存儲(chǔ)在GPU顯存中；涉及復(fù)雜邏輯控制的部分由CPU負(fù)責(zé)，數(shù)據(jù)存儲(chǔ)在主存中；處理器之間通過(guò)PCIe(peripheral component interconnect express)通道進(jìn)行數(shù)據(jù)傳輸.這種方式能充分利用CPU-GPU異構(gòu)體系結(jié)構(gòu)中2種處理器不同的數(shù)據(jù)處理特點(diǎn)，提高整體的執(zhí)行效率.本文對(duì)傳統(tǒng)相似性連接方法的主要步驟進(jìn)行分析和重新設(shè)計(jì)，如圖1所示.①使用CPU讀取數(shù)據(jù)，利用GPU并行構(gòu)建倒排索引；②使用CPU依據(jù)倒排索引生成候選對(duì)；③使用GPU對(duì)候選對(duì)進(jìn)行雙重長(zhǎng)度過(guò)濾；④使用CPU驗(yàn)證相似度得到最終結(jié)果集R. 2種處理器協(xié)同工作完成相似性連接整體任務(wù).

Fig. 1 Similarity join algorithms based on theCPU-GPU heterogeneous architecture圖1 基于CPU-GPU異構(gòu)體系的相似性連接算法

3 基于GPU的倒排索引構(gòu)建方法

在相似性連接算法中，利用倒排索引可以快速找到可能相似的候選項(xiàng)，從而達(dá)到過(guò)濾不相似項(xiàng)的效果.倒排索引是大部分過(guò)濾算法的基礎(chǔ)，為此本文首先提出使用GPU構(gòu)建倒排索引的方法.

相比于內(nèi)存空間，GPU的存儲(chǔ)空間是很有限的，GPU全局內(nèi)存(global memory， GM)一般只有幾GB的空間，而訪問(wèn)速度更快的共享內(nèi)存只有KB級(jí)別的空間，所以使用GPU生成倒排索引時(shí)必須考慮減小倒排索引的體積.同時(shí)，GPU與主機(jī)內(nèi)存之間的消息通信必須通過(guò)PCIe通道，目前CPU從內(nèi)存讀寫數(shù)據(jù)的速度是PCIe通道的4～8倍，所以需要盡可能對(duì)原始數(shù)據(jù)以及倒排索引進(jìn)行壓縮，利用GPU存儲(chǔ)空間來(lái)存儲(chǔ)數(shù)據(jù).出于以上的考慮本文采用了全局內(nèi)存映射表來(lái)減小數(shù)據(jù)和索引的體積.

全局內(nèi)存映射表的功能類似于數(shù)據(jù)字典，可以將體積較大的字符串類型的特征項(xiàng)轉(zhuǎn)換為數(shù)值類型的唯一序號(hào).通過(guò)這種結(jié)構(gòu)，倒排索引中每個(gè)鍵值對(duì)所占用的空間大幅減少，原始數(shù)據(jù)的體積也大幅減少，這樣就可以使用GPU全局內(nèi)存存儲(chǔ)更多的原始數(shù)據(jù)以及索引信息.

基于這個(gè)問(wèn)題，本文首先對(duì)傳統(tǒng)的倒排索引結(jié)構(gòu)進(jìn)行改進(jìn)，采用基于SoA結(jié)構(gòu)的倒排索引，充分利用GPU多線程并發(fā)訪問(wèn)的特性，提升索引訪問(wèn)和構(gòu)建速度.SoA也被稱為并行結(jié)構(gòu)體或者并行數(shù)組，這種數(shù)據(jù)結(jié)構(gòu)的出現(xiàn)主要是為了解決在并行訪問(wèn)的場(chǎng)景下傳統(tǒng)結(jié)構(gòu)體數(shù)組訪問(wèn)和寫入效率低的問(wèn)題.圖2所示為SoA與AoS這2種數(shù)據(jù)結(jié)構(gòu)的定義以及在內(nèi)存中布局方式的對(duì)比，SoA為結(jié)構(gòu)體中定義的每個(gè)屬性創(chuàng)建一個(gè)數(shù)組，相同的屬性值在內(nèi)存中連續(xù)存放，不同的數(shù)據(jù)之間沒(méi)有任何耦合.所以這種數(shù)據(jù)結(jié)構(gòu)非常適合多線程同時(shí)并發(fā)訪問(wèn)，并且全部由基本數(shù)據(jù)類型組成的數(shù)組在訪問(wèn)時(shí)也不需要進(jìn)行數(shù)據(jù)補(bǔ)全.

Fig. 2 Comparison of SoA and AoS structure圖2 SoA與AoS結(jié)構(gòu)對(duì)比

GPU最大的優(yōu)勢(shì)在于多線程并行計(jì)算的能力.為了充分地提高并行度，每個(gè)線程塊block將負(fù)責(zé)一部分原始數(shù)據(jù)的解析工作，block中的每個(gè)線程每次會(huì)讀取一個(gè)單詞，根據(jù)全局映射表解析數(shù)據(jù)生成tid,sid，然后查找全局倒排索引，使用函數(shù)atomicAdd將sid和tid分別寫入對(duì)應(yīng)的位置，等到所有線程完成各自的任務(wù)后，SoA型倒排索引的構(gòu)建工作也就完成了.如果想要進(jìn)一步提高索引的讀寫速度，可將得到的全局倒排索引按照共享內(nèi)存的大小順序劃分，劃分后的部分索引傳入共享內(nèi)存中等待后續(xù)使用.將構(gòu)建完成的索引回傳至主存，然后對(duì)tid相同的匹配對(duì)進(jìn)行合并就得到了通用性更好的傳統(tǒng)倒排索引.算法1表述了基于GPU的倒排索引的構(gòu)建過(guò)程.

算法1.基于GPU的倒排索引構(gòu)建算法.

輸入：字符串集S;

輸出：倒排索引ISoA.

① 初始化：

② 基于字符串集S構(gòu)建全局映射表Map；

③ 為字符串集S中每個(gè)token創(chuàng)建特征編號(hào)tid，為每個(gè)字符串創(chuàng)建編號(hào)sid;

④ 記錄數(shù)據(jù)集中token的數(shù)量N;

⑤ 將S和Map加載到全局內(nèi)存；

⑥ 初始化SoA結(jié)構(gòu)的倒排索引ISoA；

⑦ for eachS中的字符串si并行執(zhí)行操作：

⑧ 創(chuàng)建字符串si的token集合Tsi；

⑨ for eachTsi中的token并行執(zhí)行操作：

⑩ 基于Map解析數(shù)據(jù)生成tid,sid；

算法1中行①～④是在CPU和主存上做的準(zhǔn)備工作，主要包括數(shù)據(jù)讀取、構(gòu)建全局內(nèi)存映射表Map等.行⑤～⑥將數(shù)據(jù)和映射表通過(guò)PCIe通道傳輸至GPU全局內(nèi)存并且初始化大小SoA型倒排索引結(jié)構(gòu).行⑦～為具體的并行倒排索引構(gòu)建過(guò)程，圖3對(duì)這一過(guò)程進(jìn)行了簡(jiǎn)要的描述.對(duì)于每條數(shù)據(jù)使用一定數(shù)量的線程并行解析，根據(jù)全局內(nèi)存映射表Map解析tid,sid，使用atomicAdd函數(shù)并行補(bǔ)全SoA倒排索引.行將處理得到的SoA倒排索引回傳至主存，因?yàn)椴⑿杏?jì)算得到的倒排索引是SoA類型，行～在CPU上對(duì)倒排索引進(jìn)行合并，得到傳統(tǒng)的AoS類型的倒排索引.合并后的倒排索引具有更高的普適性和更廣泛的應(yīng)用場(chǎng)景，可應(yīng)用到搜索引擎、數(shù)據(jù)清洗等方面.

Fig. 3 Construction process of inverted index圖3 倒排索引構(gòu)建過(guò)程

4 基于CPU-GPU的并行相似性連接方法

長(zhǎng)度過(guò)濾的基本思想是：如果字符串s與r相似，則其長(zhǎng)度一定不會(huì)相差太多.以Jaccard相似度為例，給出長(zhǎng)度過(guò)濾算法中字符串長(zhǎng)度與相似度閾值的關(guān)系.長(zhǎng)度過(guò)濾因計(jì)算簡(jiǎn)單，且條件僅僅需要統(tǒng)計(jì)每條數(shù)據(jù)項(xiàng)的長(zhǎng)度等特點(diǎn)被廣泛地應(yīng)用到過(guò)濾-驗(yàn)證框架中，同時(shí)這種邏輯簡(jiǎn)單的計(jì)算密集型過(guò)濾算法特別適合GPU并行計(jì)算.因此本文考慮使用基于GPU的長(zhǎng)度過(guò)濾算法對(duì)原始數(shù)據(jù)集進(jìn)行過(guò)濾：

(1)

其中，τ為已定義的相似度閥值.如果數(shù)據(jù)集中的字符串是由許多特征組成的，那么除了使用字符串的長(zhǎng)度進(jìn)行長(zhǎng)度過(guò)濾之外，還可以使用每個(gè)字符串的特征數(shù)量進(jìn)行過(guò)濾.因?yàn)閿?shù)據(jù)集中普遍存在長(zhǎng)度相近，但是所含單詞數(shù)量相差很多的字符串，僅使用數(shù)據(jù)長(zhǎng)度無(wú)法過(guò)濾掉這些不相似的字符串.而使用長(zhǎng)度和特征數(shù)雙重過(guò)濾的方式可以過(guò)濾掉這一類型的字符串，進(jìn)一步提升過(guò)濾效果減少候選項(xiàng)的數(shù)量.長(zhǎng)度過(guò)濾算法的主要過(guò)程是統(tǒng)計(jì)每個(gè)字符串的長(zhǎng)度，以及判斷字符串的長(zhǎng)度是否在相似度閾值規(guī)定的區(qū)間內(nèi).這2個(gè)步驟是2個(gè)完全獨(dú)立的工作，并且這2部分工作都是簡(jiǎn)單的讀寫任務(wù)，不涉及復(fù)雜的邏輯處理，因此十分適合使用GPU對(duì)這部分工作進(jìn)行并行化處理.

長(zhǎng)度過(guò)濾算法也有缺點(diǎn)，例如對(duì)相似度閾值敏感、對(duì)方差較小的短文本數(shù)據(jù)集過(guò)濾效果很差等.為了彌補(bǔ)長(zhǎng)度過(guò)濾算法的缺點(diǎn)，本文使用前綴過(guò)濾與長(zhǎng)度過(guò)濾相結(jié)合的方式進(jìn)行數(shù)據(jù)過(guò)濾.

前綴過(guò)濾算法是目前比較領(lǐng)先的過(guò)濾算法之一，并且常常與長(zhǎng)度過(guò)濾等方法一起使用來(lái)獲得更好的過(guò)濾效果.前綴過(guò)濾的基本思想是：對(duì)于已按照某種規(guī)則排序后的數(shù)據(jù)項(xiàng)，如果2個(gè)數(shù)據(jù)項(xiàng)的前p項(xiàng)特征中有相同項(xiàng)，那么這2個(gè)數(shù)據(jù)項(xiàng)就可能相似.前綴長(zhǎng)度p與字符串長(zhǎng)度|s|以及相似度閾值τ的關(guān)系：

(2)

使用前綴過(guò)濾算法對(duì)經(jīng)過(guò)長(zhǎng)度過(guò)濾之后生成的中間結(jié)果集進(jìn)行2次過(guò)濾：對(duì)于中間結(jié)果集中的每個(gè)候選項(xiàng)，根據(jù)相似度計(jì)算公式計(jì)算出前綴p，然后判斷候選項(xiàng)是否出現(xiàn)在前綴項(xiàng)對(duì)應(yīng)的倒排索引中.經(jīng)過(guò)前綴過(guò)濾之后的中間結(jié)果集被進(jìn)一步減小，從而也少了后續(xù)相似度驗(yàn)證階段的任務(wù)量.

基于以上考慮，本文首先使用算法1，利用GPU構(gòu)建倒排索引；然后使用GPU對(duì)原始數(shù)據(jù)集進(jìn)行雙重長(zhǎng)度過(guò)濾生成中間結(jié)果集；隨后根據(jù)倒排索引，使用前綴過(guò)濾算法對(duì)中間結(jié)果集進(jìn)行2次過(guò)濾，剔除不滿足前綴過(guò)濾要求的候選項(xiàng)；最后對(duì)通過(guò)2次過(guò)濾的候選項(xiàng)逐個(gè)進(jìn)行相似度驗(yàn)證，將通過(guò)驗(yàn)證的候選項(xiàng)添加至最終結(jié)果.以Jaccard相似度為例，算法2描述了使用倒排索引基于前綴過(guò)濾和長(zhǎng)度過(guò)濾思想的并行相似性連接算法.

算法2.并行相似性連接算法.

輸入：字符串集S、相似度閾值τ、相似性度量函數(shù)Sim;

輸出：相似字符串匹配集RM.

① 使用算法1創(chuàng)建SoA結(jié)構(gòu)倒排索引ISoA；

② 設(shè)置RM=?，創(chuàng)建全局字符串token映射表TS和長(zhǎng)度表LS，初始化候選匹配對(duì)集合Candi；

③ for eachS中的字符串si并行執(zhí)行

④ 使用atomicAdd函數(shù)對(duì)si中的每個(gè)token執(zhí)行操作以在TS和LS中記錄si的token數(shù)量和特征長(zhǎng)度：

⑤ end for

⑥ for eachS中排序后的字符串si并行執(zhí)行操作：

⑦low=τ|si|,high=|si|τ,min=τTS[si],max=TS[si]τ;

⑧ 對(duì)于S中其他的字符串sj，如果滿足|sj|∈[low,high]且TS[sj]∈[min,max]，則添加候選匹配對(duì)(sj,si)至Candi；

⑨ end for

⑩ for each候選對(duì)(sj,si)∈Candi執(zhí)行

算法2中行①依據(jù)算法1使用GPU并行構(gòu)建倒排索引，行②進(jìn)行相關(guān)結(jié)構(gòu)的初始化.行③～⑤解析數(shù)據(jù)統(tǒng)計(jì)每個(gè)字符串的長(zhǎng)度以及所含特征的數(shù)量.行⑥～⑨使用GPU對(duì)原始數(shù)據(jù)集進(jìn)行雙重長(zhǎng)度過(guò)濾，根據(jù)給定的相似度閾值τ計(jì)算出長(zhǎng)度和特征數(shù)范圍，將同時(shí)滿足長(zhǎng)度和特征數(shù)量要求的記錄對(duì)添加至中間結(jié)果集.行⑩～對(duì)中間結(jié)果集進(jìn)行前綴過(guò)濾，將同時(shí)滿足2種過(guò)濾條件的候選項(xiàng)添加至候選結(jié)果集中.行在CPU上對(duì)候選結(jié)果集中所有候選項(xiàng)進(jìn)行相似度驗(yàn)證，將相似度超過(guò)閾值τ的候選項(xiàng)添加至匹配結(jié)果集.

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

5.1 實(shí)驗(yàn)設(shè)置與數(shù)據(jù)集

本次實(shí)驗(yàn)采用多種不同類型的數(shù)據(jù)集，表1給出了本次實(shí)驗(yàn)所用數(shù)據(jù)集的基本信息.

Table 1 Datasets for Experiments表1 實(shí)驗(yàn)所用數(shù)據(jù)集

1) DBLP.從DBLP(database systems and logic programming)原始數(shù)據(jù)集中抽取作者名和論文名進(jìn)行拼接，然后隨機(jī)刪除、更改后形成的數(shù)據(jù)集.

2) AOL.AOL(american online)搜索引擎的查詢?nèi)罩?，該?shù)據(jù)集中的每一行代表一組查詢關(guān)鍵詞.

3) Querylog.某搜索引擎的查詢語(yǔ)句集合.

4) BMS.商業(yè)管理系統(tǒng)(business management systems， BMS)的某商店使用POS機(jī)記錄的銷售數(shù)據(jù).

5) Enron.真實(shí)的電子郵件數(shù)據(jù)集，一個(gè)字符串代表一個(gè)真實(shí)的電子郵件的信息，平均長(zhǎng)度很長(zhǎng).

本文實(shí)驗(yàn)主要測(cè)試算法的執(zhí)行時(shí)間、加速比、算法各部分占比以及數(shù)據(jù)集大小、相似度閾值等條件對(duì)算法的影響.實(shí)驗(yàn)環(huán)境：本文實(shí)驗(yàn)所用GPU：NVIDIA GTX 1060 6 GB；CPU：Intel Core i7-8700 3.20 GHz；內(nèi)存：8 GB；操作系統(tǒng)：Windows 10.算法使用CUDA 9.0和C++實(shí)現(xiàn).

5.2 實(shí)驗(yàn)結(jié)果與分析

本文將通過(guò)實(shí)驗(yàn)分別檢測(cè)GPU加速在倒排索引構(gòu)建階段和相似性連接整體執(zhí)行上的加速效果.

1) 基于GPU的倒排索引構(gòu)建方法的作用

表2記錄了分別使用GPU和CPU在不同數(shù)據(jù)集上構(gòu)建倒排索引時(shí)程序的執(zhí)行時(shí)間.可以明顯地看出使用GPU構(gòu)建倒排索引可以大幅提升倒排索引的構(gòu)建速度.在不同的數(shù)據(jù)集上，本文提出的基于GPU的SoA型倒排索引的構(gòu)建方法的加速比(并行算法與串行算法執(zhí)行時(shí)間的比值)分別達(dá)到了51.87，8.53，81.40，23.83，80.58，加速效果明顯.

在Enron，DBLP，BMS這3個(gè)數(shù)據(jù)集上獲得了較高的加速比，而在Querylog數(shù)據(jù)集上的加速比相對(duì)較低.這是因?yàn)镼uerylog是小數(shù)據(jù)集，數(shù)據(jù)集較小時(shí)并行計(jì)算帶來(lái)的計(jì)算速度的提升效果不明顯，同時(shí)GPU的引入會(huì)提升數(shù)據(jù)傳輸?shù)拇鷥r(jià)，所以加速比相對(duì)較低.而同樣是小數(shù)據(jù)集的BMS是純數(shù)字?jǐn)?shù)據(jù)集，數(shù)字類型占據(jù)空間相對(duì)較小，所以體量更小的BMS數(shù)據(jù)集的數(shù)據(jù)規(guī)模其實(shí)比Querylog數(shù)據(jù)集更大，因此使用GPU構(gòu)建倒排索引的加速效果也比較明顯.在使用CPU構(gòu)建倒排索引時(shí)需要使用Enron等較大數(shù)據(jù)集是因?yàn)椴⑿杏?jì)算大幅減少數(shù)據(jù)處理時(shí)間，所以加速效果十分明顯.

Table 2 Comparison of Inverted Index Construct Time表2 倒排索引構(gòu)建時(shí)間對(duì)比

Fig. 4 Impact of dataset size on execution time圖4 數(shù)據(jù)集大小對(duì)執(zhí)行時(shí)間的影響

圖4(a)記錄了使用GPU構(gòu)建倒排索引時(shí)方法的執(zhí)行時(shí)間隨數(shù)據(jù)集大小的變化情況，圖4(b)記錄了并行方法加速比隨數(shù)據(jù)集大小的變化情況.隨著數(shù)據(jù)集的增大，基于GPU的并行索引構(gòu)建方法的執(zhí)行時(shí)間呈近似線性增長(zhǎng).這是因?yàn)镾oA結(jié)構(gòu)保證不同線程間的讀寫沒(méi)有耦合，數(shù)據(jù)集的增大僅僅會(huì)增加單個(gè)線程完成計(jì)算任務(wù)需要的次數(shù).加速比隨著數(shù)據(jù)集的增大逐漸提升，說(shuō)明傳統(tǒng)的索引構(gòu)建方法不能在數(shù)據(jù)集增大的同時(shí)保證運(yùn)行時(shí)間的線性增長(zhǎng).因此本文提出的倒排索引構(gòu)建方法可以在數(shù)據(jù)集規(guī)模較大的時(shí)候依然保證良好的執(zhí)行效率，并且數(shù)據(jù)集越大構(gòu)建方法的加速效果越明顯.

Fig. 5 Time proportion of each part of inverted index construction algorithm圖5 倒排序索引構(gòu)建算法各部分時(shí)間占比

圖5比較了使用GPU構(gòu)建倒排索引的過(guò)程中方法各部分的時(shí)間占比.其中預(yù)處理部分包括原始數(shù)據(jù)讀取與全局映射表構(gòu)建2個(gè)步驟；GPU構(gòu)建索引部分同時(shí)也包括主存與全局內(nèi)存之間數(shù)據(jù)傳輸過(guò)程；CPU索引合并部分是指將SoA型倒排索引合并成通用的倒排索引結(jié)構(gòu)的過(guò)程.在不同數(shù)據(jù)集上的實(shí)驗(yàn)表明：數(shù)據(jù)預(yù)處理部分的時(shí)間占比最高，并且隨著數(shù)據(jù)集體積的增大，這部分的時(shí)間占比會(huì)進(jìn)一步提高；而并行計(jì)算以及索引合并2個(gè)階段的時(shí)間占比很低.所以在CPU-GPU異構(gòu)體系結(jié)構(gòu)的倒排索引構(gòu)建方法中，方法的性能瓶頸主要在CPU端的數(shù)據(jù)預(yù)處理部分.

2) 基于GPU的相似性連接方法的作用

表3記錄在不同數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)的結(jié)果，對(duì)比的串行算法為目前效率較高且適用范圍較廣的PPJoin算法[17].為了節(jié)省算法的執(zhí)行時(shí)間，本節(jié)實(shí)驗(yàn)分別從Enron，DBLP，AOL這3個(gè)數(shù)據(jù)集中抽取了24 000，60 000，140 000條數(shù)據(jù)進(jìn)行實(shí)驗(yàn).實(shí)驗(yàn)結(jié)果表明本文提出的基于CPU-GPU異構(gòu)體系結(jié)構(gòu)的算法相較于原有算法有一定的提升，在AOL數(shù)據(jù)集上獲得了最高45.6%加速效果，整體加速效果與倒排索引構(gòu)建方法相比很不明顯.

Table 3 Comparison of Algorithm Execution Time表3 算法執(zhí)行時(shí)間對(duì)比

Fig. 6 Execution time of the algorithm with differentdata scales圖6 算法在不同數(shù)據(jù)規(guī)模下的執(zhí)行時(shí)間

Fig. 7 Time proportion of each part of similarity join algorithm圖7 相似性連接算法各部分時(shí)間占比

為了探究相似性連接方法加速效果及相關(guān)影響因素，本文記錄了通過(guò)實(shí)驗(yàn)對(duì)比算法各個(gè)部分的時(shí)間占比隨數(shù)據(jù)集大小的變化情況，實(shí)驗(yàn)結(jié)果如圖6和圖7所示.圖6展示了Enron，DBLP，AOL這3個(gè)數(shù)據(jù)集在不同數(shù)據(jù)記錄數(shù)量規(guī)模下的執(zhí)行時(shí)間變化情況，從實(shí)驗(yàn)結(jié)果可見(jiàn)，隨著數(shù)據(jù)規(guī)模的增大，算法的執(zhí)行時(shí)間呈近似線性增長(zhǎng).圖7展示了Enron，DBLP，AOL這3個(gè)數(shù)據(jù)集在不同數(shù)據(jù)記錄數(shù)量規(guī)模下的算法各部分執(zhí)行時(shí)間占比，從實(shí)驗(yàn)結(jié)果圖可以看出使用GPU執(zhí)行的創(chuàng)建索引(create index)和過(guò)濾記錄對(duì)(filter pairs)這2個(gè)階段的時(shí)間占比較低，隨數(shù)據(jù)集的變大逐漸減少或保持平穩(wěn)；而相似度驗(yàn)證記錄對(duì)(verify pairs)階段時(shí)間占比最高，超過(guò)了其余步驟的總和，并且隨著數(shù)據(jù)集的增大不斷增大.因此，最后在CPU端執(zhí)行的相似度驗(yàn)證階段是本文提出的相似性連接方法加速效果不明顯的主要原因，要進(jìn)一步提升算法的加速效果，必須重新設(shè)計(jì)適合GPU并行計(jì)算的相似度計(jì)算方法.

圖8和圖9分別比較了相似度閾值τ對(duì)算法執(zhí)行時(shí)間和過(guò)濾效果的影響.隨著相似度閾值的增加，候選項(xiàng)的數(shù)量以及算法的整體執(zhí)行時(shí)間成近似線性減少，算法的過(guò)濾效果良好.其中DBLP數(shù)據(jù)集對(duì)閾值變化最敏感，因?yàn)榇藬?shù)據(jù)集中字符串長(zhǎng)度方差最大，所以使用前綴過(guò)濾和長(zhǎng)度過(guò)濾時(shí)提升相似度閾值可以大幅減少候選項(xiàng)的數(shù)量，迅速減少算法執(zhí)行時(shí)間.

Fig. 8 Effect of similarity threshold on execution time圖8 相似度閾值對(duì)算法執(zhí)行時(shí)間的影響

Fig. 9 Influence of similarity threshold on candidatefiltration圖9 相似度閾值對(duì)算法過(guò)濾效果的影響

通過(guò)本節(jié)實(shí)驗(yàn)可以得出2個(gè)結(jié)論：

1) 使用GPU構(gòu)建倒排索引可以明顯加快索引的構(gòu)建速度，并且數(shù)據(jù)集數(shù)據(jù)量越大，算法的加速效果越明顯；

2) 基于CPU-GPU異構(gòu)體系結(jié)構(gòu)的并行相似性連接方法過(guò)濾效果良好，與傳統(tǒng)方法相比具有一定的加速效果.

6 總結(jié)與展望

本文提出了基于CPU-GPU異構(gòu)體系結(jié)構(gòu)的倒排索引構(gòu)建方法以及相似性連接方法.采用SoA型的倒排索引結(jié)構(gòu)加快并行條件下索引的讀寫速度，在獲得較高加速比的同時(shí)保證索引具有良好的通用性.基于前綴和長(zhǎng)度過(guò)濾的并行相似性連接方法在一定程度上進(jìn)一步提升了傳統(tǒng)方法的執(zhí)行速度，并且為相似性連接算法的研究提供了一個(gè)新的思路.但是本文提出的方法依然存在局限性，實(shí)驗(yàn)結(jié)果表明數(shù)據(jù)讀取和相似度驗(yàn)證的2個(gè)階段時(shí)間占比較高，如果可以使用例如直接尋址等技術(shù)讀取數(shù)據(jù)并且構(gòu)建適合GPU并行計(jì)算的相似性度量，就可以進(jìn)一步提升方法的執(zhí)行速度.下一步，我們將試圖在本文的基礎(chǔ)上解決這一問(wèn)題.