Fault Covering Problems in Reconfigurable VLSI Systems

Ran Libeskind-Hadas

ISBN 10: 0792392310 / ISBN 13: 9780792392316

Editore: Springer US, Springer New York Apr 1992, 1992

Riguardo questo articolo

This item is printed on demand - Print on Demand Titel. Neuware -Fault Covering Problems in Reconfigurable VLSI Systems describes the authors' recent research on reconfiguration problems for fault-tolerance in VLSI and WSI Systems. The book examines solutions to a number of reconfiguration problems.Efficient algorithms are given for tractable covering problems and general techniques are given for dealing with a large number of intractable covering problems.The book begins with an investigation of algorithms for the reconfiguration of large redundant memories. Next, a number of more general covering problems are considered and the complexity of these problems is analyzed. Finally, a general and uniform approach is proposed for solving a wide class of covering problems.The results and techniques described here will be useful to researchers and students working in this area. As such, the book serves as an excellent reference and may be used as the text for an advanced course on the topic.Springer Verlag GmbH, Tiergartenstr. 17, 69121 Heidelberg 148 pp. Englisch.

Codice articolo 9780792392316

Dati bibliografici

• Titolo: Fault Covering Problems in Reconfigurable VLSI Systems
• Editore: Springer US, Springer New York Apr 1992
• Data di pubblicazione: 1992
• Lingua: Inglese
• ISBN 10: 0792392310
• ISBN 13: 9780792392316
• Rilegatura: Buch
• Condizione: Neu
• Dimensioni: 241 L x 160 A x 13 P (millimetri) 241 millimetri di larghezza per 160 millimetri di altezza per 13 millimetri di profondità
• Peso: 395 grammi

Descrizione articolo

Riassunto

Fault Covering Problems in Reconfigurable VLSI Systems describes the authors' recent research on reconfiguration problems for fault-tolerance in VLSI and WSI Systems. The book examines solutions to a number of reconfiguration problems.
Efficient algorithms are given for tractable covering problems and general techniques are given for dealing with a large number of intractable covering problems.
The book begins with an investigation of algorithms for the reconfiguration of large redundant memories. Next, a number of more general covering problems are considered and the complexity of these problems is analyzed. Finally, a general and uniform approach is proposed for solving a wide class of covering problems.
The results and techniques described here will be useful to researchers and students working in this area. As such, the book serves as an excellent reference and may be used as the text for an advanced course on the topic.

Contenuti

1 An Overview.- 1.1 Introduction.- 1.2 The Embedding Approach.- 1.3 The Covering Approach.- 1.3.1 Previous Work.- 1.3.2 Physical Implementation Issues in Reconfigurable Design.- 1.4 Overview of Remaining Chapters.- 2 Fault Covers in Rectangular Arrays.- 2.1 Introduction.- 2.2 Admissible Assignments.- 2.3 The Feasible Minimum Cover Problem.- 2.3.1 Critical Sets.- 2.3.2 An Exhaustive Search Algorithm for the Feasible Minimum Cover Problem.- 2.3.3 Experimental Results.- 2.4 The Feasible Cover Problem.- 2.4.1 Excess-k Critical Sets.- 2.4.2 Experimental Results.- 2.5 Two Reconfiguration Problems.- 2.5.1 Reconfiguration with Shared Spares.- 2.5.2 Reconfiguration of Programmable Logic Arrays.- 2.6 Summary.- 3 Fault Covers in Heterogeneous and General Arrays.- 3.1 Introduction.- 3.2 Fault Covers in Heterogeneous Arrays.- 3.2.1 The Feasible Cover Problem.- 3.2.2 The Feasible Minimum Cover Problem.- 3.2.3 The Minimum Feasible Cover Problem.- 3.2.4 The Feasible Cover Problem with multiple Spare Arrays.- 3.2.5 Applications of the Heterogeneous Array Model.- 3.3 Fault Covers in General Arrays.- 3.3.1 The Feasible Cover Problem.- 3.3.2 The Feasible Minimum Cover Problem.- 3.3.3 The Minimum Feasible Cover Problem.- 3.4 Summary.- 4 General Formulation of Fault Covering Problems.- 4.1 Introduction.- 4.2 A General Formulation.- 4.3 Illustrative Examples.- 4.4 Integer Linear Programming Approach.- 4.4.1 The General Transformation.- 4.4.2 Experimental Results.- 4.5 Complexity Analysis of Subcases.- 4.5.1 The Definition of Subcases and Their Complexities.- 4.5.2 Polynomial Time Algorithms.- 4.5.3 NP-Completeness Results.- 4.6 Summary.