Graph matching and coloring constitute two fundamental classes of combinatorial problems having numerous established as well as emerging applications in computational science and engineering, high-performance computing, and informatics. We provide a snapshot of an on-going work on the design and implementation of new highly-scalable distributed-memory parallel algorithms for two prototypical problems from these classes, edge-weighted matching and distance-1 vertex coloring. Graph algorithms in general have low concurrency and poor data locality, making it challenging to achieve scalability on massively parallel machines. We overcome this challenge by employing a variety of techniques, including approximation, speculation and iteration, optimized communication, and randomization, in concert. We present preliminary results on weak and strong scalability studies conducted on an IBM Blue Gene/P machine employing up to tens of thousands of processors. The results show that the algorithms hold strong potential for computing at petascale.
Revised: December 27, 2012 |
Published: May 31, 2011
Citation
Catalyurek U., F. Dobrian, A.H. Gebremedhin, M. Halappanavar, and A. Pothen. 2011.Distributed-memory Parallel Algorithms for Matching and Coloring. In IEEE International Symposium on Parallel and Distributed Processing Workshops and Phd Forum (IPDPSW 2011), May 16-20, 2011 Anchorage, Alaska, 1971-1980. Piscataway, New Jersey:Institute of Electrical and Electronics Engineers.PNNL-SA-77038.doi:10.1109/IPDPS.2011.360