Computing Optimal Cycle Mean in Parallel on CUDA

Jiri Barnat, Petr Bauch, Lubos Brim, Milan Ceska
Faculty of Informatics, Masaryk University, Brno, Czech Republic
EPTCS 72, pp. 68-83, 2011


   author={Barnat}, J. and {Bauch}, P. and {Brim}, L. and {{v C}e{v s}ka}, M.},

   title={"{Computing Optimal Cycle Mean in Parallel on CUDA}"},

   journal={ArXiv e-prints},




   keywords={Computer Science – Distributed, Parallel, and Cluster Computing, Computer Science – Data Structures and Algorithms},




   adsnote={Provided by the SAO/NASA Astrophysics Data System}


Download Download (PDF)   View View   Source Source   



Computation of optimal cycle mean in a directed weighted graph has many applications in program analysis, performance verification in particular. In this paper we propose a data-parallel algorithmic solution to the problem and show how the computation of optimal cycle mean can be efficiently accelerated by means of CUDA technology. We show how the problem of computation of optimal cycle mean is decomposed into a sequence of data-parallel graph computation primitives and show how these primitives can be implemented and optimized for CUDA computation. Finally, we report a fivefold experimental speed up on graphs representing models of distributed systems when compared to best sequential algorithms.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2017 hgpu.org

All rights belong to the respective authors

Contact us: