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

有效

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

1.一種基于異構平臺的高維詞匯樹構建方法，其特征在于包括：利用異構平臺中圖形處理器GPU強大的并行計算能力與可編程性；利用高維詞匯樹算法特性和圖形處理器的內存訪問模式優化算法；采用主機和圖形處理器在高維詞匯樹算法運行過程中的協調策略；

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

在運行建樹程序前，將所有圖片的高維特征點作為一整個節點放入隊列中；

開始運行建樹程序，建樹過程根據主機端的主線程維護的隊列進行，具體步驟如下：

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

根據節點大小的不同，將采用不同的GPU協同策略：將節點分為下述三種，并放到不同的隊列中進行處理；在前一個隊列處理完之前程序不處理下一個隊列中的節點；

第一種是大型節點，這類節點的大小超過GPU主存的容量，將其劃分為可以放入GPU中的數據塊；如果是多GPU結構，每個GPU依次拿取自己的數據塊；如果是單GPU結構，該GPU順序處理所有的數據塊；每次處理完所有數據塊的分類或者求和之后，進行同步，并將結果匯總至主機端內存上的數組中，之后再進行下一部分的處理；

第二種是普通的節點，這類節點的大小可以整塊放入GPU內存中，不需要劃分為數據塊； GPU按順序從隊列中獲取任務，處理完一個任務后即可取下一塊任務；

第三種是碎片化節點，這類節點是到了隊列的尾部，高維詞匯樹的底層，產生的許多只有數百、數十個高維特征點的節點；為了充分利用GPU的計算能力，要放入盡量多的碎片化節點以填滿GPU的內存，此時GPU每次可以處理上百個節點；

第二步，對節點進行處理，生成K個子節點；

首先，在節點中隨機尋找K個高維特征點作為初始的中心點，然后對高維特征點進行分類處理，之后對每個分類求和，最后得到新的K個中心點；經過循環上述過程，至中心點結果不變后，得到K個新的中心點；

其中，GPU上節點的處理工作有兩部分：一是對每個高維特征點進行分類，二是對每個類別的高維特征點進行求和；對這兩部分采用不同的并行模式以提高并行性能：

對于分類計算，每個線程以高維特征點為任務目標，去完成分類任務；線程的任務是首先求出高維特征點與所有中心點的多維距離，然后確定與之距離最短的中心點，將結果存儲到全局內存中；由于計算最短距離不適合由多個線程共同完成，所以GPU采用根據高維特征點進行處理的方式，線程各自讀取高維特征點進行處理；中心點的數據被存儲在線程塊的共享內存中，這是所有高維特征點公用的數據，放在共享內存中能夠減少不必要的主存訪問；當一個線程在處理完一個節點后，讀取下一個要處理的高維特征點并循環直至處理完所有的節點；

對于求和計算，GPU按維度進行并行處理，一個線程塊處理一組節點，每個線程負責特定的維度，每個線程只存儲自己負責的維度的局部和，這樣就能將局部和放在共享內存上，減少不必要的GPU主存訪問；每次處理完一個點中的特定維度，線程根據線程塊中的總線程數累加一定的地址得到下一部分有相同維度的數據；最終，在這組節點中所有線程都完成累加后，有特定的線程將各自負責的值累加到全局變量上；

第三步，將子節點放入隊列中；

當前節點生成的K個子節點中，超過預定的層數L或者特征點過少的節點不會被放入隊列，其余節點會被放到相應節點中；

第四步，重復第一至第三步的過程，當隊列為空時，高維詞匯樹的構建工作完成。

2.根據權利要求1所述的基于異構平臺的高維詞匯樹構建方法，其特征在于在第二步中，還對于GPU中的內存訪問進行了優化，優化目標是減少對全局內存的訪問或者將經常訪問的數據放置到共享內存上，包括：

（1）采用數據壓縮的內存訪問方式

在每次讀取數據時將多個維度的數據拼接成與帶寬匹配的數據一次讀??；對于分類的過程，一個點中相鄰的多個維度放在一起，作為一個數據讀??；對于求和的過程，將相鄰的多個點的同一個維度抽取出來進行拼接，作為一個數據讀?。?/p>

（2）進行數據重構

在分類的過程中，數據重構，就是使warp中線程訪問數據時，數據在GPU主存中的分布是連續的，即warp訪問的特征點的同一維在GPU主存中是連續的；同時，將同一個點的多個維度先作為一塊存放，再和相鄰點的相同維度一起存放；在求和的過程中，數據重構是將一組特征點的同一維度一起存放，以適應壓縮訪問的要求；

（3）逆向的數據塊遍歷和數據塊加載順序的優化

對于大型節點，由于節點大小大于GPU主存的容量，所以需要將其劃分為多個數據塊依次放入GPU中進行處理；將數據塊設計成小于GPU內存的一半，在使用GPU生成新節點的時候就能使用GPU的第二個工作流進行數據裝載的工作，將下一塊數據塊裝載在GPU的另一半內存上；

節點的處理會循環多次，對數據塊也會進行多次遍歷，為在遍歷的過程中減少數據塊的讀取次數，前一循環的結尾數據塊在后一循環開始時仍然儲存在GPU主存中，所以讓相鄰的兩個循環以逆向的方向進行數據塊的遍歷處理，這樣每一個GPU在頭部和尾部都可以節省一次數據塊載入的工作。