| Údaje o výsledku |
| Identifikační kód | RIV/00216224:14330/11:00049681 |
| Název v původním jazyce | Computing Strongly Connected Components in Parallel on CUDA |
| Druh | D - Článek ve sborníku |
| Jazyk | eng - angličtina |
| Obor | IN - Informatika |
| Rok uplatnění | 2011 |
| Kód důvěrnosti údajů | S - Úplné a pravdivé údaje nepodléhající ochraně podle zvláštních právních předpisů |
| Počet výskytů výsledku | 2 |
| Údaje z Hodnocení výsledků výzkumných organizací 2014 |
| Výsledek byl hodnocen v Pilíři I |
| Rozsah vyřazení výsledku | Tento výskyt výsledku není vyřazen |
| Zařazení výsledku v hodnocení | D - Článek ve sborníku |
| Skupina oboru v hodnocení | 04 - Technické a informatické vědy |
| Konkrétní způsob(y) hodnocení výsledku | Výsledek hodnocený již v předchozím hodnocení, body se přebírají |
| Bodové ohodnocení | 8,000 |
| Faktor korekce | 100,9 % |
| Body (upravené podle přílohy č. 8 Metodiky) | 8,074 |
| Rozdělení výsledku mezi předkladatele |
| Organizace | Výzkumná organizace? | Podíl | Body | Body (upravené podle přílohy č. 8 Metodiky) |
|---|
| Masarykova univerzita / Fakulta informatiky | ano | 100,0 % | 8,000 | 8,074 |
|
| Tvůrci výsledku |
| Počet tvůrců celkem | 4 |
| Počet domácích tvůrců | 4 |
| Tvůrce | Barnat Jiří (státní příslušnost: CZ - Česká republika; A - domácí tvůrce; vedidk: 5692792) |
| Tvůrce | Bauch Petr (státní příslušnost: CZ - Česká republika; A - domácí tvůrce; vedidk: 5736935) |
| Tvůrce | Brim Luboš (státní příslušnost: CZ - Česká republika; A - domácí tvůrce; vedidk: 6500773) |
| Tvůrce | Češka Milan (státní příslušnost: CZ - Česká republika; A - domácí tvůrce; G - garant výsledku; vedidk: 1846000) |
| Údaje blíže specifikující výsledek |
| Popis 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 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. |
| Klíčová slova | parallel graph algorithms; strongly connected components; CUDA |
| Název sborníku | Proceedings of 25th IEEE International Parallel & Distributed Processing Symposium |
| Rozsah stran | 544-555 |
| ISSN | 1530-2075 |
| ISBN | 978-1-61284-372-8 |
| Počet stran výsledku | 12 |
| Název nakladatele | IEEE Computer Society |
| Místo vydání | Anchorage, AK |
| Místo konání akce | Anchorage, AK |
| Rok konání akce | 2011 |
| Typ akce podle státní příslušnoti účastníků | CST - Celostátní |
| Údaje o tomto záznamu o výsledku |
| Předkladatel | Masarykova univerzita / Fakulta informatiky |
| Dodavatel | MSM - Ministerstvo školství, mládeže a tělovýchovy (MŠMT) |
| Rok sběru | 2012 |
| Systémové označení dodávky dat | RIV12-MSM-14330___/01:1 |
| Specifikace | RIV/00216224:14330/11:00049681!RIV12-MSM-14330___ |
| Kontrolní kód | [BDC270067A2A] |
| Další výskyty tohoto výsledku od stejného předkladatele |
| Dodáno GA ČR v roce 2012 | Záznam s identifikačním kódem RIV/00216224:14330/11:00049681 v dodávce dat RIV12-GA0-14330___/02:1 |
| Odkazy na výzkumné aktivity, při jejichž řešení výsledek vznikl |
| Projekt | GA201/09/1389 - Verifikace a analýza velmi velkých počítačových systémů (2009-2011, GA0/GA) |
| Projekt | GD102/09/H042 - 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ů (2009-2012, GA0/GD) |
| Projekt | GP201/09/P497 - Automatizovaná formální verifikace s využitím soudobého hardware (2009-2011, GA0/GP) |
| Výzkumný záměr | MSM0021622419 - Vysoce paralelní a distribuované výpočetní systémy (2005-2011, MSM) |
| S - Specifický výzkum na vysokých školách |