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