Fault Covering Problems in Reconfigurable VLSI Systems

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.