DocumentCode :
3575026
Title :
A Synchronous Parallel Max-Flow Algorithm for Real-World Networks
Author :
Guojing Cong
Author_Institution :
IBM T.J. Watson Res. Center, Yorktown Heights, NY, USA
fYear :
2014
Firstpage :
68
Lastpage :
75
Abstract :
We study computing maximum flows for real-world networks. In contrast to prior studies, our implementation is bulk synchronous. Our algorithm applies push and relabel operations on all active vertices in parallel, and maintains a preflow through a delayed flow update approach with handshakes between flow pushing and flow receiving. In our implementation the heuristics are no longer entangled with 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 vision images show that our parallel implementation on the target 8-core machine is up to 8.6 times faster than the best sequential implementation. We also propose a new augmenting path based heuristic for small-world graphs. On large social networks with up to billions of edges our implementation achieves close to 40 times parallel speedup.
Keywords :
graph theory; mathematics computing; network theory (graphs); parallel algorithms; computer vision image; parallel implementation; real-world network; sequential algorithm; small-world graph; synchronous parallel max-flow algorithm; Algorithm design and analysis; Approximation algorithms; Communities; Computer vision; Heuristic algorithms; Program processors; Social network services; Maximum flow; augmenting path; push relabel;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
High Performance Computing and Communications, 2014 IEEE 6th Intl Symp on Cyberspace Safety and Security, 2014 IEEE 11th Intl Conf on Embedded Software and Syst (HPCC,CSS,ICESS), 2014 IEEE Intl Conf on
Print_ISBN :
978-1-4799-6122-1
Type :
conf
DOI :
10.1109/HPCC.2014.213
Filename :
7056720
Link To Document :
بازگشت