CRII: SHF: A Parallel and Distributed Framework for Graph Mining on GPUs

Mining from a big graph those subgraphs that satisfy certain conditions is useful in many applications such as community detection and subgraph matching. Subgraph mining in a big graph increasingly relies on parallel and distributed computing to scale the data processing volume and velocity. Numerous central processing unit (CPU)-based systems have been developed to parallelize graph mining algorithms.

However, our nation is replacing CPU supercomputers with graphics processing unit (GPU) supercomputers faster than ever before, with the expectation that heterogeneous CPU/GPUs will not only boost performance but also conserve energy. This trend poses difficulties for large-scale graph processing, as users must design GPU programs tailored to each individual graph problem.

The project’s novelties are: 1) a new graph parallel and distributed framework will be developed, which will accelerate graph computations in a GPU-rich environment; 2) multiple graph mining tasks, including dense subgraph mining and subgraph matching, will be implemented atop this framework to take advantage of the massive parallelism of multi-GPUs. The project's impacts are: 1) it serves a number of cross-disciplinary projects, such as bioinformatics and chem-informatics 2) this project will be released for public use and will enrich existing courses related to big data and parallel computing, thereby providing long-term benefits to the scientific community.

This project aims to build on the success in scaling graph processing in a multi-CPU environment and investigate novel task-based techniques to scale fundamental compute-intensive graph operations in a multi-GPU environment. Existing GPU algorithms impose a memory restriction because of the restricted size of GPU memory, which limits the size of input graphs that can be processed.

This project will explore effective representation schemes that encode and compress the input graph and intermediate subgraph results compactly to minimize the memory footprint of the GPU. This will enable coalesced global memory access and enable data reuse in shared memory. GPU-friendly task-based algorithms will be designed for fundamental graph operations including subgraph matching and dense subgraph mining, to unleash the massive parallelism enabled by a multi-GPU environment.

All graph mining pruning rules will be carefully re-designed using the GPU advanced warp-level primitives in association with the new task schemes.

This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.