Research On Parallel Algorithms Of Flow Direction Over Flat Terrain

The flow direction matrix is an essential input parameter in the process of the drainage network extraction.A flat is an area without local elevation gradient,and it is a major difficulty when extracting flow directions.With the volume of the Digital Elevation Model(DEM)increases,the amount of DEM data is increasing.Traditional serial algorithms can no longer handle massive DEM.This paper aims to improve the existing serial algorithms for assigning flow directions over flat surfaces,and designs two parallel algorithms for it to meet the flow directions assignment of massive DEM.The specific researches are as follows:(1)This paper proposes an improved serial algorithm for assigning flow directions over flat surfaces.The improved serial algorithm reduces the number of cells in the queue during the calculation process,ensuring that each flat cell only enters the queue once,and avoids repeated entry into the queue.In the process of calculating the geodesic distance between flat cells and lower terrain,the flow direction of the cell can be directly obtained.Compared with the Barnes algorithm,the average running speed is increased by 13%.Compared with the G&M algorithm and the Barnes algorithm,the improved serial algorithm runs the fastest.Therefore.the improved serial algorithm is applied to the parallel algorithms for flow directions assignment.(2)Based on the three-step parallel framework and the improved serial algorithm,this paper proposed a parallel algorithm for flow directions assignment.Firstly,the parallel algorithm allocated the pre-divided DEM tiles to multiple consumers.Consumers construct local graphs for these tiles,which contain the geodesic distances of tile border flat cells from higher terrain and lower terrain,then send local graphs to the producer.The producer constructs global graphs based on all the local graphs,and calculates the global geodesic distances,then sends the global information to consumers.Finally,consumers update the geodesic distances and assign flow directions.When the number of consumers reaches 35,the speed up ratios of the parallel algorithm are greater than 7.When the number of the consumers reaches 30,the average strong scaling efficiency is about 30%.When the number of consumers is greater than 5,the weak scaling efficiencies are less than 20%.The memory usage of the parallel algorithm with a consumer and a producer is less than that of the improved algorithm uses.Therefore,the parallel algorithm can process massive DEM that the serial algorithm cannot process.(3)The local graphs of the parallel algorithm are very complicated.This paper also proposes an efficient parallel algorithm for flow directions assignment over flat surfaces.the efficient parallel algorithm simplifies the construction of the local graphs,and obtains the approximate geodesic distances of flat cells to higher terrain or lower terrain.When the number of consumers reaches 30,the speed up ratios are greater than 6.When the number of consumers reaches 30,the strong scaling efficiencies reach 20%.When the number of consumers reaches 8,the weak scaling efficiencies are less than 10%.Although the efficient parallel algorithm obtains approximate geodesic distances,the similarity between the efficient parallel algorithm and the parallel algorithm can be more than 96.1%,and the running time and memory usage of the efficient parallel algorithm are greatly reduced.