Computing Optimal Cycle Mean in Parallel on CUDA

Jiří Barnat
Petr Bauch
Luboš Brim
Milan Češka

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.

In Jiří Barnat and Keijo Heljanko: Proceedings 10th International Workshop on Parallel and Distributed Methods in verifiCation (PDMC 2011), Snowbird, Utah, USA, July 14, 2011, Electronic Proceedings in Theoretical Computer Science 72, pp. 68–83.
Published: 31st October 2011.

ArXived at: http://dx.doi.org/10.4204/EPTCS.72.8 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org