Exploiting Massive Parallelism for IndexingMulti-Dimensional Datasets on the GPU
- 12 August 2014
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Parallel and Distributed Systems
- Vol. 26 (8) , 2258-2271
Abstract
Inherently multi-dimensional n-ary indexing structures such as R-trees are not well suited for the GPU because of their irregular memory access patterns and recursive back-tracking function calls. It has been known that traversing hierarchical tree structures in an irregular manner makes it difficult to exploit parallelism and to maximize the utilization of GPU processing units. Moreover, the recursive tree search algorithms often fail with large indexes because of the GPU's tiny runtime stack size. In this paper, we propose a novel parallel tree traversal algorithm-massively parallel restart scanning (MPRS) for multi-dimensional range queries that avoids recursion and irregular memory access. The proposed MPRS algorithm traverses hierarchical tree structures with mostly contiguous memory access patterns without recursion, which offers more chances to optimize the parallel SIMD algorithm. We implemented the proposed MPRS range query processing algorithm on n-ary bounding volume hierarchies including R-trees and evaluated its performance using real scientific datasets on an NVIDIA Tesla M2090 GPU. Our experiments show braided parallel SIMD friendly MPRS range query algorithm achieves at least 80 percent warp execution efficiency while task parallel tree traversal algorithm shows only 9-15 percent efficiency. Moreover, braided parallel MPRS algorithm accesses 7-20 times less amount of global memory than task parallel parent link algorithm by virtue of minimal warp divergence.Keywords
Funding Information
- MKE/KEIT (10041608)
This publication has 23 references indexed in Scilit:
- Medical image processing on the GPU – Past, present and futureMedical Image Analysis, 2013
- Efficient stack-less BVH traversal for ray tracing2011
- A Fast Iterative Method for Eikonal EquationsSIAM Journal on Scientific Computing, 2008
- Accelerating molecular modeling applications with graphics processorsJournal of Computational Chemistry, 2007
- Stackless KD‐Tree Traversal for High Performance GPU Ray TracingComputer Graphics Forum, 2007
- A Survey of General‐Purpose Computation on Graphics HardwareComputer Graphics Forum, 2007
- KD-tree acceleration structures for a GPU raytracer2005
- Analysis of the clustering properties of the Hilbert space-filling curveIEEE Transactions on Knowledge and Data Engineering, 2001
- Efficiency Issues for Ray TracingJournal of Graphics Tools, 1998
- R-trees1984