On the parallel implementation of Goldberg's maximum flow algorithm
Richard J Anderson, João Carlos Setúbal · 1992
We describe an efficient parallel implementation of Goldberg's maximum flow algorithm for a shared-memory multiprocessor.Our main technical innovation is a method that allows a "global relabeling" heuristic to be executed concurrently with the main algorithm; this heuristic is essential for good performance in practice.We present performance results from a Sequent Symmetry for a variety of input distributions.We achieve speed-ups of up to 8.8 with 16 processors, relative to the parallel program with 1 processor (5.8 when compared to our best sequential program).We consider these speed-ups very good and we provide evidence that hardware effects and insufficient parallelism in certain inputs are the main obstacles to achieving better performance.