Boolean Circuit Rewiring

Tak-Kei Lam, The Chinese University of Hong Kong, Hong Kong. Wai-Chung Tang, Queen Mary University of London, UK. Xing Wei, Easy-Logic Technology Ltd. Hong Kong. Yi Diao, Easy-Logic Technology Ltd. Hong Kong. David Yu-Liang Wu, Easy-Logic Technology Ltd. Hong Kong.

• List of Figures ixList of Tables xiiiPreface xvIntroduction xvii1 Preliminaries 11.1 Boolean Circuits 11.2 Redundancy and Stuck-at Faults 41.3 Automatic Test Pattern Generation (ATPG) 61.4 Dominators 61.5 Mandatory Assignments and Recursive Learning 71.6 Graph Theory and Boolean Circuits 8References 102 Concept of Logic Rewiring 112.1 What is Rewiring? 112.2 ATPG-based Rewiring Techniques 122.2.1 Add-First 122.2.2 Delete-First 182.3 Non-ATPG-based Rewiring Techniques 242.3.1 Graph-based Alternate Wiring (GBAW) 242.3.2 SPFD 252.4 Why are Rewiring Techniques Important? 31References 333 Add-First and Non-ATPG-Based Rewiring Techniques 373.1 Redundancy Addition and Removal (RAR) 373.1.1 RAMBO 373.1.2 REWIRE 383.1.3 RAMFIRE 413.1.4 Comparison Between RAR-Based Rewiring Techniques 433.2 Node-Based Network Addition and Removal (NAR) 433.2.1 Node Merging 433.2.2 Node Addition and Removal 483.3 Other Rewiring Techniques 513.3.1 SPFD-Based Rewiring 51References 654 Delete-First Rewiring Techniques 674.1 IRRA 694.1.1 Destination of Alternative Wires 714.1.2 Source of Alternative Wires 724.2 ECR 764.2.1 Destination of Alternative Wires 804.2.2 Source of Alternative Wires 854.2.3 Overview of the Approach of Error-Cancellation-Based Rewiring 864.2.4 Complexity Analysis of ECR 874.2.5 Comparison Between ECR and Other Resynthesis Techniques 904.2.6 Experimental Result 924.3 FECR 964.3.1 Error Flow Graph Construction 974.3.2 Destination Node Identification 984.3.3 Source Node Identification 1024.3.4 ECR is a Special Case of FECR 1044.3.5 Complexity Analysis of FECR 1054.3.6 Experimental Result 1054.4 Cut-Based Error Cancellation Rewiring 1074.4.1 Preliminaries 1074.4.2 Error Frontier 1094.4.3 Cut-Based Error Cancellation Rewiring 1174.4.4 Verification of Alternative Wires 1214.4.5 Complexity Analysis of CECR 1224.4.6 Relationship Between ECR, FECR, and CECR 1224.4.7 Extending CECR for n-to-m Rewiring 1234.4.8 Speedup for CECR 1244.4.9 Experimental Results 125References 1295 Applications 1335.1 Area Reduction 1335.1.1 Preliminaries 1345.1.2 Our Methodology (“Long tail” vs “Bump tail” Curves) 1355.1.3 Details of our Approach 1405.1.4 Experimental Results 1435.2 Postplacement Optimization 1455.2.1 Wire-Length-Driven Rewiring-Based Postplacement Optimization 1455.2.2 Timing-Driven Rewiring-Based Postplacement Optimization 1515.3 ECO Timing Optimization 1585.3.1 Preliminaries 1605.3.2 Nego-Rout Operation 1615.3.3 Path-Restructuring Operation 1645.3.4 Experimental Results 1665.4 Area Reduction in FPGA Technology Mapping 1675.4.1 Incremental Logic Resynthesis (ILR): Depth-Oriented Mode 1705.4.2 Incremental Logic Resynthesis (ILR): Area-Oriented Mode 1715.4.3 Experimental Results 1735.4.4 Conclusion 1835.5 FPGA Postlayout Routing Optimization 1845.5.1 Optimization by Alternative Functions 1855.5.2 Optimization with Mapping-to-Routing Logic Rewirings 1875.5.3 Optimization by SPFD-Based Rewiring 1985.6 Logic Synthesis for Low Power Using Clock Gating and Rewiring 1995.6.1 Mechanism of Clock Gating 1995.6.2 Rewiring-Based Optimization 203References 2076 Summary 211Index 213

Select Guide Rating