Self-Configuration of Defective Cellular Arrays
Myoung Sung Lee
Gideon Frieder
Departments of Electrical Engineering and Computer Science,
University of Michigan,
Ann Arbor, MI 48109, USA
Abstract
Rapid advances in VLSI technology are making it feasible to consider the construction of parallel computers with very large numbers of cells. One promising architecture for such computers is a VLSI cellular array that interconnects many simple processing cells on a single large chip or wafer. It will be very difficult, however, to make a chip of this kind without many defects. With a fixed interconnection pattern between cells, the whole cellular array may not be usable when there are any defects. Furthermore, an architecture with a fixed interconnection pattern is limited in the range of computations that it can support efficiently. By providing reconfiguration mechanisms, a VLSI cellular array can be designed so that it can be reconfigured for fault-tolerance and specialized for various computations.
This paper discusses a massively fault-tolerant cellular array, which contains identical cells with connections only to immediate neighbors, where the cells and the connections may be defective with a high probability. The cell can function as a processing element, as a memory, or as a switching element that connects to other cells. On the defective array, a large cluster of interconnected working cells is formed, and the working cells in the cluster are configured into a graph that determines the function of the array.
The detailed architecture of the massively fault-tolerant cellular array is described, and the distributed algorithms for forming the cluster of working cells and configuring the cells into a linear array, a two-dimensional array, a binary tree, and signal flow graphs for various filters are presented. Simulation data are presented when both cells and connections are defective with various probabilities.
