Graph Processing Scheme Using GPU With Value-Driven Differential Scheduling

Abstract

Researchers have recently been using GPUs to process large quantities of graph data. However, the challenges in Host–GPU data transfer must be addressed to effectively use GPUs for graph processing. Although existing frameworks have attempted to mitigate this problem by managing active graph data transfers, issues persist owing to the need to divide graphs into subgraphs for parallel processing across multiple GPU cores. This division often leads to duplicated data transfers, resulting in high transmission overhead and low bandwidth utilization. To address these challenges and expedite graph computation, this study proposes a graph processing scheme using a GPU with value-driven differential scheduling. This approach involves dividing large graphs into subgraphs of similar sizes and contiguous vertices, allowing efficient parallelization on the GPU. The value of each subgraph is assessed based on its activity level, and its computation load is estimated using a differential subgraph scheduling technique. The proposed scheme distinguishes between high-value and low-value subgraphs and allocates them to different graph processing engines. This reduces the redundant data transmissions and enhances the transmission rate of active edges, thereby reducing the Host–GPU data transmission overhead. Experimental results demonstrate that the proposed scheme achieves a notable speedup of up to 6.6 times compared to the existing GPU-accelerated graph processing systems, including GraphCage and Subway.

Keywords

• GPU
• graph processing
• graph partitioning