Computing Optimal Cycle Mean in Parallel on CUDA
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F11%3A00050202" target="_blank" >RIV/00216224:14330/11:00050202 - isvavai.cz</a>
Výsledek na webu
<a href="http://dx.doi.org/10.4204/EPTCS.72.8" target="_blank" >http://dx.doi.org/10.4204/EPTCS.72.8</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.4204/EPTCS.72.8" target="_blank" >10.4204/EPTCS.72.8</a>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
Computing Optimal Cycle Mean in Parallel on CUDA
Popis výsledku v původním jazyce
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 ofoptimal 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 beimplemented 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.
Název v anglickém jazyce
Computing Optimal Cycle Mean in Parallel on CUDA
Popis výsledku anglicky
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 ofoptimal 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 beimplemented 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.
Klasifikace
Druh
J<sub>x</sub> - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)
CEP obor
IN - Informatika
OECD FORD obor
—
Návaznosti výsledku
Projekt
Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.
Návaznosti
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)
Ostatní
Rok uplatnění
2011
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Údaje specifické pro druh výsledku
Název periodika
Electronic Proceedings in Theoretical Computer Science
ISSN
2075-2180
e-ISSN
—
Svazek periodika
72
Číslo periodika v rámci svazku
2011
Stát vydavatele periodika
US - Spojené státy americké
Počet stran výsledku
16
Strana od-do
68-83
Kód UT WoS článku
—
EID výsledku v databázi Scopus
—