Abstract: This paper is a survey of a class of reconfigurable massively parallel computers known as reconfigurable mesh computers or rmeshes. Their most distinguishing feature is the utilization of the reconfigurability of the interconnection network to establish a network topology well mapped to the algorithm communication graph. This reconfiguration is data-driven, helping them achieve far higher efficiency than standard mesh-connected computers. Reconfiguration can also be used to remove faulty processors from the network with only a slight degradation of efficiency.

Reconfigurable massively parallel computers are primarily SIMD systems due to the large numbers of processors involved. However, they differ from the typical SIMD distributed memory model in that their interconnection network is dynamic, modified by local decisions at each processor.

We examine some specific architectures, including the Polymorphic-torus, Gated-Connection Network, PAPIA2, CLIP 7, and reconfigurable bus architectures. For these architectures we consider fundamental algorithms to perform OR, XOR, addition, and component labeling of images. Fault tolerance via reconfiguration is also examined.

Keywords: reconfigurable parallel computer, ultrafast parallel algorithm, image processing, fault tolerance, arithmetic algorithms, massively parallel, SIMD.

Complete Paper. The paper appeared in Proceedings of the IEEE 79 (1991), pp. 429-443. It was digitized by IEEE.

Parallel Computing

A modest explanation of parallel computing, and a tutorial.
An overview of my work, and relevant papers.

Reconfigurable Mesh

An important early journal article is Parallel computations on reconfigurable meshes. Much of this work had appeared in conference proceedings in 1988. For additional information there is the book Reconfigurable Massively Parallel Computers.

Copyright © 2005-2018 Quentin F. Stout