SHF: Small: GPU-dedicated Graph Transformations for Accelerating Iterative Graph Analytics

University Of California-Riverside, Riverside CA

Investigators

Abstract

Graph analytics yields deeper knowledge in many scientific domains by mining large volumes of highly connected data, such as social networks, airline networks, biological networks, and internet topology. Due to its compute and data-intensive nature, GPUs with massive parallelism hold great potential in accelerating graph analytics. However, existing solutions exhibit low utilization of GPU resources caused by the mismatch between GPU's design for regular computations and the highly irregular nature of real-world graphs. Moreover, GPUs often fail to handle relatively large graphs due to their limited on-device memory. The goal of this research is to dramatically improve the GPU resource utilization and boost the scalability of graph analytics by transforming the graphs in ways that make the data and workloads better fit in the GPU computing. The results of this research include software products that can be readily deployed on existing large-scale high-performance systems equipped with GPUs for executing real-world graph applications. More broadly, this research helps accelerate new discoveries in scientific fields like bioinformatics, social science, and public security. Specifically, this research develops a series of GPU-oriented graph transformations that together address the challenges of irregularity, scalability, and load imbalance at the input graph level. These include: (1) graph transformations for regularity which transform the irregular graph structures into more regular ones to address the low GPU efficiency; (2) graph transformations for scalability which transform a large graph into a mix of acyclic and cyclic small graphs, with each of them fitting into the GPU global memory. By maximally migrating computation from the acyclic graphs to the cyclic ones, the transformations can greatly reduce the data movement between GPU memory and host memory; and (3) graph transformations for multi-GPU systems which address the GPU load imbalance caused by the variation of active nodes in iterative graph analytics. This is achieved by generating small yet overlapped graphs and selectively processing the overlapped regions. Finally, this research integrates the above transformations to maximize the overall benefits by tailoring the design of the transformations to the properties of input graphs and GPU platforms. The evaluation includes large graph data sets from KONNECT and SNAP repositories. The implementations of graph analysis algorithms are packaged into easy-to-use programming interfaces and released over the course of this project. 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.