Exploiting reuse for GPU subgraph enumeration
enumeration is important for many applications such as network motif
discovery, community detection, and frequent subgraph mining. To accelerate
the execution, recent works utilize graphics processing units (GPUs) to
parallelize subgraph enumeration. The performances of these parallel schemes
are dominated by the set intersection operations which account for up to
$95\%$ of the total processing time. (Un)surprisingly, a significant portion
(as high as $99\%$) of these operations is actually redundant, i.e., the same
set of vertices is repeatedly encountered and evaluated. Therefore, in this
paper, we seek to salvage and recycle the results of such operations to avoid
repeated computation. Our solution consists of two phases. In the first
phase, we generate a reusable plan that determines the opportunity for reuse.
The plan is based on a novel reuse discovery mechanism that can identify
available results to prevent redundant computation. In the second phase, the
plan is executed to produce the subgraph enumeration results. This processing
is based on a newly designed reusable parallel search strategy that can
efficiently maintain and retrieve the results of set intersection operations.
Our implementation on GPUs shows that our approach can achieve up to $5$
times speedups compared with the state-of-the-art GPU solutions.