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