|
|
ix | |
|
|
xiii | |
Preface |
|
xv | |
Introduction |
|
xvii | |
|
|
1 | (10) |
|
|
1 | (3) |
|
1.2 Redundancy and Stuck-at Faults |
|
|
4 | (2) |
|
1.3 Automatic Test Pattern Generation (ATPG) |
|
|
6 | (1) |
|
|
6 | (1) |
|
1.5 Mandatory Assignments and Recursive Learning |
|
|
7 | (1) |
|
1.6 Graph Theory and Boolean Circuits |
|
|
8 | (3) |
|
|
10 | (1) |
|
2 Concept of Logic Rewiring |
|
|
11 | (26) |
|
|
11 | (1) |
|
2.2 ATPG-based Rewiring Techniques |
|
|
12 | (12) |
|
|
12 | (6) |
|
|
18 | (6) |
|
2.3 Non-ATPG-based Rewiring Techniques |
|
|
24 | (7) |
|
2.3.1 Graph-based Alternate Wiring (GBAW) |
|
|
24 | (1) |
|
|
25 | (6) |
|
2.4 Why are Rewiring Techniques Important? |
|
|
31 | (6) |
|
|
33 | (4) |
|
3 Add-First and Non-ATPG-Based Rewiring Techniques |
|
|
37 | (30) |
|
3.1 Redundancy Addition and Removal (RAR) |
|
|
37 | (6) |
|
|
37 | (1) |
|
|
38 | (3) |
|
|
41 | (2) |
|
3.1.4 Comparison Between RAR-Based Rewiring Techniques |
|
|
43 | (1) |
|
3.2 Node-Based Network Addition and Removal (NAR) |
|
|
43 | (8) |
|
|
43 | (5) |
|
3.2.2 Node Addition and Removal |
|
|
48 | (3) |
|
3.3 Other Rewiring Techniques |
|
|
51 | (16) |
|
3.3.1 SPFD-Based Rewiring |
|
|
51 | (14) |
|
|
65 | (2) |
|
4 Delete-First Rewiring Techniques |
|
|
67 | (66) |
|
|
69 | (7) |
|
4.1.1 Destination of Alternative Wires |
|
|
71 | (1) |
|
4.1.2 Source of Alternative Wires |
|
|
72 | (4) |
|
|
76 | (20) |
|
4.2.1 Destination of Alternative Wires |
|
|
80 | (5) |
|
4.2.2 Source of Alternative Wires |
|
|
85 | (1) |
|
4.2.3 Overview of the Approach of Error-Cancellation-Based Rewiring |
|
|
86 | (1) |
|
4.2.4 Complexity Analysis of ECR |
|
|
87 | (3) |
|
4.2.5 Comparison Between ECR and Other Resynthesis Techniques |
|
|
90 | (2) |
|
4.2.6 Experimental Result |
|
|
92 | (4) |
|
|
96 | (11) |
|
4.3.1 Error Flow Graph Construction |
|
|
97 | (1) |
|
4.3.2 Destination Node Identification |
|
|
98 | (4) |
|
4.3.3 Source Node Identification |
|
|
102 | (2) |
|
4.3.4 ECR is a Special Case of FECR |
|
|
104 | (1) |
|
4.3.5 Complexity Analysis of FECR |
|
|
105 | (1) |
|
4.3.6 Experimental Result |
|
|
105 | (2) |
|
4.4 Cut-Based Error Cancellation Rewiring |
|
|
107 | (26) |
|
|
107 | (2) |
|
|
109 | (8) |
|
4.4.3 Cut-Based Error Cancellation Rewiring |
|
|
117 | (4) |
|
4.4.4 Verification of Alternative Wires |
|
|
121 | (1) |
|
4.4.5 Complexity Analysis of CECR |
|
|
122 | (1) |
|
4.4.6 Relationship Between ECR, FECR, and CECR |
|
|
122 | (1) |
|
4.4.7 Extending CECR for n-to-m Rewiring |
|
|
123 | (1) |
|
|
124 | (1) |
|
4.4.9 Experimental Results |
|
|
125 | (4) |
|
|
129 | (4) |
|
|
133 | (78) |
|
|
133 | (12) |
|
|
134 | (1) |
|
5.1.2 Our Methodology ("Long tail" vs "Bump tail" Curves) |
|
|
135 | (5) |
|
5.1.3 Details of our Approach |
|
|
140 | (3) |
|
5.1.4 Experimental Results |
|
|
143 | (2) |
|
5.2 Postplacement Optimization |
|
|
145 | (13) |
|
5.2.1 Wire-Length-Driven Rewiring-Based Postplacement Optimization |
|
|
145 | (6) |
|
5.2.2 Timing-Driven Rewiring-Based Postplacement Optimization |
|
|
151 | (7) |
|
5.3 ECO Timing Optimization |
|
|
158 | (9) |
|
|
160 | (1) |
|
5.3.2 Nego-Rout Operation |
|
|
161 | (3) |
|
5.3.3 Path-Restructuring Operation |
|
|
164 | (2) |
|
5.3.4 Experimental Results |
|
|
166 | (1) |
|
5.4 Area Reduction in FPGA Technology Mapping |
|
|
167 | (17) |
|
5.4.1 Incremental Logic Resynthesis (ILR): Depth-Oriented Mode |
|
|
170 | (1) |
|
5.4.2 Incremental Logic Resynthesis (ILR): Area-Oriented Mode |
|
|
171 | (2) |
|
5.4.3 Experimental Results |
|
|
173 | (10) |
|
|
183 | (1) |
|
5.5 FPGA Postlayout Routing Optimization |
|
|
184 | (15) |
|
5.5.7 Optimization by Alternative Functions |
|
|
185 | (2) |
|
5.5.2 Optimization with Mapping-to-Routing Logic Rewirings |
|
|
187 | (11) |
|
5.5.3 Optimization by SPFD-Based Rewiring |
|
|
198 | (1) |
|
5.6 Logic Synthesis for Low Power Using Clock Gating and Rewiring |
|
|
199 | (12) |
|
5.6.1 Mechanism of Clock Gating |
|
|
199 | (4) |
|
5.6.2 Rewiring-Based Optimization |
|
|
203 | (4) |
|
|
207 | (4) |
|
|
211 | (2) |
Index |
|
213 | |