5632

Brief announcement: better speedups for parallel max-flow

George Constantin Caragea, Uzi Vishkin
University of Maryland, College Park, MD, USA
Proceedings of the 23rd ACM symposium on Parallelism in algorithms and architectures, SPAA ’11, 2011

@inproceedings{caragea2011brief,

   title={Brief announcement: better speedups for parallel max-flow},

   author={Caragea, G.C. and Vishkin, U.},

   booktitle={Proceedings of the 23rd ACM symposium on Parallelism in algorithms and architectures},

   pages={131–134},

   year={2011},

   organization={ACM}

}

Download Download (PDF)   View View   Source Source   

892

views

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.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2017 hgpu.org

All rights belong to the respective authors

Contact us: