Parallel algorithm of raster river network extraction based on CUDA

doi:10.11772/j.issn.1001-9081.2015.04.0960

Journal of Computer Applications ›› 2015, Vol. 35 ›› Issue (4): 960-963.DOI: 10.11772/j.issn.1001-9081.2015.04.0960

Previous Articles Next Articles

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-10 Published:2015-04-08

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

王玉着, 刘修国, 张唯

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

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

Abstract

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

摘要：

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

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

CLC Number:

TP333.9

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.

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

References

[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]	XIE Wenbo, WEI Yongzhuang, LIU Zhenghong. Parallel implementation and analysis of SKINNY encryption algorithm using CUDA [J]. Journal of Computer Applications, 2021, 41(4): 1136-1141.
[2]	YANG Xianfeng, GUI Hongjun, FU Chunchang. F-X domain predictive filtering parallel algorithm based on compute unified device architecture [J]. Journal of Computer Applications, 2021, 41(2): 486-491.
[3]	ZENG Zhiyang, CHEN Yan, WANG Ke. Design and implementation of parallel genetic algorithm for cutting stock of circular parts [J]. Journal of Computer Applications, 2020, 40(2): 392-397.
[4]	CUI Yixin, CHEN Xiaodong. Spark framework based optimized large-scale spectral clustering parallel algorithm [J]. Journal of Computer Applications, 2020, 40(1): 168-172.
[5]	HE Xi, WU Yantao, DI Zhenwei, CHEN Jia. GPU-based morphological reconstruction system [J]. Journal of Computer Applications, 2019, 39(7): 2008-2013.
[6]	CHENG Lu, ZHOU Bo. Slope unit extraction algorithm based on texture watershed [J]. Journal of Computer Applications, 2019, 39(6): 1810-1815.
[7]	SHA Zongxuan, XUE Fei, ZHU Jie. Scheduling strategy of cloud robots based on parallel reinforcement learning [J]. Journal of Computer Applications, 2019, 39(2): 501-508.
[8]	WANG Peng, ZHOU Yan. MPI big data processing for high performance applications [J]. Journal of Computer Applications, 2018, 38(12): 3496-3499.
[9]	ZHANG Runlian, ZHANG Xin, ZHANG Chuyun, XI Yuang. Path planning algorithm based on distance and slope in regular Grid digital elevation model [J]. Journal of Computer Applications, 2018, 38(11): 3188-3192.
[10]	HAN Litao, LIU Hailong, KONG Qiaoli, YANG Fanlin. Parallel algorithm for hillshading under multi-core computing environment [J]. Journal of Computer Applications, 2017, 37(7): 1911-1915.
[11]	JIAO Jiafeng, LI Yun. Review of typical machine learning platforms for big data [J]. Journal of Computer Applications, 2017, 37(11): 3039-3047.
[12]	ZHAO Yongtao, CHEN Qingkui, FANG Yuling, ZHAO Deyu, JI Lina. Early warning method for driving safety based on CUDA [J]. Journal of Computer Applications, 2017, 37(1): 134-137.
[13]	JI Lina, CHEN Qingkui, CHEN Yuanjing, ZHAO Deyu, FANG Yuling, ZHAO Yongtao. Real-time crowd counting method from video stream based on GPU [J]. Journal of Computer Applications, 2017, 37(1): 145-152.
[14]	XUE Jun, DUAN Fajie, JIANG Jiajia, LI Yanchao, YUAN Jianfu, WANG Xianquan. Parallel cyclic redundancy check Verilog program generating method based on Matlab [J]. Journal of Computer Applications, 2016, 36(9): 2503-2507.
[15]	XING Shuning, LIU Fang'ai, ZHAO Xiaohui. Parallel high utility pattern mining algorithm based on cluster partition [J]. Journal of Computer Applications, 2016, 36(8): 2202-2206.

Parallel algorithm of raster river network extraction based on CUDA

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

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics