Computer Science and Engineering, University of Michigan

**Abstract:**
We consider the effects of augmenting a mesh-connected
computer with a second communication system that is bus-based. On this
bus, a processor may broadcast a value to all other processors
simultaneously, taking unit time, with the restriction that only one
broadcast occurs at any one time. We show that this significantly
decreases the time to do simple problems such as semigroup calculations
or finding the median, but it cannot significantly improve sorting. For
example, in a one-dimensional mesh computer without broadcasting, if
there are *n* processors and each has one value, then
Θ(n) time is needed to find the minimum, find the median, or
sort them, while with broadcasting this can be accomplished in
Θ(n^{1/2}), Θ((n log n)^{1/2}), and
Θ(n)
time, respectively. The times for minimum and sorting on the mesh with
broadcasting are shown to be optimal.

More generally, for any dimension
*d*, finding a minimum of *n* values, or any other semigroup
computation, on a d-dimensional mesh with broadcasting with *n*
processors (with equal extent in all dimensions) can be completed in
Θ(n^{1/(d+1)}) time,
and this time is proven to be optimal.

**Keywords:** parallel computer,
bus, broadcasting, mesh connected computer, median, selection, semigroup
computation, sorting, communication lower bounds

**Complete paper**.
This paper appears in
*IEEE Transactions on Computers* C-32 (1983), pp. 826-830.

**Related work:**

- I've worked on several different models of mesh-conected computers
with broadcasting:
- 2-dimensional mesh computers with broadcasting with the same broadcast model as here, i.e., one bus for the entire system.
- meshes with multiple buses where there can be a broadcasting bus for each row and for each column, and more complex scenarios as well,
- reconfigurable meshes, where the buses are created dynamically.

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

Copyright © 2008-2018 Quentin F. Stout. |