Multi-GPU Efficient Indexing For Maximizing Parallelism of High Dimensional Range Query Services

Numerous research efforts have been proposed for efficient processing of range queries in high-dimensional space by either redesigning R-tree access structure for exploring massive parallelism on single GPU or exploring distributed framework of R-tree. However, none of the existing efforts explores the integration of the parallelization of the R-tree on a single GPU with a distributed framework for the R-tree. The problem of designing an efficient multi-GPU indexing method, which can effectively combine the parallelism maximization with distributed processing of the R-tree, remains an open challenge. In this article, we present a novel multi-GPU efficient parallel and distributed indexing method, called LBPG-tree. The rationale of the LBPG-tree is to combine the advantages of an instruction pipeline in CPU with the massive parallel processing potential of multiple GPUs by introducing two new optimization strategies: First, we exploit the GPU L2 cache for accelerating both index search and index node access on GPUs. Second, we further improve utilization of L2 cache on GPUs by compacting and sorting candidate nodes called Compact-and-Sort. Our experimental results show that the LBPG-tree outperforms G-tree, the previous representative GPU index method and effectively support multiple GPUs for providing efficient high dimensional range query service.