[發明專利]一種基于異構平臺的高維詞匯樹構建方法

有效

• 申請號: 201510938217.1
• 申請日: 2015-12-16
• 公開（公告）號: CN105573834B
• 公開（公告）日: 2018-12-11
• 發明（設計）人: 張為華;季曉楓;余時強
• 申請（專利權）人: 復旦大學
• 主分類號: G06F9/48
• 分類號: G06F9/48
• 代理公司: 上海正旦專利代理有限公司 31200
• 代理人: 陸飛;盛志范

本發明屬于并行處理器技術領域，具體為一種基于異構平臺的面向高維詞匯樹構建方法。本發明利用異構處理平臺（通用處理器和圖形處理器（GPGPU）混合架構）上圖形處理器強大的并行計算能力與可編程性，提升高維詞匯樹構建過程的速度。本發明利用圖形處理器高并發性的特點加速高維詞匯樹算法的核心過程，利用高維詞匯樹算法特性和圖形處理器的內存訪問模式優化算法的訪存過程，并設計了主機和圖形處理器在高維詞匯樹算法運行過程中的協調策略。本發明方法可以有效提升面向高維數據的詞匯樹的構建速度。

技術領域

本發明屬于并行處理器技術領域，具體涉及一種基于異構平臺處理能力的面向高維數據的詞匯樹（Vocabulary Tree）構建方法。

背景技術

隨著大數據時代的到來，海量數據已經滲透到社會的每一個行業，對于海量數據的處理已經成為議論的熱點。在圖像檢索領域，大量的數據圖片給檢索帶來了前所未有的困難。根據資料顯示，Facebook每天上傳的圖片量達到3.5億，數據量達到7PB，對于如此龐大的數據，如何快速有效的檢索從而提供更好的用戶體驗變成了巨大的挑戰。高維Vocabulary Tree（詞匯樹）的提出有效地提高了圖像識別方面的性能，該算法首先用局部特征提取算法對圖像提取特征點，然后將這些圖像特征點的集合通過聚類的方法生成數據詞匯，接著采用TF-IDF的加權方法，使得圖片的檢索時間能夠有效地縮短。

雖然高維詞匯樹的提出有效地高了圖像檢索的效率，但是基于大數據圖片的高維詞匯樹的構建過程仍然十分耗時，一百萬張圖片，包含了四億多個特征點，而每個特征點都是由64維或者128構成的高維數據，總數據量將近50GB，其建樹過程需要花費64個小時。而假如要處理前文提到的Facebook的數據量，即使處理時間是線性增長的，也需要9000多個小時——超過一年的時間。而一旦圖像數據庫發生改動，那就需要重新為新的圖像數據集建樹，如此長的建樹時間給圖像搜索應用帶來極大的不便。因此提升高維詞匯樹構建過程的速度是十分必要的。

在過去的近十年時間內，圖形處理器（GPU）不僅在圖像處理方面發揮作用，在并行處理領域也得到了飛速的發展，而且在性能加速方面的能力也已經遠遠勝出CPU。由于GPU通用計算的編程模型（如CUDA、OpenCL）逐漸成熟，越來越多復雜的、計算量大的難題都已經移植到GPU上處理，很多已經得到了解決并且在性能方面有很大提升。同時隨著多核CPU處理器技術的出現，CPU強大的計算能力也不容忽視，超級計算機通常配置幾百個CPU處理器。在GPU和多核CPU快速發展的情形下，完全能夠利用這些強大的計算資源來提升構建高維詞匯樹的速度。而節點的處理算法中分類以及求和這兩個數據密集型的過程又非常適合使用GPU進行加速。因此，高維詞匯樹的構建適合部署到異構處理平臺（通用處理器和圖形處理器（GPGPU）混合架構）上進行。本發明致力于利用異構平臺處理器，以提升高維詞匯樹構建速度。

發明內容

本發明的目的在于提供一種高速的面向高維數據詞匯樹的構建方法。

本發明提供的面向高維數據的詞匯樹的構建方法，是基于異構平臺（通用處理器和圖形處理器（GPGPU）混合架構）的，包括：利用異構平臺中圖形處理器（GPU）強大的并行計算能力與可編程性，提升高維詞匯樹構建過程的速度；利用高維詞匯樹算法特性和圖形處理器的內存訪問模式優化算法；提出主機和圖形處理器在高維詞匯樹算法運行過程中的協調策略。

在高維詞匯樹的構建中，計算量主要集中在節點生成的部分，所以本發明將高維詞匯樹中隊列管理以及預處理工作放在主機端，生成新節點算法中的分類以及求和兩個部分交由GPU進行處理。

詞匯樹的構建流程如下：

在運行建樹程序前，將所有圖片的高維特征點作為一整個節點放入隊列中。之后，開始運行建樹程序，建樹過程根據主機端的主線程維護的隊列進行。

第一步，程序從任務隊列中取出待處理的節點，并將需要處理的數據傳輸到GPU的主存中。