4.3 Flurplan – Floorplanning
4.3.1 Einführung4.3.2 Optimierungsziele4.3.3 Begriffe und Datenstrukturen4.3.4 Algorithmen für das Floorplanning
4.3.4.1 Floorplan-Sizing-Algorithmus4.3.4.2 Cluster-Wachstums-Algorithmus (Cluster Growth)
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
73
4.3.4.2 Cluster-Wachstums-Algorithmus (Cluster Growth)4.3.4.3 Weitere Algorithmen für das Floorplanning
4.3.5 Pinzuordnung (Pin Assignment)4.3.5.1 Problembeschreibung4.3.5.2 Pinzuordnung mittels konzentrischer Kreise4.3.5.3 Topologische Pinzuordnung
4.3 Flurplan – Floorplanning
VerhaltensentwurfLogischer Entwurf
Floorplanning
ENTITY test isport a: in bit;
end ENTITY test;Partitionierung
Systemspezifikation
Architekturentwurf
Schaltungsentwurf
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
74
Layoutsynthese
Layoutverifikation
Chip
Platzierung
Verdrahtung
Kompaktierung
Herstellung
Schaltungsentwurf
Verpackung/Test
4.3 Flurplan – Floorplanning4.3.1 Einführung
Die Aufgabe des Floorplanning das Ergebnis der Schaltungspartitionierung so aufzuberei-ten, dass jeder dabei erstellte Block intern platziert und verdrahtet werden kann.
Dazu sind im Allgemeinendie Abmessungen bzw. Seitenverhältnisse der einzelnen
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
75
die Abmessungen bzw. Seitenverhältnisse der einzelnen Blöcke, und evtl. auch der Topzelle, festzulegen
die Positionen der Außenanschlüsse in den einzelnen Blöcken zu bestimmen (Pinzuordnung)
die Positionen dieser Blöcke innerhalb der Topzelle zu definieren
4.3 Flurplan – Floorplanning4.3.1 Einführung
Gegeben: Drei Blöcke mit folgenden Seitenverhältnissen (Breite w, Höhe h) Block A: w = 1, h = 4 oder w = 4, h = 1 oder w = 2, h = 2 Block B: w = 1, h = 2 oder w = 2, h = 1 Block C: w = 1, h = 3 oder w = 2, h = 2 oder w = 4, h = 1 Gesucht: Floorplan mit minimaler Gesamtfläche der Topzelle Lösung: Seitenverhältnisse Block A mit w = 2, h = 2; Block B mit w = 2, h = 1; Block C mit w = 1, h = 3
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
76
Mögliche Anordnung der Blöcke: Damit entspricht diese Lösung dem theoretischen Optimum (neun Flächeneinheiten).
A
B
C
4.3 Flurplan – Floorplanning4.3.2 Optimierungsziele
Zu optimieren sindFläche und Form des umschließenden Rechtecks
• entspricht der Topzelle
Gesamtverbindungslänge minimieren
∑ ⋅= dcL
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
77
ci,j : Matrixelement, das Verbindungsgrad (Anzahl Verbindungen) zwischen Partition i und j angibtdi,j : Entfernung zwischen Partitionen i und j
• Z.B. Manhatten-Metrik• Euklid-Metrik
∑ ⋅=ji
jiji dcL,
,,
4.3 Flurplan – Floorplanning4.3.2 Optimierungsziele
Längenbestimmung über Manhattan-Entfernung (Manhattan-Metrik)Längenbestimmung über minimalen Spannbaum (euklidische Metrik)
Euklidische Metrik Manhattan-Metrik
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
78
P1
P2
n=1 für Manhattan-Metrik
n=2 für euklidische Metrikn
2112x :Abstandn
yyn
x −+−
4.3 Flurplan – Floorplanning4.3.2 Optimierungsziele
Zu optimieren sind ferner
Signalverzögerungen Zunahme der Taktfrequenzen
• Erfordert Einhalten maximaler Signalverzögerungen auf einzelnen Netzen
• Flurplan gesucht, der getätigte Vorgaben hinsichtlich Timing
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
79
• Flurplan gesucht, der getätigte Vorgaben hinsichtlich Timing zwischen Netzen erfüllt
– Kritische Pfadlängen bzw. Netze bestimmen – Zugehörige Partitionen zuerst im Flurplan mit minimalen
Abständen anordnen
4.3 Flurplan – Floorplanning4.3.2 Optimierungsziele
Flächenminimale Topzelle angestrebtSoft Blocks (Definition s. nächste Folie):
• Flächenminimierung der Topzelle erfolgt – unter Ausnutzung der Flexibilität in den Formen der
einzelnen Blöcke (bei soft blocks möglich)– lassen sich flächenminimal anordnen, wenn man ihre
Formen zueinander passend gestaltet
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
80
Hard Blocks (Definition s. nächste Folie): • Keine Flexibilität der Blockformen („Bin Packing Problem“)
Evtl. Einhalten Formvorgaben der Topzelle
4.3 Flurplan – Floorplanning4.3.3 Begriffe und Datenstrukturen
Blöcke mit variablen Formen, bei denen nur die Flächen vorgegeben sind, werden als flexible Blöcke bezeichnet
Flexible Blöcke (Soft blocks) , feste Blöcke (Hard blocks)
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
81
Bei festen Blöcken ist die äußere Form festgelegt
4.3 Flurplan – Floorplanning4.3.3 Begriffe und Datenstrukturen
Basiszellen sind nicht
ausschließlich durch
vertikale oder horizontale
Zweiteilung entstanden
Geschnittener Floorplan(Slicing floorplan)
Ungeschnittener Floorplan(Non-slicing floorplan)
Basiszellen sind durch
(wiederholte) vertikale
oder horizontale Zweiteilung
entstanden
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
82
B
D
AE
CA
BC
D
E
Zweiteilung entstanden
Mindestens fünf Basiszellen, sog. Rad
(Wheel)
entstanden
B
DA
E
C
F
4.3 Flurplan – Floorplanning4.3.3 Begriffe und Datenstrukturen
Ein Floorplan besitzt die Ordnung n, wenn er durch Teilung eines Rechtecks in maximal n Teile entstanden ist.
Floorplan n-ter Ordnung
BD
Ordnung 5
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
83
Geschnittener (Slicing) Floorplan: Ordnung 2 Ungeschnittener (Non-slicing) Floorplan: mindestens Ordnung 5
A
B
C
D
E
F
G
4.3 Flurplan – Floorplanning4.3.3 Begriffe und Datenstrukturen
Ein Schnittbaum ist die Modellierung eines geschnittenen Floorplans durch einen Binärbaum mit k Blättern und k-1 Knoten
Schnittbaum (Slicing tree)
B C
H
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
84
Jeder Knoten repräsentiert dabei eine Schnittlinie und jedes Blatt einen BlockWesentliches Merkmal eines Schnittbaums ist seine Binärstruktur, d.h. jeder Knoten hat genau zwei Kinder
A
B CA V
B C
H
V
BHC
Beispiel: Schnittbaum (Slicing tree)
4.3 Flurplan – Floorplanning4.3.3 Begriffe und Datenstrukturen
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
85
H
A
B
C H
D VD
E F
H
B
A
E
C
F
H
V
H H
V
HC
4.3 Flurplan – Floorplanning4.3.3 Begriffe und Datenstrukturen
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
86
H
A
B
C H
D VD
E F
H H
A B D H
C V
E F
H
B
A
E
C
F
4.3 Flurplan – Floorplanning4.3.3 Begriffe und Datenstrukturen
Jeder hierarchische Floorplan (geschnitten und ungeschnitten) kann durch einen Floorplanbaum repräsentiert werden
Floorplanbaum (Floorplan tree)
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
87
Jedes Blatt verkörpert dabei einen Block, jeder Knoten entweder einen vertikalen bzw. horizontalen Schnittoperator oder ein Rad
Binäre Schnittbäume (Slicing trees) sind damit Untermengen der Floorplanbäume
H
HV W
BD
EG
Floorplanbaum (Floorplan tree)
4.3 Flurplan – Floorplanning4.3.3 Begriffe und Datenstrukturen
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
88
H H IA
CF
A B
C D E F G
H
I
4.3 Flurplan – Floorplanning4.3.3 Begriffe und Datenstrukturen
Blöcke mit flexiblen Abmessungen sind durch Flächenvorgabe A bestimmt
Unabhängig von der Form des Blocks
Formfunktionen
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
89
Unabhängig von der Form des BlocksHöhe h und die Breite w haben der Randbedingung h w ≥ A zu genügen
Abhängigkeit zwischen Höhe und Breite eines Blocks (z.B. Höhe als Funktion der Breite) wird als Formfunktion (Shape function) des Blocks bezeichnet
4.3 Flurplan – Floorplanning4.3.3 Begriffe und Datenstrukturen
ErlaubteBlockformen
ErlaubteBlockformen
h h
Nac
h G
erez
, S
. H.:
Alg
orith
ms
for
VLS
I Des
ign
‚Aut
omat
ion,
Wile
y, 2
000
Formfunktionen
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
90
w w
Nac
h G
erez
, S
. H.:
Alg
orith
ms
for
VLS
I Des
ign
‚Aut
omat
ion,
Wile
y, 2
000
Mit minimalen Höhen- undBreitenbeschränkungen
ha*aw ≥ A
4.3 Flurplan – Floorplanning4.3.3 Begriffe und Datenstrukturen
h
Formfunktionen
Nac
h G
erez
, S
. H.:
Alg
orith
ms
for
VLS
I Des
ign
‚Aut
omat
ion,
Wile
y, 2
000
h
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
91
w
Bibliotheksblock mit zwei Anordnungsmöglichkeiten
Nac
h G
erez
, S
. H.:
Alg
orith
ms
for
VLS
I Des
ign
‚Aut
omat
ion,
Wile
y, 2
000
w
Mit diskreten Höhen- und Breitenwerten
4.3 Flurplan – Floorplanning4.3.4 Flurplan -Algorithmen - Begriffe
Einzelne diskrete Form-Möglichkeiten eines Blocks,
Spiegeln sich in „äußeren“ wider
Eckwerte
h
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
92
„äußeren“ widerwerden als Eckwerte (Break points) bezeichnet
w
4.3 Flurplan – Floorplanning4.3.4 Flurplan -Algorithmen - Begriffe
5
5
Eckwerte
h
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
93
5
2
2
2 5
2
5
w
4.3 Flurplan – Floorplanning4.3.4 Flurplan -Algorithmen
Floorplan-Sizing-Algorithmus (flexible Blöcke, soft blocks)
Cluster-Wachstums-Algorithmus (feste Blöcke, hard blocks)
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
94
4.3 Flurplan – Floorplanning4.3.4 Flurplan -Algorithmen
Floorplan-Sizing-AlgorithmusAufgabe: Ermittlung der Formfunktionen aller in der Topzelle anzuordnenden Blöcke
Ermittlung der Formfunktion der Topzelle mit einer Bottom-up-Strategie
• bei der vom niedrigsten Blockniveau ausgehend•
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
95
• bei der vom niedrigsten Blockniveau ausgehend• die Formfunktionen der Blöcke kombiniert werden• Ergebnis: Ermittlung der optimalen Größe bzw. Form der
Topzelle
Von der Formfestlegung der Topzelle ausgehend, • wird der Schnittbaum nach „unten“ (Top down) abgearbeitet
und • dabei die jeweilige zusammengesetzte Blockform ermittelt, bis
sämtliche (Basis-) Blöcke erreicht sind
4.3 Flurplan – Floorplanning4.3.4 Flurplan -Sizing -Algorithmus - Beispiel
1. Ermitteln der Formfunktionen der Blöcke
Block A:
5
5
3 h
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
96
24
2
2
4
Block B:
53
w2 6
2
4
4
65
3
4.3 Flurplan – Floorplanning4.3.4 Flurplan -Sizing -Algorithmus - Beispiel
Block A:
5
5
3
3
h
1. Ermitteln der Formfunktionen der Blöcke
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
97
4
2
2
4
Block B:
3
w2 6
2
4
4
6
hA(w)
4.3 Flurplan – Floorplanning4.3.4 Flurplan -Sizing -Algorithmus - Beispiel
Block A:
5
5
3
3
h
1. Ermitteln der Formfunktionen der Blöcke
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
98
4
2
2
4
Block B:
3
hB(w)
w2 6
2
4
4
6
hA(w)
4.3 Flurplan – Floorplanning4.3.4 Flurplan -Sizing -Algorithmus - Beispiel
h
2. Ermitteln der Formfunktion der Topzelle (vertikale Zusammensetzung)
h
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
99
w2 6
2
4
4
6
hB(w)hA(w)
8
w2 6
2
4
4
6
hB(w)hA(w)
8
4.3 Flurplan – Floorplanning4.3.4 Flurplan -Sizing -Algorithmus - Beispiel
2. Ermitteln der Formfunktion der Topzelle (vertikale Zusammensetzung)
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
100
4.3 Flurplan – Floorplanning4.3.4 Flurplan -Sizing -Algorithmus - Beispiel
hh
88
2. Ermitteln der Formfunktion der Topzelle (vertikale Zusammensetzung)
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
101
w2 6
2
4
4
6
w2 6
2
4
4
6
hB(w)hA(w)
hB(w)hA(w)
hC(w)
88
4.3 Flurplan – Floorplanning4.3.4 Flurplan -Sizing -Algorithmus - Beispiel
h
2. Ermitteln der Formfunktion der Topzelle (vertikale Zusammensetzung)
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
102
w2 6
2
4
4
6
hB(w)hA(w)
hC(w)
5 x 5
8
4.3 Flurplan – Floorplanning4.3.4 Flurplan -Sizing -Algorithmus - Beispiel
hh3 x 9
2. Ermitteln der Formfunktion der Topzelle (vertikale Zusammensetzung)
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
103
w2 6
2
4
4
6
w2 6
2
4
4
6
hB(w)hA(w)
hB(w)hA(w)
hC(w)4 x 7
5 x 5
88
4.3 Flurplan – Floorplanning4.3.4 Flurplan -Sizing -Algorithmus - Beispiel
hh3 x 9
88
2. Ermitteln der Formfunktion der Topzelle (vertikale Zusammensetzung)
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
104
w2 6
2
4
4
6
w2 6
2
4
4
6
hB(w)hA(w)
hB(w)hA(w)
hC(w)4 x 7
5 x 5
88
Minimale Topzellen-Flächebei vertikaler Zusammensetzung
4.3 Flurplan – Floorplanning4.3.4 Flurplan -Sizing -Algorithmus - Beispiel
h
hA(w)hB(w)
2. Ermitteln der Formfunktion der Topzelle (horizontale Zusammensetzung)
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
105
w2 6
2
4
4
6
8
4.3 Flurplan – Floorplanning4.3.4 Flurplan -Sizing -Algorithmus - Beispiel
h
hA(w)hB(w)
2. Ermitteln der Formfunktion der Topzelle (horizontale Zusammensetzung)
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
106
w2 6
2
4
4
6
8
4.3 Flurplan – Floorplanning4.3.4 Flurplan -Sizing -Algorithmus - Beispiel
hh
hA(w)hB(w) hC(w)hA(w)hB(w)
2. Ermitteln der Formfunktion der Topzelle (horizontale Zusammensetzung)
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
107
w2 6
2
4
4
6
w2 6
2
4
4
6
88
4.3 Flurplan – Floorplanning4.3.4 Flurplan -Sizing -Algorithmus - Beispiel
hh
hA(w)hB(w) hC(w)hA(w)hB(w)5 x 5
2. Ermitteln der Formfunktion der Topzelle (horizontale Zusammensetzung)
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
108
w2 6
2
4
4
6
w2 6
2
4
4
6
9 x 3
7 x 4
88
5 x 5 ist minimale Topzellen-Flächebei horizontaler Zusammensetzung
4.3 Flurplan – Floorplanning4.3.4 Flurplan -Sizing -Algorithmus - Beispiel
h
3. Formfestlegung von Topzelle und Blöcken(horizontale Zusammensetzung)
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
109
w2 6
2
4
4
6
1. Minimale Fläche der Topzelle: 5 x 5
2. Abgeleitete Blockformen: 2 x 4 und 3 x 5
82 x 4 3 x 5
5 x 5
4.3 Flurplan – Floorplanning4.3.4 Flurplan -Sizing -Algorithmus - Beispiel
Resultierender Schnittbaum
5 x 5
V
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
110
Resultierender Schnittbaum
2 x 4 3 x 5
B AB A
4.3 Flurplan – Floorplanning4.3.4 Cluster-Wachstum -Algorithmus
Konstruktives VerfahrenBlockanordnung erfolgt Schritt für Schritt
Initiale Platzierung eines Blocks in einem Eck (z.B. links unten)
Danach Platzierung übriger Blöcke• Entweder vertikal, diagonal, horizontal• Gegeben durch Form der Topzelle
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
111
• Gegeben durch Form der Topzelle
w
h
Topzelle w x h
4.3 Flurplan – Floorplanning4.3.4 Cluster-Wachstum -Algorithmus
Welche Blöcke werden platziert?Lineare Blockanordnung bestimmen
• mit dem Ziel der Minimierung der Anzahl der Netze, die bei einem beliebigen Schnitt durch diese Blockfolge aufzutrennen sind
Rangordnung mit Hilfe von NetzklasenEndende Netze, neue Netze, weitergeführte Netze
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
112
Endende Netze, neue Netze, weitergeführte Netze
…
Endende Netze Neue Netze
Weitergeführte Netze
3.4.2 Cluster-Wachstum: Lineare Anordnung
Blockanordnung bestimmt durch Anzahl der Netze innerhalb der mit einem Block verbundenen Netzklassen
Gewinn (Gain) eines Blockes m:Gain m = (Anzahl der in m endenden Netze)
– (von m ausgehende neue Netze)
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
113
Block mit höchstem Gewinn als nächstes platzieren
A B
N1
N4
GainB = 1 (N1) – 1 (N4) = 0
4.3 Flurplan – Floorplanning4.3.4 Cluster-Wachstum -Algorithmus
Algorithmus zur linearen Anordnung
S : Menge aller Blöcke Order: Reihenfolge der Blöcke /* anfangs leer */ Begin
Seed = Auswahl eines Anfangsblocks Order = [Seed] S = S – { Seed } Repeat
ForEach Block m ∈ S Do Ermitteln des Gewinns (Gain) des aktuellen Blocks m Gainm =(Anzahl der in m endenden Netze)–(von m ausgehende neue Netze)
End ForEach
Nac
h S
ait,
S. M
., Y
ouss
ef, H
.: V
LSI P
hysi
cal D
esig
n A
utom
atio
n
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
114
End ForEach Auswahl des Blocks m* mit maximalem Gewinn Gainm If Gleichheit Then
Auswahl des Blocks, der die meisten Netze beendet ElseIf Gleichheit Then
Auswahl des Blocks mit der größten Anzahl ausgehender Netze ElseIf Gleicheit Then
Auswahl des Blocks mit der geringsten Anzahl von Verbindungen Else
Willkürliche Auswahl eines Blocks Order = [Order, m* ] /* Hinzufügen von m* zur existierenden Folge */ S = S – { m* }
Until S = ∅ End.
Nac
h S
ait,
S. M
., Y
ouss
ef, H
.: V
LSI P
hysi
cal D
esig
n A
utom
atio
n
4.3 Flurplan – Floorplanning4.3.4 Cluster-Wachstum -Algorithmus
Gegeben: – Netzliste mit fünf Blöcken A, B, C, D, E und sechs Netzen
N1 = {A, B} N2 = {A, D} N3 = {A, C, E} N4 = {B, D} N5 = {C, D, E} N6 = {D, E}
– Anfangsblock: A
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
115
Gesucht: Lineare Anordnung mit minimalen Netzkosten
A B C D E
N1
N2
N3
N4
N5
N6
Schritt Blöcke Neue Netze Endende Gewinn Weitergeführte
A B C D E
N1
N2
N3
N4
N5
N6
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
116
Schritt #
Blöcke Neue Netze Endende Netze
Gewinn (Gain)
Weitergeführte Netze
0 A N1, N2, N3 - -3 -
Geg.: Anfangsblock A
GainA = (Anzahl der in A endenden Netze) – (von A ausgehende neue Netze)
Schritt #
Blöcke Neue Netze Endende Netze
Gewinn (Gain)
Weitergeführte Netze
0 A N1, N2, N3 - -3 - 1 B
C
D E
N4 N5 N4, N5, N6 N , N
N1 - N2 -
0 -1 -2 -2
- N3 - N
A B C D E
N1
N2
N3
N4
N5
N6
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
117
E N5, N6 - -2 N3 2 C
D E
N5 N5, N6 N5, N6
- N2, N4
-
-1 0 -2
N3 - N3
3 C E
- -
- N6
0 +1
N3, N5 N3, N5
4 C - N3, N5, +2 -
A B D E C
N1
N2
N3
N4 N5
N6
4.3 Flurplan – Floorplanning4.3.4 Cluster-Wachstum -Algorithmus
A B C D E
N1
N2
N3
N4
N5
N6
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
118
A B D E C
N1
N2
N3
N4 N5
N6
4.3 Flurplan – Floorplanning4.3.4 Cluster-Wachstum -AlgorithmusGegeben: Blöcke A, B, C, D, E mit freier Orientierung und der linearen Anordnung [A, B, D, E, C] sowie festen Abmessungen.
Gesucht: Topzelle mit minimaler Fläche
Lösung:
Block Breite w Höhe h A 2 3 B 2 1 C 2 4 D 3 3 E 6 1
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
119
A
B
DC
E
4.3 Flurplan – Floorplanning4.3.4 Pinzuordnung
Die bei der Partitionierung anfallenden Teilschaltungen (Blöcke) sind durch eine Menge von externen Netzen charakterisiert, mit denen sie untereinander in Verbindung stehen
Außenanschlüsse: Pinanschlüsse am Rand der Teilschaltungen, zwischen denen die externe
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
120
Teilschaltungen, zwischen denen die externe Verdrahtung zu realisieren ist
Die Lage der Außenanschlüsse ist in den meisten Fällen vorgegeben, jedoch nicht ihre Zuordnung zu den einzelnen Netzen
4.3 Flurplan – Floorplanning4.3.4 Pinzuordnung
Aufgabe der Pinzuordnung bei Zellen ist die Optimierung der Netzzuordnung innerhalb funktional äquivalenter bzw. äquipotentialer Pingruppen.
Funktional äquivalente Pins:Austausch beeinflusst nicht die
Schaltung (z.B. die beiden Eingangspins eines NAND-Gattters
Äquipotentiale Pins:sind zellintern miteinander verbunden und
repräsentieren damit das gleiche Netz
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
121
Kontakt (contact cut)
Metal1 (metal1)
Polyebene (polysilicon)
Diffusionsschicht (p/n diffusion)
Via (via)
Metal2 (metal2)
können i.d.R. ausgetauscht werden)
4.3 Flurplan – Floorplanning4.3.4 Pinzuordnung
Beispiel für einfachere Verdrahtung durch Nutzung funktional äquivalenter und äquipotentialer Anschlüsse
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
122
4.3 Flurplan – Floorplanning4.3.4 Pinzuordnung
Pinzuordnung mittels konzentrischer Kreise: BeispielKreisbestimmungAnnahme:
• Äußeren Punkte fix• Inneren Punkte variabel
Nac
h K
oren
, N
. L.:
Pin
Ass
ignm
ent i
n A
utom
ated
Prin
ted
Circ
uit B
oard
s
Zuordnungsproblem 1. Kreisbestimmung
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
123
Nac
h K
oren
, N
. L.:
Pin
Ass
ignm
ent i
n A
utom
ated
Prin
ted
Circ
uit B
oard
s
Zuordnungsproblem 1. Kreisbestimmung
4.3 Flurplan – Floorplanning4.3.4 Pinzuordnung
Pinzuordnung mittels konzentrischer Kreise: BeispielPunktbestimmung
Nac
h K
oren
, N
. L.:
Pin
Ass
ignm
ent i
n A
utom
ated
Prin
ted
Circ
uit B
oard
s2. Punktbestimmung
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
124
Nac
h K
oren
, N
. L.:
Pin
Ass
ignm
ent i
n A
utom
ated
Prin
ted
Circ
uit B
oard
s
4.3 Flurplan – Floorplanning4.3.4 Pinzuordnung
Pinzuordnung mittels konzentrischer Kreise: BeispielAnfangszuordnung
Nac
h K
oren
, N
. L.:
Pin
Ass
ignm
ent i
n A
utom
ated
Prin
ted
Circ
uit B
oard
s3. Anfangszuordnung
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
125
Nac
h K
oren
, N
. L.:
Pin
Ass
ignm
ent i
n A
utom
ated
Prin
ted
Circ
uit B
oard
s
4.3 Flurplan – Floorplanning4.3.4 Pinzuordnung
Pinzuordnung mittels konzentrischer Kreise: BeispielAnfangszuordnung und Zuordnungsoptimierung
Nac
h K
oren
, N
. L.:
Pin
Ass
ignm
ent i
n A
utom
ated
Prin
ted
Circ
uit B
oard
s
3. Anfangszuordnung und 4. Zuordnungsoptimierung (komplette Rotation)
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
126
Nac
h K
oren
, N
. L.:
Pin
Ass
ignm
ent i
n A
utom
ated
Prin
ted
Circ
uit B
oard
s
4.3 Flurplan – Floorplanning4.3.4 Pinzuordnung
Pinzuordnung mittels konzentrischer Kreise: BeispielAnfangszuordnung und Zuordnungsoptimierung
Nac
h K
oren
, N
. L.:
Pin
Ass
ignm
ent i
n A
utom
ated
Prin
ted
Circ
uit B
oard
s
3. Anfangszuordnung und 4. Zuordnungsoptimierung (komplette Rotation)
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
127
Nac
h K
oren
, N
. L.:
Pin
Ass
ignm
ent i
n A
utom
ated
Prin
ted
Circ
uit B
oard
s
4.3 Flurplan – Floorplanning4.3.4 Pinzuordnung
Pinzuordnung mittels konzentrischer Kreise: BeispielErgebnis der Zuordnungsoptimierung
Nac
h K
oren
, N
. L.:
Pin
Ass
ignm
ent i
n A
utom
ated
Prin
ted
Circ
uit B
oard
s
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
128
Nac
h K
oren
, N
. L.:
Pin
Ass
ignm
ent i
n A
utom
ated
Prin
ted
Circ
uit B
oard
s
Resultierende Pinzuordnung
4.3 Platzierung
VerhaltensentwurfLogischer Entwurf
Floorplanning
ENTITY test isport a: in bit;
end ENTITY test;Partitionierung
Systemspezifikation
Architekturentwurf
Schaltungsentwurf
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
129
Layoutsynthese
Layoutverifikation
Chip
Platzierung
Verdrahtung
Kompaktierung
Herstellung
Verpackung/Test
4.3 Platzierung
Situation: Partitionen und Pinzuordnungen gegeben
Die Aufgabe der Platzierung ist die Anordnung der einzelnen Schaltungselemente (z.B. Zellen und Bauelemente) in den Partitionen
unter Berücksichtigung von
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
130
unter Berücksichtigung von Randbedingungen (u.a. Überlappungsfreiheit) und Optimierungsziele (z.B. minimale Verbindungslänge)
4.3 Platzierung - Begriffe
a) Schaltungs-beispiel
b) Eindimensionale Platzierung
(Reihenanordnung)
1
2
4
5
3
6
7 8
56487231
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
131
8 5 4 1
7 6 3 2
d) Platzierung und Verdrahtung im Standardzellenlayout
GND
Vdd
c) Zweireihige Platzierung
6
4
7 23
18 5
4.3.1 Optimierungsziel: Gesamtverbindungslänge
Ziel: Minimierung der GesamtverbindungslängePlatzierung hat starken EinflussSiehe linkes Ergebnis (gut) und rechtes Ergebnis (schlecht)
15 8 106 811
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
132
2
3
47
6 912
11 1
2
3 54
7
912
10
4.3.1 Optimierungsziel: Gesamtverbindungslänge
Weitere Optimierungsziele
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
133
Gesamtverbindungslänge Anzahl der geschnittenen Netze
Lokale Verdrahtungsdichte
Signalverzögerungen
Halber Umfang des Kompletter Graph Minimale Kette
4.3.1 Optimierungsziel: Gesamtverbindungslänge
Abschätzung der Verdrahtungslängen bei Mehrpunktnetzen
Während der Platzierung kann Verbindungslänge nur abgeschätzt werden (Verdrahtung erfolgt erst später)Verschiedene Möglichkeiten bei Mehrpunktnetzen
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
134
Länge halber Netz-umfang = 9
4
5
minimal umschließenden Rechtecks
(Semi-perimeter method)
(Complete graph)
Länge kompletter Graph * 2 / Pinanzahl = 14,5
36
5
3
8
4
(Minimum chain)
Kettenlänge = 12
3
3
6
Quelle-Senken-Verbindung
(Source to sink connection)
Minimaler rektilinearer Spannbaum
(Minimum rectilinear spanning tree)
Steinerbaum-Abschätzung (Steiner tree
approximation)
4.3.1 Optimierungsziel: Gesamtverbindungslänge
Weitere Möglichkeiten
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
135
Quelle-Senken-Länge= 15
83
4
Spannbaum-Länge = 11
3
3
5
Steinerbaum-Länge = 10
3 16
Netze GewichtN1 = (A, B, D1) w1 = 2
AC
4.3.1 Optimierungsziel: Gesamtverbindungslänge – Beispiel
Zusätzlich Einführung von GewichtungenZ.B. zur Berücksichtigung kritischer Netze
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
136
N2 = (C, D2, F1) w1 = 4N3 = (F2, E) w1 = 1
33314472)( =⋅+⋅+⋅=⋅=∑∈Nn
nn dwPL
B
D
E
F
Netze x1 x2 x1 x2
4.3.2 Optimierungsziel: Anzahl der geschnittenen Netze – Beispiel
Anzahl der Schnitte über horizontale und vertikale Netze zählen
ΨP(xi) : Anzahl geschnittener Netze über Gerade xi
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
137
Netze N1 = (A, B, D1) N2 = (C, D2, F1) N3 = (F2, E)
ψP(x1) = 1 ψP(x2) = 2
ψP(y1) = 3 ψP(y2) = 2
A
B
C
D
E
F
y1
y2
x1 x2
1 2
A
B
C
D
E
F
y1
y2
x1 x2
0;0
1
2
1 2
Netze x1 x2 x1 x2
4.3.2 Optimierungsziel: Anzahl der geschnittenen Netze – Beispiel
Aus Anzahl geschnittener horizontaler und vertikaler Netze lässt sich auf Gesamtverbindungslänge schließen
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
138
Netze N1 = (A, B, D1) N2 = (C, D2, F1) N3 = (F2, E)
ψP(x1) = 1 ψP(x2) = 2
ψP(y1) = 3 ψP(y2) = 2 Zielfunktion (Gesamtverbindungslänge):
82321)()()()()()()( 2P1P2P1PPP =+++=+++=+= ∑∑ yyxxyxPL jj
ii
ψψψψψψ
A
B
C
D
E
F
y1
y2
1 2
A
B
C
D
E
F
y1
y2
0;0
1
2
1 2
4.3.3 Optimierungsziel: Lokale Verdrahtungsdichte – Beispiel
Unterscheidung Kanäle (A2) – Switchboxen (A1)Switchbox hat vertikale und horizontale Verdrahtungskapazität Kanal nur vertikale Verdrahtungskapazität
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
139
A1A1
A2 A2
Netze
4.3.3 Optimierungsziel: Lokale Verdrahtungsdichte – Beispiel
Verdrahtungskapazität bestimmenUm Verdrahtbarkeit einer Platzierung zu testenLokale Verbindungsdichte einer Kante
)(
)()(
iP
iPiP e
eed
φη=
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
140
Netze N1 = (A, B, D1) N2 = (C, D2, F1) N3 = (F2, E)
Jede Kante besitzt eine Kapazität φP(ei) = 3.
A
B
C
D
E
ηP(e9) = 2
ηP(e12) = 0
ηP(e4) = 0
F
ηP(e3) = 1ηP(e1) = 1
ηP(e6) = 1 ηP(e8) = 2
Netze N1 = (A, B, D1) N2 = (C, D2, F1) N3 = (F2, E)
Jede Kante besitzt eine Kapazität φP(ei) = 3.
A
B
C
D
E
ηP(e9) = 2
ηP(e12) = 0
ηP(e4) = 0
F
ηP(e3) = 1ηP(e1) = 1
4.3.3 Optimierungsziel: Lokale Verdrahtungsdichte – Beispiel
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
141
Maximum ηP(ei) = 2, φP(ei) = 3, womit D(P) = 2/3, d.h. D(P) ≤ 1, die Platzierung P also einfach zu verdrahten sein sollte.
B EηP(e12) = 0
ηP(e6) = 1 ηP(e8) = 2
4.3 Platzierungsalgorithmen
Partitionierende Algorithmen (rekursive Algorithmen): Optimierung der Platzierungsanordnung mittels rekursiver und dabei immer feinerer Partitionierung der Netzliste und des Platziergebiets Nutzung von Graphenpartitionierern Beispiel: Min-Cut-Platzierung
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
142
Analytische Vorgehensweisen: Nutzung von mathematischen Methoden (z.B. lineare Gleichungssysteme) zur Abbildung und Optimierung des PlatzierungsproblemsBeispiel: Quadratische Platzierung
4.3 Platzierungsalgorithmen
Stochastische Algorithmen:Mit Hilfe von stochastischen Methoden wird das Minimum einer beliebigen Kostenfunktion gesucht Einbeziehung von Zufallsentscheidungen, womit bei gleicher Aufgabenstellung unterschiedliche Lösungen erzeugt werdenBeispiel: Simulated Annealing
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
143
Beispiel: Simulated Annealing
StochastischPartitionierend Analytisch
Quadratische PlatzierungMin-Cut-Platzierung Platzierung mit SA
4.3 Platzierungsalgorithmen
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
144
Quadratische PlatzierungMin-Cut-Platzierung Platzierung mit SA
4.3.4 Min-Cut-Platzierung
Platzierungsfläche sequentiell mit Schnittlinien durchzogen, bis die Schnittflächen so klein sind, dass sie nur noch wenige/eine Zelle einschließen
Bei jedem Schnitt werden die Zellen z.B. so auf die beiden entstehenden Teilflächen aufgeteilt, dass am Ende die Anzahl der die Schnittlinien cr kreuzenden
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
145
Ende die Anzahl der die Schnittlinien cr kreuzenden Netze P(cr) minimiert ist
Algorithmen zur Minimierung von P(cr) sind oft der Kernighan-Lin-Algorithmus (KL-Algorithmus) sowie der Fiduccia-Mattheyses-Algorithmus (FM-Algorithmus)
4.3.2 Partitionierung - Min -Cut-Platzierung
Min-Cut-Algorithmus (Quadratur Platzierung)Aufteilung der Layoutfläche in zwei Teilflächen mit senkrechter oder horizontaler Schnittrichtung
Anwendung eines geeigneten Algorithmus zur optimierten Verteilung der Zellen auf die beiden Teilflächen
• z.B. des KL- oder FM-Algorithmus
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
146
• z.B. des KL- oder FM-Algorithmus
Aufteilung in neue Teilflächen und jeweils Initialzuordnung der Zellen auf diese
• Alternierender Wechsel zwischen senkrechter und horizontaler Schnittrichtung
ENDE, falls jede Teilfläche genau eine Zelle enthält, sonst weiter mit Schritt 2
Quadratur-Platzierung(Quadrature placement)
Halbierungs-Platzierung
(Bisection placement)
Reihen-/Halbierungs-Platzierung
(Slice/bisection placement)
4.3.2 Partitionierung - Min -Cut-Platzierung
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
147
1
2
3a
3b
4a 4b
1
6b
2a
2b
6a 4
3a
3b
3c
3d
5a 6c5b 6d
4
10b
2
6
10a8
1
3
5
7
9a10c
9b10d
Gegeben:1
2
3
4
5 6
4.3.2 Partitionierung - Min -Cut-Platzierung
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
148
Gesucht: 4 x 2 Platzierung mit minimaler Netzlänge
4.3.2 Partitionierung - Min -Cut-Platzierung
1
2
3
4
5 6
c1
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
149
Vertikaler Initialschnitt c1: L={1,2,3}, R={4,5,6}
1
2
3
0
4
5
6
0
1
2 3
0
4 5
6
0
c1 c1
z.B. KL-Algorithmus
Horizontaler Schnitt c2L: T={1,4}, B={2,0}
Horizontaler Schnitt c2R: T={3,5}, B={6,0}
1
2 3
0
4 5
6
0
c1
4.3.2 Partitionierung - Min -Cut-Platzierung
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
150
c2L: T={1,4}, B={2,0}
1
2 0
4
c2R: T={3,5}, B={6,0}
3 5
60
1
20
4 5 3
06
c3L c3R
1 4 5 3
2 6
c2L c2R
4.3.2 Partitionierung - Min -Cut-Platzierung
Vorteile:Sehr schnellKostenfunktion kann beliebig erweitert werden, d.h. auch für Timing-driven Placement anwendbarVon Natur aus hierarchisch, daher für große Schaltungen nutzbar
Nachteile:
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
151
Nachteile:Viele Verschiebungen ohne AuswirkungenOft Zufallsfaktoren eingeschlossen, daher nicht immer deterministischUnterhalb bestimmter Partitionsgröße andere Ansatz zur Platzierung sinnvollNur sequentielle Optimierung, d.h. die Optimierung bezieht sich immer nur auf die Zuordnung zur jeweils betrachteten Schnittlinie