一種適合Tegra K1架構(gòu)的Top-k查詢(xún)優(yōu)化算法

李靚琦 黃玉龍 謝紹國(guó)

（1.吉安職業(yè)技術(shù)學(xué)院機(jī)械與電子工程學(xué)院 江西省吉安市 343000）

（2.新余學(xué)院數(shù)學(xué)與計(jì)算機(jī)學(xué)院 江西省新余市 338004 3.安慶師范大學(xué)計(jì)算機(jī)與信息學(xué)院 安徽省安慶市 246133）

1 引言

在當(dāng)今移動(dòng)互聯(lián)網(wǎng)時(shí)代，NVIDIA 推出了擁有192 個(gè)CUDA[1]核心的嵌入式GPU — Tegra K1 來(lái)提升移動(dòng)應(yīng)用性能。禁止隨機(jī)訪(fǎng)問(wèn)的Top-k 查詢(xún)?yōu)樾畔z索領(lǐng)域的典型問(wèn)題，在移動(dòng)應(yīng)用中得到了廣泛使用。作為禁止隨機(jī)讀的代表性算法--NRA 算法[2]使用分值上下界逐次逼近策略，算法可在未獲取所有對(duì)象的準(zhǔn)確聚合分值前獲得最終結(jié)果。為了減少計(jì)算代價(jià)，Guntzer 以及Mamoulis 等分別提出了SC 算法[3]及LARA 算法[4]。為了充分利用臺(tái)式GPU 的計(jì)算性能，黃玉龍等提出了分段Top-k 查詢(xún)算法[5]。然而，由于嵌入式硬件GPU 與CPU 共享運(yùn)行內(nèi)存等特點(diǎn)，這些算法均不能適應(yīng)在Tegra TK1 上運(yùn)行。為此，本文提出了一種適合Tegra K1 架構(gòu)的查詢(xún)優(yōu)化算法。

2 共享內(nèi)存的CUDA模型

在CUDA 編程模型中，通常需將CPU 看作是主機(jī)，將GPU看作是設(shè)備。為此，可將程序分為兩類(lèi)：一種是運(yùn)行在CPU 上的宿主代碼，另一種為GPU 執(zhí)行的設(shè)備代碼。由于CPU 和GPU 在硬件架構(gòu)上存在差異，這兩類(lèi)代碼可訪(fǎng)問(wèn)的資源是不一樣的。

與傳統(tǒng)架構(gòu)不同，嵌入式GPGPU 與CPU 共享運(yùn)行內(nèi)存，即：基于嵌入式GPGPU 算法的執(zhí)行時(shí)間T= Th+Td。其中，Th表示host端執(zhí)行時(shí)間，而Td為device 端執(zhí)行時(shí)間。

3 查詢(xún)優(yōu)化算法

由文獻(xiàn)[1]可知：Top-k 查詢(xún)就是在規(guī)模為m 的空間中找出聚合分值最高的k 個(gè)對(duì)象。其中，每個(gè)對(duì)象由n 個(gè)屬性組成且所有對(duì)象在屬性i 下的得分降序保存到一規(guī)模為m 的列表Li。其中，每個(gè)存儲(chǔ)位的結(jié)構(gòu)為(id,score)。由于CUDA 適合處理線(xiàn)性結(jié)構(gòu)，在此將輸入數(shù)據(jù)數(shù)組合并為一個(gè)m*n 的一維數(shù)組L。為了存儲(chǔ)候選結(jié)果，算法執(zhí)行前需分配一個(gè)長(zhǎng)度為k 的對(duì)象集合Ck。集合中每個(gè)元素的結(jié)構(gòu)為（oID,w,b,visited）。其中，oID 為標(biāo)識(shí)符，b 和w 分別表示分值上下界，visited 位圖則記錄對(duì)象的訪(fǎng)問(wèn)狀況。此外，為記錄集合Ck外的已訪(fǎng)問(wèn)對(duì)象，還需分配一個(gè)變長(zhǎng)對(duì)象數(shù)組Ck。同理，在此將集合Ck與Ck合并為集合C。為了盡可能地利用Tegra K1 的線(xiàn)程資源，我們的算法還采用分段執(zhí)行策略。即，一次執(zhí)行有序列表STRIDE個(gè)層次。基于以上定義，下面分兩個(gè)階段闡述查詢(xún)優(yōu)化算法。

3.1 擴(kuò)展階段

開(kāi)始時(shí)，數(shù)組C 為空，在此僅需將讀到的數(shù)組L 中的元素簡(jiǎn)單插入集合C 即可，具體流程為：循環(huán)批量讀取L 中元素及下標(biāo)。在此，可將讀取到的元素分為兩類(lèi)：一類(lèi)是從未讀取過(guò)。對(duì)于此類(lèi)元素，直接將其插入數(shù)組C 即可。另一類(lèi)元素是數(shù)組C 保存對(duì)象的屬性值。對(duì)于此類(lèi)元素，需要更新相關(guān)對(duì)象的訪(fǎng)問(wèn)狀況并且更新其分值下界b，直至數(shù)組C 的長(zhǎng)度大于等于k 為止。此階段的具體思想如下：

For each tid∈[0,STRIDE ) parallel do item ←L[tid].id; //tid 為線(xiàn)程編號(hào)if(item.id ≠obj.oID)// obj 為數(shù)組C 中的對(duì)象obj.oID=item.id;obj.w=item.score;將obj 追加到數(shù)組C 末尾；else obj.w=obj.w+item.score;//更新對(duì)象obj 的分值下界end if更新obj 的visited 位圖;End parallel for使用thrust 庫(kù)[5]中的sort_by_key 原語(yǔ)排序數(shù)組C；

此時(shí)，在host 端將當(dāng)前閾值T 與數(shù)組C 末尾對(duì)象的分值下界進(jìn)行比較，如大于等于，則算法進(jìn)入下一階段。否則，繼續(xù)批量訪(fǎng)問(wèn)數(shù)組L，直至數(shù)組C 末尾對(duì)象的分值下界大于等于當(dāng)前閾值為止。

3.2 剪枝階段

此階段，數(shù)組L 的對(duì)象個(gè)數(shù)將維持不變。訪(fǎng)問(wèn)中，如遇到上階段從未訪(fǎng)問(wèn)的對(duì)象，則不予處理。為了減少比較次數(shù)，在此使用類(lèi)似SC 算法策略，僅維護(hù)分值上界即可。為了充分利用GPU 的性能，在此亦采用相似批量處理策略循環(huán)執(zhí)行。同樣地，此階段一次遍歷數(shù)組L 中STRIDE 個(gè)元素且每次遍歷的流程如下：

（1）并行獲取L 中從第 j 到 j + STRIDE 層所有元素及下標(biāo);//j為上階段訪(fǎng)問(wèn)的層次。

（2）更新數(shù)組C 中相關(guān)對(duì)象的分值下界及訪(fǎng)問(wèn)狀況visited 位圖;

圖1：算法執(zhí)行時(shí)間

圖2：算法的加速比

（3）如果數(shù)組C 存在k 個(gè)或以上對(duì)象的聚合分值完全確定，則執(zhí)行步驟4；

（4）并行獲取數(shù)組C 中已確定聚合分值的對(duì)象到臨時(shí)數(shù)組tmp;

（5）并行刪除數(shù)組C 中相應(yīng)位置對(duì)象；

（6）使用thrust[5]庫(kù)中的sort_by_key 原語(yǔ)排序tmp 以及C 數(shù)組；

（7）如果tmp[k-1]的分值score 大于等于C[0]的分值上界b，則算法結(jié)束，tmp 數(shù)組前k 個(gè)對(duì)象即為查詢(xún)結(jié)果；否則，重復(fù)執(zhí)行步驟1～6，直至算法結(jié)束。

由此可知，本文提出的算法在綜合LARA 及SC 算法的優(yōu)點(diǎn)基礎(chǔ)上，充分利用了Tegra K1 GPU 強(qiáng)大的線(xiàn)程資源，可快速獲得查詢(xún)結(jié)果。與此同時(shí)，考慮到Tegra K1 與CPU 共享內(nèi)存的特點(diǎn)，使用位圖結(jié)構(gòu)記錄對(duì)象訪(fǎng)問(wèn)狀態(tài)，從而可處理更大規(guī)模的查詢(xún)。

4 性能分析

為了驗(yàn)證本文算法的有效性，在嵌入式開(kāi)發(fā)板Jetson-TK1 上進(jìn)行了實(shí)驗(yàn)。開(kāi)發(fā)板硬件配置為：CPU 為 ARM Cortex-A15，主頻為1.3GHz；GPU 為擁有192 個(gè)CUDA 核心的Tegra K1，每個(gè)核心主頻為0.825GHz。CPU 與GPU 共享2GB 運(yùn)行內(nèi)存；操作系統(tǒng)為Ubuntu14.04，CUDA 工具包為6.5 版本。實(shí)驗(yàn)數(shù)據(jù)集為隨機(jī)生成的均勻分布數(shù)據(jù)，其中，每個(gè)對(duì)象的屬性分值都服從(0,1)分布?；诖耍S機(jī)生成了1M、2M、4M、6M、8M 以及10M 規(guī)模的實(shí)驗(yàn)數(shù)據(jù)，每個(gè)對(duì)象包含了4 個(gè)屬性。算法返回的對(duì)象數(shù)量100；分值計(jì)算函數(shù)為∑ ui(0 ≤i＜m)，m 為有序列表數(shù)量。STRIDE 步長(zhǎng)為100。根據(jù)上述規(guī)定，下面給出了算法的具體執(zhí)行時(shí)間以及算法的加速比，分別如圖1 和2所示。

由圖1 可知，在一次訪(fǎng)問(wèn)100 個(gè)輸入元素基礎(chǔ)上，我們的算法在10M 規(guī)模數(shù)據(jù)集上執(zhí)行top-100 查詢(xún)，可在2 秒內(nèi)完成，這樣的性能非常適合在大規(guī)模集合上執(zhí)行top-k 查詢(xún)。從圖2 中可以得知，與單線(xiàn)程CPU 算法比較，我們的算法可以獲得2.7 至3.8 倍的加速比，這主要因?yàn)殡m然Tegra K1 的計(jì)算核心數(shù)量眾多，但工作頻率低且算法中存在多處線(xiàn)程同步，需要消耗大量通信代價(jià)。

5 結(jié)論

作為信息檢索的一個(gè)經(jīng)典問(wèn)題，Top-k 查詢(xún)?cè)谝苿?dòng)應(yīng)用中得到了廣泛使用。為了提高移動(dòng)應(yīng)用的查詢(xún)性能，NVIDIA 公司推出了一個(gè)擁有192 個(gè)計(jì)算核心的Tegra K1 GPU。為此，本文研究了一種適合Tegra K1 架構(gòu)的分段查詢(xún)算法。結(jié)合LARA 以及SC 算法的優(yōu)勢(shì)，本文的算法在10M 規(guī)模對(duì)象中查找出100 個(gè)最高分值對(duì)象的過(guò)程可在2 秒鐘內(nèi)完成。與單線(xiàn)程CPU 算法比較，本文的算法有著顯著的性能提升。