Computer Science and Engineering, University of Michigan

**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. A specific example is the "leftmost 1" problem:
all processors have either a 0 or a 1, and the goal is for each processor
to determine the leftmost processor in its row which has a 1.
For an *n* x *n* mesh this can be solved in

- Θ(n) time if no broadcasting is used,
- Θ(n
^{1/2}) time if each row uses only its own bus, and - Θ(n
^{1/3}) time if the rows cooperate.

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, row broadcasting, row bus, mesh computer,
cooperative problem solving,
cooperative speedup, optimal stepwise simulation, minimum, component
labeling, spanning forest, tree, pyramid, mesh-of-trees

**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**

- I've worked on several different models of mesh-connected computers
with broadcasting:
- 1-dimensional mesh computers with broadcasting with one bus for the entire system.
- 2-dimensional mesh computers with broadcasting with one bus for the entire system.
- reconfigurable meshes, where the buses are created dynamically.

- My papers in parallel computing and an overview of my research.
- An explanation of parallel computing and a tutorial, Parallel Computing 101.

Copyright © 2005-2024 Quentin F. Stout. |