Research On Key Techniques Of Parallel Algorithms For Watershed Topographic Analysis Based On Digital Elevation Models

Watershed topographic analysis based on DEMs, an indispensable tool of spatial analysis in GIS applications, is a core part of digital terrain analysis. It plays an important role in many research fields such as landform, soil, hydrology and ecology. At present, with the development of spatial data acquisition technology, the quick acquisition of terrain data with large areas and fine scales becomes a solid reality; it provides rich data sources for watershed topographic analysis. Under the background of big data, it becomes a great difficulty in GIS that how to process and analyze these massive datasets quickly and efficiently to turn it into the required geological knowledge. Parallel computing brings an opportunitie to meet this challenge with the development of computer technology. In this paper, aiming at high performance computation in watershed topographic analysis, the key techniques of parallel computing in watershed topographic analysis have been deeply researched on the basis of the theories and methods of digital terrain analysis. This study has the practical significance for us to enrich the theoretical and methodological system of digital terrain analysis, to improve the platforms of geological knowledge mining and knowledge conversion, and to promote the effective application of terrain analysis techonology with large scopes and fine scales into many research fields such as digital watershed. The research findings can be as the theoretical and methodological references to high-performance computation in GIS spatial analysis under the age of big data.The mainly contents and research achievements of this paper are as follows:(1) A quantitative model for parallelizing algorithms of watershed topographic analysis, namely, parallel granularity model, is presented. The model integrates the elements of data, task and structure. These elements are involved by a problem of watershed topographic analysis. From the data attributes and data volume, parameters and load in a task, and the effective memory of a computing platform, the model carries on the effective quantitative unification to these three elements. The parallel granularity model provides a quantitative foundation to task decomposition in the design of parallel algorithm for watershed topographic analysis.(2) From the aspects of data decomposition, resulting fusion and data communication, the strategies of parallel computing for watershed topographic ananlysis are presented. According to the thought of data redundancy replication and parallel granularity model, the row-decomposition strategy and subwatershed-decomposition strategy based on parallel granularity model are designed. Using the parallel granularity as a control parameter, the global data is divided into multiple parallel blocks, and each parallel block contains multiple process subdomains as the same as the number of processes. On this basis, the corresponding resulting fusion strategy is studied. For the row-decomposition strategy, the resulting fusion is processed by the data anchor point of the process subdomain and a triple approach is adopted to merge the subresult of each process subdomain for subwatershed-decomposition strategy. The strategy of data communication is also presented in the view of communication mode and data compression. The efficiencies of point-to-point communication and group communication in MPI are analized, and the method of memory compression for DEM dataseets is designed from the aspects of transform compression and coding compression.(3) Based on the parallel strategies of watershed topographic analysis, parallel algorithms with parallel granularity control of watershed topographic partition are proposed. Facing to the row-decomposition strategy based on parallel granularity model, a two-phase parallelizing strategy is put forward. Based on the two-phase parallelizing strategy, parallel algorithms are respectively designed to calculate a basin with an outlet, subwatersheds with a watershed-area threshold, and watershed coding with an improved coding method considering topological relations and areas of subwatersheds. The experiment reulsts show that, with parallel granularity control, the parallel algorithms of watershed topographic partition can effectively improve the computaional efficiency and the processing-data scale.(4) According to the watershed structure, patallel algorithms with parallel granularity control of watershed topographic characteristics extraction are studied. On the basis of the two-phase parallelizing approach of the subwatershed-decomposition strategy, parallel algorithms are designed to extracte the stream network of a watershed and calculate drainage densities based on subwatersheds in a watershed. In the process of parallel computing, the key issues are researched in detail, such as subwatershed merger, load balancing and task allocation, and information transmission between subwatersheds. Experimental results prove that, the parallel algorithms based on the subwatershed-decomposition strategy can make full use of the characteristic that subwatershed can be considered as an independent computing unit, which makes the totoal execution time greately decrease; meanwhile, the parallel algorithms are under the condition of parallel granularity control and achieve a good parallel performance.