A data relocation approach for terrain surface analysis on multi-GPU systems: a case study on the total viewshed problem.

Abstract

Digital Elevation Models (DEMs) are important datasets for modelling line-of-sight phenomena such as radio signals, sound waves and human vision. These are commonly analysed using rotational sweep algorithms. However, such algorithms require large numbers of memory accesses to 2D arrays which, despite being regular, result in poor data locality in memory. This paper proposes a new methodology called skewed Digital Elevation Model (sDEM), which substantially improves the locality of memory accesses and largely increases the inherent parallelism involved in the computation of rotational sweep-based algorithms. In particular, sDEM applies a data restructuring technique before accessing the memory and performing the computation. To demonstrate the high efficiency of sDEM, we use the problem of total viewshed computation as a case study. Different implementations for single-core, multi-core, single-GPU and multi-GPU platforms are provided. We conducted two experiments in which sDEM is compared with (i) the most used geographic information systems (GIS) software and (ii) the state-of-the-art algorithm. In the first experiment, sDEM is in average 8.8x faster than current GIS software despite being able to consider only few points because of their limitations. In the second experiment, sDEM is 827.3x faster than the state-of-the-art algorithm, considering the best studied case