2021/05/02 by Seher Acer, Erik G. Boman, Acer, Seher +5 · 1 citation
Computer Science · #68W10 #Caching and Content Delivery #Discrete Mathematics (cs.DM) #Distributed #FOS: Computer and information sciences #Graph Theory and Algorithms #Mathematical Software (cs.MS) #Network Packet Processing and Optimization #Parallel #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.2105.00578
openalex publication_date 2021/05/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Graph partitioning has been an important tool to partition the work among several processors to minimize the communication cost and balance the workload. While accelerator-based supercomputers are emerging to be the standard, the use of graph partitioning becomes even more important as applications are rapidly moving to these architectures. However, there is no distributed-memory parallel, multi-GPU graph partitioner available for applications. We developed a spectral graph partitioner, Sphynx, using the portable, accelerator-friendly stack of the Trilinos framework. In Sphynx, we allow using different preconditioners and exploit their unique advantages. We use Sphynx to systematically evaluate the various algorithmic choices in spectral partitioning with a focus on the GPU performance. We perform those evaluations on two distinct classes of graphs: regular (such as meshes, matrices from finite element methods) and irregular (such as social networks and web graphs), and show that different settings and preconditioners are needed for these graph classes. The experimental results on the Summit supercomputer show that Sphynx is the fastest alternative on irregular graphs in an application-friendly setting and obtains a partitioning quality close to ParMETIS on regular graphs. When compared to nvGRAPH on a single GPU, Sphynx is faster and obtains better balance and better quality partitions. Sphynx provides a good and robust partitioning method across a wide range of graphs for applications looking for a GPU-based partitioner.