Fault Covering Problems in Reconfigurable VLSI Systems Book

	Preface
1	An Overview	1
1.1	Introduction	1
1.2	The Embedding Approach	3
1.3	The Covering Approach	7
1.3.1	Previous Work	7
1.3.2	Physical Implementation Issues in Reconfigurable Design	9
1.4	Overview of Remaining Chapters	15
2	Fault Covers in Rectangular Arrays	19
2.1	Introduction	19
2.2	Admissible Assignments	21
2.3	The Feasible Minimum Cover Problem	24
2.3.1	Critical Sets	25
2.3.2	An Exhaustive Search Algorithm for the Feasible Minimum Cover Problem	33
2.3.3	Experimental Results	38
2.4	The Feasible Cover Problem	39
2.4.1	Excess-k Critical Sets	39
2.4.2	Experimental Results	45
2.5	Two Reconfiguration Problems	47
2.5.1	Reconfiguration with Shared Spares	49
2.5.2	Reconfiguration of Programmable Logic Arrays	50
2.6	Summary	54
3	Fault Covers in Heterogeneous and General Arrays	55
3.1	Introduction	55
3.2	Fault Covers in Heterogeneous Arrays	56
3.2.1	The Feasible Cover Problem	58
3.2.2	The Feasible Minimum Cover Problem	62
3.2.3	The Minimum Feasible Cover Problem	64
3.2.4	The Feasible Cover Problem with Multiple Spare Arrays	71
3.2.5	Applications of the Heterogeneous Array Model	74
3.3	Fault Covers in General Arrays	76
3.3.1	The Feasible Cover Problem	78
3.3.2	The Feasible Minimum Cover Problem	83
3.3.3	The Minimum Feasible Cover Problem	86
3.4	Summary	89
4	General Formulation of Fault Covering Problems	91
4.1	Introduction	91
4.2	A General Formulation	93
4.3	Illustrative Examples	96
4.4	Integer Linear Programming Approach	100
4.4.1	The General Transformation	101
4.4.2	Experimental Results	105
4.5	Complexity Analysis of Subcases	107
4.5.1	The Definition of Subcases and Their Complexities	108
4.5.2	Polynomial Time Algorithms	110
4.5.3	NP-Completeness Results	112
4.6	Summary	116
	Bibliography	119
	Index	129