EECS Department, University of Michigan

**Abstract:**
This paper develops optimal parallel algorithms for 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. For a variety of semigroup and image
processing problems this provides a significant improvement over the
times possible using only the base mesh computer.
These algorithms provide counterexamples to a published theorem.
Algorithms are given for computing global reductions of semigroup operations,
such as the sum or max of all values, and for various
operations on digitized black/white image input. These image operations are

- finding the median row of the black pixels,
- finding the extreme points of the convex hull of the black pixels,
- finding the nearest black neighbor of each black pixel, and
- finding the closest pair of black pixels.

**Keywords:**
bus, broadcasting, mesh computer, semigroup computation, image
processing, convex hull, nearest neighbors, wave propagation,
parallel computing, parallel algorithms

**Complete paper:**
This paper appears in
*Proc. 1982 Conf. on Information Sciences and Systems*,
Princeton University (1982), pp. 85-90.

**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 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.
- An explanation of parallel computing and a tutorial, Parallel Computing 101.

Copyright © 2006-2018 Quentin F. Stout. |