Tree structured data processing on GPUs

Thumbnail Image
Journal Title
Journal ISSN
Volume Title
University of New Brunswick
Tree-structured data are used in many applications. In order to reduce the computing time for processing large tree-structured data sets, parallel processing has been used. Recently, research has been done on parallel computing of tree-structured data on graphics processing units (GPUs). However, tree data structures on GPUs are commonly applied to storing a particular kind of tree, and support limited types of tree traversals. In this thesis, we propose a tree data structure which can apply to storing many types of trees, and support four common types of tree traversals: pre-order, postorder, in-order and breadth-first traversals. Therefore, most tree algorithms can be implemented on GPUs by using this data structure. We implemented a weighted similarity algorithm on an NVIDIA GPU for demonstration of the performance of this data structure. The results showed that this GPU application can get speedup of about 4000 compared to an application running on a single AMD Opteron CPU core.