Fast Minimum Spanning Tree for Large Graphs on the GPU

Simple item page
dc.contributor.authorVineet, Vibhaven_US
dc.contributor.authorHarish, Pawanen_US
dc.contributor.authorPatidar, Suryakanten_US
dc.contributor.authorNarayanan, P. J.en_US
dc.contributor.editorDavid Luebke and Philipp Slusalleken_US
dc.date.accessioned2013-10-29T15:48:19Z
dc.date.available2013-10-29T15:48:19Z
dc.date.issued2009en_US
dc.description.abstractGraphics Processor Units are used for many general purpose processing due to high compute power available on them. Regular, data-parallel algorithms map well to the SIMD architecture of current GPU. Irregular algorithms on discrete structures like graphs are harder to map to them. Efficient data-mapping primitives can play crucial role in mapping such algorithms onto the GPU. In this paper, we present a minimum spanning tree algorithm on Nvidia GPUs under CUDA, as a recursive formulation of Boruvka's approach for undirected graphs. We implement it using scalable primitives such as scan, segmented scan and split. The irregular steps of supervertex formation and recursive graph construction are mapped to primitives like split to categories involving vertex ids and edge weights. We obtain 30 to 50 times speedup over the CPU implementation on most graphs and 3 to 10 times speedup over our previous GPU implementation. We construct the minimum spanning tree on a 5 million node and 30 million edge graph in under 1 second on one quarter of the Tesla S1070 GPU.en_US
dc.description.seriesinformationHigh-Performance Graphicsen_US
dc.identifier.isbn978-1-60558-603-8en_US
dc.identifier.issn2079-8687en_US
dc.identifier.urihttps://doi.org/10.1145/1572769.1572796en_US
dc.publisherThe Eurographics Associationen_US
dc.titleFast Minimum Spanning Tree for Large Graphs on the GPUen_US
Files
Collections
High-Performance Graphics 2009