A scalable, asynchronous spanning tree algorithm on a cluster of SMPs

Author

Cong, Guojing ; Xue, Hanhong

Author_Institution

IBM Res., Yorktown Heights, NY

fYear

2008

Firstpage

1

Lastpage

6

Abstract

Large-scale data science applications require manipulating large graphs distributed across multiple processors. In this paper we present our experimental study of an asynchronous, distributed spanning tree algorithm that handles the challenging random, sparse graphs with billions of vertices. With a constant number of barriers, our implementation scales to 1024 processors on a cluster of SMPs. Our algorithm sheds new light on the design and implementation of graph algorithms on distributed-memory machines.

Keywords

graph theory; multiprocessing systems; asynchronous spanning tree algorithm; distributed spanning tree algorithm; distributed-memory machines; multiple processors; sparse graphs; Algorithm design and analysis; Clustering algorithms; Computational biology; Databases; Design optimization; Large-scale systems; Phase change random access memory; Scalability; Tree graphs; Very large scale integration; Breadth-first Search; Cluster; Depth-first Search; Spanning Tree; Symmetric Multiprocessors;

fLanguage

English

Publisher

ieee

Conference_Titel

Parallel and Distributed Processing, 2008. IPDPS 2008. IEEE International Symposium on

Conference_Location

Miami, FL

ISSN

1530-2075

Print_ISBN

978-1-4244-1693-6

Electronic_ISBN

1530-2075

Type

conf

DOI

10.1109/IPDPS.2008.4536346

Filename

4536346