统一设备计算架构下的栅格河网提取并行算法

doi:10.11772/j.issn.1001-9081.2015.04.0960

计算机应用 ›› 2015, Vol. 35 ›› Issue (4): 960-963.DOI: 10.11772/j.issn.1001-9081.2015.04.0960

统一设备计算架构下的栅格河网提取并行算法

王玉着, 刘修国, 张唯

中国地质大学(武汉) 信息工程学院, 武汉 430074

收稿日期:2014-10-21 修回日期:2015-01-07 发布日期:2015-04-08 出版日期:2015-04-10
通讯作者: 张唯
作者简介:王玉着(1984-),女,安徽宿州人,博士研究生,主要研究方向:栅格数据空间分析、高性能计算; 刘修国(1969-),男,河南潢川人,教授,博士,主要研究方向:遥感数据处理、信息快速提取; 张唯(1980-),女,湖北孝感人,讲师,博士,主要研究方向:数字地形、空间统计分析。
基金资助:
国家科技支撑计划项目(2011BAH06B04);国家自然科学基金资助项目(41001225)。

Parallel algorithm of raster river network extraction based on CUDA

WANG Yuzhuo, LIU Xiuguo, ZHANG Wei

College of Information Engineering, China University of Geosciences, Wuhan Hubei 430074, China

Received:2014-10-21 Revised:2015-01-07 Online:2015-04-08 Published:2015-04-10

摘要/Abstract

摘要：

针对大规模高分辨率数字地形数据提取栅格河网效率低下的问题,提出了基于统一设备计算架构(CUDA)利用淹没模型提取栅格河网的并行算法。使用图形处理器(GPU)将汇流累积量计算分解为独立的多任务并行处理,通过数据异步传输减少数据交换时间,进而加速河网提取的运算。实验结果表明,该算法运行效率明显优于串行河网提取算法,在NVIDIA Geforce GTX660上对数据量为600 MB(网格大小为9784×8507)数字高程模型(DEM)数据提取河网加速比达到62。

关键词: 统一设备计算架构, 数字高程模型, 栅格河网, D8算法, 并行计算

Abstract:

Concerning the low efficiency of calculating flow accumulation on high resolution digital terrain data, a parallel algorithm was put forward based on the Compute Unified Device Architecture (CUDA) and flooding model. Based on the technology of Graphic Processing Unit (GPU), two strategies were designed to improve the speed of the extraction. Firstly, the calculation of flow accumulation was divided into a plurality of independent tasks for parallel processing. Secondly, the time of data exchange was reduced through the asynchronous data transmission. The experimental results show that the efficiency of the parallel algorithm is superior of the serial algorithm. The acceleration of river network extraction reached 62 times in NVIDIA Geforce GTX660 for 600 MB DEM data with 9784×8507 grid size.

Key words: Compute Unified Device Architecture (CUDA), Digital Elevation Model (DEM), raster river network, D8 algorithm, parallel computing

中图分类号:

TP333.9

王玉着, 刘修国, 张唯. 统一设备计算架构下的栅格河网提取并行算法[J]. 计算机应用, 2015, 35(4): 960-963.

WANG Yuzhuo, LIU Xiuguo, ZHANG Wei. Parallel algorithm of raster river network extraction based on CUDA[J]. Journal of Computer Applications, 2015, 35(4): 960-963.

参考文献

[1] CHOI Y. A new algorithm to calculate weighted flow-accumulation from a DEM by considering surface and underground stormwater infrastructure[J]. Environmental Modelling and Software,2012,30:81-91.
[2] SHI X, YANG Z, YAN D, et al. On hydrological response to land-use/cover change in Luanhe river basin[J]. Advances in Water Science, 2014, 25(1):21-27.(史晓亮,杨志勇,严登华,等. 滦河流域土地利用/覆被变化的水文响应[J]. 水科学进展, 2014, 25(1):21-27.)
[3] SONG Y, LI Z, YANG T. Application of distributed hydrological model to flood forecasting for upper reaches of the Huaihe river above Hongze lake[J]. Journal of Hohai University: Natural Science,2006,34(2):127-131.(宋玉,李致家,杨涛. 分布式水文模型在淮河洪泽湖以上流域洪水预报中的应用[J]. 河海大学学报:自然科学版, 2006,34(2):127-131.)
[4] ZUO J, CAI Y. An automated watershed delineations approach for plain river network regions: a case study in Shanghai[J]. Advances in Water Science,2011,22(3):337-343.(左俊杰,蔡永立.平原河网地区汇水区的划分方法:以上海市为例[J].水科学进展, 2011, 22(3):337-343.)
[5] DO H T, LIMET S, MELIN E. Parallel computing flow accumulation in large digital elevation models[J]. Procedia Computer Science,2011,4:2277-2286.
[6] XU R, HUANG X, LUO L, et al. A new grid-associated algorithm in distributed hydrological model simulations[J]. Science in China Series E: Technological Sciences, 2010, 53(1):235-241.
[7] ORTEGA L, RUEDA A. Parallel drainage network computation on CUDA[J].Computers and Geosciences, 2010,36(2):171-178.
[8] QIN C, ZHAN L. Parallelizing flow-accumulation calculations on graphics processing units — from iterative DEM preprocessing algorithm to recursive multiple-flow-direction algorithm[J]. Computers and Geosciences, 2012, 43:7-16.
[9] RUEDA A, NOGUERA J M, MARTINEZ-CRUZ C. A flooding algorithm for extracting drainage networks from unprocessed digital elevation models[J]. Computers and Geosciences, 2013, 59:116-123.
[10] CUI X, CHARLES J S, POTOK T. GPU enhanced parallel computing for large scale data clustering[J]. Future Generation Computer Systems, 2013,29(7):1736-1741.
[11] ZHANG J, ZHOU S, YUAN G, et al. Parallel processing mapping strategy of spatial analysis under the heterogeneous environment[J]. Journal of Shanghai Jiaotong University,2013,47(1):70-75.(张剑波,周斯波,袁国斌,等. 异构环境下的空间分析并行映射策略[J].上海交通大学学报, 2013,47(1):70-75.)
[12] LIU Y. Thinking from spatial analysis to spatial decision-making[J]. Geomatics and Information Science of Wuhan University,2007,32(11):1050-1055.(刘耀林.从空间分析到空间决策的思考[J].武汉大学学报:信息科学版,2007,32(11):1050-1055.)
[13] ZHENG J, AN X, HUANG M. GPU-based parallel algorithm for particle contact detection and its application in self-compacting concrete flow simulations[J]. Computers and Structures, 2012, 112-113:193-204.

[1]	张润莲, 张密, 武小年, 舒瑞. 基于GPU的大状态密码S盒差分性质评估方法[J]. 《计算机应用》唯一官方网站, 2024, 44(9): 2785-2790.
[2]	刘乾, 张洋铭, 万定生. 网格化分布式新安江模型并行计算算法[J]. 《计算机应用》唯一官方网站, 2023, 43(11): 3327-3333.
[3]	姜松岩, 廖晓鹃, 陈光柱. 基于可满足性模理论的多处理机通信延迟优化任务调度方法[J]. 《计算机应用》唯一官方网站, 2023, 43(1): 185-191.
[4]	蔡婧雯, 韦永壮, 刘争红. 基于GPU的密码S盒代数性质评估方法[J]. 《计算机应用》唯一官方网站, 2022, 42(9): 2750-2756.
[5]	邱鑫源, 叶泽聪, 崔翛龙, 高志强. 联邦学习通信开销研究综述[J]. 《计算机应用》唯一官方网站, 2022, 42(2): 333-342.
[6]	徐启迪, 刘争红, 郑霖. 基于GPU的低密度奇偶校验码译码加速技术[J]. 《计算机应用》唯一官方网站, 2022, 42(12): 3841-3846.
[7]	解文博, 韦永壮, 刘争红. 基于CUDA的SKINNY加密算法并行实现与分析[J]. 计算机应用, 2021, 41(4): 1136-1141.
[8]	杨先凤, 贵红军, 傅春常. 统一计算设备架构下的F-X域预测滤波并行算法[J]. 计算机应用, 2021, 41(2): 486-491.
[9]	曾志阳, 陈燕, 王珂. 圆片下料并行遗传算法的设计与实现[J]. 《计算机应用》唯一官方网站, 2020, 40(2): 392-397.
[10]	崔艺馨, 陈晓东. Spark框架优化的大规模谱聚类并行算法[J]. 计算机应用, 2020, 40(1): 168-172.
[11]	何希, 吴炎桃, 邸臻炜, 陈佳. 基于图形处理器的形态学重建系统[J]. 计算机应用, 2019, 39(7): 2008-2013.
[12]	程露, 周波. 基于纹理分水岭的斜坡单元提取算法[J]. 计算机应用, 2019, 39(6): 1810-1815.
[13]	沙宗轩, 薛菲, 朱杰. 基于并行强化学习的云机器人任务调度策略[J]. 计算机应用, 2019, 39(2): 501-508.
[14]	冯凯, 李婧. k元n方体的可靠性评估[J]. 计算机应用, 2019, 39(11): 3323-3327.
[15]	付朝江, 王天奇, 林悦荣. 基于有效并行求解策略的显式有限元分析并行算法[J]. 计算机应用, 2018, 38(4): 1072-1077.

统一设备计算架构下的栅格河网提取并行算法

Parallel algorithm of raster river network extraction based on CUDA

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics