Parallel Digital Terrain Models And Data Analysis Algorithms Splitting Methods

The size of all kinds of data is getting bigger and bigger, so is Digital Elevation Model (DEM) dataset. Coupled with the complexity of geo-spatial processing, algorithms based on single-core computer serial digital terrain analysis algorithm has been unable to meet people’s needs. So to develop new parallel digital terrain analysis algorithms with massive DEM data in the new parallel computing environment is needed in order to adapt to the development needs in the new era.When writing a parallel algorithm, many factors must be taken, such as, dependency, particle size, locality, load balancing and other issues. First, this paper discussed the usage of some common parallel mode on parallel digital terrain analysis algorithm method, including data parallelism, task parallelism, recursive splitting, and pipeline.Above all, this paper designed a framework for parallel digital terrain analysis algorithms. This framework uses data parallelism. Regard each block of data calculated as a separate task, and dynamically allocate them to each process for computing. In this framework, there is less inter-process communication, and the load balancing is better.Then, this paper designed one regular data splitting method and one irregular data splitting method. This paper classified digital terrain analysis algorithms into two categories:neighborhood scope algorithms and global scope algorithms, according to the computational characteristics of them. This paper designed a suitable method to split DEM data for neighborhood scope algorithms which can be used in the above framework. The method is a rule method, and is very suitable for neighborhood scope algorithms, including splitting data by rows, columns, and blocks. This paper also designed a suitable method to split DEM data for global scope algorithms which had taken into account the computing character of the algorithm. This is an irregular method based on resampling. It splits DEM data using a low-resolution record which can be obtained by resampling and analysis.At last, this paper built an experiment system which used a cluster of PCs as hardware and MPI+OpenMP as software. Then do some experiments using the above framework and data splitting method. The experiments use slope algorithm as an example of neighborhood scope algorithm and filling the depressions algorithm as an example of globe scope algorithm. The experiments show that all the above parallel method can help us get a good result on parallel speedup and parallel efficiency. In this paper, the given digital terrain analysis algorithms framework and the corresponding data splitting method, are suitable for most of the neighborhood scope algorithms and global scope algorithms. It provides a beneficial theory and technical support for the meticulous parallel digital terrain analysis on a wide range and high-resolution DEM data.