Tree structured data processing on GPUs
Loading...
Files
Date
2014
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
University of New Brunswick
Abstract
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.