Speeding up set intersections in graph algorithms using SIMD instructions
- Publication Type:
- Conference Proceeding
- Citation:
- Proceedings of the ACM SIGMOD International Conference on Management of Data, 2018, pp. 1587 - 1602
- Issue Date:
- 2018-05-27
Closed Access
| Filename | Description | Size | |||
|---|---|---|---|---|---|
| p1587-han.pdf | Published version | 1.57 MB |
Copyright Clearance Process
- Recently Added
- In Progress
- Closed Access
This item is closed access and not available.
© 2018 Association for Computing Machinery. In this paper, we focus on accelerating a widely employed computing pattern-set intersection, to boost a group of graph algorithms. Graph's adjacency-lists can be naturally considered as node sets, thus set intersection is a primitive operation in many graph algorithms. We propose QFilter, a set intersection algorithm using SIMD instructions. QFilter adopts a merge-based framework and compares two blocks of elements iteratively by SIMD instructions. The key insight for our improvement is that we quickly filter out most of unnecessary comparisons in one byte-checking step. We also present a binary representation called BSR that encodes sets in a compact layout. By combining QFilter and BSR, we achieve dataparallelism in two levels-inter-chunk and intra-chunk parallelism. Moreover, we find that node ordering impacts the performance of intersection by affecting the compactness of BSR.We formulate the graph reordering problem as an optimization of the compactness of BSR, and prove its strong NP-completeness. Thus we propose an approximate algorithm that can find a better ordering to enhance the intra-chunk parallelism. We conduct extensive experiments to confirm that our approach can improve the performance of set intersection in graph algorithms significantly.
Please use this identifier to cite or link to this item: