Experiences with Parallel Multi-threaded Network Maximum Flow Algorithm

Print Friendly, PDF & Email

praceThe European PRACE organization has published a series of excellent whitepapers on scalable algorithms. Produced as part of the Work Package 8 of the PRACE 1IP Project, the most recent paper is entitled: Experiences with Parallel Multi-threaded Network Maximum Flow Algorithm.

The problem of computing the maximum flow problem on capacitated networks arises in many application areas. In the area of heterogeneous computing, it arises in job or process scheduling when allocations of resources to jobs/processesneed to be tuned. The maximum ow solver is difficult to parallelize. Highly optimized sequential version of maximum flow solvers such as those by Goldberg exists. This work describes how some of the concurrency problems are resolved in our existing Pmaxflow solver. Pmaxflow employs a parallel pre-flow push algorithm to compute the maximum flow. Results of various tests that compare Goldberg’s sequential solvers and Pmaxflow on a NUMA shared memory computer are presented.

Additional papers include:

Read the Full Story.