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.