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.

REFERENCES

• 1: Carver Mead , Lynn Conway, Introduction to VLSI Systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1979
• 2: James L. Peterson, Petri Nets, ACM Computing Surveys (CSUR), v.9 n.3, p.223-252, Sept. 1977 [doi>10.1145/356698.356702]
• 3: Guibas, L. Private communication.
• 4: Kung, H.T. and Leiserson, C.E. Systolic Arrays (for VLSI), in Duff, I.S. and Stewart, G.W., eds., Sparse Matrix Processings 1978, pages 256-282. Society for Industrial and Applied Mathematics, 1979. (A slightly different version appears in (1), Section 8.3.)
• 5: Kung, H.T. Let's design algorithms for VLSI systems, in Proc. Conference on Very Large Scale Integration: Architecture, Design, Fabrication. California Institute of Technology, Jan. 1979.
• 6: Foster, M.J. and Kung, H.T., The design of special-purpose VLSI chips, IEEE Computer, Jan. 1980.
• 7: Kung Sun-Yuan, VLSI array processor for signal processing, Tech. Report, Dept. of E.E. Systems, USC, Los Angeles, Calif. (Also presented at Conference on Advanced Research in Integrated Circuits, M.I.T., Cambridge, Mass., Jan. 1980).
• 8: Leiserson, C.E. Systolic priority queues, Tech. Report, Dept. of Computer Science, CMU.
• 9: Hoare, C.A.R. Communicating sequential processes, CACM, vol. 21, Aug. 1977.
• 10: Israel Koren, A reconfigurable and fault-tolerant VLSI multiprocessor array, Proceedings of the 8th annual symposium on Computer Architecture, p.425-442, May 12-14, 1981, Minneapolis, Minnesota, United States
• 11: Kung, H.T. The structure of VLSI algorithms, Tech. Report, Dept. of Computer Science, CMU.
• 12: Seitz, C.L. Self-timed VLSI systems, in Proc. Conference on Very Large Scale Integration: Architecture, Design Fabrication. California Institute of Technology, Jan. 1979.
• 13: Manning, F.B. An Approach to Highly Integrated, Computer-Maintained Cellular Array, IEEE Trans. on Computers, Vol. c-26, June 1977.
• 14: Aubusson, R.C. and Catt, I., Wafer-Scale Integration - A Fault-Tolerant Procedure, IEEE J. Solid-State, Vol. SC-13, No. 3, June 1978.
• 15: Hayes, J.P. A graph model for fault-tolerant computing systems, IEEE Trans. on Computers, Vol. c-25, September 1976.
• 16: Williams, J. W. J. Algorithm 232: HEAPSORT, CACM, Vol. 7, June 1964.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.8 Performance and Reliability
      B.8.1 Reliability, Testing, and Fault-Tolerance

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: Algorithms implemented in hardware; VLSI (very large scale integration)

General Terms:
Algorithms, Design, Performance, Reliability