Name
Abstract | ||
|---|---|---|
We design and implement distributed-memory parallel algorithms for computing maximal cardinality matching in a bipartite graph. Relying on matrix algebra building blocks, our algorithms expose a higher degree of parallelism on distributed-memory platforms than existing graph-based algorithms. In contrast to existing parallel algorithms, empirical approximation ratios of the new algorithms are insensitive to concurrency and stay relatively constant with increasing processor counts. On real instances, our algorithms achieve up to 300x speedup on 1024 cores of a Cray XC30 supercomputer. Even higher speedups are obtained on larger synthetically generated graphs where our algorithms show good scaling on up to 16,384 processors. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1109/CLUSTER.2015.62 | Cluster Computing |
Keywords | Field | DocType |
matching,cardinality matching,bipartite graph,maximal matching,matrix algebra | Adjacency matrix,Approximation algorithm,Line graph,Supercomputer,Computer science,Folded cube graph,Bipartite graph,Parallel computing,Algorithm,Matching (graph theory),3-dimensional matching | Conference |
ISSN | Citations | PageRank |
1552-5244 | 2 | 0.37 |
References | Authors | |
21 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ariful Azad | 1 | 138 | 15.71 |
| Aydin Buluc | 2 | 1057 | 67.49 |