Fault-tolerant wafer-scale architectures for VLSI

Abstract

The basic problem which limits both yields and chip sizes is the fact that circuits created using current design techniques will not function correctly in the presence of even a single flaw of sufficient size anywhere on the chip. In this work we examine the problem of constructing chips up to the size of a wafer which operate correctly despite the presence of such flaws. This can be accomplished by building on the wafer a nearest-neighbor network of small, independent, asynchronously communicating modules. A specific algorithm to be performed by the wafer is then mapped onto a fault-free subgraph of the network. We are interested in algorithms which map naturally onto a linear array of identical processors. Construction of fault-tolerant implementations of these algorithms is addressed in two contexts. First we consider the general problem of finding a fault-free subgraph of the host network which is isomorphic to the linear array required to solve a problem. We then examine ways to tailor a specific, known algorithm to the fault-tolerant context.