Accelerated Multilevel Graph Partitioning on GPUs

Graph partitioning is a long-standing research problem and has applications in various domains, such as data mining, scientific computing, VLSI design. For many years researchers have been focusing on improving the performance of graph partitioning using multi-core CPUs and accelerators like GPUs. However, efficient implementation of graph partitioning on GPU is a challenge. This is because graphs exhibit irregular behavior whereas GPUs follow SIMD execution patterns and GPUs have various resources and efficient utilization is the key to improving the performance.This paper aims to provide an efficient GPU based implementation of multi-level graph partitioning scheme. We provide GPU implementations of coarsening, partitioning, and refinement phases of the algorithm, to improve the overall performance of the graph partitioning scheme. We evaluated our implementation on various real-world datasets, and we observed a significant improvement in the performance when compared to the baseline METIS.