基于CUDA的地表水动态模拟并行方法
吴钱娇(1990— ),女,安徽铜陵人,博士生,主要从事数字地形分析方面的研究。E-mail:qianjiaowu@whu.edu.cn |
收稿日期: 2019-09-06
要求修回日期: 2019-12-11
网络出版日期: 2020-05-18
基金资助
国家自然科学基金项目(41671380)
版权
A Parallel Method of Surface Flow Dynamics Simulation based on CUDA
Received date: 2019-09-06
Request revised date: 2019-12-11
Online published: 2020-05-18
Supported by
National Natural Science Foundation of China(41671380)
Copyright
如何高效地动态监测、模拟和预测地表水过程是防灾减灾中亟待解决的问题,也是科学化的国土整治、区域规划、环境保护和水资源管理的基础。因此,本文利用统一计算设备架构(CUDA)对基于不规则三角网(TIN)的地表水动态模拟算法进行并行化改进,提出了一种基于CUDA的地表水动态模拟并行方法,旨在对任意时刻的地表水进行快速、高精度的动态模拟,从而满足实际的应用需求。该算法从高精度的数字高程模型(DEM)中提取地形特征点和流域线,生成受流域线约束的TIN。在此基础上,根据TIN表面的三角面坐标数据获取水流方向,再结合任意位置的降雨源点追踪得到流水线网络。基于曼宁公式,利用流水线流速计算核函数得到每条流水线上雨滴的流速,结合预设的时间,利用汇流量统计核函数得到该时刻的地表汇流量。具体的并行化过程包括数据的传输,CUDA中线程的划分和流水线流速计算核函数和汇流量统计核函数的实现。本文选取位于加拿大新布伦瑞克西北部的BBW(Black Brook Watershed)流域作为实验样区,将该算法与改进前的方法进行对比表明,该模型在保持精度的同时,大幅提高了模拟效率,加速比达到11.2;另外,通过与SWAT(Soil and Water Assessment Tool)模型进行对比,结果表明,该并行方法的Nash系数提高了88%,相关系数提高了5%。
关键词: 数字高程模型(DEM); 统一计算设备架构(CUDA); 不规则三角网(TIN); 地表水动态模拟; 汇流量; 流水线; 流速; 加速比
吴钱娇 , 陈玉敏 . 基于CUDA的地表水动态模拟并行方法[J]. 地球信息科学学报, 2020 , 22(3) : 505 -515 . DOI: 10.12082/dqxxkx.2020.190500
Simulating the surface flow dynamics is of great importance in disaster prevention and mitigation, which could benefit the land remediation, regional planning, environmental protection and water resource management. Therefore, in this paper the Compute-Unified-Device-Architecture (CUDA) is embedded into the TIN-based surface flow dynamic simulation algorithm to get a parallel method for simulating the surface flow discharge. The aim of this study is to rapidly and accurately perform the surface flow dynamic simulation at any position and any time to meet the actual application requirements. First, the proposed algorithm extracts the critical points and drainage network from a high-precision Digital Elevation Model (DEM) to generate a drainage-constrained Triangulated Irregular Network (TIN). Second, the flow direction of each triangular facet over the TIN is calculated by the coordinate data of the triangular facets. Third, the flow path network is traced by the flow direction and rainfall source points. Fourth, the flow velocity of rain dropsover the flow paths is obtained by the flow velocity calculation kernel function based on the manning formula. Finally, by combing the flow velocity with the pre-set time, the algorithm can rapidly simulate the flow discharge at any location by usingthe flow discharge count kernel function. The specific paralle lization process consists of the transmission mode of data, partition model of thread and implement ation of the flow velocity calculation kernel function and flow discharge count kernel function. Data transmission in the paralle lization process includes the input and output of data. It inputs the data of the DEM, rainfall source points and flow path network from the CPU to GPU and outputs the data of the flow discharge calculated by the above two kernel functions from the GPU to CPU. The two kernel functions are parallelized by the flow paths. Each thread handles a single flow path. As a result, flow paths are divided by the partitioning method to obtain numerous thread blocks and the number of the thread in each thread block is allocated by the computing power of the GPU. The Black Brook Watershed (BBW) located in the north-eastern of New Brun swick was selected as the study area. To validate its accuracy and efficiency, the proposed method was compared with TIN-based surface flow dynamic simulation method. The experimental results demonstrate that the proposed algorithm can greatly improve the simulation efficiency while maintaining the accuracy simultaneously and its acceleration ratio can reach up to 11.2. In addition, the parallel algorithm was compared with the Soil and Water Assessment Tool (SWAT) model to verify its precision. The experimental results indicate that the Nash coefficient of the parallel method is increased by 88% and the correlation coefficient is increased by 5%.
算法 1 流水线流速计算核函数 |
---|
Input: number of the flow lines (e.g. flineNum), the location of the flow line (e.g. flineTrackSize[]), the break points of the flow line (e.g. flowTrack[]),range of the DEM (e.g. xMin, Ymax), the resolution of the DEM (e.g. dx, dy), the width of the DEM (e.g. imgWidth), the runoff of the rainfall source points (e.g. rVal) 1: idx = blockIdx.x * blockDim.x + threadIdx.x 2: idy = threadIdx.y 3: id= idy*(gridDim.x * blockDim.x) + idx 4: ifid>flineNum 5: terminate 6:ifid > 0 7: Calculate the index of the flow line over flow track network (e.g. flineStart = flineTrackSize[id-1]) 8: Calculate the start point of the flow line over flow track network (e.g. sP = flowTrack[flineStart) 9: Calculate the column and row of the start point (e.g. col = (sP.x-xMin)/dx, row = (yMax-sP.y)/dy) 10: Calculate the runoff of the start point (e.g. pRVal = rVal[row*imgWidth+col]) 11:ifpRVal> 0 12:Calculate the flow velocity by the Manning’s equation 13: Calculate the discharge of the start point’s location after time interval (e.g. fVal[]=pRVal) |
Obtain: the discharge of all of the start points after everytime interval(e.g. fVal[]) |
算法 2 汇流量统计核函数 |
---|
Input: number of the flow lines (e.g. flineNum), the location of the flow line (e.g. flineTrackSize[]),the width of height of the DEM (e.g. imgWidth, imgHeight),range of the DEM (e.g. xMin, Ymax), the resolution of the DEM (e.g. dx, dy), the width of the DEM (e.g. imgWidth), the discharge of all of the start pointsafter every time interval(e.g. fVal[]) 1: idx = blockIdx.x * blockDim.x + threadIdx.x 2: idy = threadIdx.y 3: id = idy*(gridDim.x * blockDim.x) + idx 4: if id >flineNum 5: terminate 6: Calculate the index of the flow line over flow track network (e.g. flineStart = flineTrackSize[id-1]) 7: Calculating the index of all of the raindrops (e.g. runP=flowTracks[flineStart+rainIdx[]]) 8: Calculate the row and height of all the raindrops(e.g. col= (runP.x-xMin)/dx, row= (yMax-runP.y)/dy) 9: Calculate the discharge of all grid cells (e.g. pOutDis[]+=fVal[]) |
Output: the discharge of all grid cells (e.g. pOutDis[]) |
表1 BBW流域的不同阈值下TIN的精度结果Tab.1 The accuracy of TIN under different thresholds on the BBW |
阈值/m | 0.5 | 1.0 | 1.5 | 2.0 | 2.5 |
---|---|---|---|---|---|
特征点数量/个 | 10 859 | 4295 | 2149 | 1268 | 822 |
TIN表面三角面的数量/个 | 23 348 | 11 079 | 6854 | 5139 | 4285 |
RMSE/m | 0.17 | 0.31 | 0.45 | 0.58 | 0.73 |
表2 BBW流域出口水汇流量模拟精度的评价对比结果Tab. 2 Accuracy comparison of simulating the flow discharge at the outlet of the BBW |
阈值/m | 算法 | 模型 | 降雨源点尺度/m | ||||
---|---|---|---|---|---|---|---|
10 | 15 | 20 | 25 | 30 | |||
0.5 | 基于TIN的地表 水动态模拟算法 | N | 0.77 | 0.77 | 0.77 | 0.77 | 0.77 |
R | 0.91 | 0.91 | 0.91 | 0.91 | 0.91 | ||
B | 1.30 | 1.31 | 1.31 | 1.30 | 1.30 | ||
基于CUDA的地表水动态模拟并行方法 | N | 0.77 | 0.77 | 0.77 | 0.77 | 0.77 | |
R | 0.91 | 0.91 | 0.91 | 0.91 | 0.91 | ||
B | 1.30 | 1.31 | 1.31 | 1.30 | 1.30 | ||
1.0 | 基于TIN的地表 水动态模拟算法 | N | 0.77 | 0.77 | 0.77 | 0.77 | 0.77 |
R | 0.91 | 0.91 | 0.91 | 0.91 | 0.91 | ||
B | 1.31 | 1.31 | 1.31 | 1.31 | 1.31 | ||
基于CUDA的地表水动态模拟并行方法 | N | 0.77 | 0.77 | 0.77 | 0.77 | 0.77 | |
R | 0.91 | 0.91 | 0.91 | 0.91 | 0.91 | ||
B | 1.31 | 1.31 | 1.31 | 1.31 | 1.31 | ||
1.5 | 基于TIN的地表 水动态模拟算法 | N | 0.77 | 0.77 | 0.77 | 0.77 | 0.77 |
R | 0.91 | 0.91 | 0.91 | 0.91 | 0.91 | ||
B | 1.31 | 1.31 | 1.32 | 1.32 | 1.31 | ||
基于CUDA的地表水动态模拟并行方法 | N | 0.77 | 0.77 | 0.77 | 0.77 | 0.77 | |
R | 0.91 | 0.91 | 0.91 | 0.91 | 0.91 | ||
B | 1.31 | 1.31 | 1.32 | 1.32 | 1.31 | ||
2.0 | 基于TIN的地表 水动态模拟算法 | N | 0.77 | 0.77 | 0.77 | 0.77 | 0.77 |
R | 0.91 | 0.91 | 0.91 | 0.91 | 0.91 | ||
B | 1.31 | 1.32 | 1.31 | 1.32 | 1.31 | ||
基于CUDA的地表水动态模拟并行方法 | N | 0.77 | 0.77 | 0.77 | 0.77 | 0.77 | |
R | 0.91 | 0.91 | 0.91 | 0.91 | 0.91 | ||
B | 1.31 | 1.32 | 1.31 | 1.32 | 1.31 | ||
2.5 | 基于TIN的地表 水动态模拟算法 | N | 0.77 | 0.77 | 0.77 | 0.77 | 0.77 |
R | 0.91 | 0.91 | 0.91 | 0.91 | 0.91 | ||
B | 1.31 | 1.31 | 1.32 | 1.32 | 1.32 | ||
基于CUDA的地表水动态模拟并行方法 | N | 0.77 | 0.77 | 0.77 | 0.77 | 0.77 | |
R | 0.91 | 0.91 | 0.91 | 0.91 | 0.91 | ||
B | 1.31 | 1.31 | 1.32 | 1.32 | 1.32 |
表3 SWAT模型的精度评价结果(DEM为30 m)Tab. 3 Statistical factors utilized to assess the precision of SWAT model (scale of DEM is 30 m) |
评价参数 | |||
---|---|---|---|
N | R | B | |
SWAT | 0.41 | 0.87 | 0.96 |
表4 BBW流域出口水汇流量模拟的运行时间统计结果Tab. 4 Computation performance of simulating the flow discharge at the outlet of the BBW (s) |
阈值/m | 算法 | 降雨源点尺度/m | ||||
---|---|---|---|---|---|---|
10 | 15 | 20 | 25 | 30 | ||
0.5 | 基于TIN的地表水动态模拟算法 | 953.82 | 425.37 | 278.18 | 213.77 | 169.77 |
基于CUDA的地表水动态模拟并行方法 | 93.16 | 43.49 | 28.34 | 22.72 | 19.00 | |
1.0 | 基于TIN的地表水动态模拟算法 | 912.16 | 407.40 | 278.21 | 203.25 | 159.87 |
基于CUDA的地表水动态模拟并行方法 | 86.32 | 42.75 | 27.72 | 21.23 | 18.47 | |
1.5 | 基于TIN的地表水动态模拟算法 | 899.07 | 395.99 | 267.96 | 196.33 | 159.60 |
基于CUDA的地表水动态模拟并行方法 | 80.51 | 41.88 | 27.23 | 20.74 | 17.88 | |
2.0 | 基于TIN的地表水动态模拟算法 | 893.92 | 396.22 | 270.80 | 198.07 | 159.21 |
基于CUDA的地表水动态模拟并行方法 | 86.14 | 43.86 | 28.01 | 21.39 | 17.95 | |
2.5 | 基于TIN的地表水动态模拟算法 | 892.59 | 400.38 | 260.40 | 199.60 | 164.56 |
基于CUDA的地表水动态模拟并行方法 | 85.61 | 43.60 | 27.77 | 20.80 | 17.29 |
图10 模拟结果的相关系数分布Fig. 10 Correlation coefficient distribution map of simulation results |
[1] |
|
[2] |
|
[3] |
|
[4] |
|
[5] |
|
[6] |
|
[7] |
|
[8] |
王纲胜, 夏军, 谈戈 , 等. 潮河流域时变增益分布式水循环模型研究[J]. 地理科学进展, 2002,21(6):573-582.
[
|
[9] |
|
[10] |
|
[11] |
|
[12] |
|
[13] |
|
[14] |
|
[15] |
|
[16] |
蔡明勇 . DTVGM模型参数的遥感驱动研究与应用[D]. 北京:北京师范大学, 2011: 14-16.
[
|
[17] |
|
[18] |
|
[19] |
|
[20] |
|
[21] |
陈玉敏, 吴钱娇, 巴倩倩 , 等. 多尺度地表水动态模拟及应用[J]. 测绘学报, 2015,44(S0):36-41.
[
|
[22] |
|
[23] |
|
[24] |
NVIDIA Corporation. NVIDIA CUDA C Best Practice Guide[M]. Santa Clara, California: NVIDIA Corporation, 2010.
|
[25] |
NVIDIA Corporation. NVIDIA CUDA C Programming Guide[M]. Santa Clara, California: NVIDIA Corporation, 2010.
|
[26] |
|
[27] |
|
[28] |
|
[29] |
王浩, 王含宇, 杨名宇 , 等. Retinex图像增强在GPU平台上的实现[J]. 地球信息科学学报, 2019,21(4):623-629.
[
|
[30] |
|
[31] |
|
[32] |
刘扬, 付征叶, 郑逢斌 . 高分辨率遥感影像目标分类与识别研究进展[J]. 地球信息科学学报, 2015,17(9):1080-1091.
[
|
[33] |
|
[34] |
|
[35] |
|
[36] |
赵向辉, 苗青, 付忠良 , 等. 基于CUDA的汇流分析并行算法的研究与方法[J]. 计算机应用研究, 2010,27(7):2445-2451.
[
|
[37] |
|
[38] |
|
[39] |
|
[40] |
|
[41] |
|
[42] |
国家测绘局测绘标准化研究所. CH/T1008—2001基础地理信息数字产品1:10 000, 1:50 000数字高程模型[S]. 北京:国家测绘局, 2001.
[ State Bureau of Surveying and Mapping. 1:10000 and 1:50000 digital elevation model. The Basic Digital Geographical Information Product, Standard CH/T 1008-2001[S]. Beijing: The State Bureau of Surveying and Mapping of China, 2001. ]
|
[43] |
刘学军, 卢华兴, 卞璐 , 等. 基于DEM的河网提取算法的比较[J]. 水利学报, 2006,37(9):1134-1141.
[
|
[44] |
金鑫, 金彦香, 杨登兴 . SWAT模型在土地利用/覆被变化剧烈地区的改进与应用[J]. 地球信息科学学报, 2018,20(8):1064-1073.
[
|
[45] |
|
/
〈 |
|
〉 |