J 2011

Computing Optimal Cycle Mean in Parallel on CUDA

BARNAT, Jiří, Petr BAUCH, Luboš BRIM and Milan ČEŠKA

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

Language

English

Type of outcome

Článek v odborném periodiku

Field of Study

10201 Computer sciences, information science, bioinformatics

Country of publisher

United States of America

Confidentiality degree

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

References:

RIV identification code

RIV/00216224:14330/11:00050202

Organization unit

Faculty of Informatics

DOI

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
Změněno: 12/12/2012 11:09, Mgr. Petr Bauch, Ph.D.

Abstract

ORIG CZ

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.

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