Back to Search
Start Over
An Asynchronous Multithreaded Algorithm for the Maximum Network Flow Problem with Nonblocking Global Relabeling Heuristic
- Source :
- IEEE Transactions on Parallel and Distributed Systems. 22:1025-1033
- Publication Year :
- 2011
- Publisher :
- Institute of Electrical and Electronics Engineers (IEEE), 2011.
-
Abstract
- In this paper, we present a novel asynchronous multithreaded algorithm for the maximum network flow problem. The algorithm is based on the classical push-relabel algorithm, which is essentially sequential and requires intensive and costly lock usages to parallelize it. The novelty of the algorithm is in the removal of lock and barrier usages, thereby enabling a much more efficient multithreaded implementation. The newly designed push and relabel operations are executed completely asynchronously and each individual process/thread independently decides when to terminate itself. We further propose an asynchronous global relabeling heuristic to speed up the algorithm. We prove that our algorithm finds a maximum flow with O(|V|2||-E|) operations, where |V| is the number of vertices and |E| is the number of edges in the graph. We also prove the correctness of the relabeling heuristic. Extensive experiments show that our algorithm exhibits better scalability and faster execution speed than the lock-based parallel push-relabel algorithm.
- Subjects :
- Push–relabel maximum flow algorithm
Correctness
Speedup
Computational complexity theory
Computer science
Heuristic
Maximum flow problem
Parallel algorithm
Out-of-kilter algorithm
Graph theory
Parallel computing
Flow network
Graph
Vertex (geometry)
Computational Theory and Mathematics
Hardware and Architecture
Signal Processing
Non-blocking algorithm
Algorithm design
Algorithm
Subjects
Details
- ISSN :
- 10459219
- Volume :
- 22
- Database :
- OpenAIRE
- Journal :
- IEEE Transactions on Parallel and Distributed Systems
- Accession number :
- edsair.doi...........295c8a25e889f76ab86f3d46660afa3a