Efficient quadratic placement of VLSI circuits [Elektronische Ressource] / Peter Spindler

Informations

• Publié par: technische_universitat_munchen
• Publié le: 01 janvier 2008
• Nombre de lectures: 22
• Langue: English
• Poids de l'ouvrage: 1 Mo

Extrait

Lehrstuhl fu¨r Entwurfsautomatisierung
der Technischen Universita¨t Mu¨nchen
Efficient Quadratic Placement of VLSI Circuits
Peter Spindler
Vollsta¨ndiger Abdruck der von der Fakulta¨t fu¨r Elektrotechnik und Informationstechnik der
Technischen Universita¨t Mu¨nchen zur Erlangung des akademischen Grades eines
Doktor-Ingenieurs
genehmigten Dissertation.
Vorsitzender: Univ.-Prof. Dr. techn. Josef A. Nossek
Pru¨fer der Dissertation:
1. Univ.-Prof. Dr.-Ing. Frank M. Johannes
2. Univ.-Prof. Dr.-Ing. Jens Lienig
Technische Universita¨t Dresden
Die Dissertation wurde am 20.12.2007 bei der Technischen Universita¨t Mu¨nchen eingereicht
und durch die Fakulta¨t fu¨r Elektrotechnik und Informationstechnik am 05.06.2008 angenom-
men.Acknowledgment
This thesis is the result of my work and all the help and advice that has been provided to
me through all of my years at the Institute for Electronic Design Automation, Technische
Universita¨t Mu¨nchen, Germany.
The person who deserves most of my credit is undoubtedly my adviser Professor Frank
M. Johannes. With the prolific discussions, not only about the field of research, and his
continuous encouragement, he gave the essential requirements for successful research. I am
also very grateful for the constant support and inspiration of Professor Ulf Schlichtmann. I
would also like to thank Professor Jens Lienig and Professor Josef A. Nossek for their interest
in my thesis and their job as reviewers.
The many interesting discussions with my colleagues contributed much to this thesis.
Amongst others, I would like to thank Martin Strasser, Dr. Helmut Gra¨b, and my predecessor
in the layout group, Dr. Bernd Obermeier. Special thanks go to Dr. Hans Eisenmann, who laid
with his work the basis for this thesis. I owe respect to Dr. Bernd Finkbein, Getraude Kall-
weit, Hans Ranke, Werner Tolle, Susanne Werner, and Ju¨rgen Zenz for their administrative
and technical support.
Finally, I would like to thank with all my heart my girlfriend Katrin Mayer-Arnold, who
always stands behind me and supports me under all circumstances.Contents
1 Introduction 1
1.1 Electronic Design Automation . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Types of Integrated Circuits . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Placement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2 State of the Art 7
2.1 Global Placement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.1.1 Greedy Placement . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.1.2 Cluster-Growth . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.1.3 Min-Cut Placement . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.1.4 Stochastic Placement . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.1.5 Analytical Placement . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.1.6 Warping Placement . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.2 Multilevel Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.3 Net Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.3.1 Graphs and Metrics . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.3.2 Net Models for Quadratic Placement . . . . . . . . . . . . . . . . . . 18
2.4 Routability-Driven Placement . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.4.1 Congestion Estimation . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.4.2 Integration in Placement . . . . . . . . . . . . . . . . . . . . . . . . 20
2.5 Final Placement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.5.1 Legalization of Standard Cell Circuits . . . . . . . . . . . . . . . . . 22
2.5.2 Legalization of Macros in Mixed-Size Circuits . . . . . . . . . . . . 22
3 This Thesis 25
3.1 “Kraftwerk”: Force-Directed Quadratic Placement . . . . . . . . . . . . . . 25
3.2 “Bound2Bound” Net Model . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.3 Routability-Driven Placement . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.3.1 “RUDY”: Routing Demand Estimation . . . . . . . . . . . . . . . . 26
3.3.2 Integration in Placement . . . . . . . . . . . . . . . . . . . . . . . . 27
3.4 “Abacus” and “Puzzle”: Legalization . . . . . . . . . . . . . . . . . . . . . . 27
III CONTENTS
4 Bound2Bound Net Model 29
4.1 Clique/Star Net Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
4.2 Bound2Bound Net Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
4.3 Comparison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
4.4 Approximation Error depending on Module Movement . . . . . . . . . . . . 34
5 Kraftwerk: Force-Directed Quadratic Placement 35
5.1 Quadratic Placement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
5.2 Creation of MatrixC and Vectord . . . . . . . . . . . . . . . . . . . . . . 37x x
5.3 Force-directed Quadratic Placement . . . . . . . . . . . . . . . . . . . . . . 39
5.4 Geometry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
5.5 One Placement Iteration . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
5.5.1 Move Force . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
5.5.2 Hold Force . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
5.5.3 Illustration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
5.6 Core of Kraftwerk . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
5.7 Overview of the Placement Algorithm . . . . . . . . . . . . . . . . . . . . . 47
5.8 Quality Control . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
5.9 Convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
5.9.1 Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
5.9.2 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . 52
5.9.3 Limitations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
5.10 Advanced Module Demand . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
5.11 Advanced Module Supply . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
5.12 Implementation Details . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
5.12.1 Calculation of the Potential . . . . . . . . . . . . . . . . . . . . . . . 57
5.12.2 Solving the System of Linear Equations . . . . . . . . . . . . . . . . 58
6 Routability-Driven Placement 61
6.1 RUDY: Efficient Routing Demand Estimation . . . . . . . . . . . . . . . . . 62
6.2 Characteristics of RUDY . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
6.3 Routing Supply . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
6.4 Integration in Kraftwerk . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
7 Legalization 69
7.1 Puzzle: Macro Legalization . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
7.1.1 Construction of MatrixA and Vectorb . . . . . . . . . . . . . . . . 72
7.1.2 Initial Legalization . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
7.1.3 Constraint Direction based on Placement . . . . . . . . . . . . . . . 73
7.1.4 Optimization of Constraint Direction . . . . . . . . . . . . . . . . . 74
7.1.5 Comparison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
7.2 Abacus: Standard Cell Legalization . . . . . . . . . . . . . . . . . . . . . . 79
7.2.1 PlaceRow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
7.2.2 Implementation by Dynamic Programming . . . . . . . . . . . . . . 82CONTENTS III
7.2.3 Worst-Case Computational Complexity . . . . . . . . . . . . . . . . 84
7.2.4 Average-Case Computational Complexity . . . . . . . . . . . . . . . 84
7.2.5 Comparison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
7.3 Tetris . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
8 Experimental Results 89
8.1 Stability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
8.2 Engineering Change Order . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
8.3 IBM-PLACE 2.0 Benchmark Suite . . . . . . . . . . . . . . . . . . . . . . . 92
8.4 ISPD 2006 Contest Benchmark Suite . . . . . . . . . . . . . . . . . . . . . . 94
8.5 ISPD 2005 Contest Benchmark Suite . . . . . . . . . . . . . . . . . . . . . . 96
8.6 ICCAD 2004 Mixed-Size Benchmark Suite . . . . . . . . . . . . . . . . . . 97
+8.7 IBM-HB Floorplacement Benchmark Suite . . . . . . . . . . . . . . . . . . 97
8.8 Average-Case Computational Complexity . . . . . . . . . . . . . . . . . . . 98
9 Conclusion 101
Bibliography 103
List of Variables 123
List of Figures 126IV CONTENTSChapter 1
Introduction
Integrated circuits (ICs) are part of our daily live as they are the hearts of MP3 players, cell
phones, personal digital assistants (PDAs), laptops, and even cars have a high number of
integrated circuits. Also the industry mainly depends on integrated circuits in different appli-
cations, ranging from simulations of complex processes on main-frame computers to efficient
control of production lines.
The history of integrated circuits started around 1960,