針對空間遙感技術的快速發(fā)展導致地理空間數據呈幾何級數增長,傳統(tǒng)GIS空間分析面臨巨大的計算實時性需求的問題,該文為提高GIS數字地形分析算法在處理海量高分辨率DEM數據時的計算效率,基于CUDA眾核流處理器并行編程模型,采用不同數據劃分方法、紋理內存及異步數據傳輸機制等技術,對串行D8算法進行了并行化設計及算法優(yōu)化,探索并分析了D8并行算法的數據拷貝與算法執(zhí)行等環(huán)節(jié)的計算效率變化。實驗結果表明,CUDA并行編程能夠對D8算法實現(xiàn)較為明顯的加速,在按5個行子塊進行劃分、調用1 344個線程時并行加速效果達到最佳,加速比為19.5。并且,在不同行子塊劃分方式下且調用線程數不超過1 344個時,加速比隨調用線程數的增加而增長,計算時間占比隨線程數的增加呈遞減趨勢。 

【文章來源】：測繪科學. 2020,45(03)北大核心CSCD

【文章頁數】：7 頁

【部分圖文】：

部分DEM高程值與方向編碼值

1)數據并行。數據并行的關鍵是數據劃分,優(yōu)秀的數據劃分方法能夠有效提升算法的計算效率,在串行算法并行化中極為重要。本文所用DEM數據為m行、m列的規(guī)則矩陣形式,在設備端使用二維CUDA數組進行存儲。一般說來,數據劃分有規(guī)則劃分和不規(guī)則劃分兩類方法[22]。規(guī)則劃分包括按行、按列以及二維塊劃分,不規(guī)則劃分是根據DEM中地貌地形特征來劃分的,本文根據D8算法的特點采用規(guī)則格網劃分方法,運用基于行模式的GDAL庫對數據進行讀寫,由于其在行方向上讀寫效率高,研究選取行為單位的條帶式劃分方法,如圖2所示。2)異步傳輸。GPU擁有大量的流處理器單元,使其在密集型計算方面有著顯著的優(yōu)勢,計算效率較高。然而GPU本身無法直接獲取數據,需要從主機端接收,受主機內存與GPU顯存之間的帶寬的限制,兩者之間數據拷貝速度遠低于GPU的計算速度,這在一定程度上限制了D8算法計算的加速比的上升。因此,為了進一步提升D8算法的整體效率,引入了異步傳輸模式[23],以降低數據復制與核函數執(zhí)行之間的相互等待時間。

3)紋理內存。紋理內存是CUDA編程模型獨有的一種只讀內存,針對二維空間的局部性訪問會獲得加速,且適用于大量數據的隨機和非對齊訪問。DEM柵格數據由CUDA數組進行存儲,使用紋理參考實現(xiàn)紋理坐標與格網柵格數據數組的映射綁定。流向計算過程中只需通過紋理拾取訪問不同紋理坐標值,即可讀取到對應不同柵格單元及其鄰接柵格數據,無需進行多個存儲器之間的數據交換,降低額外時間開銷,提高計算效率。如圖4所示,數據已進行紋理綁定,右側中間4個地址不連續(xù),但通過紋理拾取進行訪問會獲得一定的加速效果。在為核函數分配線程數目時,根據DEM數據的數據量大小及GPU流處理器核心的數目來確定。并行算法的流程設計如圖5所示。

【參考文獻】：
期刊論文
[1]CUDA環(huán)境下地形因子的并行計算[J]. 陳亮,趙磊,李珂.  北京測繪. 2017(04)
[2]多種數據劃分方法下D8算法的多核并行化實驗對比[J]. 高琪,范俊甫,何惠馨,孔維華,周玉科.  地理與地理信息科學. 2017(02)
[3]基于GPU的RFT算法并行化[J]. 商哲然,譚賢四,曲智國,王紅,豐驍.  雷達科學與技術. 2016(05)
[4]CPU/GPU異構混合并行的柵格數據空間分析研究——以地形因子計算為例[J]. 盧敏,王金茵,盧剛,陶偉東,王結臣.  計算機工程與應用. 2017(01)
[5]基于GPU的二維矢量場LIC算法研究[J]. 陳丁,萬剛,王龍,趙宸立.  測繪工程. 2015(03)
[6]格網DEM水系提取并行算法研究[J]. 江嶺,劉學軍,陽建逸,劉凱,宋效東.  地理與地理信息科學. 2013(04)
[7]地形分析中坡度坡向算法并行化方法研究[J]. 江嶺,劉學軍,湯國安,宋效東.  計算機工程與科學. 2013(04)
[8]DEM與地形分析的并行計算[J]. 宋效東,劉學軍,湯國安,王永君,田劍,竇萬峰.  地理與地理信息科學. 2012(04)
[9]一個基于DEM的數字河網體系提取算法的應用[J]. 崔青春,吳孟泉,孔祥生,張麗.  計算機技術與發(fā)展. 2011(06)
[10]利用CUDA的地圖代數局部算子優(yōu)化[J]. 張劍波,楊文鑫,周斯波,張帥.  測繪科學. 2012(02)

博士論文
[1]基于DEM的流域地形分析并行算法關鍵技術研究[D]. 江嶺.南京師范大學 2014

碩士論文
[1]并行數字地形分析數據劃分方法研究[D]. 張剛.南京師范大學 2014



本文編號：3301821