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. Online. 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. [citováno 2024-04-23]

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

• Originální 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í
• WWW: 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

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.

Anotace č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