University of South Florida
Efficient Viewshed Computation Algorithms On GPUs and CPUs
Abstract
dc:descriptionNowadays 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 × 6Identifiers
dc:identifier.*- Repository record dc:identifier
- https://digitalcommons.usf.edu/etd/8480