Doctor of Philosophy (Ph.D.)
Degree Granting Department
Computer Science and Engineering
Yicheng Tu, Ph.D.
Adriana Iamnitchi, Ph.D.
Yan Zhang, Ph.D.
Zhuo Lu, Ph.D.
Joni Downs, Ph.D.
Computing visibility, GIS, GPU, Parallel algorithm, Spatial data analysis
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.
Scholar Commons Citation
Qarah, Faisal F., "Efficient Viewshed Computation Algorithms On GPUs and CPUs" (2020). Graduate Theses and Dissertations.