Title
Parallel Acceleration of CPU and GPU Range Queries Over Large Data Sets
Department/School
Computer and Information Sciences
Date
2020
Document Type
Article
Keywords
bitmap indices, WAH compression, range queries, GPU
DOI
https://doi.org/10.1186/s13677-020-00191-w
Abstract
Data management systems commonly use bitmap indices to increase the efficiency of querying scientific data. Bitmaps are usually highly compressible and can be queried directly using fast hardware-supported bitwise logical operations. The processing of bitmap queries is inherently parallel in structure, which suggests they could benefit from concurrent computer systems. In particular, bitmap-range queries offer a highly parallel computational problem, and the hardware features of graphics processing units (GPUs) offer an alluring platform for accelerating their execution. In this paper, we present four GPU algorithms and two CPU-based algorithms for the parallel execution of bitmap-range queries. We show that in 98.8% of our tests, using real and synthetic data, the GPU algorithms greatly outperform the parallel CPU algorithms. For these tests, the GPU algorithms provide up to 54.1 × speedup and an average speedup of 11.5× over the parallel CPU algorithms. In addition to enhancing performance, augmenting traditional bitmap query systems with GPUs to offload bitmap query processing allows the CPU to process other requests.
Published in
Journal of Cloud Computing
Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.
Citation/Other Information
Nelson, M., Sorenson, Z., Myre, J.M., Sawin, J., Chiu, D. (2020). Parallel Acceleration of CPU and GPU Range Queries Over Large Data Sets. Journal of Cloud Computing, 9, 1-21. https://doi.org/10.1186/s13677-020-00191-w