Variation-Aware Analog Structural Synthesis (eBook)

Trent McConaghy is co-founder and Chief Scientific Officer of Solido Design Automation Inc. He was a co-founder and Chief Scientist of Analog Design Automation Inc., which was acquired by Synopsys Inc. in 2004. Prior to that, he did research for the Canadian Department of National Defense. He received his PhD degree in Electrical Engineering from the Katholieke Universiteit Leuven, Belgium, in 2008. He received a Bachelor’s in Engineering (with great distinction), and a Bachelor’s in Computer Science (with great distinction), both from the University of Saskatchewan, Canada, in 1999. He has about 40 peer-reviewed technical papers and patents granted / pending. He has given invited talks / tutorials at many labs, universities, and conferences such as JPL, MIT, ICCAD, and DAC. He is regularly a technical program committee member and reviewer in both the CAD and intelligent systems fields, such as IEEE Trans CAD, ACM TODAES, Electronics Letters, to IEEE Trans Evolutionary Computation, the Journal of Genetic Programming and Evolvable Machines, GPTP, GECCO, ICES, etc. His research interest is in statistical machine learning and intelligent systems, with transistor-level CAD applications such as variation-aware design, analog topology design, automated sizing, knowledge extraction, and symbolic modeling.Michiel Steyaert was born in Aalst, Belgium, in 1959. He received the masters degree in electrical-mechanical engineering and the Ph.D. degree in electronics from the Katholieke Universiteit Leuven (K.U.Leuven), Heverlee, Belgium in 1983 and 1987, respectively. From 1983 to 1986 he obtained an IWNOL fellowship (Belgian National Fundation for Industrial Research) which allowed him to work as a Research Assistant  at the Laboratory ESAT at K.U.Leuven. In 1987 he was responsible for several industrial projects in the field of analog micropower circuits at the Laboratory ESAT as an IWONL Project Researcher. In 1988 he was a Visiting Assistant Professor at the University of California, Los Angeles. In 1989 he was appointed by the National Fund of Scientific Research (Belgium) as Research Associate, in 1992 as a Senior Research Associate and in 1996 as a Research Director at the Laboratory ESAT, K.U.Leuven. Between 1989 and 1996 he was also a part-time Associate Professor. He is now a Full Professor at the K.U.Leuven. His current research interests are in high-performance and high-frequency analog integrated circuits for telecommunication systems and analog signal processing. Prof.Steyaert received the 1990 and 2001 European Solid-State Circuits Conference Best Paper Award. He received the 1991 and the 2000 NFWO Alcatel-Bell-Telephone award for innovative work in integrated circuits for telecommunications. Prof.Steyaert received the 1995 and 1997 IEEE-ISSCC Evening Session Award, the 1999 IEEE Circuit and Systems Society Guillemin-Cauer Award and is currently an IEEE-Fellow.Georges Gielen received the MSc and PhD degrees in Electrical Engineering from the Katholieke Universiteit Leuven, Belgium, in 1986 and 1990, respectively. He currently is a Full Professor at the Katholieke Universiteit Leuven. His research interests are in the design of analog and mixed-signal integrated circuits, and especially in analog and mixed-signal CAD tools and design automation (modeling, simulation and symbolic analysis, analog synthesis, analog layout generation, analog and mixed-signal testing). He is coordinator or partner of several (industrial) research projects in this area, including several European projects (EU, MEDEA, ESA). He has authored or coauthored five books and more than 300 papers in edited books, international journals and conference proceedings. He regularly is a member of the Program Committees of international conferences (DAC, ICCAD, ISCAS, DATE, CICC...), and served as General Chair of the DATE conference in 2006 and of the International Conference on Computer-Aided Design in 2007. He serves regularly as member of editorial boards of international journals (IEEE Transactions on Circuits and Systems, Springer international journal on Analog Integrated Circuits and Signal Processing, Elsevier Integration). He received the 1995 Best Paper Award in the John Wiley international journal on Circuit Theory and Applications, and was the 1997 Laureate of the Belgian Royal Academy on Sciences, Literature and Arts in the discipline of Engineering. He received the 2000 Alcatel Award from the Belgian National Fund of Scientific Research for his innovative research in telecommunications, and won the DATE 2004 Best Paper Award. He is a Fellow of the IEEE, served as elected member of the Board of Governors of the IEEE Circuits And Systems (CAS) society and as chairman of the IEEE Benelux CAS chapter. He served as the President of the IEEE Circuits And Systems (CAS) Society in 2005. He was elected DATE Fellow in 2007, and received the IEEE Computer Society Outstanding Contribution Award and the IEEE Circuits and Systems Society Meritorious Service Award in 2007.

Summary of Contents 6
Contents 7
Preface 10
Acronyms and Notation 13
Chapter 1 Introduction 20
1.1 Motivation 20
1.1.1 Exponential Improvement of Computational Substrate Could Stop or Slow 21
1.1.2 Exponential Improvement in Algorithms/ Software Could Stop or Slow 22
1.2 Background and Contributions to Analog CAD 23
1.2.1 Analog CAD’s Context 23
1.2.2 Basic Analog Design Flow 24
1.2.3 Handling Complex Chips via Hierarchical Design 25
1.2.4 Systematic Analog Design 27
1.2.5 SPICE in the Design Flow 27
1.2.6 Beyond SPICE: Other Industrial Analog CAD Tools 28
1.2.7 Tool Categories and Design Automation 28
1.2.8 Design Automation Tools: Adoption Criteria 29
1.2.9 Front-End Design Automation Tools in Industry 30
1.2.10 Motivation for Knowledge Extraction 32
1.2.11 Contributions to Analog CAD 34
1.3 Background and Contributions to AI 36
1.3.1 Challenges in AI 36
1.3.2 GP and Complex Design 37
1.3.3 Building Block Reuse in GP 38
1.3.4 Contribution to AI: Complex Design 40
1.3.5 Other Contributions to AI 42
1.4 Analog CAD Is a Fruit.y for AI 43
1.5 Conclusion 43
Chapter 2 Variation-Aware Sizing: Background 45
2.1 Introduction and Problem Formulation 45
2.1.1 Introduction 45
2.1.2 Problem Formulation 45
2.1.3 Yield Optimization Tool Requirements 48
2.2 Review of Yield Optimization Approaches 50
2.2.1 Approach: Direct Monte Carlo on SPICE 50
2.2.2 Approach: Direct Monte Carlo on Symbolic Models 53
2.2.3 Approach: Direct Monte Carlo on Precomputed Regression Models 53
2.2.4 Approach: Adaptively Updated Regression Models 54
2.2.5 Approach: FF/SS Corners 55
2.2.6 Approach: 3-s Hypercube Corners 56
2.2.7 Approach: Inner-Loop Corners 56
2.2.8 Approach: Inner-Sampling Corners 57
2.2.9 Approach: Device Operating Constraints 57
2.2.10 Approach: Device Operating Constraints Plus Safety Margins 57
2.2.11 Approach: Density Estimation from SPICE Monte Carlo 58
2.2.12 Approach: Density Estimation from Regression Models 59
2.2.13 Approach: Spec-Wise Linearization and Sensitivity Updates 59
2.2.14 Approach: Maximum Volume Ellipsoid 61
2.2.15 Approach: Tradeo. Response Surface 62
2.3 Conclusion 62
Chapter 3 Globally Reliable, Variation-Aware Sizing: SANGRIA 64
3.1 Introduction 64
3.2 Foundations: Model-Building Optimization (MBO) 65
3.3 Foundations: Stochastic Gradient Boosting 70
3.4 Foundations: Homotopy 76
3.5 SANGRIA Algorithm 76
3.6 SANGRIA Experimental Results 87
3.7 On Scaling to Larger Circuits 99
3.8 Conclusion 100
Chapter 4 Knowledge Extraction in Sizing: CAFFEINE 101
4.1 Introduction and Problem Formulation 101
4.1.1 Chapter Summary 101
4.1.2 Motivation 102
4.1.3 Approach 103
4.1.4 Problem Formulation 105
4.1.5 Chapter Outline 106
4.2 Background: GP and Symbolic Regression 106
4.2.1 Background: High-Level Issues 106
4.2.2 Background: Speci.c SR Issues 107
4.3 CAFFEINE Canonical Form Functions 110
4.4 CAFFEINE Search Algorithm 112
4.4.1 Multi-Objective Approach 113
4.4.2 Grammar Implementation of Canonical Form Functions 114
4.4.3 High-Level CAFFEINE Algorithms 115
4.4.4 Evolutionary Search Operators 117
4.5 CAFFEINE Results 118
4.5.1 Experimental Setup 118
4.5.2 Results: Whitebox Models and Tradeo.s 120
4.5.3 Results: Comparison to Posynomial-Based Symbolic Modeling 124
4.5.4 Results: Comparison to State-of-the-Art Blackbox Regression Approaches 126
4.6 Scaling Up CAFFEINE: Algorithm 129
4.6.1 Technique: Subtree Caching 129
4.6.2 Technique: On-the-.y Pruning with Gradient Directed Regularization 130
4.6.3 Technique: Pre-Evolution Filtering of Single-Variable Expressions 131
4.6.4 Technique: Always Include All Linear Basis Functions 133
4.7 Scaling Up CAFFEINE: Results 133
4.8 Application: Behaviorial Modeling 137
4.9 Application: Process-Variable Robustness Modeling 141
4.9.1 Introduction 141
4.9.2 Process-Variable Robustness Modeling: Initial Tests 143
4.9.3 Process-Variable Robustness Modeling: Latent Variable Regression 146
4.9.4 Process-Variable Robustness Modeling: Experiments Using Latent Variable Regression 149
4.10 Application: Design-Variable Robustness Modeling 154
4.11 Application: Automated Sizing 155
4.12 Application: Analytical Performance Tradeo.s 155
4.13 Sensitivity To Search Algorithm 155
4.14 Conclusion 156
Chapter 5 Circuit Topology Synthesis: Background 158
5.1 Introduction 158
5.2 Topology-Centric Flows 160
5.2.1 Flow: Industrial Status Quo 160
5.2.2 Flow: Automated Topology Selection 161
5.2.3 Flow: Flat, Lightweight Multi-Topology Sizing 163
5.2.4 Flow: Open-Ended Topology Synthesis 164
5.2.5 Flow: Hierarchical, Massively Multi-Topology Sizing 165
5.2.6 Hierarchical, Massively Multi-Topology Sizing With Novelty 167
5.2.7 Flows: Summary 168
5.3 Reconciling System-Level Design 168
5.4 Requirements for a Topology Selection/Design Tool 171
5.5 Open-Ended Synthesis and the Analog Problem Domain 172
5.5.1 Design “Implementation” 173
5.5.2 Analog Designer Perspective 173
5.5.3 Performance Estimation and Circuit Robustness 174
5.5.4 Robustness of Manually-Designed Topologies 176
5.5.5 An Updated Model of the Open-Ended Synthesis Problem 179
5.6 Conclusion 182
Chapter 6 Trustworthy Topology Synthesis: MOJITO Search Space 183
6.1 Introduction 183
6.1.1 Target Flow 183
6.1.2 Background: The Power of Domain Knowledge 184
6.1.3 Reuse of Structural Domain Knowledge 185
6.2 Search Space Framework 187
6.2.1 Search Space Framework I: Base 187
6.2.2 Search Space Framework II: On “Small” Changes 190
6.3 A Highly Searchable Op Amp Library 194
6.4 Operating-Point Driven Formulation 195
6.5 Worked Example 196
6.6 Size of Search Space 200
6.6.1 Size of Op Amp Space 201
6.6.2 How Rich can a Search Space Be? 202
6.6.3 This is Trustworthy Analog Structural Synthesis 203
6.7 Conclusion 204
Chapter 7 Trustworthy Topology Synthesis: MOJITO Algorithm 205
7.1 Introduction 205
7.1.1 Problem Formulation 206
7.2 High-Level Algorithm 207
7.3 Search Operators 210
7.3.1 Mutation Operator 210
7.3.2 Crossover Operator 213
7.4 Handling Multiple Objectives 213
7.4.1 Multi-Objective Selection: Round One: NSGA-II 213
7.4.2 Multi-Objective Selection: Round Two: ARF 214
7.4.3 Multi-Objective Selection: Round Three: MOEA/D 215
7.4.4 Multi-Objective Selection: Round Four: TAPAS 216
7.5 Generation of Initial Individuals 216
7.5.1 Initial Individuals: Round One: Approach 217
7.5.2 Initial Individuals: Round One: Issues 218
7.5.3 Initial Individuals: Round Two: Approach 218
7.5.4 Initial Individuals: Round Two: Issues 219
7.5.5 Initial Individuals: Round Three 219
7.5.6 Initial Individuals: Round Three: Observations 220
7.6 Experimental Setup 221
7.7 Experiment: Hit Target Topologies? 222
7.8 Experiment: Diversity? 223
7.9 Experiment: Human-Competitive Results? 223
7.10 Discussion: Comparison to Open-Ended Structural Synthesis 226
7.11 Conclusion 227
Chapter 8 Knowledge Extraction in Topology Synthesis 228
8.1 Introduction 228
8.1.1 Abstract 228
8.1.2 Background 229
8.1.3 Aims 229
8.2 Generation of Database 231
8.3 Extraction of Specs-To-Topology Decision Tree 232
8.3.1 Introduction 232
8.3.2 Decision Tree: Problem Formulation and Approach 234
8.3.3 Decision Tree: Experimental Results 234
8.3.4 Decision Tree: Discussion 235
8.4 Global Nonlinear Sensitivity Analysis 236
8.4.1 Introduction 236
8.4.2 Sensitivity Analysis: Problem Formulation and Approach 236
8.4.3 Sensitivity Analysis: Results and Discussion 239
8.5 Extraction of Analytical Performance Tradeo.s 240
8.5.1 Introduction 240
8.5.2 Analytical Performance Tradeo.s: Approach 241
8.5.3 Analytical Performance Tradeo.s: Results and Discussion 242
8.6 Conclusion 242
Chapter 9 Variation-Aware Topology Synthesis & Knowledge Extraction
9.1 Introduction 244
9.2 Problem Speci.cation 244
9.3 Background 245
9.3.1 Robust Topology Synthesis in Analog CAD 245
9.3.2 Robust Topology Synthesis in Genetic Programming 246
9.4 Towards a Solution 247
9.5 Proposed Approach: MOJITO-R 247
9.6 MOJITO-R Experimental Validation 250
9.6.1 Generation of Database 250
9.6.2 Performances on Whole Pareto Front 251
9.6.3 Topologies on the Whole Pareto Front 253
9.6.4 100%-Yield Pareto Front 254
9.7 Conclusion 257
Chapter 10 Novel Variation-Aware Topology Synthesis 259
10.1 Introduction 259
10.2 Background 260
10.3 MOJITO-N Algorithm and Results 261
10.3.1 Target Work.ow for Designers 261
10.3.2 MOJITO-N Aims 262
10.3.3 MOJITO-N Inputs and Outputs 262
10.3.4 MOJITO-N Algorithm 263
10.3.5 MOJITO-N Results 264
10.4 ISCLEs Algorithm And Results 265
10.4.1 Motivations 265
10.4.2 Machine Learning and ISCLEs 267
10.4.3 ISCLEs Weak Learners 270
10.4.4 Multi-Topology Sizing 271
10.4.5 ISCLEs Experimental Results 273
10.5 Conclusion 278
Chapter 11 Conclusion 279
11.1 General Contributions 279
11.2 Specific Contributions 279
11.3 Future Work 282
11.4 Final Remarks 287
References 288
Index 312