TY - GEN
T1 - A performance study of traversing spatial indexing structures in parallel on GPU
AU - Kim, Jinwoong
AU - Hong, Sumin
AU - Nam, Beomseok
PY - 2012
Y1 - 2012
N2 - CUDA is a parallel programming environment that enables significant performance improvement by leveraging the massively parallel processing capability of the GPU. Inherently spatial indexing structures such as R-Trees are not well suited for CUDA environment due to its irregular tree traversal for range queries. Traversing irregular tree search paths makes it hard to maximize the utilization of many-core architectures. In this paper, we propose assigning an individual sub-tree to each SMP (streaming multi-processor) in GPGPU, such that CUDA cores in the same SMP co-operate to navigate tree index nodes. This parallel partitioned-indexing improves the utilization of many cores in GPGPU significantly. Also, we propose a new range query search algorithm - {\em three-phase-search} that avoids non-sequential random access to tree nodes and accelerates the search performance of spatial indexing structures on GPU. Our experimental results show that GPU-based parallel spatial indexing scheme on NVIDA Tesla M2090 GPGPU outperforms the CPU-based multi-threaded R-trees on AMD Opteron 6128HE processor by two times.
AB - CUDA is a parallel programming environment that enables significant performance improvement by leveraging the massively parallel processing capability of the GPU. Inherently spatial indexing structures such as R-Trees are not well suited for CUDA environment due to its irregular tree traversal for range queries. Traversing irregular tree search paths makes it hard to maximize the utilization of many-core architectures. In this paper, we propose assigning an individual sub-tree to each SMP (streaming multi-processor) in GPGPU, such that CUDA cores in the same SMP co-operate to navigate tree index nodes. This parallel partitioned-indexing improves the utilization of many cores in GPGPU significantly. Also, we propose a new range query search algorithm - {\em three-phase-search} that avoids non-sequential random access to tree nodes and accelerates the search performance of spatial indexing structures on GPU. Our experimental results show that GPU-based parallel spatial indexing scheme on NVIDA Tesla M2090 GPGPU outperforms the CPU-based multi-threaded R-trees on AMD Opteron 6128HE processor by two times.
KW - GPGPU indexing
KW - Multi-dimensional indexing
KW - Multi-dimensional range query
UR - https://www.scopus.com/pages/publications/84870405425
U2 - 10.1109/HPCC.2012.121
DO - 10.1109/HPCC.2012.121
M3 - Conference contribution
AN - SCOPUS:84870405425
SN - 9780769547497
T3 - Proceedings of the 14th IEEE International Conference on High Performance Computing and Communications, HPCC-2012 - 9th IEEE International Conference on Embedded Software and Systems, ICESS-2012
SP - 855
EP - 860
BT - Proceedings of the 14th IEEE International Conference on High Performance Computing and Communications, HPCC-2012 - 9th IEEE International Conference on Embedded Software and Systems, ICESS-2012
T2 - 14th IEEE International Conference on High Performance Computing and Communications, HPCC-2012 - 9th IEEE International Conference on Embedded Software and Systems, ICESS-2012
Y2 - 25 June 2012 through 27 June 2012
ER -