1998 · 17 citations · 24 references
ComputingComputer EngineeringComputer ScienceAlgorithmsParallel AlgorithmsParallel ComputingAlgorithm AnalysisParallel Algorithm DesignParallel Computing SystemsParallel Data StructuresParallel Performance AnalysisParallel Tree AlgorithmsMinimum Spanning Tree AlgorithmsParallel Minimum Spanning TreeParallel Minimum Spanning Tree AlgorithmsTree Algorithms
Lower and upper bounds for finding a minimum spanning tree (MST) in a weighted undirected graph on the BSP model are presented. We provide the first non-trivial lower bounds on the communication volume required to solve the MST problem. Let p denote the number of processors, n the number of nodes of the input graph, and m the number of edges of the input graph. We show that in the worst case a total of \\Omega\\Gamma \\Delta min(m;pn)) bits need to be transmitted in order to solve the MST problem, where is the number of bits required to represent a single edge weight. This implies that if each message contains bits, any BSP algorithm for finding an MST requires communication time\\Omega\\Gamma g \\Delta min(m=p; n)), where g is the gap parameter of the BSP model. In addition, we present two algorithms whose running times match the lower bounds in different situations. Both algorith...
24
A bridging model for parallel computation
Leslie G. Valiant · Communications of the ACM · 1990 · 3.7K citations · Full text
LogP: towards a realistic model of parallel computation
David Culler, Richard M. Karp, David A. Patterson et al. · 1993 · 1.5K citations
LogP: towards a realistic model of parallel computation
David Culler, Richard M. Karp, David A. Patterson et al. · ACM SIGPLAN Notices · 1993 · 336 citations · Full text