Show simple item record

dc.contributor.authorBader, David A.
dc.contributor.authorSachdeva, Vipin
dc.date.accessioned2007-05-15T21:03:44Z
dc.date.available2007-05-15T21:03:44Z
dc.date.issued2006-02-25
dc.identifier.urihttp://hdl.handle.net/1853/14384
dc.description.abstractThe maximum flow problem is a combinatorial problem of significant importance in a wide variety of research and commercial applications. It has been extensively studied and implemented over the past 40 years. The push-relabel method has been shown to be superior to other methods, both in theoretical bounds and in experimental implementations. Our study discusses the implementation of the push-relabel network flow algorithm on present-day symmetric multiprocessors (SMP's) with large shared memories. The maximum flow problem is an irregular graph problem and requires frequent fine-grained locking of edges and vertices. Over a decade ago, Anderson and Setubal implemented Goldberg's push-relabel algorithm for shared memory parallel computers; however, modern systems differ significantly from those targeted by their implementation in that SMP's today have deep memory hierarchies and different performance costs for synchronization and fine-grained locking. Besides our new cache-aware implementation of Goldberg's parallel algorithm for modern shared-memory parallel computers, our main new contribution is the first parallel implementation and analysis of the gap relabeling heuristic that runs from 2.1 to 4.3 times faster for sparse graphs.en
dc.description.sponsorshipThis work was supported in part by NSF Grants CAREER ACI-00-93039, NSF DBI-0420513, ITR ACI-00- 81404, DEB-99-10123, ITR EIA-01-21377, Biocomplexity DEB-01-20709, and ITR EF/BIO 03-31654; and DARPA Contract NBCH30390004.en
dc.language.isoen_USen
dc.publisherGeorgia Institute of Technologyen
dc.relation.ispartofseriesCSE Technical Reports; GT-CSE-06-05en
dc.subjectFine-grained lockingen
dc.subjectGap relabeling heuristicen
dc.subjectParallel algorithmsen
dc.subjectPush-relabel algorithmen
dc.subjectSymmetric multiprocessors (SMPs)en
dc.titleA Cache-Aware Parallel Implementation of the Push-Relabel Network Flow Algorithm and Experimental Evaluation of the Gap Relabeling Heuristicen
dc.typeTechnical Reporten


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record