PROJECT TITLE :

Exploiting Reuse for GPU Subgraph Enumeration

ABSTRACT:

The process of enumerating subgraphs is essential for a wide variety of applications, including the identification of communities and network motifs, as well as frequent subgraph mining. Recent works have been making use of graphics processing units (GPUs) to parallelize the enumeration of subgraphs in order to speed up the execution. The set intersection operations are responsible for up to 95 percent of the total processing time, and as a result, they have a significant impact on the performances of these parallel schemes. A significant portion (as high as 99 percent) of these operations is actually redundant, which means that the same set of vertices is encountered and evaluated multiple times. This finding may or may not come as a surprise. As a result, in this article, we aim to salvage and recycle the results of such operations in order to avoid performing the computation more than once. The implementation of our solution will occur in two stages. In the first phase, we create a plan that can be reused and evaluates whether or not there is an opportunity for reuse. The strategy relies on an innovative mechanism for reusing previously discovered information that can locate already computed results to avoid performing the same work twice. During the second phase, the plan is carried out in order to generate the results of the subgraph enumeration. This processing is based on a newly designed reusable parallel search strategy that was created with the intention of efficiently maintaining and retrieving the results of set intersection operations. The results of our implementation on GPUs show that our method can achieve speedups that are up to five times greater than those achieved by the most advanced GPU solutions.