3378

A Batched GPU Algorithm for Set Intersection

Di Wu, Fan Zhang, Naiyong Ao, Fang Wang, Xiaoguang Liu, Gang Wang
Nankai-Baidu Joint Lab, College of Information Technical Science, Nankai University, Weijin Road 94, Tianjin, 300071, China
10th International Symposium on Pervasive Systems, Algorithms, and Networks (ISPAN), 2009
@conference{di2009batched,

   title={A Batched GPU Algorithm for Set Intersection},

   author={Di Wu, F.Z. and Ao, N. and Wang, F. and Liu, X. and Wang, G.},

   booktitle={2009 10th International Symposium on Pervasive Systems, Algorithms, and Networks},

   pages={752–756},

   year={2009},

   organization={IEEE}

}

Download Download (PDF)   View View   Source Source   

821

views

Intersection of inverted lists is a frequently used operation in search engine systems. Efficient CPU and GPU intersection algorithms for large problem size are well studied. We propose an efficient GPU algorithm for high performance intersection of inverted index lists on CUDA platform. This algorithm feeds queries to GPU in batches, thus can take full advantage of GPU processor cores even if problem size is small. We also propose an input preprocessing method which alleviate load imbalance effectively. Our experimental results based on a real world test set show that the batched algorithm is much faster than the fastest CPU algorithm and plain GPU algorithm.
VN:F [1.9.22_1171]
Rating: 0.0/5 (0 votes cast)

* * *

* * *

Follow us on Twitter

HGPU group

1941 peoples are following HGPU @twitter

Like us on Facebook

HGPU group

441 people like HGPU on Facebook

HGPU group © 2010-2016 hgpu.org

All rights belong to the respective authors

Contact us: