Computing Strongly Connected Components in Parallel on CUDA

BARNAT, Jiří, Petr BAUCH, Luboš BRIM a Milan ČEŠKA. Computing Strongly Connected Components in Parallel on CUDA. In Proceedings of 25th IEEE International Parallel & Distributed Processing Symposium. Anchorage, AK: IEEE Computer Society, 2011, s. 544 - 555. ISBN 978-1-61284-372-8.

Základní údaje

Originální název

Computing Strongly Connected Components in Parallel on CUDA

Autoři

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

Vydání

Anchorage, AK, Proceedings of 25th IEEE International Parallel & Distributed Processing Symposium, od s. 544 - 555, 12 s. 2011

Nakladatel

IEEE Computer Society

---

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Česká republika

Utajení

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

Odkazy

URL

Kód RIV

RIV/00216224:14330/11:00049681

Organizační jednotka

Fakulta informatiky

ISBN

978-1-61284-372-8

ISSN

Klíčová slova anglicky

parallel graph algorithms; strongly connected components; CUDA

Štítky

best

Příznaky

Mezinárodní význam, Recenzováno

---

Anotace

V originále

The problem of decomposing a directed graph into its strongly connected components is a fundamental graph problem inherently present in many scientific and commercial applications. In this paper we show how some of the existing parallel algorithms can be reformulated in order to be accelerated by NVIDIA CUDA technology. In particular, we design a new CUDA-aware procedure for pivot selection and we adapt the particular parallel algorithms for CUDA accelerated computation. We also experimentally demonstrate that with a single GTX 480 GPU card we can easily outperform optimal serial CPU implementation -- by an order of magnitude in most cases, 40 times on some sufficiently big instances. This is a particularly interesting result as unlike the serial CPU case, the asymptotic complexity of the parallel algorithms is not optimal.

---

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/0057/2011, interní kód MU	Název: Posílení zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity (Akronym: SKONF) Investor: Masarykova univerzita, Posílení zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity, DO R. 2020_Kategorie A - Specifický výzkum - Studentské výzkumné projekty
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