SC Conference - Activity Details

Doruk Bozdag  (Ohio State University)

Ümit Çatalyürek  (Ohio State University)

Florin Dobrian  (Conviva, Inc.)

Assefaw Gebremedhin  (Purdue University)

Mahantesh Halappanavar  (Old Dominion University)

Alex Pothen  (Purdue University)

Tuesday,  05:15PM - 07:00PM

Room Oregon Ballroom Lobby

Combinatorial models and their algorithms play a crucial enabling role in scientific and high-performance computing. Graph coloring and matching represent two fundamental classes of such combinatorial problems. We have developed highly scalable parallel algorithms for prototypical problems from these two classes, distance-1 coloring and edge-weighted matching. The underlying serial algorithms in both cases yield empirically high-quality approximate solutions extremely fast. The algorithms are, however, inherently sequential and thus challenging to parallelize. The novel techniques we employ to overcome the challenge include: graph partitioning; speculation—maximizing concurrency by tentatively allowing inconsistencies; randomization; and bundled communication. The algorithms have been efficiently implemented using MPI. We describe the algorithms and present results---that demonstrate scalable performance---from experiments conducted on an IBM Blue Gene/P and Cray XT-4 machines using tens of thousands of processors. We will also discuss computational science contexts in which the coloring and matching models are utilized.