Computing Strongly Connected Components in Parallel on CUDA

BARNAT, Jiří, Petr BAUCH, Luboš BRIM and 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, p. 544 - 555. ISBN 978-1-61284-372-8.

Basic information

Original name

Computing Strongly Connected Components in Parallel on CUDA

Authors

BARNAT, Jiří (203 Czech Republic, 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, guarantor, belonging to the institution)

Edition

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

Publisher

IEEE Computer Society

---

Other information

Language

English

Type of outcome

Stať ve sborníku

Field of Study

10201 Computer sciences, information science, bioinformatics

Country of publisher

Czech Republic

Confidentiality degree

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

References:

URL

RIV identification code

RIV/00216224:14330/11:00049681

Organization unit

Faculty of Informatics

ISBN

978-1-61284-372-8

ISSN

Keywords in English

parallel graph algorithms; strongly connected components; CUDA

Tags

best

Tags

International impact, Reviewed

---

Abstract

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.

---

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/0057/2011, interní kód MU	Name: Posílení zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity (Acronym: SKONF) Investor: Masaryk University, Category A
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