2013/01/01 by Aydın Buluç, Kamesh Madduri · 1 citation
Computer Science · Mathematics · #Graph Theory and Algorithms #Interconnection Networks and Systems #Complexity and Algorithms in Graphs #Mathematics #Graph partition #Graph #Scalability #Computation #Theoretical computer science #Voltage graph #Computer science #Line graph #Discrete mathematics #Algorithm #Database
paper · doi:10.1090/conm/588/11709
openalex publication_date 2013/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/15
Inter-node communication time constitutes a significant fraction of the execution time of graph algorithms on distributed-memory systems. Global computations on large-scale sparse graphs with skewed degree distributions are particularly challenging to optimize for, as prior work shows that it is difficult to obtain balanced partitions with low edge cuts for these graphs. In this work, we attempt to determine the optimal partitioning and distribution of such graphs, for load-balanced parallel execution of communication-intensive graph algorithms. We use breadth-first search (BFS) as a representative example, and derive upper bounds on the communication costs incurred with a two-dimensional partitioning of the graph. We present empirical results for communication costs with various graph partitioning strategies, and also obtain parallel BFS execution times for several large-scale DIMACS Challenge instances on a supercomputing platform. Our performance results indicate that for several graph instances, reducing work and communication imbalance among partitions is more important than minimizing the total edge cut.