Nam / Cong Modern Circuit Placement

Best Practices and Results
1. Auflage 2007
ISBN: 978-0-387-68739-1
Verlag: Springer
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, 324 Seiten

Reihe: Integrated Circuits and Systems

This book covers advanced techniques in modern circuit placement. It details all of most recent placement techniques available in the field and analyzes the optimality of these techniques. Coverage includes all the academic placement tools that competed against one another on the same industrial benchmark circuits at the International Symposium on Physical Design (ISPD), these techniques are also extensively being used in industrial tools as well. The book provides significant amounts of analysis on each technique such as trade-offs between quality-of-results (QoR) and runtime.

Autoren/Hrsg.

Nam, Gi-Joon

Cong, Jason

Cong, Jingsheng Jason

Inhaltsverzeichnis

1;Contents;7
2;Foreword;14
3;Preface;15
3.1;References;18
4;Part I Benchmarks;19
4.1;1 ISPD 2005/2006 Placement Benchmarks;20
4.1.1;1.1 Introduction;20
4.1.2;1.2 ISPD 2005 Placement Contest and Benchmark1;21
4.1.3;1.3 ISPD 2006 Placement Contest and Benchmark;24
4.1.4;1.4 ISPD Placement Contest Results;25
4.1.5;References;28
4.2;2 Locality and Utilization in Placement Suboptimality;30
4.2.1;2.1 Introduction;30
4.2.2;2.2 Peko-MC Benchmark Construction;32
4.2.3;2.3 Peko-MS Benchmark Construction;34
4.2.4;2.4 Experiments;39
4.2.5;2.5 Conclusions;51
4.2.6;2.6 Acknowledgments;52
4.2.7;References;52
5;Part II Flat Placement Techniques;54
5.1;3 DPlace: Anchor Cell-Based Quadratic Placement with Linear Objective;55
5.1.1;3.1 Introduction;55
5.1.2;3.2 Preliminaries and the Motivation;57
5.1.3;3.3 Global Placement in DPlace;61
5.1.4;3.4 Legalization and Detailed Placement;69
5.1.5;3.5 Overall Algorithm;69
5.1.6;3.6 Experiments;69
5.1.7;3.7 Conclusions;72
5.1.8;References;73
5.2;4 Kraftwerk: A Fast and Robust Quadratic Placer Using an Exact Linear Net Model;75
5.2.1;4.1 Introduction;75
5.2.2;4.2 Net Model;78
5.2.3;4.3 Quadratic Placement Methodology;83
5.2.4;4.4 Implementation Details;88
5.2.5;4.5 Experimental Results;97
5.2.6;4.6 Conclusion;106
5.2.7;References;107
6;Part III Top-Down Partitioning-Based Techniques;110
6.1;5 Capo: Congestion-Driven Placement for Standard-cell and RTL Netlists with Incremental Capability;111
6.1.1;5.1 Introduction;111
6.1.2;5.2 Min-Cut Placement in Capo;113
6.1.3;5.3 Floorplacement;114
6.1.4;5.4 Flexible Whitespace Allocation;118
6.1.5;5.5 Detail Placement;121
6.1.6;5.6 Placement for Routability;124
6.1.7;5.7 Improved RTL Placement;127
6.1.8;5.8 Incremental Placement;132
6.1.9;5.9 Memory Profile;138
6.1.10;5.10 Performance on Publicly Available Benchmarks;139
6.1.11;5.11 Conclusions;145
6.1.12;References;145
6.2;6 Congestion Minimization in Modern Placement Circuits;148
6.2.1;6.1 Introduction;148
6.2.2;6.2 Overview of Dragon;149
6.2.3;6.3 Mixed-Size Placement;151
6.2.4;6.4 Congestion Estimation;155
6.2.5;6.5 Congestion Removal;166
6.2.6;6.6 Target Utilization Control;171
6.2.7;6.7 Experimental Result;173
6.2.8;References;175
7;Part IV Multilevel Placement Techniques;177
7.1;7 APlace: A High Quality, Large-Scale Analytical Placer;178
7.1.1;7.1 Introduction;178
7.1.2;7.2 Clustering and Unclustering;180
7.1.3;7.3 Global Placement;182
7.1.4;7.4 Legalization and Detailed Placement;188
7.1.5;7.5 ISPDÌ06 Contest and APlace3.0;192
7.1.6;7.6 Experimental Results;194
7.1.7;References;200
7.2;8 FastPlace: An Efficient Multilevel Force-Directed Placement Algorithm;204
7.2.1;8.1 Introduction;204
7.2.2;8.2 Overview of the Algorithm;205
7.2.3;8.3 Quadratic Placement Methodology;207
7.2.4;8.4 Hybrid Net Model;208
7.2.5;8.5 Cell Shifting;212
7.2.6;8.6 Iterative Local Refinement;216
7.2.7;8.7 Clustering for Placement;220
7.2.8;8.8 Legalization;223
7.2.9;8.9 FastDP: Efficient and Effective Detailed Placement;226
7.2.10;8.10 Experimental Results and Analysis;233
7.2.11;8.11 Conclusions;237
7.2.12;References;238
7.3;9 mFAR: Multilevel Fixed-Points Addition-Based VLSI Placement;240
7.3.1;9.1 Introduction;240
7.3.2;9.2 Background;241
7.3.3;9.3 Fixed Points;242
7.3.4;9.4 Fixed-Points Addition-Based Placement;246
7.3.5;9.5 mFAR: Multilevel Fixed-Point Addition-Based Placement;251
7.3.6;9.6 Experimental Results;253
7.3.7;9.7 Conclusions;255
7.3.8;References;255
7.4;10 mPL6: Enhanced Multilevel Mixed-Size Placement with Congestion Control;257
7.4.1;10.1 Introduction;257
7.4.2;10.2 Definitions and Notations;258
7.4.3;10.3 Problem Formulation;258
7.4.4;10.4 Multilevel Framework;259
7.4.5;10.5 Generalized Force-Directed Algorithm;265
7.4.6;10.6 Legalization and Detailed Placement;284
7.4.7;10.7 Numerical Results;294
7.4.8;References;295
7.5;11 NTUplace3: An Analytical Placer for Large-Scale Mixed- Size Designs;299
7.5.1;11.1 Introduction;299
7.5.2;11.2 Analytical Placement Model;300
7.5.3;11.3 Core Techniques;302
7.5.4;11.4 Experimental Results;313
7.5.5;References;318
7.6;12 Conclusion and Challenges;320
8;Index;322