In IEEE Transactions on Computers 42 (1993), pp. 678-692.

Parallel Computations on Reconfigurable Meshes

Russ Miller
Dept of Comp Sci & Eng, State University of New York at Buffalo

V. K. Prasanna-Kumar, Dionisios I. Reisis
Department of Electrical Engineering-Systems, University of Southern California

Quentin F. Stout
EECS Department, University of Michigan

Abstract: This paper introduces the mesh with reconfigurable bus (reconfigurable mesh) as a model of computation. The reconfigurable mesh captures salient features from a variety of sources, including the CAAPP, CHiP, polymorphic-torus network, and bus automaton. It consists of an array of processors interconnected by a reconfigurable bus system, which can be used to dynamically obtain various interconnection patterns between the processors. In this paper, we introduce a variety of fundamental data movement operations for the reconfigurable mesh. Based on these operations, we also introduce new algorithms that are efficient for solving a variety of problems involving graphs and digitized images. The algorithms that we present are asymptotically superior to those previously obtained for the aforementioned reconfigurable architectures, as well as to those previously obtained for the mesh, the mesh with multiple broadcasting, the mesh with multiple buses, the mesh-of-trees, and the pyramid computer, to name a few. Highlights include a logarithmic time algorithm to label the connected components of a graph given its adjacency matrix, as well as polylogarithmic time algorithms to solve problems involving convexity and connectivity of figures in images. We also show the power of reconfigurability by solving some problems, such as exclusive OR, more efficiently on the reconfigurable mesh than is possible on the PRAM.

Keywords: parallel computer, reconfigurable mesh, image algorithms, graph algorithms, parallel algorithms, VLSI, mesh, PRAM, mesh-of-trees, pyramid computer, component labeling, global or, prefix calculation, parity, graph theory, computer architecture, image processing, computer science

IEEE has digitized this paper and made it available.
Full paper (PDF) Full paper (Postscript)
Full paper (compressed Postscript)

Russ Miller (miller@cse.buffalo.edu)