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 on an n×n reconfigurable mesh, their sum and parity can be computed in constant time. On a reconfigurable mesh with n processors the time required is Θ(loglog n). In comparison, these operation require Ω(log n /loglog n) time on a CRCW PRAM with a polynomial number of processors. 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.
|Copyright © 2005-2017 Quentin F. Stout|