What designers of wafer scale systems should know about local sparing
- 17 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
Local sparing is a simple way to organize the redundancy of a fault tolerant system. Any system can be locally spared. Furthermore, local sparing preserves both regularity and planarity. In spite of this, the potential usefulness of local sparing appears to have been overlooked. Suppose that the designer wishes to assure, with high probability, a fault-free copy of the n-element system desired. If local sparing is used then, as proved, i) the resulting area is /spl Theta/(log n) times the area of the system desired; ii) the wire length is /spl Oscr/(/spl radic/(log n)) times the maximum wirelength in the desired system; iii) an optimal diagnosis algorithm identifies the faulty elements in /spl Theta/(n log/sup 2/ n) time; iv) in optimal time /spl Theta/(n log n+number of wires in the desired system), a simple configuration algorithm achieves a fault-free copy of the desired system if and only if a fault-free copy exists. The authors illustrate these results for arrays, binary trees, and hypercubes. In addition, v) if Y denotes the probability of achieving a fault-free copy of the system desired then, using h-fold redundancy, the maximum rate at which elements can fail is ((/spl minus/ln Y)/n)/sup 1/h/. Local sparing is simple, widely-applicable, and low-cost. A disadvantage is that, depending on the system desired, the cost may not be optimal. However, there is strong reason to prefer local sparing over global sparing, and in some cases local sparing is better than more popular approaches to configuration.<>Keywords
This publication has 15 references indexed in Scilit:
- Extremally fault tolerant arraysPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Architectural yield analysis of random defects in wafer scale integrationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- A new statistical approach for fault-tolerant VLSI systemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- On the reconfiguration of memory arrays containing clustered faultsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Almost sure diagnosis of almost every good elementPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Almost Sure Fault Tolerance in Random GraphsSIAM Journal on Computing, 1987
- A review of fault-tolerant techniques for the enhancement of integrated circuit yieldProceedings of the IEEE, 1986
- Wafer-Scale Integration of Systolic ArraysIEEE Transactions on Computers, 1985
- Sources of failures and yield improvement for VLSI and restructurable interconnects for RVLSI and WSI: Part I—Sources of failures and yield improvement for VLSIProceedings of the IEEE, 1984
- On the Connection Assignment Problem of Diagnosable SystemsIEEE Transactions on Electronic Computers, 1967