Russ Miller

Dept. of Computer Science, 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

Computer Science and Engineering, University of Michigan

**Abstract:**
This paper introduces the *reconfigurable mesh (mesh with reconfigurable
bus, rmesh)* as a model of computation.
It consists of an array of processors interconnected by
a reconfigurable bus system, which can be used to
dynamically obtain
interconnection patterns between the processors.
This reconfigurable computer captures salient features from a variety
of sources, including the CAAPP,
CHiP, polymorphic-torus network, and
bus automaton.

We develop several fundamental data movement operations for the reconfigurable mesh. Based on these operations, we develop new efficient algorithms for a variety of problems involving graphs and digitized images. These algorithms are asymptotically superior to those previously obtained for the aforementioned architectures, as well as to those possible on 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.
For *n* bits stored one per column on an *n*×*n* reconfigurable
mesh, their sum and parity can be computed in constant time, and if they are stored one per processor on a reconfigurable mesh with *n* processors the time is Θ(loglog *n*).
In comparison, these operation require
Ω(log *n* /loglog *n*) time
on a CRCW PRAM with a polynomial number of processors.
Many of the algorithms in this paper are also faster than is possible
via quantum computing.

**Keywords:**
parallel computer, reconfigurable computer, image algorithms,
graph algorithms,
parallel algorithm, VLSI, mesh, PRAM, mesh-of-trees, pyramid computer,
component labeling, prefix calculation, parity, XOR, graph theory

**Complete paper.**
This appeared in *IEEE Transactions on Computers* 42 (1993), pp. 678-692.
IEEE digitized it and made it available.

- Reconfigurable mesh
- Much of the work in this paper first appeared in conference proceedings in 1988, especially Data operations on reconfigurable VLSI arrays and applications, Proc. 1988 Int'l. Conf. on Parallel Processing, vol. I, IEEE, pp. 205-208, and Meshes with reconfigurable buses, Proc. 5th MIT Conf. on Advanced Research in VLSI (1988), pp. 163-178. Here is an early survey of reconfigurable mesh-connected parallel computers and some associated algorithms.
- Meshes with static buses
- I've worked with 1-dimensional mesh computers with broadcasting where there is one bus for the entire system, 2-dimensional mesh computers with broadcasting with one bus for the entire system, and meshes with multiple buses where there can be a broadcasting bus for each row and for each column (and more complex configurations).
- Parallel Computing
- A modest
explanation of
parallel computing, a
tutorial, Parallel Computing 101, and
a list of
parallel computing resources

An overview of my work, and relevant papers. - Ultrafast Algorithms
- The parity and bit summation algorithms in this paper solve problems in poly-loglog time. Other such algorithms that I've developed are surveyed in Ultrafast Parallel Algorithms and Reconfigurable Meshes.

Copyright © 2005-2018 Quentin F. Stout |