[發(fā)明專利]一種基于CPU-GPU異構(gòu)體系結(jié)構(gòu)的并行相似性連接方法

有效

• 申請?zhí)枺?/td>: 201911057101.1
• 申請日: 2019-11-01
• 公開（公告）號: CN111046092B
• 公開（公告）日: 2022-06-17
• 發(fā)明（設(shè)計(jì)）人: 聶鐵錚;徐坤浩;申德榮;于戈;寇月
• 申請（專利權(quán)）人: 東北大學(xué)
• 主分類號: G06F16/25
• 分類號: G06F16/25;G06F16/22;G06F15/163
• 代理公司: 沈陽東大知識產(chǎn)權(quán)代理有限公司 21109
• 代理人: 李在川

本發(fā)明公開一種基于CPU?GPU異構(gòu)體系結(jié)構(gòu)的并行相似性連接方法，屬于計(jì)算機(jī)數(shù)據(jù)庫技術(shù)與并行計(jì)算技術(shù)領(lǐng)域。該方法通過對數(shù)據(jù)相似性連接方法進(jìn)行分析設(shè)計(jì)，構(gòu)建新的倒排索引結(jié)構(gòu)，實(shí)現(xiàn)在GPU上并行構(gòu)建倒排索引，對相似性連接方法進(jìn)行分解，根據(jù)兩種處理器不同的計(jì)算特性重新設(shè)計(jì)計(jì)算過程，基于GPU實(shí)現(xiàn)雙重前綴過濾，有效減小候選集體積。本發(fā)明提供的基于CPU?GPU異構(gòu)體系結(jié)構(gòu)的相似性連接方法能夠?qū)鹘y(tǒng)的數(shù)據(jù)相似性連接準(zhǔn)確地轉(zhuǎn)換到CPU?GPU異構(gòu)計(jì)算體系上，從而有效提高大規(guī)模數(shù)據(jù)集相似性連接的處理效率。

技術(shù)領(lǐng)域

本發(fā)明涉及計(jì)算機(jī)數(shù)據(jù)庫技術(shù)與并行計(jì)算技術(shù)領(lǐng)域，尤其涉及一種基于CPU-GPU異構(gòu)體系結(jié)構(gòu)的并行相似性連接方法。

背景技術(shù)

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

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

目前，對相似性連接算法的優(yōu)化主要集中在過濾階段的優(yōu)化，通過對過濾算法的優(yōu)化提升過濾效果，減少驗(yàn)證階段的任務(wù)量。現(xiàn)有研究工作提出了很多的過濾算法，其中包括基于倒排索引的計(jì)數(shù)過濾算法、基于位置的過濾算法、基于長度的過濾算法以及基于前綴的過濾算法。這些算法在一定程度上都提升了過濾階段的效率，但都是基于串行處理的設(shè)計(jì)思想，處理效率受到了極大的限制。

發(fā)明內(nèi)容

針對上述現(xiàn)有技術(shù)的不足，本發(fā)明提供一種基于CPU-GPU異構(gòu)體系結(jié)構(gòu)的并行相似性連接方法。

為解決上述技術(shù)問題，本發(fā)明所采取的技術(shù)方案是：一種基于CPU-GPU異構(gòu)體系結(jié)構(gòu)的并行相似性連接方法，其流程如圖1所示，包括如下步驟：

步驟1：使用GPU對初始數(shù)據(jù)集S并行構(gòu)建SoA新型倒排索引，如圖2所示為構(gòu)建的基于SoA的倒排索引示意圖；

步驟1.1：給定數(shù)據(jù)集S，將其中每行數(shù)據(jù)Si切分成若干個(gè)數(shù)據(jù)集合token；

步驟1.2：為每個(gè)不同的token分配全局唯一數(shù)字類型tid；

步驟1.3：在GPU顯存中使用全局映射表記錄token與分配的tid之間的映射關(guān)系，并借助全局映射操作，將體積較大的字符串類型的token轉(zhuǎn)換為數(shù)字類型的tid，使得原數(shù)據(jù)的體積大幅減少，從而大幅減少后續(xù)倒排索引中每個(gè)關(guān)鍵詞的占用空間；

步驟1.4：全局映射關(guān)系構(gòu)建完成后傳輸至GPU的global memory；

步驟1.5：使用GPU構(gòu)建SoA新型倒排索引；