[發明專利]基于CPU+GPU架構的多邊形數據空間關系查詢并行系統

有效

• 申請號: 201410061347.7
• 申請日: 2014-02-24
• 公開（公告）號: CN103823860B
• 公開（公告）日: 2019-12-13
• 發明（設計）人: 謝傳杰;馬益杭;劉高煥;劉慶生;龍嘉懿;黃翀;史磊
• 申請（專利權）人: 中國科學院地理科學與資源研究所
• 主分類號: G06F16/29
• 分類號: G06F16/29;G06F16/2453
• 代理公司: 11251 北京科迪生專利代理有限責任公司
• 代理人: 成金玉

基于CPU+GPU架構的多邊形數據空間關系查詢并行系統，該系統由4個模塊組成：線段間相交分析模塊、環間拓撲關系分析模塊、多邊形間DE?9IM計算模塊以及圖層間空間關系查詢模塊。本發明使用戶可以在CPU+GPU架構上，并行加速完成對海量多邊形數據的空間關系查詢操作，準確輸出所有滿足空間關系查詢條件的多邊形數據，有效提高了空間關系查詢的處理速度并且保證其準確性。

技術領域

本發明涉及基于CPU+GPU架構的多邊形數據空間關系查詢并行系統，屬于信息技術領域，主要是綜合了異構多核并行技術，計算機圖形學技術和空間關系查詢技術，解決了在CPU+GPU架構上，對海量多邊形數據進行空間關系查詢的并行加速問題。

背景技術

隨著空間信息獲取技術更加成熟，空間數據的數據量急速增加。如何將這些海量、超海量空間數據應用于地學計算，能夠快速的得到處理從而獲得更有價值的信息，已經成為現今地理信息系統技術創新的熱點。隨著并行計算機越來越普及，并行技術的逐步成熟，并行計算已經成為解決快速處理大數據問題的主流手段。在數據量巨大的地學領域，依靠并行計算機的強大處理能力已經毫無疑問地成為滿足加速需求的最優選擇，由此應運而生的地學算法并行化改造，也必然成為大數據時代的重點和難點。

從基于CPU多核的并行到CPU+GPU的異構并行，硬件產品的更新換代對傳統地學計算算法的并行化產生了重大的影響。CPU的邏輯處理能力強，而GPU數學計算性能強大，大規模并行處理機制強大。將兩者結合成為一個異構平臺，發揮各自的特長，是并行計算的發展趨勢。在具有如此強大計算能力的架構平臺上，對原有的地學計算進行并行化改造，以實現超海量空間數據加速處理，是一項極其有意義的工作。

空間關系查詢指的是從空間數據集中查找滿足某種空間關系的空間目標的過程。開放地理信息系統協會（Open GIS Consortium，OGC）制定的開源GIS實施標準協議中規定，兩個空間幾何體之間的空間關系，需要通過基于維度擴展九交模型（DimensionallyExtended9-Intersection Model，DE-9IM）進行判斷。

在諸多開源的GIS代碼庫中，幾乎全部使用plane sweep算法及其衍生算法獲取兩個幾何體間的DE-9IM信息。但由于plane sweep算法其本身的逐一掃描特性，致使其無法適應并行化加速改造，也因此無法移植到異構多核架構上。為解決上述問題，需要從可以實現數據并行的方面入手，構建一套全新的并行技術。本發明對于海量多邊形數據間空間關系查詢算法的并行化改造，正是基于CPU+GPU架構，利用其強大的并行計算能力，大批量處理線段相交運算，從而更快得到所有滿足查詢條件的多邊形數據。

發明內容

本發明的技術解決問題是：克服現有空間關系查詢技術不具備并行化改造條件，無法適應CPU+GPU架構的不足，設計了一種基于CPU+GPU架構的多邊形數據空間關系查詢并行系統，解決了空間關系查詢技術的并行化改造問題，可以利用CPU+GPU架構強大的并行計算能力，加速海量多邊形數據間空間關系查詢處理。

本發明的技術解決方案：一種基于CPU+GPU架構的多邊形數據空間關系查詢并行系統，包括：線段間相交分析模塊、環間拓撲關系分析模塊、多邊形間DE-9IM計算模塊和圖層間空間關系查詢模塊，其中：

線段間相交分析模塊：對于輸入的兩個海量多邊形圖層數據，分別遍歷提取兩個海量多邊形圖層數據中所有多邊形的線段信息，將不屬于同一圖層的獨立線段兩兩組合，利用CPU+GPU架構的并行計算技術，對所有線段組合進行并行分析，得到所有相交線段集合及其相交種類，分析過程中排除不相交的線段組合，只記錄所有相交的線段組合，同時記錄它們的相交種類；線段相交種類分為為四大類：若交點不是兩條線段的四個端點中的任何一點，則為普通相交；若交點是兩條線段的四個端點中的一點，則為丁字相交；若交點是兩條線段的四個端點中的兩點，則為連接相交；若兩條線段有公共重合線段，則為疊置相交；最終輸出為所有相交線段集合，供環間拓撲關系分析模塊調用；