PairGraph: An Efficient Search-space-aware Accelerator for High-performance Concurrent Pairwise Queries

Pairwise queries have been widely used in many applications. Although several approaches have been recently proposed to accelerate a single query, they still suffer from irregular memory access and fragmented data sharing when processing Concurrent Pairwise Queries (CPQ) because of the poor temporal and spatial locality of traversal overlaps (i.e., graph structure data traversed by several queries). To address these challenges, this paper presents an accelerator named PairGraph to effectively support CPQ based on a novel Search-spaceaware Processing Model (SPM). The key insight is the strong similarity of queries’ search spaces, which are primarily concentrated on the graph topology between source and destination vertices. Consequently, our approach identifies the graph structure data traversed by most of the queries according to the graph topology between multiple pairs of vertices, and then fully reuses the data worth sharing to reduce off-chip communications. The experimental results indicate that PairGraph gains speedups of $5.59 \times \sim 14.25 \times$ and $3.76 \times \sim 7.58 \times$ compared with the state-of-the-art CPU-based system Gemini and the GPU-based system Gunrock, respectively. Compared with three cutting-edge accelerators, i.e., LCCG, ScalaGraph, and ReGraph, it gains speedups of $1.67 \times \sim 2.72 \times$, $1.93 \times \sim 4.26 \times$, and $2.66 \times \sim 4.28 \times$, respectively.