Technical Papers Archive

Optimizing Random Access to Hierarchically-Compressed Data on GPU

Authors: Feng Zhang, Yihua Hu, Haipeng Ding, Zhiming Yao, Zhewei Wei, Xiao Zhang, and Xiaoyong Du (Renmin University of China)

Abstract: GPU’s powerful computational capacity holds great potential for processing hierarchically-compressed data without decompression. Unfortunately, existing GPU approaches offer only traversal-based analytics; random access is extremely inefficient, substantially limiting their utility. To solve this problem, we develop a novel and broadly applicable optimization enabling efficient random access to hierarchically-compressed data in GPU memory. We address three major challenges. The first is designing GPU data structures that support random access. The second is efficiently generating data structures on GPUs. Generating data structures for random access is costly on the CPU, and the inefficiency increases dramatically when PCIe data transmission is incorporated. The third is query processing on compressed data in GPU memory. Random accesses result in severe conflicts between massive threads. We evaluate our solution on two GPU platforms using five real-world datasets. Experiments show that the random access operations on GPU can achieve 65.04x average speedup compared to the state-of-the-art method.




Back to Technical Papers Archive Listing