Designing Scalable b-Matching Algorithms on Distributed Memory Multiprocessors by Approximation
SessionCombinatorial and Multigrid Algorithms
Session ChairJed Brown
Event Type
Paper
Algorithms
Intermediate
Introductory
TimeThursday, November 17th1:30pm - 2pm
Location355-E
DescriptionA b-Matching is a subset of edges M such that at most b(v) edges in M are incident on each vertex v, where b(v) is specified. We present a distributed-memory parallel algorithm, b-Suitor, that computes a b-Matching with more than half the maximum weight in a graph with weights on the edges. The approximation algorithm is designed to have high concurrency and low time complexity. We organize the implementation of the algorithm in terms of asynchronous supersteps that combine computation and communication, and balance the computational work and frequency of communication to obtain high performance. We present several strategies to reduce the communication volume. We implement the algorithm using a hybrid strategy using MPI and OpenMP. We demonstrate strong and weak scaling of b-Suitor up to 16K processors on two supercomputers. We compute a b-Matching in a graph with 2 billion edges in under 4 seconds using 16K processors.
