Parallel Graph Partitioning on a CPU-GPU Architecture

Graph partitioning has important applications inmultiple areas of computing, including scheduling, socialnetworks, and parallel processing. In recent years, GPUshave proven successful at accelerating several graphalgorithms. However, the irregular nature of the real-worldgraphs poses a problem for GPUs, which favor regularity. Inthis paper, we discuss the design and implementation of aparallel multilevel graph partitioner for a CPU-GPU system. The partitioner aims to overcome some of the challengesarising due to memory constraints on GPUs and maximizesthe utilization of GPU threads through suitable load-balancingschemes. We present a lock-free shared-memoryscheme since fine-grained synchronization among thousandsof threads imposes too high a performance overhead. Thepartitioner, implemented in CUDA, outperforms serial Metisand parallel MPI-based ParMetis. It performs similar to theshared-memory CPU-based parallel graph partitioner mt-metis.