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)