Fast resource sharing in VLSI routing [Elektronische Ressource] / vorgelegt von Dirk Müller

Dirk Müller

Informations

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

Extrait

FastResourceSharing
in
VLSIRouting
Dissertation
zurErlangungdesDoktorgrades
derMathematisch-NaturwissenschaftlichenFakultät
derRheinischenFriedrich-Wilhelms-UniversitätBonn
vorgelegtvon
DirkMüller
ausAachen
imSeptember2009AngefertigtmitGenehmigungderMathematisch-NaturwissenschaftlichenFakultät
derRheinischenFriedrich-Wilhelms-UniversitätBonn
Erstgutachter: ProfessorDr.JensVygen
Zweitgutachter:Dr.BernhardKorte
TagderPromotion: 18.Dezember2009
Erscheinungsjahr: 2010Acknowledgments
I like to express my gratitude to my supervisors, Professor Dr. Bernhard Korte and Pro-
fessor Dr. Jens Vygen. This work would not have been possible without their guidance
and valuable ideas, and the optimal working conditions that the Institute for Discrete
Mathematics at the University of Bonn offers under their leading.
I am very thankful to my past and present colleagues at the institute, especially Dr.
Sven Peyer, Christian Panten, Christian Schulte and Jun.-Prof. Dr. Tim Nieberg. The
friendly and efficient working atmosphere in our team contributed much to the success
®of BonnRoute in the last years.
I am thankful to all people at IBM who shared their knowledge with me and provided
me with a lot of practical background information, in particular Karsten Muuss, Dr.
Jürgen Köhl, Gustavo Tellez and Dr. Matthias Ringe, and again Dr. Sven Peyer, of
®course. Their expertise and continuous suggestions for improving BonnRoute have
been very valuable.
Sincere thanks go to Dr. Asmus Hetzel. I had the exciting experience to work to-
gether with him on the project of writing a completely new global router. His work was
essential for putting this new global router into operation at Magma Design Automation,
Inc.
Special thanks go to my colleagues for the support they gave me in the recent months
in finalizing this thesis, especially for proof-reading important parts and making valu-
able comments. I explicitely want to mention Christian and Christian, Ulrich, Sven,
Tim, Nico, Daniel and Thomas.
I thank my parents who made a care-free student life possible, and my whole family
for being a source of advice and recreation.
My biggest thanks however go to Cathrin for her loving encouragements and tol-
erance of the many evenings I came home late during the recent weeks and months
working towards completion of this thesis.
iiiContents
1 Introduction 1
®1.1 BonnRoute . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2 Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2 Modeling Routing Space 11
2.1 Basic Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.1.1 Wire and Via Representation . . . . . . . . . . . . . . . . . . . 14
2.1.2 Minimum Distance Rules . . . . . . . . . . . . . . . . . . . . 16
2.1.3 Routing Tracks and Track Graph . . . . . . . . . . . . . . . . . 18
2.2 The Shape Grid . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.2.1 Storing Net Identifiers . . . . . . . . . . . . . . . . . . . . . . 22
2.2.2 Choosing Cell Boundaries . . . . . . . . . . . . . . . . . . . . 24
2.3 The Fast Grid . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.3.1 On-Track Jogs . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.3.2 Updating the Fast Grid . . . . . . . . . . . . . . . . . . . . . . 29
2.3.3 Choosing Wire and Via Models for the Fast Grid . . . . . . . . 30
2.3.4 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.4 Determining Routing Tracks . . . . . . . . . . . . . . . . . . . . . . . 33
2.4.1 The Maximum Weighted Stable Interval Covering Problem . . . 33
2.4.2 Application . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
2.5 Discussion and Outlook . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3 Resource Sharing 45
3.1 Problem Statement and Overview . . . . . . . . . . . . . . . . . . . . 46
3.1.1 Previous work . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.1.2 Fractional packing . . . . . . . . . . . . . . . . . . . . . . . . 47
3.1.3 Our Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.2 A Sequential Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.2.1 Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
3.2.2 An Example Attaining the Worst Case Runtime . . . . . . . . . 57
3.3 Parallelization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
3.3.1 The Memory Model . . . . . . . . . . . . . . . . . . . . . . . 61
iiiiv CONTENTS
3.3.2 A Lock-free Parallel Algorithm for the Resource Sharing
Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
3.4 Randomized Rounding . . . . . . . . . . . . . . . . . . . . . . . . . . 81
3.5 Discussion and Outlook . . . . . . . . . . . . . . . . . . . . . . . . . . 83
4 Global Routing 85
4.1 Problem Statement and Overview . . . . . . . . . . . . . . . . . . . . 87
4.1.1 Previous Work . . . . . . . . . . . . . . . . . . . . . . . . . . 89
4.2 Application of the Resource Sharing Algorithm . . . . . . . . . . . . . 92
4.2.1 Yield Model . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
4.3 Global Routing Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
4.3.1 Construction of the Global Routing Grid Graph . . . . . . . . . 98
4.3.2 Capacity Estimation . . . . . . . . . . . . . . . . . . . . . . . 98
4.4 Global Routing Net Model . . . . . . . . . . . . . . . . . . . . . . . . 100
4.4.1 Construction of Standard Global Routing Nets . . . . . . . . . 104
4.5 Port Assignment in Hierarchical Design . . . . . . . . . . . . . . . . . 107
4.6 An Optimum Algorithm for Routing a Single Net . . . . . . . . . . . . 110
4.7 Implementation Aspects . . . . . . . . . . . . . . . . . . . . . . . . . 113
4.7.1 Resource Sharing Algorithm . . . . . . . . . . . . . . . . . . . 114
4.7.2 Parallelization . . . . . . . . . . . . . . . . . . . . . . . . . . 119
4.7.3 The Standard Block Solver . . . . . . . . . . . . . . . . . . . . 121
4.7.4 Randomized Rounding and Iterative Refinement . . . . . . . . 125
4.7.5 Technical Aspects . . . . . . . . . . . . . . . . . . . . . . . . 126
4.8 Fast Tree Enumeration . . . . . . . . . . . . . . . . . . . . . . . . . . 127
4.8.1 Application . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
4.9 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
4.10 Discussion and Outlook . . . . . . . . . . . . . . . . . . . . . . . . . . 146
Bibliography 149
Summary 159Chapter 1
Introduction
The design of VLSI logic circuits is fascinating in itself because of the enormous com-
plexity and multitude of structures packed on an area of five square centimeters or
smaller, and it is a fascinating field for applying mathematics. Millions of elementary
devices, called standard cells, and a few hundred or thousand more complex building
blocks (macros) have to be placed on a limited area, connected with each other, with
power supply, and with the “outside world” via primary inputs and outputs of the chip.
They all have to be synchronized with each other by feeding clock signals to each of
them, and optimized with respect to timing, power consumption and other metrics such
as manufacturing yield which can be significantly affected by how the devices and wires
connecting them are arranged in physical design.
Figure 1.1 shows an example of a standard cell which computes a four-way NAND
function f(a;b;c;d) := a^ b^ c^ d for Boolean input variables a, b, c, and d. Although
it is well known that the two-way NAND function is universal, i.e. all complex Boolean
functions can be expressed using only two-way NAND operators, standard cell libraries
used in practice comprise also the other common elementary functions such as AND,
OR, exclusive OR (evaluating to true iff exactly one input is true), NOR, NOT, etc.
There are also a number of other standard cells, including low-complexity composite
functions of these elementary Boolean functions, and latches for storing the result of a
computation performed in one clock cycle, allowing to use it as input for computations
in the next cycle. Each device comes in different discrete sizes, larger versions offering
a higher driving strength, and thus the ability to send the output signal across a longer
wire to its destination, at the cost of higher power consumption. Altogether, a standard
cell library in current technologies typically contains a few thousand different of such
device templates. A state-of-the-art chip can contain ten million and more instantiations
of them. If the design of such a chip was printed at the same scale as figure 1.1, it would
cover an area of 700 700 square meters, i.e. roughly the area of 70 soccer fields.
While the designs of the earliest chips in the 1960’s were composed by hand, subse-
quently complemented by simple automated solutions as the number of elements to be
arranged grew larger, mathematical methods began to become increasingly important to
find “good” solutions. Today, given the huge instance sizes, even the attempt to find a
12 CHAPTER1. INTRODUCTION
Figure 1.1: A 4-way NAND circuit with four input pins a, b, c, and d (small yellow
areas) computing the function a^ b^ c^ d (identifying variables and pins for simplic-
ity), whose resulting value is