GPU-accelerated Graph Processing

Abstract:

Graph processing is of vital significance for investigating complex relationships and mining underlying knowledge in different fields. The rapidly increasing scale of problems and the strict requirement for real-time solutions have drastically raised interest in the area of high-performance graph processing. Specifically, graph processing on graphics processing units (GPUs) has recently attracted a great deal of attention in both industry and academia, due to the GPU's enormous potential for boosting the graph processing efficiency as an accelerator.

Although prior studies migrate various graph applications to GPUs and demonstrate a significantly boosted graph processing performance achieved on GPUs, there still exist many challenges that impede the popularization of GPUs as a graph processing accelerator in broader application scenarios. Therefore, in this thesis, we aim to propose a systematic solution to make GPU-accelerated graph processing more practical, i.e., to develop a hardware-agnostic graph processing system that handles large-scale and dynamic graphs.

First, to meet the requirement for handling dynamic graph application scenarios on GPUs, we propose GPMA. GPMA is a dynamic graph storage scheme on GPUs which supports dynamic insertions, deletions, and modifications of graph data on GPUs with a sub-linear complexity guarantee, and is the first study to explore efficient dynamic graph maintenance on GPUs. It puts an end to the status that, when facing dynamic graph processing scenarios where graphs are frequently evolving, an entire static graph rebuilding is inevitable for every single update, which results in a severe graph update overhead.

Second, to cope with graphs that are overly large to fit into the device memory of GPUs, we propose GCGT. GCGT is the first study to conduct GPU-accelerated graph processing tasks on compressed graphs without explicit decompression for effectively reducing the memory footprint of graph data, to alleviate the scarce device memory issue of GPUs for large-scale graphs. Benefited from the proposed GCGT for compressed graph processing, the GPU's device memory occupied by the graph applications can be reduced by 2x-14x with slight and negligible performance degradation.

Third, to mitigate the issue of the steep learning curve for graph application developers, which is caused by various dedicated techniques for optimizing the performance of GPU-based graph processing from different perspectives, we propose SAGE, a hardware-agnostic solution from the perspective of developers. SAGE is a self-adaptive GPU-accelerated graph processing approach, which can start from commonly used graph representations without any preprocessing, and gradually optimize the graph data arrangement for the hardware adaptation on the fly by maintaining intermediate auxiliary information and sampling runtime memory access patterns. SAGE takes effect in a self-adaptive manner, which not only effectively reduces the programming difficulty of graph applications but also gets rid of the overhead of preprocessing introduced by dedicated solutions.