[發明專利]基于CUDA的并行空間查詢方法

在審

• 申請號: 201610741535.3
• 申請日: 2016-08-26
• 公開（公告）號: CN107784001A
• 公開（公告）日: 2018-03-09
• 發明（設計）人: 趙艷偉;楊雄軍;王曉光;楊帆
• 申請（專利權）人: 北京計算機技術及應用研究所
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 中國兵器工業集團公司專利中心11011
• 代理人: 劉東升

1.一種基于CUDA的并行空間查詢方法，其特征在于，所述方法包括下列步驟：

步驟100.讀取矢量要素，根據要素類型和索引ID，建立適用于GPU環境的并行的柵格索引；

步驟200.根據顯存空間對所述柵格索引進行瓦片分解，并根據空間訪問習慣建立索引替換策略進行瓦片索引替換；

步驟300.利用GPU中的多線程機制及生成的瓦片索引，實現并行空間查詢。

2.根據權利要求1所述的基于CUDA的并行空間查詢方法，其特征在于，所述步驟100，包括下列步驟：

步驟110.輸入矢量要素信息，讀取矢量要素的點坐標以及對應的矢量要素索引信息；

步驟120.根據矢量要素信息，對矢量要素進行柵格渲染；柵格渲染過程分為三步，第一步，提取矢量要素的輪廓信息；第二步，掃描輪廓并計算填充格網區域；第三步，按照水平掃描的方式對填充區域進行跨段或跨單元填充；

最后執行索引解析，通過輸入的矢量要素獲得索引信息，通過索引轉換引擎將其映射到對應的柵格單元中，最后與矢量要素柵格化的結果通過渲染緩存生成柵格索引。

3.根據權利要求2所述的基于CUDA的并行空間查詢方法，其特征在于，所述步驟200，包括下列步驟：

步驟210.根據顯存空間大小及GPU線程數量，對柵格索引進行瓦片分割，并將其裝配到顯存中；

步驟220.當顯存中的柵格索引無法滿足查詢需要時，根據LFU策略進行瓦片索引替換，否則按照索引訪問頻率選取下一個待替換的瓦片。

4.根據權利要求3所述的基于CUDA的并行空間查詢方法，其特征在于，所述步驟300，包括下列步驟：

步驟310.將生成的瓦片索引從主機端傳輸到設備端；

首先，對于給定的顯存大小，確定待存儲索引的范圍，若假設包含m行n列瓦片，則應存儲的索引集合為i代表索引所在行，j代表索引所在列，然后對各個瓦片之間，采用Hilbert曲線的方式進行存儲，最后針對每個瓦片內部，采取行掃描的方式存儲；

步驟320.將查詢請求條件Bbox裝載到設備端；

步驟330.指定線程塊和線程數目，啟動設備端的并行查詢核函數；

其中線程數目以二維方式指定，且按照查詢請求的MBR范圍來計算線程塊數量；

步驟340.當查詢的索引不在顯存內時，將顯存中的部分索引移回主機端，主機端相應的索引傳輸到設備端；

步驟350.根據線程啟動策略，執行并行查詢核函數，提取空間索引集；

步驟360.將篩選后的索引傳輸回主機端，根據查詢到的索引輸出對應的矢量要素。

5.根據權利要求4所述的并行提取空間索引集合的方法，其特征在于，所述步驟350，包括下列步驟：

步驟351.利用線程合并訪問原則，并行查詢索引結果集；

首先根據線程啟動策略，通過三層偏移關系計算出線程處理的空間位置，通過該空間位置計算出該空間位置所屬的索引瓦片，根據瓦片Hilbert曲線排序對應的H-code進一步確定該索引在顯存內的偏移，H-code表示Hilbert編碼；

步驟352.利用線程并行壓縮及前驅求和，對索引結果集進行并行壓縮及匯總；

利用CUDPP的并行歸并算法對提取的有效索引ID進行排序，對排序后的索引集合使每個線程分別處理一個元素，計算該元素與其前驅的差值并保存為標識量flag，根據flag的標識性質，對索引集合利用CUDPP compact進行并行壓縮，將標識量非0的要素ID前置，最后利用并行Prefix sum方法求得最終ID結果集。