A fast, parallel spanning tree algorithm for symmetric multiprocessors (SMPS)

被引:48
作者
Bader, DA [1 ]
Cong, GJ
机构
[1] Georgia Inst Technol, Coll Comp, Atlanta, GA 30332 USA
[2] IBM Corp, TJ Watson Res Ctr, Yorktown Hts, NY USA
基金
美国国家科学基金会;
关键词
parallel graph algorithms; connectivity; shared memory; high-performance algorithm engineering;
D O I
10.1016/j.jpdc.2005.03.011
中图分类号
TP301 [理论、方法];
学科分类号
081202 [计算机软件与理论];
摘要
The ability to provide uniform shared-memory access to a significant number of processors in a single SMP node brings us much closer to the ideal PRAM parallel computer. Many PRAM algorithms can be adapted to SMPs with few modifications. Yet there are few studies that deal with the implementation and performance issues of running PRAM-style algorithms on SMPs. Our study in this paper focuses on implementing parallel spanning tree algorithms on SMPs. Spanning tree is an important problem in the sense that it is the building block for many other parallel graph algorithms and also because it is representative of a large class of irregular combinatorial problems that have simple and efficient sequential implementations and fast PRAM algorithms, but these irregular problems often have no known efficient parallel implementations. Experimental studies have been conducted on related problems (minimum spanning tree and connected components) using parallel computers, but only achieved reasonable speedup on regular graph topologies that can be implicitly partitioned with good locality features or on very dense graphs with limited numbers of vertices. In this paper we present a new randomized algorithm and implementation with superior performance that for the first time achieves parallel speedup on arbitrary graphs (both regular and irregular topologies) when compared with the best sequential implementation for finding a spanning tree. This new algorithm uses several techniques to give an expected running time that scales linearly with the number p of processors for suitably large inputs (n > p(2)). As the spanning tree problem is notoriously hard for any parallel implementation to achieve reasonable speedup, our study may shed new light on implementing PRAM algorithms for shared-memory parallel computers. The main results of this paper are 1. A new and practical spanning tree algorithm for symmetric multiprocessors that exhibits parallel speedups on graphs with regular and irregular topologies; and 2. an experimental study of parallel spanning tree algorithms that reveals the superior performance of our new approach compared with the previous algorithms. The source code for these algorithms is freely-available from our web site. (c) 2005 Elsevier Inc. All rights reserved.
引用
收藏
页码:994 / 1006
页数:13
相关论文
共 40 条
[1]
[Anonymous], DIMACS SERIES DISCRE
[2]
AWERBUCH B, 1987, IEEE T COMPUT, V36, P1258, DOI 10.1109/TC.1987.1676869
[3]
Bader DA, 2002, LECT NOTES COMPUT SC, V2552, P63
[4]
SIMPLE:: A methodology for programming high performance algorithms on clusters of symmetric multiprocessors (SMPs) [J].
Bader, DA ;
JáJá, J .
JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 1999, 58 (01) :92-108
[5]
BADER DA, 2004, P INT PAR DISTR PROC
[6]
BADER DA, 2001, P 5 INT WORKSHOP ALG, V2141, P129
[7]
Modeling Internet topology [J].
Calvert, KL ;
Doar, MB ;
Zegura, EW .
IEEE COMMUNICATIONS MAGAZINE, 1997, 35 (06) :160-163
[8]
Starfire: Extending the SMP envelope [J].
Charlesworth, A .
IEEE MICRO, 1998, 18 (01) :39-49
[9]
CHARLESWORTH A, 2001, P SUP SC 2001 CO NOV, P1
[10]
EFFICIENT PARALLEL ALGORITHMS FOR SOME GRAPH PROBLEMS [J].
CHIN, FY ;
LAM, J ;
CHEN, IN .
COMMUNICATIONS OF THE ACM, 1982, 25 (09) :659-665