CUDA is a parallel programming environment that facilitates significant performance improvement by leveraging the massively parallel processing capability of the GPU. The general purpose computing, on graphics processing unit (GP-GPU) has turn up as a new cost effective parallel computing framework, in high performance computing research that enables large amounts of datasets to be processed in parallel. Large scale scientific data intensive applications have been playing a major role in modern high performance computing research. This large amount of data can be accessed by scientific data analysis applications such as multi-dimensional range query, but not much research has been conducted on multidimensional range query on the GP-GPU. Inherently multi-dimensional indexing trees such as R-Trees are not well suited for GPU environment because of its irregular tree traversal. It has been known that traversing hierarchical tree structures in an irregular manner make it difficult to exploit parallelism and to maximize the utilization of GPU processing units. Then to avoid the drawbacks of R-Tree the novel MPTS (Massively Parallel Three-phase Scanning) R-tree traversal algorithm for multi-dimensional range query was proposed, that Recursive access to tree nodes into sequential access. Furthermore, the recursive tree search algorithms often fail because of the GPU's tiny runtime stack size. Then the proposed work of a novel parallel tree traversal algorithm—massively parallel restart scanning (MPRS) for multi-dimensional range queries avoids recursion and irregular memory access. Then 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

1. NVIDIA CUDA Compute Unified Device Architecture. (2014). [Online]. Available: http://www. nvidia. com/
2. Jinwoong Kim,Won-Ki Jeong and Beomseok Nam, "Exploiting Massive Parallelism for Indexing Multi-Dimensional Datasets on the GPU," IEEE Trans. Parallel Distrib. Sys. ,VOL. 26, NO. 8, AUGUST 2015.
3. Jinwoong Kim, Beomseok Nam, "Parallel Multi-dimensional Range Query Processing with R-Trees on GPU," School of Electrical and Computer Engineering ,UNISTUlsan, 689-798, Korea.
4. R. E. Bellman, Adaptive Control Processes: A GuidedTour. Princeton, NJ, USA: Princeton Univ. Press, 1961.
5. Norbery Beckmann, Hans-Peter Kriegel, Ralf Schneider, and Bernhard Seeger. The R?-tree: An efficient and robust access method for points and Rectangles. In Proceedings of 1990 ACM SIGMOD International Conferenceon Management of Data (SIGMOD), pages 322–331, May 1990.
6. Antonin Guttman. R-trees: A dynamic index structure for spatial searching. In Proceedings of 1984 ACM SIGMOD International Conference on Management of Data (SIGMOD), 1984.
7. Kaushik Chakrabarti and Sharad Mehrotra. The Hybrid tree: An index structure for high dimensional feature spaces. In Proceedings of the 15th International Conference on Data Engineering (ICDE), pages 440–447, 1999.
8. T. Foley and J. Sugerman, "KD-tree acceleration structures for a GPU raytracer," in Proc. ACM SIGGRAPH/EUROGRAPHICS Conf. Graph. Hardware, 2005, pp. 15–22.
9. D. Horn, J. Sugerman, M. Houston, and P. Hanrahan, "Interactive k-d tree GPU raytracing," in Proc. Symp. Interact. 3D Graph. Games, 2007, pp. 167–174.
10. B. Smits, "Efficiency issues for ray tracing," J. Graph. Tools, vol. 3,no. 2, pp. 1–14, 1998
11. Hapala, T. Davidoiv, I. Wald, V. Havran, and P. Slusallek, "Efficient stack-less BVH traversal for ray tracing," in Proc. 27th Spring Conf. Comput. Graph. , 2011, pp. 7–12.
12. Jingren Zhou and Kenneth A. Ross. Implementing database operations using simd instructions. In Proceedings of 2002 ACM SIGMOD InternationalConference on Management of Data (SIGMOD), 2002.
13. Tim Kaldewey, Jeff Hagen, Andrea Di Blas, and Eric Sedlar. Parallel search on video cards. In Proceedings of the First USENIX conference on Hot topics in parallelism (HotPar 09), 2009.
14. Changkyu Kim, Jatin Chhugani, Nadathur Satish, Eric Sedlar, Anthony D Nguyen, Tim Kaldewey, Victor W. Lee, Scott A. Brandt, and Pradeep Dubey. Fast: Fast architecture sensitive tree search on modern cpus and gpus. In Proceedings of 2010 ACM SIGMOD International Conference on Management of Data (SIGMOD), 2010.
15. Jordan Fix, Andrew Wilkes, and Kevin Skadron. Accelerating braided b+ tree searches on a gpu with cuda. In 2nd Workshop on Applications forMulti and Many Core Processors: Analysis, Implementation, and Performance (A4MMC), in conjunction with ISCA, 2011
16. Lijuan Luo, Martin D. F. Wong, and Lance Leong. Parallel implementation of R-trees on the GPU. In Proceedings of the 17th Asia and South Pacific DesignAutomation Conference (ASP-DAC), 2012.
17. V. Havran, J. Bittner, and J. Zara, "Ray tracing with rope trees," in Proc. 14th Spring Conf. Comput. Graph. , 1998, pp. 130–139.
18. S. Popov, J. Gunther, H. -P. Seidel, and P. Slusallek, "Stackless KDtree traversal for high performance GPU ray tracing," Comput. Graph. Forum (Proc. Eurograph. ), vol. 26, pp. 415–424, 2007.
19. B. Moon, H. V. Jagadish, C. Faloutsos, and J. H. Saltz, "Analysis of the clustering properties of the hilbert space-filling curve," IEEE Trans. Knowl. Data Eng. , vol. 13, no. 1, pp. 124–141, Jan. 2001.
20. R. Rew, G. Davis, and S. Emmerson. (1997). NetCDF User's Guide for C [Online]. Available: http://www. unidata. ucar. edu/packages /netcdf/cguide. pdf
21. NVIDIA Thrust. (2014). [Online]. Available: https://developer. nvidia. com/thrust

Cuda Gpgpu parallel Multi-dimensional Indexing Multi-dimensional Range Query parallel R-tree