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
