TY - GEN
T1 - A synchronous parallel max-flow algorithm for real-world networks
AU - Cong, Guojing
N1 - Publisher Copyright:
© 2014 IEEE.
PY - 2014/3/9
Y1 - 2014/3/9
N2 - 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.
AB - 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.
KW - Maximum flow
KW - augmenting path
KW - push relabel
UR - http://www.scopus.com/inward/record.url?scp=84949925314&partnerID=8YFLogxK
U2 - 10.1109/HPCC.2014.213
DO - 10.1109/HPCC.2014.213
M3 - Conference contribution
AN - SCOPUS:84949925314
T3 - Proceedings - 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
SP - 68
EP - 75
BT - Proceedings - 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
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 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
Y2 - 20 August 2014 through 22 August 2014
ER -