2011/06/04 by George C. Caragea, Uzi Vishkin · 1 citation
Computer Science · Mathematics · #Parallel Computing and Optimization Techniques #Advanced Data Storage Technologies #Complexity and Algorithms in Graphs #Computer science #Programmer #Parallel computing #Workflow #Architecture #Flow (mathematics) #Algorithmics #Parallel algorithm #Maximum flow problem #Algorithm #Operating system #Mathematics #Mathematical optimization
paper · doi:10.1145/1989493.1989511
openalex publication_date 2011/06/04 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/29
We present a parallel solution to the Maximum-Flow (Max-Flow) problem, suitable for a modern many-core architecture. We show that by starting from a PRAM algorithm, following an established "programmer's workflow" and targeting XMT, a PRAM-inspired many-core architecture, we achieve significantly higher speed-ups than previous approaches. Comparison with the fastest known serial max-flow implementation on a modern CPU demonstrates for the first time potential for orders-of-magnitude performance improvement for Max-Flow. Using XMT, the PRAM Max-Flow algorithm is also much easier to program than for other parallel platforms, contributing a powerful example toward dual validation of both PRAM algorithmics and XMT.