Please use this identifier to cite or link to this item: https://doi.org/10.1145/2145816.2145842
Title: Scalable parallel minimum spanning forest computation
Authors: Nobari, S.
Cao, T.-T.
Karras, P.
Bressan, S. 
Keywords: GPU
Minimum spanning forest
Parallel graph algorithms
Issue Date: 2012
Source: Nobari, S.,Cao, T.-T.,Karras, P.,Bressan, S. (2012). Scalable parallel minimum spanning forest computation. Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPOPP : 205-214. ScholarBank@NUS Repository. https://doi.org/10.1145/2145816.2145842
Abstract: The proliferation of data in graph form calls for the development of scalable graph algorithms that exploit parallel processing environments. One such problem is the computation of a graph's minimum spanning forest (MSF). Past research has proposed several parallel algorithms for this problem, yet none of them scales to large, high-density graphs. In this paper we propose a novel, scalable, parallel MSF algorithm for undirected weighted graphs. Our algorithm leverages Prim's algorithm in a parallel fashion, concurrently expanding several subsets of the computed MSF. Our effort focuses on minimizing the communication among different processors without constraining the local growth of a processor's computed subtree. In effect, we achieve a scalability that previous approaches lacked. We implement our algorithm in CUDA, running on a GPU and study its performance using real and synthetic, sparse as well as dense, structured and unstructured graph data. Our experimental study demonstrates that our algorithm outperforms the previous state-of-the-art GPU-based MSF algorithm, while being several order of magnitude faster than sequential CPU-based algorithms. Copyright © 2012 ACM.
Source Title: Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPOPP
URI: http://scholarbank.nus.edu.sg/handle/10635/40902
ISBN: 9781450311601
DOI: 10.1145/2145816.2145842
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

8
checked on Dec 13, 2017

Page view(s)

72
checked on Dec 9, 2017

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.