Parallel Computations on Reconfigurable Meshes

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 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.