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.

Inhalt

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.