Boolean Circuit Rewiring Bridging Logical and Physical Designs

Demonstrates techniques which will allow rewiring rates of over 95%, enabling adoption of deep sub-micron chips for industrial applications

Logic synthesis is an essential part of the modern digital IC design process in semi-conductor industry. This book discusses a logic synthesis technique called “rewiring” and its latest technical advancement in term of rewirability. Rewiring technique has surfaced in academic research since 1993 and there is currently no book available on the market which systematically and comprehensively discusses this rewiring technology. The authors cover logic transformation techniques with concentration on rewiring. For many decades, the effect of wiring on logic structures has been ignored due to an ideal view of wires and their negligible role in the circuit performance. However in today’s semiconductor technology wiring is the major player in circuit performance degeneration and logic synthesis engines can be improved to deal with this through wire-based transformations. This book introduces the automatic test pattern generation (ATPG)-based rewiring techniques, which are recently active in the realm of logic synthesis/verification of VLSI/SOC designs.

• Unique comprehensive coverage of semiconductor rewiring techniques written by leading researchers in the field
• Provides complete coverage of rewiring from an introductory to intermediate level
• Rewiring is explained as a flexible technique for Boolean logic synthesis, introducing the concept of Boolean circuit transformation and testing, with examples
• Readers can directly apply the described techniques to real-world VLSI design issues
• Focuses on the automatic test pattern generation (ATPG) based rewiring methods although some non-ATPG based rewiring methods such as graph based alternative wiring (GBAW), and “set of pairs of functions to be distinguished” (SPFD) based rewiring are also discussed

A valuable resource for researchers and postgraduate students in VLSI and SoC design, as well as digital design engineers, EDA software developers, and design automation experts that specialize in the synthesis and optimization of logical circuits.

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 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

The New copy of this book will include any supplemental materials advertised. Please check the title of the book to determine if it should include any access cards, study guides, lab manuals, CDs, etc.

The Used, Rental and eBook copies of this book are not guaranteed to include any supplemental materials. Typically, only the book itself is included. This is true even if the title states it includes any access cards, study guides, lab manuals, CDs, etc.