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 Θ(n1/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 Θ(n1/(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.
|Copyright © 2008-2016 Quentin F. Stout.|