Publication details

<< back
 

Computing Optimal Cycle Mean in Parallel on CUDA

Basic information
Original title:Computing Optimal Cycle Mean in Parallel on CUDA
Authors:Jiří Barnat, Petr Bauch, Luboš Brim, Milan Češka
Further information
Citation:BARNAT, Jiří - BAUCH, Petr - BRIM, Luboš - ČEŠKA, Milan. Computing Optimal Cycle Mean in Parallel on CUDA. Electronic Proceedings in Theoretical Computer Science, USA. ISSN 2075-2180, 2011, vol. 72, no. 2011, pp. 68-83. PDMC 2011.
Original language:English
Field:Informatika
WWW:link to a new windowEPTCS volume 72
Type:Article in Periodical
Keywords:Model checking; hardware platforms; parallelism

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:

 
 
top