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.