Research On Parallel Computing And Fault Tolerant In Viewshed Analysis Algorithm

With bigger topographic data, higher data resolution, and more complex data, digital terrain analysis algorithms is facing increasingly severe challenges. Viewshed analysis as an important component of digital terrain analysis algorithms has a higher demand on computer’s performance, and the traditional serial computing system can hardly meet it which measures by the number of instructions processed per unit time. Therefore, parallel computing must be adopted. Yet the efficiency of prevalent parallel computing is on a coarse-grained level, and the one on a fine-grained level has to be further developed and advanced, which can combine parallel architecture with specific geological significance.To begin with, this thesis focuses on digital terrain analysis and parallel computing, analyzes the feature and data dependence of viewshed analysis algorithm and discusses the relationship between global and local data dependence in viewshed analysis. The author probes into data’s parallel strategy and provides theoretical basis for data partitioning.Then, on the basis of isometric partitioning and homalographic partitioning, this thesis presents a data partitioning method according to the data of calculation window. By extending and filling in the raster, task scheduling and load balancing, the thesis handles the potential problem that random viewpoint may affect isometric partitioning.Next, concerning the data-intensive characteristic, this thesis provides an error detection in parallel digital terrain analysis which uses PC cluster’s computing acceleration to carry out double calculation, subtraction and comparison on data collected. Then, based on parallel error detection, multi-copy technology is employed to realize terrain analysis fault-tolerant method in parallel architecture, offering, an available solution for fault-tolerant problems.In the end, based on viewshed analysis, the thesis applies data dependence method to other algorithms of terrain analysis and offers a universal solution to analysis algorithms that has global data dependence problems in terrain analysis.