A parallel implementation of WAND algorithm on GPUs

Abstract

In this paper we propose and evaluate new strategies for the parallel top-k query processing on GPUs. Our strategies are based on the document-at-a-time approach and have been implemented and tested with the WAND ranking algorithm. In our first strategy (named homogeneous), the posting lists are evenly partitioned among thread blocks. Our second algorithm, named heterogeneous, partitions the posting lists according to document identifier intervals, thus partitions may have different sizes. We also propose three threshold sharing policies, named Local, Safe-R and Safe-WR, which emulate the WAND algorithm global pruning technique. We evaluated our proposals using AND/OR queries, and the results show that the homogeneous algorithm allows better speedups through higher occupancy of the SMs, but at the cost of a lower recall. The heterogeneous algorithm produces the exact top-k documents and shows promising speedups. Also, the Shared-R and Shared-WR policies for threshold propagation allowed better performance, provided there is enough amount of work per thread block, which proved true for queries composed of at least a few millions documents.