Accelerating Graph Partitioning on Modern GPUs

Abstract

The graph partitioning problem is critical to many traditional applications such as work balancing in distributed computing systems, layout mapping for VLSI designs, and more. Recent emergence of big data sets makes graph partitioning even more useful to problems that are larger than ever before, including ranking of web pages, identification and analysis of social communities, and many other data mining applications. Graph partitioning algorithms have high computing costs, and processing such massive graphs calls for greater performance. This study reviews previous work on graph partitioning algorithms, and discusses the possibility of accelerating them on GPUs.