4.3 Layoutsynthese (Flurplan Floorplanning) · PDF fileLehrstuhl für Informatik 3 - Prof. D. Fey Vorlesung Einführung digitaler ASIC Entwurf WS 2010/11 Folie 73 4.3 Layoutsynthese

Lehrstuhl fr Informatik 3 - Prof. D. Fey
Vorlesung Einfhrung digitaler ASIC Entwurf
WS 2010/11 Folie 73
4.3 Layoutsynthese (Flurplan Floorplanning)
4.3.1 Einfhrung
4.3.2 Optimierungsziele
4.3.3 Begriffe und Datenstrukturen
4.3.4 Algorithmen fr das Floorplanning- Floorplan-Sizing-Algorithmus
- Cluster-Wachstums-Algorithmus (Cluster Growth)
- Weitere Algorithmen fr das Floorplanning
4.3.5 Pinzuordnung (Pin Assignment)
- Problembeschreibung
- Pinzuordnung mittels konzentrischer Kreise
- Topologische Pinzuordnung

WS 2010/11 Folie 74
4.3 Flurplan Floorplanning
Verhaltensentwurf
Logischer Entwurf
Layoutsynthese
Layoutverifikation
Chip
Floorplanning
Platzierung
Verdrahtung
Kompaktierung
ENTITY test isport a: in bit;
end ENTITY test;Partitionierung
Herstellung
Systemspezifikation
Architekturentwurf
Schaltungsentwurf
Verpackung/Test

WS 2010/11 Folie 75
4.3.1 Einfhrung
Die Aufgabe des Floorplanning
das Ergebnis der Schaltungspartitionierung so aufzubereiten, dass
jeder dabei erstellte Block intern platziert und verdrahtet werden
kann.
Dazu sind im Allgemeinen
die Abmessungen bzw. Seitenverhltnisse der einzelnen Blcke,
und evtl. auch der Topzelle, festzulegen
die Positionen der Auenanschlsse in den einzelnen Blcken zu
bestimmen (Pinzuordnung)
die Positionen dieser Blcke innerhalb der Topzelle zu definieren

WS 2010/11 Folie 76
4.3.1 EinfhrungBeispiel
Gegeben: Drei Blcke mit folgenden Seitenverhltnissen (Breite w, Hhe 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 Gesamtflche der Topzelle
Lsung:
Seitenverhltnisse
Block A mit w = 2, h = 2; Block B mit w = 2, h = 1; Block C mit w = 1, h = 3
Mgliche Anordnung der Blcke:
Damit entspricht diese Lsung dem theoretischen Optimum (neun Flcheneinheiten).
A
B
C

WS 2010/11 Folie 77
Zu optimieren sind
Flche und Form des umschlieenden Rechtecks
entspricht der Topzelle
Gesamtverbindungslnge minimieren
ci,j : Matrixelement, das Verbindungsgrad (Anzahl Verbindungen)
zwischen Partition i und j angibt
di,j : Entfernung zwischen Partitionen i und j
Z.B. Manhattan-Metrik
Euklid-Metrik
ji
jiji dcL,
,,

WS 2010/11 Folie 78
Lngenbestimmung ber Manhattan-Entfernung (Manhattan-Metrik)
Lngenbestimmung ber minimalen Spannbaum (euklidische
Metrik)
P1
P2
Euklidische Metrik Manhattan-Metrik
n=1 fr Manhattan-Metrik
n=2 fr euklidische Metrik
n2112
x :Abstandn
yyn
x

WS 2010/11 Folie 79
Zu optimieren sind ferner
Signalverzgerungen
Zunahme der Taktfrequenzen
Erfordert Einhalten maximaler Signalverzgerungen auf einzelnen Netzen
Flurplan gesucht, der gettigte Vorgaben hinsichtlich Timing zwischen Netzen erfllt
Kritische Pfadlngen bzw. Netze bestimmen
Zugehrige Partitionen zuerst im Flurplan mit minimalen Abstnden
anordnen

WS 2010/11 Folie 80
Flchenminimale Topzelle angestrebt
Soft Blocks (Definition s. nchste Folie):
Flchenminimierung der Topzelle erfolgt unter Ausnutzung der Flexibilitt in den Formen der einzelnen Blcke (bei
soft blocks mglich)
lassen sich flchenminimal anordnen, wenn man ihre Formen zueinander
passend gestaltet
Hard Blocks (Definition s. nchste Folie):
Keine Flexibilitt der Blockformen (Bin Packing Problem)
Evtl. Einhalten Formvorgaben der Topzelle

WS 2010/11 Folie 81
Blcke mit variablen Formen, bei denen nur die Flchen
vorgegeben sind, werden als flexible Blcke bezeichnet
Bei festen Blcken ist die uere Form festgelegt
Flexible Blcke (Soft blocks) , feste Blcke (Hard blocks)

WS 2010/11 Folie 82
B
D
AE
CA
BC
D
E
Basiszellen sind nicht
ausschlielich durch
vertikale oder horizontale
Zweiteilung entstanden
Mindestens fnf Basiszellen, sog. Rad
(Wheel)
Geschnittener Floorplan
(Slicing floorplan)
Ungeschnittener Floorplan
(Non-slicing floorplan)
Basiszellen sind durch
(wiederholte) vertikale
oder horizontale Zweiteilung
entstanden
B
DA
E
C
F

WS 2010/11 Folie 83
Ein Floorplan besitzt die Ordnung n, wenn er durch Teilung
eines Rechtecks in maximal n Teile entstanden ist.
Geschnittener (Slicing) Floorplan: Ordnung 2
Ungeschnittener (Non-slicing) Floorplan: mindestens Ordnung 5
Floorplan n-ter Ordnung
A
B
C
D
E
F
G
Ordnung 5

WS 2010/11 Folie 84
Ein Schnittbaum ist die Modellierung eines geschnittenen Floorplans durch einen Binrbaum mit k Blttern und k-1 Knoten
Jeder Knoten reprsentiert dabei eine Schnittlinie und jedes Blatt einen Block
Wesentliches Merkmal eines Schnittbaums ist seine Binrstruktur, d.h. jeder Knoten hat genau zwei Kinder
Schnittbaum (Slicing tree)
A
B C
H
A V
B C

WS 2010/11 Folie 85
H
V
A
B
C H
D VD
E F
H
B
A
E
C
F
Beispiel: Schnittbaum (Slicing tree)

WS 2010/11 Folie 86
H
V
A
B
C H
D VD
E F
H H
V
A B D H
C V
E F
H
B
A
E
C
F

WS 2010/11 Folie 87
Jeder hierarchische Floorplan (geschnitten und
ungeschnitten) kann durch einen Floorplanbaum
reprsentiert werden
Jedes Blatt verkrpert dabei einen Block, jeder Knoten
entweder einen vertikalen bzw. horizontalen
Schnittoperator oder ein Rad
Binre Schnittbume (Slicing trees) sind damit
Untermengen der Floorplanbume
Floorplanbaum (Floorplan tree)

WS 2010/11 Folie 88
H
HV
H H I
W
A
B
C
D
E
F
G
A B
C D E F G
H
I
Floorplanbaum (Floorplan tree)

WS 2010/11 Folie 89
Blcke mit flexiblen Abmessungen sind durch
Flchenvorgabe A bestimmt
Unabhngig von der Form des Blocks
Hhe h und die Breite w haben der Randbedingung
h w A zu gengen
Abhngigkeit zwischen Hhe und Breite eines Blocks (z.B.
Hhe als Funktion der Breite) wird als Formfunktion (Shape
function) des Blocks bezeichnet
Formfunktionen

WS 2010/11 Folie 90
4

Documents

4.3 Layoutsynthese (Flurplan Floorplanning) · PDF fileLehrstuhl für Informatik 3 - Prof. D. Fey Vorlesung Einführung digitaler ASIC Entwurf WS 2010/11 Folie 73 4.3 Layoutsynthese