2002 · 66 citations · 8 references
ComputingComputer ScienceComputer ArchitectureParallel AlgorithmsParallel ComputingCommunication OverheadDistributed ComputingDistributed Memory ParallelismDistributed Memory SystemsParallel Computing SystemsParallel Performance AnalysisDistributed MemoryMinimum Spanning Tree AlgorithmsMinimum Spanning Tree ProblemParallel Algorithm AnalysisParallel Graph AlgorithmsParallel Minimum Spanning TreeParallel Minimum Spanning Tree AlgorithmsParallel Speedup Analysis
We study parallel algorithms for the minimum spanning tree problem, based on the sequential algorithm of O. Boruvka (1926). The target architectures for our algorithm are asynchronous, distributed-memory machines. Analysis of our parallel algorithm on a simple model that is reminiscent of the LogP model, shows that in principle a speedup proportional to the number of processors can be achieved, but that communication costs can be significant. To reduce these costs, we develop a new randomized linear work pointer jumping scheme that performs better than previous linear work algorithms. We also consider empirically the effects of data imbalance on the running time. For the graphs used in our experiments, load balancing schemes result in little improvement in running times. Our implementations on sparse graphs with 64,000 vertices on Thinking Machine's CM-5 achieve a speedup factor of about 4 on 16 processors. On this environment, packaging of messages turns out to be the most effective way to reduce communication costs.
8
LogP: towards a realistic model of parallel computation
David Culler, Richard M. Karp, David A. Patterson et al. · 1993 · 1.5K citations
Albert D. Alexandrov, Mihai Ionescu, Klaus E. Schauser et al. · 1995 · 490 citations
Deterministic parallel list ranking
Richard Anderson, Gary L. Miller · Algorithmica · 1991 · 74 citations