Mixed-Signal Layout Generation Concepts

by Van Roermund, Arthur H. M.; Leenaerts, Domine M. W.

• ISBN13: 9781402075988
• ISBN10: 1402075987
• Format: Hardcover
• Copyright: 2003-11-01
• Publisher: Kluwer Academic Pub

Summary

Mixed-Signal Layout Generation Concepts covers important physical-design issues that exist in contemporary analog and mixed-signal design flows. Due to the increasing pressure on time-to-market, the steep increase in chip fabrication costs, and the increasing design complexity, it becomes even more challenging to produce a first-time right IC layout. The fundamental issues in creating a layout are placement and routing. Although these coupled problems have been investigated for many decades, no satisfactory automated solution has emerged yet. Fortunately, supported by modern computing power and results of new research that further improve computation efficiency, significant steps forward have been taken. Mixed-Signal Layout Generation Concepts brings together many principles and techniques required to successfully develop and implement layout generation tools to accommodate many mixed-signal layout generation needs. Not only does it provide a comprehensive overview of state-of-the-art concepts, it also illustrates many concepts with intuitive examples and pseudo code. Altogether, it facilitates creation of insight in a vast and complex area. For those who are new to the area of mixed-signal layout generation, this book provides an excellent introduction to advanced topics in this area. A practicing EDA researcher or tool developer might find this book a useful reference that combines classical and new principles. In addition, this book relates theories to each other and to pragmatic implementations. Finally, the designer, or layout artist, interested to have a thorough understanding of fundamental concepts in mixed-signal layout generation, can take advantage of the self-contained chapters in this book.

Table of Contents

Preface	v
List of Abbreviations	xi
1 Introduction	1	(6)
1.1 Outline of the Book	4	(3)
2 Mapping Problems in the Design Flow	7	(12)
2.1 Top-Down Flow and Bottom-Up Approach	7	(7)
2.1.1 A VLSI Design Cycle	8	(1)
2.1.2 Physical Design	9	(2)
2.1.3 Mixed Signal Layout Styles	11	(1)
2.1.4 From Circuit to Layout	12	(1)
2.1.5 Layout System Requirements	13	(1)
2.2 The Mapping Problem	14	(3)
2.2.1 High-Level Specifications	14	(1)
2.2.2 Layout System Specifications	14	(1)
2.2.3 Constraint Mapping Problem	15	(1)
2.2.4 High Level Sensitivities	15	(1)
2.2.5 Lower Level Sensitivities	16	(1)
2.2.6 Sensitivity Computation Problem	16	(1)
2.3 Placement and Routing Constraints	17	(2)
3 Optimization Methods	19	(12)
3.1 VLSI Optimization Methods	19	(4)
3.1.1 Deterministic Algorithms	20	(1)
3.1.2 Stochastic Algorithms	21	(1)
3.1.3 Heuristic Algorithms	22	(1)
3.2 Simulated Annealing	23	(6)
3.2.1 Basic SA Algorithm	23	(2)
3.2.2 Problem Representation	25	(1)
3.2.3 Perturbation Operators	26	(1)
3.2.4 Acceptance and Generation Functions	27	(1)
3.2.5 Temperature Schedule	27	(1)
3.2.6 Stop Criterion	28	(1)
3.2.7 Cost Function	28	(1)
3.3 Concluding Remarks	29	(2)
4 Optimization Approach Based on Simulated Annealing	31	(10)
4.1 Optimization Flow	32	(2)
4.2 Problem Representation	34	(2)
4.2.1 Placement	34	(1)
4.2.2 Routing	34	(2)
4.2.3 Substrate Coupling	36	(1)
4.3 Perturbation Operators	36	(2)
4.4 Acceptance and Generation Functions	38	(1)
4.5 Temperature Schedule	38	(1)
4.6 Stop Criterion	39	(1)
4.7 Cost Function	39	(1)
4.7.1 Implicit Cost Evaluation	40	(1)
4.8 Concluding Remarks	40	(1)
5 Efficient Algorithms and Data Structures	41	(14)
5.1 Computational Model	42	(1)
5.2 Asymptotic Analysis	42	(1)
5.3 Computational Complexity	43	(1)
5.4 Data Structures for CAD	44	(9)
5.4.1 Corner Stitching	44	(3)
5.4.2 Linked List	47	(1)
5.4.3 Splay Tree	48	(2)
5.4.4 Hash Table	50	(2)
5.4.5 Priority Queue	52	(1)
5.4.6 Other Advanced Data Structures	53	(1)
5.5 Concluding Remarks	53	(2)
6 Placement	55	(70)
6.1 Previous Work	58	(1)
6.2 Effective and Efficient Placement	59	(2)
6.3 Representation Generality, Flexibility and Sensitivity	61	(3)
6.4 Sequence Pair Representation	64	(4)
6.5 Graph-Based Packing Computation	68	(11)
6.5.1 Relative Placement Computation	69	(5)
6.5.2 An Efficient Relative Placement Algorithm	74	(2)
6.5.3 Absolute Placement Computation	76	(3)
6.6 Non-Graph-Based Packing Computation	79	(6)
6.6.1 Maximum-Weight Common Subsequence (MWCS) Problem	79	(2)
6.6.2 Maximum-Weight Monotone Subsequence (MWMS) Problem	81	(4)
6.7 Graph-based Incremental Placement Computation	85	(19)
6.7.1 Incremental Relative Placement Computation	87	(7)
6.7.2 Incremental Relative Placement Computational Complexity	94	(2)
6.7.3 Incremental Absolute Placement Computation	96	(2)
6.7.4 Incremental Absolute Placement Computational Complexity	98	(6)
6.7.5 Average Incremental Computational Complexity	104	(1)
6.8 Implementation Considerations	104	(1)
6.9 Experimental Results	105	(6)
6.9.1 A Single Iteration	105	(1)
6.9.2 Packing Optimization	106	(4)
6.9.3 Conclusions	110	(1)
6.10 Placement-to-Sequence-Pair Mapping	111	(3)
6.11 Constrained Block Placement	114	(9)
6.11.1 Non-Graph-Based Constrained Placement	115	(3)
6.11.2 Implementation Considerations	118	(1)
6.11.3 Experimental Results on Non-Graph-Based Constrained Block Placement	118	(3)
6.11.4 Incremental Graph-Based Constrained Placement	121	(2)
6.12 Concluding Remarks	123	(2)
7 Routing	125	(44)
7.1 The Routing Problem	126	(1)
7.2 Classification of Routing Approaches	127	(4)
7.2.1 Routing Hierarchy	128	(2)
7.2.2 Routing Model	130	(1)
7.3 Previous Work	131	(1)
7.4 Computational Complexity	132	(1)
7.5 Global Routing Model	133	(4)
7.5.1 Model Efficiency	133	(1)
7.5.2 Global Routing Graph Computation	134	(1)
7.5.3 Supporting Dynamic Changes	135	(2)
7.6 Global Routing Algorithms	137	(14)
7.6.1 Two-pin Routing Algorithms	138	(4)
7.6.2 Minimal Bounding Box (MBB) Routing	142	(1)
7.6.3 Minimum Spanning Tree (MST) Routing	143	(1)
7.6.4 Path-Based Routing	144	(5)
7.6.5 Node-Based Routing	149	(2)
7.7 Benchmarking of Heuristics in Our Routing Model	151	(7)
7.7.1 Benchmark Problem Instances	151	(1)
7.7.2 Experimental Results	152	(6)
7.7.3 Concluding Remarks	158	(1)
7.8 Incremental Routing	158	(6)
7.8.1 Re-routing Nets Connected to Moved Modules	158	(4)
7.8.2 Re-routing Affected Nets Not Connected to Moved Modules	162	(2)
7.9 Impact of Routing on Placement Quality	164	(3)
7.9.1 Integrated Placement and Routing	164	(1)
7.9.2 Experimental Results	165	(2)
7.9.3 Conclusions	167	(1)
7.10 Concluding Remarks	167	(2)
8 Dealing with Physical Phenomena: Parasitics, Crosstalk and Process Variations	169	(16)
8.1 Previous Work	170	(1)
8.2 Efficiency and Accuracy Requirements	170	(1)
8.3 Self Parasitics	171	(1)
8.3.1 Wire Resistance, Capacitance and Inductance	171	(1)
8.3.2 Via Resistance and Area	171	(1)
8.4 Crosstalk	172	(3)
8.4.1 Substrate Coupling	172	(2)
8.4.2 Parasitic Coupling Capacitance	174	(1)
8.5 Process Variations	175	(1)
8.6 Incorporating Crosstalk and Parasitics into Routing	175	(1)
8.7 Incorporating Substrate Coupling into Placement	176	(7)
8.7.1 A Basic Module	176	(1)
8.7.2 Generalized 2-Dimensional Substrate Coupling Model	177	(2)
8.7.3 Substrate Coupling Impact Minimization	179	(1)
8.7.4 An Efficient Substrate Coupling Impact Minimization Algorithm	180	(1)
8.7.5 Implementation Considerations	181	(1)
8.7.6 Experimental Results	181	(1)
8.7.7 Conclusions	182	(1)
8.8 Incremental Substrate Coupling Impact Minimization	183	(1)
8.9 Concluding Remarks	183	(2)
9 Conclusions	185	(4)
Bibliography	189	(10)
About the Authors	199	(2)
Index	201