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

在審

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

技術領域

本發明涉及計算機技術領域，具體涉及一種基于CUDA的并行空間查詢方法。

背景技術

指控系統作為武器系統裝備的一個重要組成部分，是整個武器系統的信息處理中心，也是指揮員了解戰場態勢、進行指揮決策的重要手段。而要在復雜的多維空間戰場進行指揮控制，必須處理極為龐大和繁雜的戰術信息。其中60％與地理背景密切相關，尤其在野戰過程中，指揮決策對于地理信息及其相關地理屬性的依賴性更為突出，地理信息直接影響作戰方案的制定和戰術思想的落實。通過指控系統的GIS功能，可實現對戰場地理空間的實時綜合處理和直觀可視化分析，形象表示敵我態勢，從而輔助指揮員進行戰場指揮決策。

在指控系統中，最為常用的GIS功能就是戰場電子地圖的瀏覽與戰場空間查詢，根據查詢條件，指揮員可以找到一定地理范圍空間內的目標數據，例如戰場軍事標注點、遠程分隊的覆蓋區域等。

空間查詢一般指的是空間幾何查詢，也就是說，根據給定的空間查詢請求的空間范圍及空間對象的幾何屬性，找出所有滿足條件的空間實體目標集合?；谒饕龣C制的空間查詢過程主要分為過濾步驟及精煉步驟。過濾步驟負責根據空間索引利用各種過濾邊界(如凸多邊形、MBR(主引導記錄)等)對空間數據集進行初步篩選，找到一系列空間對象候選集合；精煉步驟則通過加載候選集合的幾何信息與查詢條件進行精確匹配，從而得到真正的查詢結果。

隨著網絡化、一體化作戰模式的發展，指控系統需要處理的各類數據越來越復雜，數據量越來越龐大，僅地理信息數據就能達到TB 級以上，現有的指控系統在面對如此密集的計算任務時，傳統的處理方式已無法滿足應用對大規模計算的實時性需求。當面對海量戰場空間數據的查詢與分析等復雜處理任務時，數據處理周期通常需要控制在幾百毫秒乃至數毫秒內，而傳統基于樹型索引的空間查詢方法，當數據越來越集中時，空間要素的重疊度也將越來越高，過高的重疊必然導致空間檢索過程中出現冗余路徑，嚴重影響了檢索效率，現有的GIS空間查詢功能已無法滿足指控實時性的需求。

從當今計算機科學發展的前景來看，多機集群、分布式、并行處理將成為應對大規模復雜計算模式的主流趨勢，鑒于指揮控制系統的軍事應用需求及應用特點，采用并行處理架構將成為必然。GPGPU(General Purpose Graphic Processing Unit，通用計算圖形處理器)憑借其大規模并行計算能力和易編程性已成為高性能計算和科學計算應用的重要加速手段，并廣泛應用于其它通用計算領域。GPU通用計算為復雜性超出CPU解決能力和計算需求的應用，提供了一個使用較少能耗卻能發揮更高性能的解決方案。

目前，主要的GPU硬件供應商都發布了相應的軟件開發工具SDK，使得開發者能夠使用高級編程語言進行應用開發。其中，NVIDIA公司發布的CUDA(Compute Unified Device Architecture，統一計算設備架構)可以作為C/C++語言的擴展，成為最受歡迎的并行框架之一。

在指控系統對密集型計算任務的實時處理需求下以及GPU通用計算迅猛發展的背景下，需要設計一種新的查詢優化方法。

發明內容

(一)要解決的技術問題

本發明要解決的技術問題是：如何設計一種空間查詢方法，以解決傳統基于樹型索引進行空間查詢執行步驟多、過濾篩選不細致、精確匹配計算復雜導致的查詢效率低的問題。

(二)技術方案

為了解決上述技術問題，本發明提供了一種基于CUDA的并行空間查詢方法，所述方法包括下列步驟：

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

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

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

優選地，所述步驟100，包括下列步驟：

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

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

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

優選地，所述步驟200，包括下列步驟：