一種適合Tegra K1架構的Top-k查詢優化算法

李靚琦 黃玉龍 謝紹國

（1.吉安職業技術學院機械與電子工程學院 江西省吉安市 343000）

（2.新余學院數學與計算機學院 江西省新余市 338004 3.安慶師范大學計算機與信息學院 安徽省安慶市 246133）

1 引言

在當今移動互聯網時代，NVIDIA 推出了擁有192 個CUDA[1]核心的嵌入式GPU — Tegra K1 來提升移動應用性能。禁止隨機訪問的Top-k 查詢為信息檢索領域的典型問題，在移動應用中得到了廣泛使用。作為禁止隨機讀的代表性算法--NRA 算法[2]使用分值上下界逐次逼近策略，算法可在未獲取所有對象的準確聚合分值前獲得最終結果。為了減少計算代價，Guntzer 以及Mamoulis 等分別提出了SC 算法[3]及LARA 算法[4]。為了充分利用臺式GPU 的計算性能，黃玉龍等提出了分段Top-k 查詢算法[5]。然而，由于嵌入式硬件GPU 與CPU 共享運行內存等特點，這些算法均不能適應在Tegra TK1 上運行。為此，本文提出了一種適合Tegra K1 架構的查詢優化算法。

2 共享內存的CUDA模型

在CUDA 編程模型中，通常需將CPU 看作是主機，將GPU看作是設備。為此，可將程序分為兩類：一種是運行在CPU 上的宿主代碼，另一種為GPU 執行的設備代碼。由于CPU 和GPU 在硬件架構上存在差異，這兩類代碼可訪問的資源是不一樣的。

與傳統架構不同，嵌入式GPGPU 與CPU 共享運行內存，即：基于嵌入式GPGPU 算法的執行時間T= Th+Td。其中，Th表示host端執行時間，而Td為device 端執行時間。

3 查詢優化算法

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

3.1 擴展階段

開始時，數組C 為空，在此僅需將讀到的數組L 中的元素簡單插入集合C 即可，具體流程為：循環批量讀取L 中元素及下標。在此，可將讀取到的元素分為兩類：一類是從未讀取過。對于此類元素，直接將其插入數組C 即可。另一類元素是數組C 保存對象的屬性值。對于此類元素，需要更新相關對象的訪問狀況并且更新其分值下界b，直至數組C 的長度大于等于k 為止。此階段的具體思想如下：

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

此時，在host 端將當前閾值T 與數組C 末尾對象的分值下界進行比較，如大于等于，則算法進入下一階段。否則，繼續批量訪問數組L，直至數組C 末尾對象的分值下界大于等于當前閾值為止。

3.2 剪枝階段

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

（1）并行獲取L 中從第 j 到 j + STRIDE 層所有元素及下標;//j為上階段訪問的層次。

（2）更新數組C 中相關對象的分值下界及訪問狀況visited 位圖;

圖1：算法執行時間

圖2：算法的加速比

（3）如果數組C 存在k 個或以上對象的聚合分值完全確定，則執行步驟4；

（4）并行獲取數組C 中已確定聚合分值的對象到臨時數組tmp;

（5）并行刪除數組C 中相應位置對象；

（6）使用thrust[5]庫中的sort_by_key 原語排序tmp 以及C 數組；

（7）如果tmp[k-1]的分值score 大于等于C[0]的分值上界b，則算法結束，tmp 數組前k 個對象即為查詢結果；否則，重復執行步驟1～6，直至算法結束。

由此可知，本文提出的算法在綜合LARA 及SC 算法的優點基礎上，充分利用了Tegra K1 GPU 強大的線程資源，可快速獲得查詢結果。與此同時，考慮到Tegra K1 與CPU 共享內存的特點，使用位圖結構記錄對象訪問狀態，從而可處理更大規模的查詢。

4 性能分析

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

由圖1 可知，在一次訪問100 個輸入元素基礎上，我們的算法在10M 規模數據集上執行top-100 查詢，可在2 秒內完成，這樣的性能非常適合在大規模集合上執行top-k 查詢。從圖2 中可以得知，與單線程CPU 算法比較，我們的算法可以獲得2.7 至3.8 倍的加速比，這主要因為雖然Tegra K1 的計算核心數量眾多，但工作頻率低且算法中存在多處線程同步，需要消耗大量通信代價。

5 結論

作為信息檢索的一個經典問題，Top-k 查詢在移動應用中得到了廣泛使用。為了提高移動應用的查詢性能，NVIDIA 公司推出了一個擁有192 個計算核心的Tegra K1 GPU。為此，本文研究了一種適合Tegra K1 架構的分段查詢算法。結合LARA 以及SC 算法的優勢，本文的算法在10M 規模對象中查找出100 個最高分值對象的過程可在2 秒鐘內完成。與單線程CPU 算法比較，本文的算法有著顯著的性能提升。