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 the line of sight, such as radio signals, sound waves and human vision. These are commonly analyzed 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. Here, we propose a new methodology called skewed Digital Elevation Model (sDEM), which substantially improves the locality of memory accesses and 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 considering different implementations for single-core, multi-core, single-GPU and multi-GPU platforms. We conducted two experiments to compare sDEM with (i) the most commonly used geographic information systems (GIS) software and (ii) the state-of-the-art algorithm. In the first experiment, sDEM is on 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 in the best case.

KEYWORDS:

• Data relocation
• Digital Elevation Model (DEM)
• Geographic Information Systems (GIS)
• total viewshed
• visibility analysis

Disclosure statement

No potential conflict of interest was reported by the author(s).

Data and codes availability statement

The data and codes of the sDEM algorithm that support the findings of this study are available in the ‘figshare.com’ repository with the identifier ‘https://doi.org/10.6084/m9.figshare.11370549ʹ.

Supplementary materials

Supplemental data for this article can be accessed here.

Additional information

Funding

This work was supported in part by the Spanish Ministry of Science and Technology through the TIN2016-80920-R Project, and in part by the University of Malaga through the U-Smart-Drive project and the I Plan Propio de Investigacion. Siham Tabik was supported by the Ramon y Cajal Programme under Grant RYC-2015-18136.

Notes on contributors

A. J. Sanchez-Fernandez

Andres J. Sanchez-Fernandez received the B.S. degree in industrial technology engineering with specialization in automatic systems and the M.S. degree in mechatronic engineering from the University of Malaga, Malaga, Spain, in 2016 and 2017, respectively, where he is currently pursuing the Ph.D. degree in mechatronic engineering in the field of parallel programming on heterogeneous systems. In 2018, he joined the Department of Computer Architecture, University of Malaga. His research interests include algorithm optimization, parallel programming, and large-scale data processing on heterogeneous CPU-GPU systems.

L. F. Romero

Luis F. Romero received the M.Sc. degree in physics from the Complutense University of Madrid, Madrid, Spain, in 1988, and the Ph.D. degree in computer science from the University of Malaga, Malaga, in 1996. He is currently a Full Professor with the Department of Computer Architecture, University of Malaga, where he has been since 1989. His research interests span both heterogeneous parallel computing and computer physics. Much of his work has been on improving the understanding, design, and performance of parallel and networked computer systems, mainly through physical system modeling, GIS algorithmics, and numerical integration.

G. Bandera

Gerardo Bandera received his B.Sc. and M.Sc. degrees in Computer Eng. in 1994 and his PhD degree in Computer Science in 1999 from the University of Malaga (Spain). In 1994 he became an Assistant Professor at the Dept. of Computer Architecture of the University of Malaga. Since 2001 he is an Associate Professor. Apart of regular courses, he has taught several international summer courses, and some CISCO and NVIDIA seminars, where he is a certificate lecturer. He has more than 30 contributions to international journals, conferences and book chapters, and has participated in more than 20 national/international research projects. Since 2013 he has lead more than 10 R&D projects with international companies.

S. Tabik

Siham Tabik received the B.Sc. degree in physics from University Mohammed V, Rabat, Morocco, in 1998, and the Ph.D. degree in computer science from the University of Almeria, Almeria, Spain, in 2006. She is currently a Ramón y Cajal Researcher with the University of Granada, Granada, Spain. Her research interests include machine learning and high-performance computing.