[發明專利]一種基于GPU的地形可視域分析的數據調度與分發方法

有效

• 申請號: 201710119522.7
• 申請日: 2017-03-02
• 公開（公告）號: CN106971369B
• 公開（公告）日: 2020-06-12
• 發明（設計）人: 竇萬峰;李亞楠
• 申請（專利權）人: 南京師范大學
• 主分類號: G06T1/20
• 分類號: G06T1/20;G06F9/38;G06T7/00
• 代理公司: 南京經緯專利商標代理有限公司 32200
• 代理人: 朱楨榮

本發明公開了一種基于GPU的地形可視域分析的數據調度與分發方法，具體如下：確定以視點為中心按照90°角度的三角形區域進行劃分；對于每個三角形區域數據，按照以視點為參照點和區域特征選擇行數據塊調度或列數據塊分發方法；對于行數據塊調度，CPU進程按行方式計算數據段和讀取數據，并分發給GPU設備，并啟動大量GPU線程進行并行計算；對于列數據塊調度，進程按列方式計算數據段和讀取數據，并發給GPU設備，并啟動大量GPU線程進行并行計算。本發明的數據調度方法可以保證數據單向依賴，使得后續的調度方法能有效實現并行可視域分析，提高了地形可視域分析的效率。本發明可應用于大規模海量數據的并行地形可視域分析的高性能計算的數據動態調度場合。

技術領域

本發明涉及數字地形分析的可視域分析和并行計算的交叉技術領域，特別是一種基于GPU的地形可視域分析的數據調度與分發方法。

背景技術

數字地形分析(Digital Terrain Analysis，簡稱DTA)是在數字高程模型(Digital Elevation Model，簡稱DEM)的基礎上進行地形屬性計算和特征提取的數字信息處理技術。可視性分析是數字地形分析的重要地形分析因子，包括通視性分析和可視域分析。其中，可視域分析又稱地形通視分析，指的是從單個或者多個地理位置所能看到的地形范圍或者與其他地理位置之間的可見程度，是數字地形分析中的不可缺少的一部分。地形可視域分析在很多相關領域都有比較重要的意義，已經成為景觀分析與評估、建筑規劃、軍事、空間認知與決策、考古等領域的重要研究手段。由于可視域分析算法中具有的數據的全局依賴特性和局部數據依賴特性，可視性分析并行化過程中所面臨的各種復雜的問題需要考慮，已有的并行化手段無法徹底解決這一問題，同時在并行數字地形分析的大環境下，大尺度下的復雜數據依賴問題逐漸成為制約相關算法加速效果進一步提升的瓶頸。

并行可視域分析是使用并行計算的技術來解決可視域分析中的海量數據量的高效處理問題。隨著各種新型傳感器以及測量技術的出現，DEM數據呈級數增長，從而導致單機環境下對大規模的數據進行處理是一件十分困難的事情。因此使用并行計算技術可以有效地解決單處理器的計算瓶頸問題以及提高數據處理的效率。基于規則格網DEM的可視域計算，一種簡單的方法就是沿著視線的方向，從視點開始到目標格網點，計算與視線相交的格網單元(邊或面)，判斷相交的格網單元是否可視，從而確定視點與目標視點之間是否可視。該方法存在大量的冗余計算，導致海量規則格網DEM的可視域計算非常耗時。XDraw算法是一種近似的可視域分析算法，可以采用并行化的方法進行計算，大大提高計算的效率。

GPU(Graphics Processing Unit)主要是用于圖形計算的處理單元，圖形計算通常是并行的，因此GPU的結構設計盡可能具有好的并行計算能力。Nvidia公司開發的GPU結構如圖1所示。通常，GPU被設計探究數據并行化，并能達到CPU10倍的FLOPS能力。CUDA(Compute Unified Device Architecture)是一個編程框架，其設計目的不僅是使用計算機的圖形處理單元所具有的快速圖形渲染能力，而是其強大的計算能力，也稱為通用目的GPU編程。CUDA僅支持Nvidia GPU計算，而且數據密集型的應用得益于GPU的高帶寬內存，其能夠進行I/O管理功能，因而增強I/O性能。CUDA線程模型如圖2所示，其被設計適用于數據密集型的空間分析，例如數字地形分析。