A synchronous parallel max-flow algorithm for real-world networks

Guojing Cong

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

1 Scopus citations

Abstract

We study computing maximum flows for real-worldnetworks. In contrast to prior studies, our implementation is bulksynchronous. Our algorithm applies push and relabel operationson all active vertices in parallel, and maintains a preflow througha delayed flow update approach with handshakes between flowpushing and flow receiving.In our implementation the heuristics are no longer entangledwith the push and relabel operations as in prior implementations.We apply two heuristics well known for the sequential algorithm,that is, global relabel and gap relabel, to our parallel implementation.Experiments on networks constructed for computer visionimages show that our parallel implementation on the target 8-core machine is up to 8.6 times faster than the best sequentialimplementation.We aslo propose a new augmenting path based heuristic forsmall-world graphs. On large social networks with up to billionsof edges our implementation achieves close to 40 times parallelspeedup.

Original languageEnglish
Title of host publicationProceedings - 16th IEEE International Conference on High Performance Computing and Communications, HPCC 2014, 11th IEEE International Conference on Embedded Software and Systems, ICESS 2014 and 6th International Symposium on Cyberspace Safety and Security, CSS 2014
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages68-75
Number of pages8
ISBN (Electronic)9781479961238
DOIs
StatePublished - Mar 9 2014
Externally publishedYes
Event16th IEEE International Conference on High Performance Computing and Communications, HPCC 2014, 11th IEEE International Conference on Embedded Software and Systems, ICESS 2014 and 6th International Symposium on Cyberspace Safety and Security, CSS 2014 - Paris, France
Duration: Aug 20 2014Aug 22 2014

Publication series

NameProceedings - 16th IEEE International Conference on High Performance Computing and Communications, HPCC 2014, 11th IEEE International Conference on Embedded Software and Systems, ICESS 2014 and 6th International Symposium on Cyberspace Safety and Security, CSS 2014

Conference

Conference16th IEEE International Conference on High Performance Computing and Communications, HPCC 2014, 11th IEEE International Conference on Embedded Software and Systems, ICESS 2014 and 6th International Symposium on Cyberspace Safety and Security, CSS 2014
Country/TerritoryFrance
CityParis
Period08/20/1408/22/14

Keywords

  • Maximum flow
  • augmenting path
  • push relabel

Fingerprint

Dive into the research topics of 'A synchronous parallel max-flow algorithm for real-world networks'. Together they form a unique fingerprint.

Cite this