Efficient Discrete Range Searching primitives on the GPU with applications

J. Soman, M.K. Kumar, K. Kothapalli, P.J. Narayanan
Int. Inst. of Inf. Technol., Hyderabad, India
International Conference on High Performance Computing (HiPC), 2010


   title={Efficient Discrete Range Searching primitives on the GPU with applications},

   author={Soman, J. and Kumar, M.K. and Kothapalli, K. and Narayanan, PJ},

   booktitle={High Performance Computing (HiPC), 2010 International Conference on},




Source Source   



Graphics processing units provide a large computational power at a very low price which position them as an ubiquitous accelerator. Efficient primitives that can expand the range of operations performed on the GPU are thus important. Discrete Range Searching(DRS) is one such primitive with direct applications to string processing, document and text retrieval systems, and least common ancestor queries. In this work, we present a GPU specific implementation of DRS with an optimal space-time trade off. Toward this end, we also present GPU amenable succinct representations and discuss limitations on the GPU. Our method uses 7.5 bits of additional space per element. The speedup achieved by our method is in the range of 20-25 for preprocessing, and 25-35 for batch querying over a sequential implementation. Compared to an 8-threaded implementation, our methods obtain a speedup of 6-8. We study applications of the DRS on the GPU. Also, we suggest that most graph algorithms which focus on using least common ancestor, can easily be enabled on the GPU based on range minima primitive. Beyond this, we show applications of DRS in string querying and tree queries, and suggest how DRS can be helpful in implementing tree based graph algorithms on the GPU.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2021 hgpu.org

All rights belong to the respective authors

Contact us: