Tree Structured Data Processing On GPUs

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, post-order, in-order and breadth-first traversals. Therefore, most tree algorithms can be implemented on GPUs by using this data structure.The main work and contributions of this thesis includes:(1) A tree data structure for implementing tree algorithms on GPUs is proposed;(2) Based on the proposed data structure, four basic tree traversals on GPUs, namely pre-order, in-order, post-order and breadth-first traversal are designed and implemented. Besides, experiments are carried out to study the time-cost of tree traversals;(3) Based on the proposed data structure and tree traversal methods, the weighted similarity algorithm on an NVDIAI GPU is implemented. Tests are carried out for measuring the GPU application performance and analysing the proposed data structure. Experimental results show that implementing types of tree algorithms on GPUs helps to improve system efficiency. Therefore, the time cost could be greately reduced.The work of this thesis has reference value for using GPUs to process data.