Broadcasting in Mesh-Connected Computers

Quentin F. Stout
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

For all of these, on an nxn computer the problem can be solved in Θ(n2/3) time, vs. the Θ(n) time required on a mesh-connected computer without broadcasting

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


Quentin's Home Copyright © 2006-2016 Quentin F. Stout.