SELF-CONFIGURATION OF THE MASSIVELY DEFECTIVE CELLULAR ARRAY (VLSI, PARALLEL COMPUTER, WSI (WAFER-SCALE INTEGRATION))

The rapid advancement in VLSI technology is making it feasible to consider the construction of a parallel computer that is comprised of a large number of processors previously considered impractical due to their complexity. One promising class of such architecture is a VLSI processor array that interconnects a very large number of simple processing cells on a single chip or wafer. When a huge number of devices are built on the large chip, however, it will be very difficult to make the chips without many defects. With a fixed interconnection pattern between processors, the whole processor array may not be usable when defects appear on the processor array. Furthermore, the architecture with a fixed interconnection pattern is limited in the range of computations that can be supported efficiently. By providing reconfiguration mechanisms, a VLSI processor array can be designed such that it can be reconfigured for fault-tolerance and specialization for various computations.; This thesis studies self-configuration of cells on the massively defective cellular array. We propose a massively fault-tolerant cellular array that is an array of identical cells with connections only to immediate neighbors, where the cells and the connections may be defective with high probabilities. 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. A computation model on the defective cellular array is described, and application of the architecture and self-configuration algorithms for digital signal processing is described.