Design And Implementation Of A Parallel Viewshed Analysis Algorithm Based On XDraw

Viewshed analysis is one of the important issues in terrain analysis and is applied in kinds of social life,such as prospecting,path choosing problem,security,base-locating,military routing and so on.Digital terrain analysis(DTA)based on digital elevation model(DEM)is applied in many aspects.With the rapid development of the technology of getting spatial information,the data amount of DEM grows crazy and traditional sequential algorithms have not be applied to the process of massive data.But with the development of hardware resources and the existing of parallel model,processing massive data has become possible.So the research on viewshed analysis has to change from the design of sequential algorithm to the research of parallel algorithm.The parallel viewshed analysis can be implemented by the parallelization of sequential algorithm in some corresponding platforms.It needs solving the problem of the dependency between the data to be computed to parallel the sequential algorithm,and at the same time it guarantees the computation efficiency.So the data scheduling is also an important issue.Based on it,the work of this thesis is as follows.Firstly,the thesis introduces the concepts about viewshed analysis,some common sequential and parallel algorithms,and summary of the present situation of viewshed analysis and their parallelization problems,and the applications of viewshed analysis.Secondly,for the strategy of data partition in parallel algorithm based on the XDraw algorithm,the research on the equal-angle and equal-area division approach is done and their advantages and disadvantages are deeply analyzed.Based on those analysis,an approach of equal-area division with triangle region,which can assure the load balance and satisfy the resource limitation,is proposed.According to the characteristics of the XDraw algorithm,a data scheduling strategy combining coarse and fine grain is proposed in this thesis,including data distribution and viewshed calculation in form of row or column.Moreover,we design and implement the parallel viewshed analysis algorithm based on CUDA with the GPU paralleling tech.Lastly,the experiments are executed on three data sets in different sizes.The comparison of efficiency between the process and the thread algorithm,and the comparison between the thread algorithm and the algorithm based on equal-area division are given.According to the results of these experiments,the strategy of data division and the approach of data scheduling combining coarse and fine grain proposed here can improve the efficiency of the parallel XDraw algorithm.