Back to search

University of South Florida

Efficient Viewshed Computation Algorithms On GPUs and CPUs

Abstract

dc:description

Nowadays with the advance in managing and collecting large data, GIS is one of the applications that suffer from lack of efficient data management methods. GIS data often come in form of maps with different types of data such as temperature, topology, and population. This dissertation focuses on exact-viewsheds computation for large terrains, and due to the poor performance of current exact-viewshed algorithms that may need several hours to process a midsize map, we found the need for new algorithms that are capable of efficiently computing viewshed for large size maps. This work presents a highly-efficient exact-viewshed computation algorithm based on the radial-sweep algorithm, implemented and optimized for GPUs. The first version of our GPU algorithm shows significant improvement in performance over the sequential CPU-based algorithm, providing at least an order of magnitude speedup. We further improve the algorithms by tackling two challenges in parallelizing the radial-sweep algorithm: (1) dividing the elevation-grid into small-size sectors accurately between threads and (2) consumption of excessive amount of memory. Both problems have been resolved in the newly proposed algorithms. We were able to parallelize the algorithm by building a histogram for cells’ events based on their azimuth-angle in the grid. The histogram we help each thread to know the number of events it has to process which forms a small size sector. Then, we applied prefix-sum operation on the histogram so each thread will know where to start processing the events. The second problem which is the excessive memory consumption has been resolved by dividing the grid into sectors and processing them individually to obtain a smaller intermediate result instead of processing the whole grid that would yield a larger intermediate result. Also, to search for cell IDs in each sector, the grid is divided into scan-regions where the overhead of the scan operation is minimal. The new GPU-based algorithm is 4.4x faster than the fastest existing GPU-based exact-viewshed computation algorithm, and the new sequential CPU-based algorithm is 44x times faster than the current fastest sequential algorithm.

Degree

thesis:*
Name thesis:degree_name
Doctor of Philosophy (Ph.D.)
Level thesis:degree_level
Dissertation
Discipline thesis:degree_discipline
Computer Science and Engineering
Grantor
University of South Florida
Year dc:date
2020

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Qarah, Faisal F.
Contributors dc:contributor
  • Yicheng Tu, Ph.D.
  • Adriana Iamnitchi, Ph.D.
  • Yan Zhang, Ph.D.
  • Zhuo Lu, Ph.D.
  • Joni Downs, Ph.D.

Subjects

dc:subject × 6

Identifiers

dc:identifier.*
Repository record dc:identifier
https://digitalcommons.usf.edu/etd/8480

Chain of custody

source
Harvested from
University of South Florida
Base URL
digitalcommons.usf.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Qarah, Faisal F.. Efficient Viewshed Computation Algorithms On GPUs and CPUs. Dissertation thesis, University of South Florida, 2020. https://digitalcommons.usf.edu/etd/8480