TY - GEN
T1 - A scalable, asynchronous spanning tree algorithm on a cluster of SMPs
AU - Cong, Guojing
AU - Xue, Hanhong
PY - 2008
Y1 - 2008
N2 - 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.
AB - 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.
KW - Breadth-first search
KW - Cluster
KW - Depth-first search
KW - Spanning tree
KW - Symmetric multiprocessors
UR - http://www.scopus.com/inward/record.url?scp=51049106840&partnerID=8YFLogxK
U2 - 10.1109/IPDPS.2008.4536346
DO - 10.1109/IPDPS.2008.4536346
M3 - Conference contribution
AN - SCOPUS:51049106840
SN - 9781424416943
T3 - IPDPS Miami 2008 - Proceedings of the 22nd IEEE International Parallel and Distributed Processing Symposium, Program and CD-ROM
BT - IPDPS Miami 2008 - Proceedings of the 22nd IEEE International Parallel and Distributed Processing Symposium, Program and CD-ROM
T2 - IPDPS 2008 - 22nd IEEE International Parallel and Distributed Processing Symposium
Y2 - 14 April 2008 through 18 April 2008
ER -