Title :
A Synchronous Parallel Max-Flow Algorithm for Real-World Networks
Author_Institution :
IBM T.J. Watson Res. Center, Yorktown Heights, NY, USA
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;
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
DOI :
10.1109/HPCC.2014.213