About: Computing Strongly Connected Components in Parallel on CUDA

Facets (new session)
Description
Metadata
Settings
- owl:sameAs
- Inference Rule:

About: Computing Strongly Connected Components in Parallel on CUDA Goto Sponge NotDistinct Permalink

An Entity of Type : http://linked.opendata.cz/ontology/domain/vavai/Vysledek, within Data Space : linked.opendata.cz associated with source document(s)

Attributes	Values
rdf:type	skos:Concept http://linked.opendata.cz/ontology/domain/vavai/Vysledek
Description	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. 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. (en)
Title	Computing Strongly Connected Components in Parallel on CUDA Computing Strongly Connected Components in Parallel on CUDA (en)
skos:prefLabel	Computing Strongly Connected Components in Parallel on CUDA Computing Strongly Connected Components in Parallel on CUDA (en)
skos:notation	RIV/00216224:14330/11:00049681!RIV12-GA0-14330___
http://linked.open...avai/predkladatel	Fakulta informatiky
http://linked.open...avai/riv/aktivita	P S Z
http://linked.open...avai/riv/aktivity	P(GA201/09/1389), P(GD102/09/H042), P(GP201/09/P497), S, Z(MSM0021622419)
http://linked.open...vai/riv/dodaniDat	2012
http://linked.open...aciTvurceVysledku	Češka, Milan Barnat, Jiří Bauch, Petr Brim, Luboš
http://linked.open.../riv/druhVysledku	D - Článek ve sborníku
http://linked.open...iv/duvernostUdaju	S - Úplné a pravdivé údaje nepodléhající ochraně podle zvláštních právních předpisů
http://linked.open...titaPredkladatele	Masarykova univerzita / Fakulta informatiky
http://linked.open...dnocenehoVysledku	191575
http://linked.open...ai/riv/idVysledku	RIV/00216224:14330/11:00049681
http://linked.open...riv/jazykVysledku	eng - angličtina
http://linked.open.../riv/klicovaSlova	parallel graph algorithms; strongly connected components; CUDA (en)
http://linked.open.../riv/klicoveSlovo	CUDA parallel graph algorithms strongly connected components
http://linked.open...ontrolniKodProRIV	[02CB631AA6F6]
http://linked.open...v/mistoKonaniAkce	Anchorage, AK
http://linked.open...i/riv/mistoVydani	Anchorage, AK
http://linked.open...i/riv/nazevZdroje	Proceedings of 25th IEEE International Parallel & Distributed Processing Symposium
http://linked.open...in/vavai/riv/obor	IN
http://linked.open...ichTvurcuVysledku	4 (xsd:int)
http://linked.open...cetTvurcuVysledku	4 (xsd:int)
http://linked.open...vavai/riv/projekt	Verification and Analysis of Large-Scale Computer Systems Mathematical and Engineering Approaches to Developing Reliable and Secure Concurrent and Distributed Computer Systems Automated formal verification using modern hardware
http://linked.open...UplatneniVysledku	2011
http://linked.open...iv/tvurceVysledku	Barnat, Jiří Bauch, Petr Brim, Luboš Češka, Milan
http://linked.open...vavai/riv/typAkce	CST - Celostátní
http://linked.open.../riv/zahajeniAkce	2011-01-01 (xsd:date)
http://linked.open...n/vavai/riv/zamer	Highly Parallel and Distributed Computing Systems
issn	1530-2075
number of pages	12 (xsd:int)
http://purl.org/ne...btex#hasPublisher	IEEE Computer Society
https://schema.org/isbn	978-1-61284-372-8
http://localhost/t...ganizacniJednotka	14330
is http://linked.open...avai/riv/vysledek of	Computing Strongly Connected Components in Parallel on CUDA Computing Strongly Connected Components in Parallel on CUDA

Faceted Search & Find service v1.16.118 as of Jun 21 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3240 as of Jun 21 2024, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (126 GB total memory, 58 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software