Research On Parallel Extraction Algorithm Of Flow Accumulation Oriented To Very Large-scale Digital Elevation Model

The flow accumulation is an important part of hydrological information extraction,and is also an important basic data for local water conservancy construction,flood prevention and mitigation,soil erosion,and terrain stability.The Digital Elevation Model(DEM)is a set of ordered arrays that uses elevation values to simulate ground fluctuations.The application of DEM data accelerates the process of automatic extraction of hydrological information,and also promotes the development of extraction of information on the flow accumulation.In recent years,with the improvement of DEM resolution and the increase of coverage,the data volume of digital elevation models is getting larger and larger.A data set can reach gigabytes and billions of cells,and it is still increasing.Although the computer processing and memory performance have been significantly improved,the traditional cumulant serial algorithm still cannot effectively and quickly extract the information of the flow accumulation.This paper mainly studies the parallel algorithm of the flow accumulation for ultra-large-scale DEM.The specific research contents as follows:(1)This paper proposes an improved serial algorithm of cumulant accumulation.The improved algorithm changes the order of cell calculation.After the calculation of the accumulated amount of a"small watershed"is completed,all the cells of the next"small watershed"are calculated until the calculation of all the cells is completed.The improved algorithm reduces the overhead space in the calculation process,reduces the pressure of cells entering and leaving the queue,and improves the calculation efficiency.The improved cumulant algorithm is compared with the commonly used recursive cumulant algorithm and non-recursive cumulant algorithm.Through the test data of different sizes,at 10~6 cell level,the improved algorithm is about 17%higher than the non-recursive algorithm.The calculation time of the recursive algorithm is about 3times that of the improved algorithm.Because the serial algorithm of the flow accumulation is an important part of the parallel calculation of the cumulative cumulant,it is obtained through experiments that the improved algorithm has a shorter execution time.This paper applies the improved serial algorithm of the cumulative cumulant to the parallel calculation of the flow cumulant.(2)This article adopts the Barnes parallel framework and proposes a new parallel algorithm for confluence accumulation to help super-large-scale data to calculate the multi-flow confluence accumulation.The parallel algorithm mainly adopts the parallel design pattern of single producer and multiple consumers.The parallel algorithm mainly includes three steps,namely the local calculation of the child node,the global solution construction of the master node and the final solution calculation of the child node.In this paper,a total of four data sets are used to analyze the acceleration ratio and scalability of the parallel algorithm.The acceleration ratio of all test data under the process number of 6-11 is above 3.When the number of processes is 9,the strength and scalability of all data can reach more than 40%.The results show that the algorithm can improve the calculation efficiency and has scalability.The main advantages of the parallel algorithm are:the computing resources of all child nodes are fully utilized,the load balance is better,and a large amount of time will not be wasted waiting for synchronization between the nodes;the algorithm only requires a fixed number of inter-node communication and I/O operation;the number of computing nodes required can be much smaller than the number of nodes required to be able to load the entire DEM.