A fine-granularity scheduling algorithm for parallel XDraw viewshed analysis

Viewshed analysis is widely used in many terrain applications such as siting problem, path planning problem, and etc. But viewshed computation is very time-consuming, in particular for applications with large-scale terrain data. Parallel computing as a mainstream technique with the tremendous potential has been introduced to enhance the computation performance of viewshed analysis. This paper presents a revised parallel viewshed computation approach based on the existing serial XDraw algorithm in a distributed parallel computing environment. A layered data-dependent model for processing data dependency in the XDraw algorithm is built to explore scheduling strategy so that a fine-granularity scheduling strategy on the process-level and thread-level parallel computing model can be accepted to improve the efficiency of the viewshed computation. And a parallel computing algorithm, XDraw-L, is designed and implemented taken into account this scheduling strategy. The experimental results demonstrate a distinct improvement of computation performance of the XDraw-L algorithm in this paper compared with the coarse-partition algorithm, like XDraw-E which is presented by Song et al. (Earth Sci Inf 10(5):511–523, 2016), and XDraw-B that is the basic algorithm of serial XDraw. Our fine-granularity scheduling algorithm can greatly improve the scheduling performance of the grid cells between the layers within a triangle region.