Abstract: This paper considers a model of parallel computers, mesh computers with buses, where each bus provides a broadcasting capability to the processors connected to it.
We first disprove a published claim by showing that on a 2-dimensional mesh with a bus for each row, where each row must solve its own problem with data that is independent of all other rows, there are problems where the rows can cooperatively solve all subproblems faster than any single row can solve its own problem. As a corollary we obtain efficient parallel algorithms for some graph problems.
We also consider the optimal layout of buses for a given dimension and number of buses per processor, where optimality is defined in terms of the time needed to simulate any other machine with the same constraints. Optimal or nearly optimal layouts are determined for each possible choice of dimension and number of buses per processor. These layouts are based on tree, pyramid, and orthogonal tree (mesh-of-tree) designs, and are superior to all previously suggested bus layouts.
Keywords: parallel computer, broadcasting, mesh computer, cooperative problem solving, cooperative speedup, optimal stepwise simulation, or, minimum, component labeling, spanning forest, tree, pyramid, mesh-of-trees, parallel algorithm, graph theory, discrete mathematics, VLSI layout, theoretical computer science
Complete paper. This paper appears in Proc. 27th IEEE Symp. on Foundations of Computer Science (1986), pp. 264-273.
My related work in parallel computing
|
Copyright © 2005-2008 Quentin F. Stout. |