Computing Optimal Cycle Mean in Parallel on CUDA
BARNAT, Jiří, Petr BAUCH, Luboš BRIM and Milan ČEŠKA. Computing Optimal Cycle Mean in Parallel on CUDA. Electronic Proceedings in Theoretical Computer Science. 2011, vol. 72, No 2011, p. 68-83. ISSN 2075-2180. Available from: https://dx.doi.org/10.4204/EPTCS.72.8. |
Other formats:
BibTeX
LaTeX
RIS
|
Basic information | |
---|---|
Original name | Computing Optimal Cycle Mean in Parallel on CUDA |
Name in Czech | Paralelní CUDA algoritmy pro výpočet cyklů s optimální hodnotou |
Authors | BARNAT, Jiří (203 Czech Republic, guarantor, belonging to the institution), Petr BAUCH (203 Czech Republic, belonging to the institution), Luboš BRIM (203 Czech Republic, belonging to the institution) and Milan ČEŠKA (203 Czech Republic, belonging to the institution). |
Edition | Electronic Proceedings in Theoretical Computer Science, 2011, 2075-2180. |
Other information | |
---|---|
Original language | English |
Type of outcome | Article in a journal |
Field of Study | 10201 Computer sciences, information science, bioinformatics |
Country of publisher | United States of America |
Confidentiality degree | is not subject to a state or trade secret |
WWW | EPTCS volume 72 |
RIV identification code | RIV/00216224:14330/11:00050202 |
Organization unit | Faculty of Informatics |
Doi | http://dx.doi.org/10.4204/EPTCS.72.8 |
UT WoS | 000219679600009 |
Keywords (in Czech) | Ověřování modelu; hardvérové platformy; paralelismus |
Keywords in English | Model checking; hardware platforms; parallelism |
Tags | International impact, Reviewed |
Changed by | Changed by: Mgr. Petr Bauch, Ph.D., učo 208047. Changed: 12/12/2012 11:09. |
Abstract |
---|
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. |
Abstract (in Czech) |
---|
Výpočet cyklů s optimální hodnotou v orientovaném grafu má mnoho různých využití. V tomto článku navrhujeme nový datově paralelní algoritmus pro řešení prolému s využitím technologie CUDA. Experimentální měření ukazují až pětinásobné zrychlení v porovnání s nejlepším sekvenčním algoritmem. |
Links | |
---|---|
GA201/09/1389, research and development project | Name: Verifikace a analýza velmi velkých počítačových systémů |
Investor: Czech Science Foundation, Verification and Analysis of Large-Scale Computer Systems | |
GD102/09/H042, research and development project | Name: Matematické a inženýrské metody pro vývoj spolehlivých a bezpečných paralelních a distribuovaných počítačových systémů |
Investor: Czech Science Foundation | |
GP201/09/P497, research and development project | Name: Automatizovaná formální verifikace s využitím soudobého hardware |
Investor: Czech Science Foundation, Automated formal verification using modern hardware | |
MSM0021622419, plan (intention) | Name: Vysoce paralelní a distribuované výpočetní systémy |
Investor: Ministry of Education, Youth and Sports of the CR, Highly Parallel and Distributed Computing Systems | |
MUNI/A/0914/2009, interní kód MU | Name: Rozsáhlé výpočetní systémy: modely, aplikace a verifikace (Acronym: SV-FI MAV) |
Investor: Masaryk University, Category A |
PrintDisplayed: 15/10/2024 16:35