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
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
|Copyright © 2006-2018 Quentin F. Stout.|