Computing Strongly Connected Components in Parallel on CUDA

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F11%3A00049681" target="_blank" >RIV/00216224:14330/11:00049681 - isvavai.cz</a>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Computing Strongly Connected Components in Parallel on CUDA

Popis výsledku v původním jazyce

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 bereformulated 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ázev v anglickém jazyce

Computing Strongly Connected Components in Parallel on CUDA

Popis výsledku anglicky

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 bereformulated 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.

Druh

D - Stať ve sborníku

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)<br>S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2011

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

Proceedings of 25th IEEE International Parallel & Distributed Processing Symposium

ISBN

978-1-61284-372-8

ISSN

1530-2075

e-ISSN

—

Počet stran výsledku

12

Strana od-do

544-555

Název nakladatele

IEEE Computer Society

Místo vydání

Anchorage, AK

Místo konání akce

Anchorage, AK

Datum konání akce

1. 1. 2011

Typ akce podle státní příslušnosti

CST - Celostátní akce

Kód UT WoS článku

—