Computing Optimal Cycle Mean in Parallel on CUDA

Investor logo
Investor logo
Investor logo

Warning

This publication doesn't include Faculty of Education. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

BARNAT Jiří BAUCH Petr BRIM Luboš ČEŠKA Milan

Year of publication 2011
Type Article in Periodical
Magazine / Source Electronic Proceedings in Theoretical Computer Science
MU Faculty or unit

Faculty of Informatics

Citation
Web EPTCS volume 72
Doi http://dx.doi.org/10.4204/EPTCS.72.8
Field Informatics
Keywords Model checking; hardware platforms; parallelism
Description 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.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.