Computing Optimal Cycle Mean in Parallel on CUDA

BARNAT, Jiří, Petr BAUCH, Luboš BRIM a Milan ČEŠKA. Computing Optimal Cycle Mean in Parallel on CUDA. Electronic Proceedings in Theoretical Computer Science. 2011, roč. 72, č. 2011, s. 68-83. ISSN 2075-2180. Dostupné z: https://dx.doi.org/10.4204/EPTCS.72.8.

Základní údaje

Originální název

Computing Optimal Cycle Mean in Parallel on CUDA

Název česky

Paralelní CUDA algoritmy pro výpočet cyklů s optimální hodnotou

Autoři

BARNAT, Jiří (203 Česká republika, garant, domácí), Petr BAUCH (203 Česká republika, domácí), Luboš BRIM (203 Česká republika, domácí) a Milan ČEŠKA (203 Česká republika, domácí)

Vydání

Electronic Proceedings in Theoretical Computer Science, 2011, 2075-2180

---

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Spojené státy

Utajení

není předmětem státního či obchodního tajemství

Odkazy

EPTCS volume 72

Kód RIV

RIV/00216224:14330/11:00050202

Organizační jednotka

Fakulta informatiky

DOI

http://dx.doi.org/10.4204/EPTCS.72.8

UT WoS

000219679600009

Klíčová slova česky

Ověřování modelu; hardvérové platformy; paralelismus

Klíčová slova anglicky

Model checking; hardware platforms; parallelism

Příznaky

Mezinárodní význam, Recenzováno

---

Anotace

V originále

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.

Česky

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.

---

Návaznosti

GA201/09/1389, projekt VaV	Název: Verifikace a analýza velmi velkých počítačových systémů Investor: Grantová agentura ČR, Verifikace a analýza velmi velkých počítačových systémů
GD102/09/H042, projekt VaV	Název: 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: Grantová agentura ČR, 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ů
GP201/09/P497, projekt VaV	Název: Automatizovaná formální verifikace s využitím soudobého hardware Investor: Grantová agentura ČR, Automatizovaná formální verifikace s využitím soudobého hardware
MSM0021622419, záměr	Název: Vysoce paralelní a distribuované výpočetní systémy Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Vysoce paralelní a distribuované výpočetní systémy
MUNI/A/0914/2009, interní kód MU	Název: Rozsáhlé výpočetní systémy: modely, aplikace a verifikace (Akronym: SV-FI MAV) Investor: Masarykova univerzita, Rozsáhlé výpočetní systémy: modely, aplikace a verifikace, DO R. 2020_Kategorie A - Specifický výzkum - Studentské výzkumné projekty