Facility location and clock tree synthesis [Elektronische Ressource] / vorgelegt von Jens Uwe Maßberg

Jens Uwe Maßberg

Sujets

• Mathematics

Informations

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

Extrait

Facility Location
and
Clock Tree Synthesis
Dissertation
zur Erlangung des Doktorgrades
der Mathematisch-Naturwissenschaftlichen Fakult¨at
der Rheinischen Friedrich-Wilhelms-Universit¨at Bonn
vorgelegt von
Jens Uwe Maßberg
aus Hannover
im Oktober 2009AngefertigtmitGenehmigungderMathematisch-NaturwissenschaftlichenFakult¨atder
Rheinischen Friedrich-Wilhelms-Universit¨at Bonn
Diese Disseratation ist auf dem Hochschulschriftenserver der ULB Bonn unter
http://hss.ulb.uni-bonn.de/diss online elektronisch publiziert.
Erscheinungsjahr: 2010
Erstgutachter: Prof. Dr. Jens Vygen
Zweitgutachter: Prof. Dr. Dr. h.c. Bernhard Korte
Tag der Promotion: 18.12.2009Contents
Introduction 1
1 The Sink Clustering Problem 5
1.1 Problem and Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.1.1 Problem Definition . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.1.2 Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.1.3 The Sink Clustering Algorithm . . . . . . . . . . . . . . . . . . 7
1.1.4 Variants of the Sink Clustering Algorithm . . . . . . . . . . . . 11
1.1.5 Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.2 Post Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.2.1 TwoClusterOpt . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.2.2 ChainOpt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.3 Lower Bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.3.1 Lower Bound Based on Minimum Steiner Trees . . . . . . . . . 20
1.3.2 Excursion into Matroid Theory . . . . . . . . . . . . . . . . . . 21
1.3.3 An Improved Lower Bound using ‘K-dominated’ Functions . . . 22
1.3.4 A Lower Bound Combining Dominated Functions and Steiner
Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
1.3.5 An Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
1.3.6 Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
1.4 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
2 The Sink Clustering Problem with Time Windows 45
2.1 Problem and Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 45
2.1.1 Initial Observations . . . . . . . . . . . . . . . . . . . . . . . . . 46
2.1.2 An Approximation Algorithm . . . . . . . . . . . . . . . . . . . 47
2.2 Post Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
2.3 Lower Bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
2.3.1 Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
2.4 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
3 BonnClock 59
3.1 The Clock Tree Construction Problem . . . . . . . . . . . . . . . . . . 59
3.1.1 Problem Definition . . . . . . . . . . . . . . . . . . . . . . . . . 59
3.1.2 Previous Work . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
3.2 Outline of BonnClock . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
3.3 Solution Candidates . . . . . . . . . . . . . . . . . . . . . . . . . . . . 643.4 Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
3.5 Placement Areas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
3.5.1 Blockage Grid and Distance Graph . . . . . . . . . . . . . . . . 70
3.5.2 Placement Area Computation . . . . . . . . . . . . . . . . . . . 71
3.6 Blockage Aware Top-Down Partitioning . . . . . . . . . . . . . . . . . . 71
3.7 On-Chip Variation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
3.8 An Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
3.9 Lower Bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
3.10 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
4 Repeater Tree Topology Problem 97
4.1 Previous Work and Problem Definition . . . . . . . . . . . . . . . . . . 97
4.2 A Simple Procedure and its Properties . . . . . . . . . . . . . . . . . . 100
4.3 The Online Minimax Problem . . . . . . . . . . . . . . . . . . . . . . . 105
4.3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
4.3.2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
4.3.3 Conditions for an Optimal Online Algorithms . . . . . . . . . . 108
T4.3.4ns for an Online Algorithms with s ≤OPT +c . . . . 110
4.3.5 Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
4.4 Unbalanced Binary Trees with Choosable Edge Length . . . . . . . . . 117
4.4.1 Growth of f . . . . . . . . . . . . . . . . . . . . . . . . . . . 118L(n)
04.4.2 Existence of{{1,m}}-trees andL(4)-trees . . . . . . . . . . . . 122
4.4.3 Examples of the Function f for Different Values of n . . . . 126L(n)
Bibliography 1271
Introduction
A fundamental problem in chip design is the construction of networks that distribute
an electrical signal from a given source to a set of sinks. In most cases these networks
are repeater trees. A repeater tree consists of horizontal and vertical wires connecting
the source and the sinks. Moreover, it contains repeaters (inverters or buffers) which
‘refresh’ the signal. Recent chips contain millions of repeater trees.
Clock trees are very similar to repeater trees. Their task is to distribute a clock signal
from a source to a large set of sinks. Beside the repeaters, they can contain additional
special circuits modifying the clock signal. One main goal of clock tree construction
is to minimize the power consumption. Typically, 80% to 90% of the total power
consumption of a clock tree occurs in the last stage of the tree.
This motivates us to have a closer look at this stage. It contains circuits (inverters or
special circuits) driving the sinks. Each sink is assigned to one of these drivers and
each driver is connected to the sinks that are to it by a rectilinear Steiner
tree. Each driver has to drive the electrical capacitance of the tree plus the input
capacitances of its sinks. The total capacitance it can drive is limited. The power
consumption of the last stage is equivalent to the power consumption of the trees
(proportional to their length) plus the power consumption of the drivers. Typically,
the drivers of the last stage are inverters or special circuits of the same size. In both
cases the power consumption of all drivers is the same. The key component of every
clock tree construction tool is to build a last stage that minimizes power consumption
while satisfying the capacitance limits of the drivers.
Mathematically,thistaskcanbeformulatedasthefollowingSinkClusteringProb-
2
lem: Given a finite set D of sinks with positions p(v)∈R in the plane and demands
(input capacitances) d(v)∈R for all v∈D, a facility opening cost f∈R (power≥0 >0
consumptionofadriver)andaloadlimit(capacitancelimit)u∈R ,thetaskistofind>0
˙ ˙apartitionD =D∪···∪D ofD and,forall1≤i≤k,arectilinearSteinertreeS for1 k i
{p(v)|v∈D}. Each cluster (D,S ), 1≤i≤k, has to keep the load limit, that meansi i i
P P
c(e)+ d(s)≤u. Thegoalistominimizetheweightedsumofthelengthe∈E(S ) s∈Di i
P Pkof all Steiner trees plus the number of clusters, i.e. minimize c(e)+kf.
i=1 e∈E(S )i
In Chapter 1 we study the Sink Clustering Problem for general metrics and
present the first constant-factor approximation algorithms for it. Moreover, we de-
velop several lower bounds that partly rely on fundamental connections of the Sink
Clustering Problem to matroid theory. In Section 1.4 we show experimental re-
sults on real-life instances from clock tree design. The cost (power consumption) of
the solutions computed by our algorithm is in average only about 10% over the lower
bounds.
Clock trees have to satisfy several timing constraints. Typically, the signal has to2
arrive at all sinks of a clock tree at the same time. In this case we have the Sink
Clustering Problem as defined above. However, there are clock trees where the
signal has to arrive at each sink within an individual required arrival time window.
In this case sinks can only be driven by the same circuit if the time windows of these
sinks have a point of time in common. In Chapter 2 we study this generalization of
theSink Clustering Problem, describe algorithms and lower bounds.
In Chapter 3 we present our algorithm BonnClock for sythesizing clock trees. Its
key component is theSink Clustering Algorithm as presented in Chapter 1 and
generalizedinChapter2. Theclusteringalgorithmsareusedtoconstructthelaststage
of the clock tree and also to build upper parts of the tree. It is combined with a sink
partitioning approach that is a generalization of the well-known H-trees. BonnClock
has become the standard tool used by IBM Microelectronics for constructing clock
trees. It has been used for the design of hundreds of most complex chips.
Finally, we study the Repeater Tree Topology Problem in Chapter 4. In con-
trasttoclocktrees,thetimingconstraintsofrepeatertreesaredifferent: Thesignalhas
to arrive at a sink not later than a given individual required arrival time and therefore
cannot arrive too early. We propose a greedy algorithm that can produce trees that
are either almost length optimal or timing optimal. Moreover, we present theoretical
results, including a characteriz