Flow-based partitioning and fast global placement in chip design [Elektronische Ressource] / vorgelegt von Markus Struzyna

Markus Struzyna

Sujets

• Mathematics

Informations

• Publié par: rheinische_friedrich-wilhelms-universitat_bonn
• Publié le: 01 janvier 2010
• Nombre de lectures: 35
• Langue: Deutsch
• Poids de l'ouvrage: 2 Mo

Extrait

Flow-based Partitioning and
Fast Global Placement
in Chip Design
Dissertation
zur Erlangung des Doktorgrades (Dr. rer. nat.)
der Mathematisch-Naturwissenschaftlichen Fakult¨at
der Rheinischen Friedrich-Wilhelms-Universit¨at Bonn
vorgelegt von
Markus Struzyna
aus
Tychy/Polen
Bonn, Juli 2010Angefertigt mit Genehmigung der Mathematisch-Naturwissenschaftlichen Fakult¨at der
Rheinischen Friedrich-Wilhelms-Universit¨at Bonn
Erstgutachter: Prof. Dr. Jens Vygen
Zweitgutachter: Prof. Dr. Dr. h.c. Bernhard Korte
Tag der Promotion: 30. September 2010
Erscheinungsjahr: 2010Contents
1 Introduction 7
2 Preliminaries 11
2.1 Basic Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2 The Placement Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.2.1 Net Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.2.2 Placement and Density . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.2.3 Other Constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.3 Complexity Issues in Placement . . . . . . . . . . . . . . . . . . . . . . . . 20
2.4 Global Placement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3 Global Placement Algorithms 23
3.1 Non-analytic Approaches . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.2 Analytic Netlength Minimization . . . . . . . . . . . . . . . . . . . . . . . 24
3.2.1 Non-linear Non-quadratic Net Models . . . . . . . . . . . . . . . . . 24
3.2.2 Quadratic Net Models . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.3 Density and Overlap Reduction . . . . . . . . . . . . . . . . . . . . . . . . 28
3.3.1 Penalty Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.3.2 Artificial Nets and Anchors . . . . . . . . . . . . . . . . . . . . . . 29
3.3.3 Partitioning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.4 BonnPlace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.4.1 Recursive Partitioning . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.4.2 Repartitioning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.4.3 Iterative Partitioning . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.4.4 Macro Placement and Legalization . . . . . . . . . . . . . . . . . . 37
3.4.5 Congestion-Driven Placement . . . . . . . . . . . . . . . . . . . . . 37
3.4.6 Parallelization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.4.7 Overall Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
4 Movebounds 39
4.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
4.2 Movebounds and their Properties . . . . . . . . . . . . . . . . . . . . . . . 40
4.3 Partitioning-Based Placement with Movebounds . . . . . . . . . . . . . . . 42
34 CONTENTS
4.3.1 Partitioning with Movebounds . . . . . . . . . . . . . . . . . . . . . 44
4.3.2 Movebounds and Density Constraints . . . . . . . . . . . . . . . . . 47
4.3.3 Soft Movebounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
4.3.4 Quadratic Programs . . . . . . . . . . . . . . . . . . . . . . . . . . 51
4.3.5 Congestion-Driven Placement . . . . . . . . . . . . . . . . . . . . . 52
4.3.6 Legalization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
5 New Global Partitioning Algorithm 55
5.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
5.2 Flow-based Global Partitioning . . . . . . . . . . . . . . . . . . . . . . . . 57
5.2.1 Computing Cirections . . . . . . . . . . . . . . . . . . . . . . . . . 57
5.2.2 Properties of the MinCostFlow Instance . . . . . . . . . . . . . . 64
5.2.3 Realization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
5.2.4 Refinement of the Model . . . . . . . . . . . . . . . . . . . . . . . . 75
5.3 Extensions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
5.3.1 Level Skipping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
5.3.2 Greedy Re-allocations . . . . . . . . . . . . . . . . . . . . . . . . . 77
5.3.3 Densities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
5.4 Simultaneous Inflation and Movement Model . . . . . . . . . . . . . . . . . 78
5.5 Discussion and Outlook . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
6 Data Structures and Implementation 83
6.1 Generalized Netlists and Clustering . . . . . . . . . . . . . . . . . . . . . . 83
6.1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
6.1.2 Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
6.1.3 Clustered Netlist . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
6.2 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
6.2.1 Netlist and Clustering . . . . . . . . . . . . . . . . . . . . . . . . . 91
6.2.2 Domain . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
6.2.3 Grid, Windows and Regions . . . . . . . . . . . . . . . . . . . . . . 92
6.2.4 QP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
6.2.5 Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
6.2.6 Partitioning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
6.2.7 MacroPlacement . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
6.2.8 Congestion-Driven Placement . . . . . . . . . . . . . . . . . . . . . 94
6.2.9 Legalization and Local Placement . . . . . . . . . . . . . . . . . . . 95
6.3 Parallelization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
6.3.1 Common vs. Specific Data . . . . . . . . . . . . . . . . . . . . . . . 96
6.3.2 Job Queues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
6.3.3 A-priori Job Assignment . . . . . . . . . . . . . . . . . . . . . . . . 98
6.3.4 Speed-ups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98CONTENTS 5
7 Random Walk based Clustering 101
7.1 Clustering in VLSI Placement . . . . . . . . . . . . . . . . . . . . . . . . . 101
7.2 Random Walks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
7.3 Clustering with Random Walks . . . . . . . . . . . . . . . . . . . . . . . . 105
7.3.1 Previous Approaches . . . . . . . . . . . . . . . . . . . . . . . . . . 105
7.3.2 Hitting Times in Hypergraphs . . . . . . . . . . . . . . . . . . . . . 106
7.3.3 and Bottom-up Clustering . . . . . . . . . . . . . . . 107
7.4 Fast Random Walk Model . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
7.5 Target Choices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
7.6 Geometric Information and the Overall Algorithm . . . . . . . . . . . . . . 112
7.7 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
7.8 Discussion and Outlook . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
8 Experimental Results 117
8.1 The Testbed Environment . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
8.2 Flow-based Partitioning . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
8.2.1 MinCostFlow Computation . . . . . . . . . . . . . . . . . . . . . 118
8.2.2 Realization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
8.2.3 Level Skipping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
8.2.4 Greedy Re-allocation . . . . . . . . . . . . . . . . . . . . . . . . . . 121
8.3 New vs. Old BonnPlace . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
8.3.1 Recursive Partitioning . . . . . . . . . . . . . . . . . . . . . . . . . 122
8.3.2 Flow-based P . . . . . . . . . . . . . . . . . . . . . . . . 122
8.4 New BonnPlace with Movebounds: Recursive vs. Flow-based . . . . . . . 126
8.5 Comparison to an Industrial Tool . . . . . . . . . . . . . . . . . . . . . . . 130
8.6 Benchmarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
8.7 Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
8.8 Random Walk Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
8.9 Summary and Outlook . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140
Bibliography 1436 CONTENTSChapter 1
Introduction
One of the most challenging and fascinating applications of discrete mathematics is chip
design. The development of modern processors and application specific integrated circuits
(ASICs) is unimaginable without the use of advanced mathematics. Here, various hard
problems have to be addressed on huge instances.
Modern computer chips consist of millions of modules (circuits) representing logical func-
tions and memory elements, which have to be connected by wires in the later design process.
A key task in chip design is placement, in which positions of the modules have to be
determined in a given chip area. The placement has a direct impact on the total length of
wires needed to interconnect them, and consequently on the performance of the chip — the
signal transition times and the power consumption.
In the past, meeting timing constraints was not difficult and wiring was almost always
achievable. But the technological advancement, competition and the growing complexity
of the chips now make the design process a compound, interlaced, an