Dissertation/Thesis Abstract

Heterogeneous construction of spatial data structures
by Butts, Robert O., M.S., University of Colorado at Denver, 2015, 65; 1588178
Abstract (Summary)

Linear spatial trees are typically constructed in two discrete, consecutive stages: calculating location codes, and sorting the spatial data according to the codes. Additionally, a GPU R-tree construction algorithm exists which likewise consists of sorting the spatial data and calculating nodes' bounding boxes. Current GPUs are approximately three orders of magnitude faster than CPUs for perfectly vectorizable problems. However, the best known GPU sorting algorithms only achieve 10-20 times speedup over sequential CPU algorithms. Both calculating location codes and bounding boxes are perfectly vectorizable problems. We thus investigate the construction of linear quadtrees, R-trees, and linear k-d trees using the GPU for location code and bounding box calculation, and parallel CPU algorithms for sorting. In this endeavor, we show how existing GPU linear quadtree and R-tree construction algorithms may be modified to be heterogeneous, and we develop a novel linear k-d tree construction algorithm which uses an existing parallel CPU quicksort partition algorithm. We implement these heterogeneous construction algorithms, and we show that heterogeneous construction of spatial data structures can approach the speeds of homogeneous GPU algorithms, while freeing the GPU to be used for better vectorizable problems.

Indexing (document details)
Advisor: Alaghband, Gita
Commitee: Altman, Tom, Ra, Ilkyeun
School: University of Colorado at Denver
Department: Computer Science
School Location: United States -- Colorado
Source: MAI 54/04M(E), Masters Abstracts International
Subjects: Computer science
Keywords: Graphics processing units, Heterogeneous, Quadtrees, R-trees, Spatial trees
Publication Number: 1588178
ISBN: 978-1-321-73137-8
Copyright © 2021 ProQuest LLC. All rights reserved. Terms and Conditions Privacy Policy Cookie Policy