Lehrstuhl für Informatik 3 - Prof. Dr.-Ing. D. Fey
Vorlesung Einführung digitaler ASIC Entwurf
WS 2010/11 Folie 1
4. Synthese digitaler Schaltungen
4.1 Technologieabbildung
Aufgabe Technologie-Abbildung
Abbildung der Ergebnisse einer von der Technologie
unabhängigen Optimierung einer Booleschen Netzliste auf
gewählte Zielstruktur, in welcher die Technologie des
Schaltkreisherstellers zu berücksichtigen ist
Zellen einer Technologie-Bibliothek eines bestimmten Herstellers
Eigenschaften der durch die Abbildung ermittelten Logikfelder
• Programmierung der Ausgangszellen
– Z.B. beim „Array-basierten Entwurf“, FPGA, PLD, PLA
(s. Folie 57 ff. Kap. 3)
• flexible Produkttermnutzung
• Notwendigkeit der Partitionierung in Teilfelder
Lehrstuhl für Informatik 3 - Prof. Dr.-Ing. D. Fey
Vorlesung Einführung digitaler ASIC Entwurf
WS 2010/11 Folie 2
4. Synthese digitaler Schaltungen4.1 Technologieabbildung
wichtig: Abbildung erfolgt unter Optimierung einer zugrunde
liegenden Kostenfunktion
keine abstrakte Zielfunktion wie die Zahl der Produktterme bei zweistufiger
Logik oder
die Anzahl der Literale bei mehrstufiger Logik
berücksichtigt werden
• Fläche
• Zeit
Im Folgenden wird ein Verfahren zur Technologie-Abbildung für die
mehrstufige Logik behandelt
für zellenbasierte Entwürfe
Minimierung bei Technologie-Abbildung exponentieller Aufwand
bei größeren Schaltungen sind daher Heuristiken notwendig
Lehrstuhl für Informatik 3 - Prof. Dr.-Ing. D. Fey
Vorlesung Einführung digitaler ASIC Entwurf
WS 2010/11 Folie 3
4. Synthese digitaler Schaltungen4.1 Technologieabbildung
Strategie bei der Technologie-Abbildung:
Rückführung des eingegebenen Booleschen Netzes
auf gemeinsame standardisierte Form
gewählte Standard-Beschreibung: NAND-Gatter mit zwei Eingängen
anschließend: Überprüfung welche Elemente der Bibliothek
können Teile der Schaltung ersetzen
Frage der Überdeckung von Teilen der Schaltung mit
Bibliothekselementen unter Berücksichtigung einer Kostenfunktion
Lehrstuhl für Informatik 3 - Prof. Dr.-Ing. D. Fey
Vorlesung Einführung digitaler ASIC Entwurf
WS 2010/11 Folie 4
XOR
NAND
MultiplexerNAND
&
&
&
1
&
&
&
1
&
&1
&
&
=1
S
A
B
4. Synthese digitaler Schaltungen
4.1 Technologieabbildung
Beispiel: Überdeckung einer Schaltung mit
Bibliothekselementen
Lehrstuhl für Informatik 3 - Prof. Dr.-Ing. D. Fey
Vorlesung Einführung digitaler ASIC Entwurf
WS 2010/11 Folie 5
4. Synthese digitaler Schaltungen
4.1 Technologieabbildung
Vorgehen bei der Transformation von Knoten des
Booleschen Netzes in NAND-Gatter mit zwei Eingängen
• zunächst alle Gatter mit mehr als zwei Eingängen in
Zusammenschaltungen von Gattern mit zwei Eingängen umwandeln
&
&
&
1
1
1
Lehrstuhl für Informatik 3 - Prof. Dr.-Ing. D. Fey
Vorlesung Einführung digitaler ASIC Entwurf
WS 2010/11 Folie 6
4. Synthese digitaler Schaltungen4.1 Technologieabbildung
Problem: Festlegung der Reihenfolge der Klammerung
• Assoziativgesetz gestattet hier mehrere Möglichkeiten
x1x2x3 (x1x2)x3 bzw. x1(x2 x3) bzw. (x1x3)x2
• optimale Lösung würde Berücksichtigung aller möglichen
Kombinationen erfordern
• Auswahl der Klammerungsreihenfolge erfolgt heuristisch, dabei
Berücksichtigung möglichst geringer Verzögerungen, z.B. ist
(x1x2)(x3x4) (((x1x2)x3)x4) vorzuziehen
2 Stufen 3 Stufen
Lehrstuhl für Informatik 3 - Prof. Dr.-Ing. D. Fey
Vorlesung Einführung digitaler ASIC Entwurf
WS 2010/11 Folie 7
4. Synthese digitaler Schaltungen
4.1 Technologieabbildung
Transformation UND-Gatter in NAND-Gatter
• Ausgang NAND-Gatter einfach invertieren
Transformation ODER-Gatter in NAND-Gatter
• Anwenden von De Morgan
durch Umwandlung entstandene Inverterketten auflösen
& & 1
1 &
1
1
1 1
Lehrstuhl für Informatik 3 - Prof. Dr.-Ing. D. Fey
Vorlesung Einführung digitaler ASIC Entwurf
WS 2010/11 Folie 8
4. Synthese digitaler Schaltungen
4.1 Technologieabbildung
Beispiel: Umwandlung Boolesches Netz in NAND-Struktur
x1
x2
x3
x4 x5 x6
y2 = x2 x3
y1 = x1 x2
f = y1 y2 x4 x5 x6
1
&
1
1
x1
x2
x3
x4
x5
x6
&
1f1
Lehrstuhl für Informatik 3 - Prof. Dr.-Ing. D. Fey
Vorlesung Einführung digitaler ASIC Entwurf
WS 2010/11 Folie 9
4. Synthese digitaler Schaltungen4.1 Technologieabbildung
Beispiel: Umwandlung Boolesches Netz in NAND-Struktur
1
&1
1
x1x2
x3
x4x5
x6
&
1 f11
1
1
&&
&
& & 1
&
1
1
1 1
1&
1
1
1
& 1
1
&
1
1
&
1
1
&
1
1
1&
Lehrstuhl für Informatik 3 - Prof. Dr.-Ing. D. Fey
Vorlesung Einführung digitaler ASIC Entwurf
WS 2010/11 Folie 10
4. Synthese digitaler Schaltungen4.1 Technologieabbildung
Zusammenfassen nachfolgender Inverterketten
&
1
1
1& 1
& 1
1
&
1
1
&1
1
&
1
1
&1
&
&&
1&
&
1
1
Lehrstuhl für Informatik 3 - Prof. Dr.-Ing. D. Fey
Vorlesung Einführung digitaler ASIC Entwurf
WS 2010/11 Folie 11
4. Synthese digitaler Schaltungen
4.1 Technologieabbildung
Exakte Überdeckungsbestimmung
Ziel: Überdeckung der NAND-Struktur mit Bibliothekselementen
Untersuchung aller NAND-Gatter nacheinander inklusive einer
Teilmenge der Vorgänger, inwieweit diese sich mit NAND-
Repräsentation eines Bibliothekselementes deckt
für jede mögliche Überdeckung festhalten
• Kosten
• Eingaben
• Ausgaben
Lehrstuhl für Informatik 3 - Prof. Dr.-Ing. D. Fey
Vorlesung Einführung digitaler ASIC Entwurf
WS 2010/11 Folie 12
4. Synthese digitaler Schaltungen4.1 Technologieabbildung
Beispiel: Kostenmaßstab sei die Flächezu überdeckende NAND-Struktur
Zellbibliothek in NAND-Form
&
1&&
&
1
1&
1
x1
x2
x3
x4
f1
f2
Gatter Symbol NAND-Darstellung Kosten
&
1
1&
&
& 1
&
1inv
nand2
nand3
oai21
&
1
&
&1
1
2
3
3
Lehrstuhl für Informatik 3 - Prof. Dr.-Ing. D. Fey
Vorlesung Einführung digitaler ASIC Entwurf
WS 2010/11 Folie 13
4. Synthese digitaler Schaltungen
4.1 Technologieabbildung
Aufstellung aller möglichen Überdeckungen
KostenGatter Symbol NAND-Darstellung
inv
nand2
nand3
oai21&
1
1&
&
& 1
&
1
&
1
&
&1
1
2
3
3
Gatter KostenÜberdeckung durch Eingaben Ausgabe überdeckt
g1 1inv m1 x1 g1 g1g2 1inv m2 x2 g2 g2g3 2nand2 m3 g1, g2 g3 g3g4 2nand2 m4 x1, x2 g4 g4
g5 2nand2 m5 g3, g4 g5 g53oai21 m6 x1, x2, g4 g5 g1, g2, g3, g5
g6 1inv m7 g4 g6 g6g7 2nand2 m8 g6, x3 g7 g7
3nand3 m9 x1, x2, x3 g7 g4, g6, g7g8 1inv m10 g7 g8 g8g9 2nand2 m11 g8, x4 g9 g9
3nand3 m12 g6, x3, x4 g9 g7, g8, g9
&
1&
&
&
1
1
&
1
x1
x2
x3
x4
f1
f2
g1
g2
g3
g4
g5
g6
g7 g8
g9
Lehrstuhl für Informatik 3 - Prof. Dr.-Ing. D. Fey
Vorlesung Einführung digitaler ASIC Entwurf
WS 2010/11 Folie 14
4. Synthese digitaler Schaltungen
4.1 Technologieabbildung
Nach systematischer Aufstellung aller Überdeckungs-
Möglichkeiten ist die optimale Technologie-Abbildung
aufzufinden
jede mögliche Überdeckung eines Teils der Schaltung wird durch
eine Boolesche Variable mi repräsentiert, die Kosten ki verursacht
• mi = 1 für entsprechende Teilschaltung wird mi verwendet
• mi = 0 mi wird nicht verwendet
für jedes Gatter gj muss es mi geben, welches gj überdeckt
sei üj eine Bedingung, die ausdrückt, ob gj überdeckt wird, d.h. eine
ODER-Verknüpfung aller mi, die gj überdecken
damit alle Gatter überdeckt werden muss gelten
ii
j mü
1 jj
ü
Lehrstuhl für Informatik 3 - Prof. Dr.-Ing. D. Fey
Vorlesung Einführung digitaler ASIC Entwurf
WS 2010/11 Folie 15
4. Synthese digitaler Schaltungen
4.1 Technologieabbildung
Dadurch lässt sich das Problem der optimalen Technolo-
gie-Abbildung mit minimalen Kosten wie folgt formal formulieren:
In der Gleichung * bleibt jedoch noch ein Problem unberücksichtigt
• Ursache: wenn mehrere NAND-Gatter durch ein Bibliothekselement
überdeckt werden, so ist nur noch der Ausgang des letzten überdeckten
NAND-Gatters verfügbar
• Folge: ein Gatterausgang gj eins vor dem letzten NSND-Gatter
positionierten Gatters kann von einem anderen Bibliothekselement nicht
mehr als Eingang verwendet werden
• Beispiel: Überdeckung der Gatter g4 g6 g7 durch NAND3-Gatter
(m9 = 1) Ausgang g4 nicht mehr als Eingang in g5 nutzbar
*1)(...min iij
jj
i
i
i müNdukm
Lehrstuhl für Informatik 3 - Prof. Dr.-Ing. D. Fey
Vorlesung Einführung digitaler ASIC Entwurf
WS 2010/11 Folie 16
4. Synthese digitaler Schaltungen4.1 Technologieabbildung
• Lösung: Formulierung einer weiteren logischen einzuhaltenden
Bedingung, einer sogenannten Verfügbarkeitsbedingung, die
gelten muss, wenn ein entsprechendes Bibliothekselement
verwendet wird
• dabei ist vi(mk) ein Boolescher Ausdruck, der die notwendigen
Bedingungen bei der Eingabe des durch mi repräsentierten
Bibliothekselementes ausdrückt
• Erweiterung der Nebenbedingung der Gleichung *
)()( kiikii mvmmvm
1))(()(...min kiii
iij
i
i
i mvmmNdukm
Lehrstuhl für Informatik 3 - Prof. Dr.-Ing. D. Fey
Vorlesung Einführung digitaler ASIC Entwurf
WS 2010/11 Folie 17
4. Synthese digitaler Schaltungen4.1 Technologieabbildung
• Fortsetzung des Beispiels von vorhin
– für m1 m2 sind Eingaben immer verfügbar, da primäre Eingänge der
Schaltung v1 = v2 = 1
– anders bei m3: benötigt die Ausgaben von g1 und g2; werden nur erzeugt,
wenn m1 = 1 und m2 = 1 gilt: d.h. m3 m1 m2 bzw. (m3 m1) (m3 m2)
• Überdeckungsbedingungen und Verfügbarkeitsbedingungen
ergeben dann folgenden Ausdruck (binäres
Überdeckungsproblem):
(m1 m6) ... ( m11 m12) (m3 m1) ... (m10 m8 m9) ... (m12 m7 ) = 1
Lehrstuhl für Informatik 3 - Prof. Dr.-Ing. D. Fey
Vorlesung Einführung digitaler ASIC Entwurf
WS 2010/11 Folie 18
nand3
inv
nand2
oai21
4. Synthese digitaler Schaltungen4.1 Technologieabbildung
• für diesen Ausdruck ist eine Belegung zu finden, die minimale Kosten verursacht
gegeben für m4 = m6 = m7 = m12 = 1 mi = 0 für i {1,2,3,5,8,9,10,11}
anfallende Kosten: k4 + k6 + k7 + k12 = 9
• Ergebnis: kostenminimale Überdeckung
&
1&
&
&
1
1&
1
x1
x2
x3
x4
f1
f2
1
2
3
4
5
6
7 8
9
Lehrstuhl für Informatik 3 - Prof. Dr.-Ing. D. Fey
Vorlesung Einführung digitaler ASIC Entwurf
WS 2010/11 Folie 19
4. Synthese digitaler Schaltungen
4.1 Technologieabbildung
Da das binäre Überdeckungsproblem
NP-vollständig ist, greift
man zur Lösung der Technologieabbildung auf heuristische
Verfahren zurück
Verfahren:
Schaltungsgraph wird in Bäume partitioniert
für die einzelnen Partitionen wird jeweils getrennt eine minimale
Überdeckung mit Bibliothekselementen gesucht
Problem: Auffinden einer geeigneten Partitionierung
Lehrstuhl für Informatik 3 - Prof. Dr.-Ing. D. Fey
Vorlesung Einführung digitaler ASIC Entwurf
WS 2010/11 Folie 20
4. Synthese digitaler Schaltungen
4.2 Layoutsynthese
4.2 Einführung – Was ist die Layoutsynthese?
4.2 Begriffsbestimmungen
4.2.1 Partitionierung
Optimierungsziele
– Externe Verbindungen
– Bounded-Size-Partitionierung
Partitionierungsalgorithmen
– Kernighan-Lin (KL)-Algorithmus
– Erweiterungen des Kernighan-Lin-Algorithmus
– Fiduccia-Mattheyses (FM)-Algorithmus
– Simulated-Annealing (SA)-Algorithmus
Lehrstuhl für Informatik 3 - Prof. Dr.-Ing. D. Fey
Vorlesung Einführung digitaler ASIC Entwurf
WS 2010/11 Folie 21
4. Synthese digitaler Schaltungen
4.2 Layoutsynthese
Stufen der Layoutsynthese
Verhaltensentwurf
Logischer Entwurf
Layoutsynthese
Layoutverifikation
Chip
Floorplanning
Platzierung
Verdrahtung
Kompaktierung
ENTITY test is
port a: in bit;end ENTITY test;
Partitionierung
Herstellung
Systemspezifikation
Architekturentwurf
Schaltungsentwurf
Verpackung/Test
Lehrstuhl für Informatik 3 - Prof. Dr.-Ing. D. Fey
Vorlesung Einführung digitaler ASIC Entwurf
WS 2010/11 Folie 22
4.2 Layoutsynthese
4.2.1 Partitionierung - Einführung
Die Aufgabe der Partitionierung besteht darin
eine Schaltung in Teilschaltungen, sog. Partitionen oder Blöcke,
aufzuteilen (zu partitionieren),
wobei oft die Verknüpfungen der Blöcke untereinander zu
minimieren sind.
Lehrstuhl für Informatik 3 - Prof. Dr.-Ing. D. Fey
Vorlesung Einführung digitaler ASIC Entwurf
WS 2010/11 Folie 23
4.2 Layoutsynthese
4.2.1 Partitionierung - Einführung
Gesamtschaltung:
Schnittlinie c1:
vier externe Verbindungen
1
2
4
5
3
6
7 8
5
6
48
7 23
1
56
48
7 2
3 1
Schnittlinie c1
Schnittlinie c2
Block A Block B Block A Block B
Schnittlinie c2:
zwei externe Verbindungen
Lehrstuhl für Informatik 3 - Prof. Dr.-Ing. D. Fey
Vorlesung Einführung digitaler ASIC Entwurf
WS 2010/11 Folie 24
4.2 Layoutsynthese
4.2.1 Partitionierung - Begriffsbestimmungen
5 6
4
2
1
33
2
4
5 61
Teilgraph G2: Knoten 1, 2, 6.
Teilgraph G1: Knoten 3, 4, 5.
Geschnittene Kanten bzw.
Schnittmenge (Cutset):
(1,3), (2,3), (5,6),
Block (Partition)
Zellen
Lehrstuhl für Informatik 3 - Prof. Dr.-Ing. D. Fey
Vorlesung Einführung digitaler ASIC Entwurf
WS 2010/11 Folie 25
4.2 Layoutsynthese
4.2.1.1 Partitionierung - Optimierungsziele
Minimierung der Anzahl der externen Verbindungen
und / oder
Gleichmäßige bzw. vorgegebene Flächengröße der Blöcke
(Bounded-Size-Partitionierung)
Wegen Packungsüberlegungen, Gehäuserestriktionen
Häufig Wunsch: Partitionen annähernd gleicher Größe
min)( e
ewZ
i
V
Asi
)(
Vk
sViV
i
1)(
Lehrstuhl für Informatik 3 - Prof. Dr.-Ing. D. Fey
Vorlesung Einführung digitaler ASIC Entwurf
WS 2010/11 Folie 26
4.2 Layoutsynthese
4.2.1.2 Partitionierungsalgorithmen
Partitionierungsalgorithmen
Kernighan-Lin (KL)-Algorithmus
Erweiterungen des Kernighan-Lin-Algorithmus
Fiduccia-Mattheyses (FM)-Algorithmus
Simulated-Annealing (SA)-Algorithmus
Lehrstuhl für Informatik 3 - Prof. Dr.-Ing. D. Fey
Vorlesung Einführung digitaler ASIC Entwurf
WS 2010/11 Folie 27
4.2 Layoutsynthese
4.2.1.2 Partitionierungsalgoritmen – Kernighan-Lin
Gegeben ist ein Graph
mit insgesamt 2n Knoten und
gewichteten Kanten zwischen beliebigen Knoten.
Gesucht ist die Aufteilung des Graphen
in zwei Teilgraphen (Blöcke)
• mit jeweils n Knoten (Zellen) mit minimalen Schnittkosten (Summe der
Gewichte aller geschnittenen Kanten).
2
5
6
3
1
4
7
8
Beispiel: n = 4
Block A Block B
Lehrstuhl für Informatik 3 - Prof. Dr.-Ing. D. Fey
Vorlesung Einführung digitaler ASIC Entwurf
WS 2010/11 Folie 28
4.2 Layoutsynthese
4.2.1.2 Partitionierungsalgoritmen – Kernighan-Lin
Kosten D(v) eines Knotens v
D(v) = vextern - vintern
wobei
vextern die Anzahl der von der Schnittlinie
geschnittenen Kanten des Knotens v und
vintern die Anzahl der nicht von der Schnitt-
linie erfassten Kanten des Knotens sind
Hohe Kosten (positiver D-Wert) geben
damit einen bestimmten Drang an, die
Teilmenge zu wechseln,
während niedrige Kosten (negativer D-Wert) ein gewisses
„Bleiberecht“ verkörpern.
2
5
6
3
1
4
7
8Knoten 3:
D(3) = 3-1=2
Knoten 7:
D(7) = 2-1=1
Lehrstuhl für Informatik 3 - Prof. Dr.-Ing. D. Fey
Vorlesung Einführung digitaler ASIC Entwurf
WS 2010/11 Folie 29
4.2 Layoutsynthese
4.2.1.2 Partitionierungsalgoritmen – Kernighan-Lin
Gewinnwert zweier Knoten a und b
g = D(a) + D(b) – 2 × c(a,b),
wobei
D(a), D(b) die Kosten der Knoten a, b
c(a,b) = 1, wenn zwischen a und b eine Kante existiert,
andernfalls gilt c(a,b) = 0.
g gibt damit an, wie sinnvoll es hinsichtlich der Schnittkosten des
Graphen ist, die beiden betrachteten Knoten auszutauschen.
Je größer g ist, umso mehr wird die Gesamtanzahl der
geschnittenen Kanten verringert.
2
5
6
3
1
4
7
8
Lehrstuhl für Informatik 3 - Prof. Dr.-Ing. D. Fey
Vorlesung Einführung digitaler ASIC Entwurf
WS 2010/11 Folie 30
4.2 Layoutsynthese
4.2.1.2 Partitionierungsalgoritmen – Kernighan-Lin
Beispiel:
=> Der Austausch der Knoten 3 und 7
würde die Schnittkosten um 1 verringern
2
5
6
3
1
4
7
8Knoten 3:
D(3) = 3-1=2
Knoten 7:
D(7) = 2-1=1
g (3,7) = D(3) + D(7) - 2* c(a,b) = 2 + 1 – 2 = 1
2
5
6
3
1
4
7
8
Lehrstuhl für Informatik 3 - Prof. Dr.-Ing. D. Fey
Vorlesung Einführung digitaler ASIC Entwurf
WS 2010/11 Folie 31
4.2 Layoutsynthese
4.2.1.2 Partitionierungsalgoritmen – Kernighan-Lin
Weiteres Knotenpaar auswählen
Der Austausch der Knoten 3 und 5 würde
die Schnittkosten um 3 verringern.
2
5
6
3
1
4
7
8Knoten 3:
D(3) = 3-1=2
Knoten 5:
D(5) = 2-1=1
g (3,5) = D(3) + D(5) - 2* c(a,b) = 2 + 1 – 0 = 3
2
5
6
3
1
4
7
8
Lehrstuhl für Informatik 3 - Prof. Dr.-Ing. D. Fey
Vorlesung Einführung digitaler ASIC Entwurf
WS 2010/11 Folie 32
4.2 Layoutsynthese
4.2.1.2 Partitionierungsalgoritmen – Kernighan-Lin
Gewinnwert zweier Knoten a und b
Das Ziel besteht darin,
die zwei Knoten a und b zu finden, deren Gewinnwert g am
größten von allen möglichen Knotenkombinationen ist, und diese dann
auszutauschen.
Lehrstuhl für Informatik 3 - Prof. Dr.-Ing. D. Fey
Vorlesung Einführung digitaler ASIC Entwurf
WS 2010/11 Folie 33
4.2 Layoutsynthese
4.2.1.2 Partitionierungsalgoritmen – Kernighan-Lin
Maximaler positiver Gewinn Gm eines Passes
Der maximale positive Gewinn Gm gibt die Folge von m
Vertauschungen innerhalb eines Passes an, die zu einer
maximalen Schnittkostenminimierung des Graphen führt.
Konkret ergibt sich Gm aus den aufaddierten Gewinnwerten
g von m hintereinander erfolgten Vertauschungen
innerhalb eines Passes.
Lehrstuhl für Informatik 3 - Prof. Dr.-Ing. D. Fey
Vorlesung Einführung digitaler ASIC Entwurf
WS 2010/11 Folie 34
4.2 Layoutsynthese
4.2.1.2 Partitionierungsalgoritmen – Kernighan-Lin
Kernighan-Lin-Algorithmus
Schritt 0:
V = Menge der 2n Knoten
{A, B} sei eine willkürliche Anfangspartitionierung
Schritt 1:
i = 1
Berechnung von D(v) für alle Knoten vV
Schritt 2:
Auswahl von ai und bi mit maximalem Gewinnwert
gi = D(ai) + D(bi) – 2 * c(aibi)
Vertauschen und Fixieren von ai und bi
Lehrstuhl für Informatik 3 - Prof. Dr.-Ing. D. Fey
Vorlesung Einführung digitaler ASIC Entwurf
WS 2010/11 Folie 35
4.2 Layoutsynthese
4.2.1.2 Partitionierungsalgoritmen – Kernighan-Lin
Schritt 3:
Wenn alle Knoten fixiert sind, weiter mit Schritt 4, andernfalls
Neuberechnung der D-Werte für alle Knoten, welche nicht fixiert und
mit ai und bi verbunden sind
i = i + 1
Weiter mit Schritt 2
Schritt 4:
Bestimmung der Vertauschungssequenz 1 bis m (1 m i), so dass
maximiert wird
Wenn Gm > 0, weiter mit Schritt 5, andernfalls ENDE
Schritt 5:
Durchführen aller m Vertauschungen, Beseitigen aller
Knotenfixierungen
Weiter mit Schritt 1
m
i im gG1Δ
Lehrstuhl für Informatik 3 - Prof. Dr.-Ing. D. Fey
Vorlesung Einführung digitaler ASIC Entwurf
WS 2010/11 Folie 36
4.2 Layoutsynthese
4.2.1.2 Partitionierungsalgoritmen – Kernighan-Lin
Beispiel KL-Algorithmus:
2
5
6
3
1
4
7
8
Schnittkosten: 9
Nicht fixiert:
1,2,3,4,5,6,7,8
D(1) = 1 D(5) = 1
D(2) = 1 D(6) = 2
D(3) = 2 D(7) = 1
D(4) = 1 D(8) = 1
Kosten D(v) jedes Knotens:
Auswahl der Knoten für
maximalen Gewinnwert
Lehrstuhl für Informatik 3 - Prof. Dr.-Ing. D. Fey
Vorlesung Einführung digitaler ASIC Entwurf
WS 2010/11 Folie 37
4.2 Layoutsynthese
4.2.1.2 Partitionierungsalgoritmen – Kernighan-Lin
Positiver Gewinn des Passes
2
5
6
3
1
4
7
8
Schnittkosten: 9
Nicht fixiert:
1,2,3,4,5,6,7,8
D(1) = 1 D(5) = 1
D(2) = 1 D(6) = 2
D(3) = 2 D(7) = 1
D(4) = 1 D(8) = 1
g1 = 2+1-0 = 3
Austausch (3,5)
G1 = g1 =3
Auswahl der Knoten für
maximalen Gewinnwert
Kosten D(v) jedes Knotens:
Gewinnwert bei Knotentausch
Lehrstuhl für Informatik 3 - Prof. Dr.-Ing. D. Fey
Vorlesung Einführung digitaler ASIC Entwurf
WS 2010/11 Folie 38
4.2 Layoutsynthese
4.2.1.2 Partitionierungsalgoritmen – Kernighan-Lin
2
5
6
3
1
4
7
8
Schnittkosten: 9
Nicht fixiert:
1,2,3,4,5,6,7,8
2
5
6
3
1
4
7
8
D(1) = 1 D(5) = 1
D(2) = 1 D(6) = 2
D(3) = 2 D(7) = 1
D(4) = 1 D(8) = 1
g1 = 2+1-0 = 3
Austausch (3,5)
G1 = g1 =3
Auswahl der Knoten für
maximalen Gewinnwert
Positiver Gewinn des Passes
Gewinnwert bei Knotentausch
Lehrstuhl für Informatik 3 - Prof. Dr.-Ing. D. Fey
Vorlesung Einführung digitaler ASIC Entwurf
WS 2010/11 Folie 39
4.2 Layoutsynthese
4.2.1.2 Partitionierungsalgoritmen – Kernighan-Lin
2
5
6
3
1
4
7
8
Schnittkosten: 9
Nicht fixiert:
1,2,3,4,5,6,7,8
2
5
6
3
1
4
7
8
Schnittkosten: 6
Nicht fixiert:
1,2,4,6,7,8
D(1) = 1 D(5) = 1
D(2) = 1 D(6) = 2
D(3) = 2 D(7) = 1
D(4) = 1 D(8) = 1
g1 = 2+1-0 = 3
Austausch (3,5)
G1 = g1 =3
Lehrstuhl für Informatik 3 - Prof. Dr.-Ing. D. Fey
Vorlesung Einführung digitaler ASIC Entwurf
WS 2010/11 Folie 40
4.2 Layoutsynthese
4.2.1.2 Partitionierungsalgoritmen – Kernighan-Lin
2
5
6
3
1
4
7
8
Schnittkosten: 9
Nicht fixiert:
1,2,3,4,5,6,7,8
2
5
6
3
1
4
7
8
Schnittkosten: 6
Nicht fixiert:
1,2,4,6,7,8
2
5
6
3
1
4
7
8
D(1) = 1 D(5) = 1
D(2) = 1 D(6) = 2
D(3) = 2 D(7) = 1
D(4) = 1 D(8) = 1
g1 = 2+1-0 = 3
Austausch (3,5)
G1 = g1 =3
D(1) = -1 D(6) = 2
D(2) = -1 D(7)=-1
D(4) = 3 D(8)=-1
g2 = 3+2-0 = 5
Austausch (4,6)
G2 = G1+g2 =8
Auswahl der Knoten für
maximalen Gewinnwert
Positiver Gewinn des Passes
Gewinnwert bei Knotentausch
Lehrstuhl für Informatik 3 - Prof. Dr.-Ing. D. Fey
Vorlesung Einführung digitaler ASIC Entwurf
WS 2010/11 Folie 41
4.2.4 Partitionierungsalgorithmen – Kernighan-Lin (KL)-
Algorithmus
Positiver Gewinn
des Passes
2
5
6
3
1
4
7
8
Schnittkosten: 9
Nicht fixiert:
1,2,3,4,5,6,7,8
2
5
6
3
1
4
7
8
Schnittkosten: 6
Nicht fixiert:
1,2,4,6,7,8
2
5
6
3
1
4
7
8
Schnittkosten: 1
Nicht fixiert:
1,2,7,8
2
5
6
3
1
4
7
8
Schnittkosten: 7
Nicht fixiert:
2,8
D(1) = 1 D(5) = 1
D(2) = 1 D(6) = 2
D(3) = 2 D(7) = 1
D(4) = 1 D(8) = 1
g1 = 2+1-0 = 3
Austausch (3,5)
G1 = g1 =3
D(1) = -1 D(6) = 2
D(2) = -1 D(7)=-1
D(4) = 3 D(8)=-1
g2 = 3+2-0 = 5
Austausch (4,6)
G2 = G1+g2 =8
D(1) = -3 D(7)=-3
D(2) = -3 D(8)=-3
g3 = -3-3-0 = -6
Austausch (1,7)
G3= G2 +g3 = 2
Auswahl der Knoten für
maximalen Gewinnwert
Gewinnwert bei
Knotentausch
Lehrstuhl für Informatik 3 - Prof. Dr.-Ing. D. Fey
Vorlesung Einführung digitaler ASIC Entwurf
WS 2010/11 Folie 42
4.2 Layoutsynthese
4.2.1.2 Partitionierungsalgoritmen – Kernighan-Lin
Beispiel:
2
5
6
3
1
4
7
8
Schnittkosten: 9
Nicht fixiert:
1,2,3,4,5,6,7,8
2
5
6
3
1
4
7
8
Schnittkosten: 9
Nicht fixiert:
–
2
5
6
3
1
4
7
8
Schnittkosten: 6
Nicht fixiert:
1,2,4,6,7,8
2
5
6
3
1
4
7
8
Schnittkosten: 1
Nicht fixiert:
1,2,7,8
2
5
6
3
1
4
7
8
Schnittkosten: 7
Nicht fixiert:
2,8
D(1) = 1 D(5) = 1
D(2) = 1 D(6) = 2
D(3) = 2 D(7) = 1
D(4) = 1 D(8) = 1
g1 = 2+1-0 = 3
Austausch (3,5)
G1 = g1 =3
D(1) = -1 D(6) = 2
D(2) = -1 D(7)=-1
D(4) = 3 D(8)=-1
g2 = 3+2-0 = 5
Austausch (4,6)
G2 = G1+g2 =8
D(1) = -3 D(7)=-3
D(2) = -3 D(8)=-3
g3 = -3-3-0 = -6
Austausch (1,7)
G3= G2 +g3 = 2
D(2) = -1 D(8)=-1
g4 = -1-1-0 = -2
Austausch (2,8)
G4 = G3 +g4 = 0
Lehrstuhl für Informatik 3 - Prof. Dr.-Ing. D. Fey
Vorlesung Einführung digitaler ASIC Entwurf
WS 2010/11 Folie 43
4.2 Layoutsynthese
4.2.1.2 Partitionierungsalgoritmen – Kernighan-Lin
Maximaler positiver Gewinn Gm = 8 bei m = 2.
D(1) = 1 D(5) = 1
D(2) = 1 D(6) = 2
D(3) = 2 D(7) = 1
D(4) = 1 D(8) = 1
g1 = 2+1-0 = 3
Austausch (3,5)
G1 = g1 =3
D(1) = -1 D(6) = 2
D(2) = -1 D(7)=-1
D(4) = 3 D(8)=-1
g2 = 3+2-0 = 5
Austausch (4,6)
G2 = G1+g2 =8
D(1) = -3 D(7)=-3
D(2) = -3 D(8)=-3
g3 = -3-3-0 = -6
Austausch (1,7)
G3= G2 +g3 = 2
D(2) = -1 D(8)=-1
g4 = -1-1-0 = -2
Austausch (2,8)
G4 = G3 +g4 = 0
Lehrstuhl für Informatik 3 - Prof. Dr.-Ing. D. Fey
Vorlesung Einführung digitaler ASIC Entwurf
WS 2010/11 Folie 44
4.2 Layoutsynthese
4.2.1.2 Partitionierungsalgoritmen – Kernighan-Lin
Maximaler positiver Gewinn Gm = 8 bei m = 2.
D(1) = 1 D(5) = 1
D(2) = 1 D(6) = 2
D(3) = 2 D(7) = 1
D(4) = 1 D(8) = 1
g1 = 2+1-0 = 3
Austausch (3,5)
G1 = g1 =3
D(1) = -1 D(6) = 2
D(2) = -1 D(7)=-1
D(4) = 3 D(8)=-1
g2 = 3+2-0 = 5
Austausch (4,6)
G2 = G1+g2 =8
D(1) = -3 D(7)=-3
D(2) = -3 D(8)=-3
g3 = -3-3-0 = -6
Austausch (1,7)
G3= G2 +g3 = 2
D(2) = -1 D(8)=-1
g4 = -1-1-0 = -2
Austausch (2,8)
G4 = G3 +g4 = 0
Da Gm > 0, werden die m Vertauschungen
(3,5) und (4,6) durchgeführt.2
5
6
3
1
4
7
8
Lehrstuhl für Informatik 3 - Prof. Dr.-Ing. D. Fey
Vorlesung Einführung digitaler ASIC Entwurf
WS 2010/11 Folie 45
4.2 Layoutsynthese
4.2.1.2 Partitionierungsalgoritmen – Kernighan-Lin
Maximaler positiver Gewinn Gm = 8 bei m = 2.
D(1) = 1 D(5) = 1
D(2) = 1 D(6) = 2
D(3) = 2 D(7) = 1
D(4) = 1 D(8) = 1
g1 = 2+1-0 = 3
Austausch (3,5)
G1 = g1 =3
D(1) = -1 D(6) = 2
D(2) = -1 D(7)=-1
D(4) = 3 D(8)=-1
g2 = 3+2-0 = 5
Austausch (4,6)
G2 = G1+g2 =8
D(1) = -3 D(7)=-3
D(2) = -3 D(8)=-3
g3 = -3-3-0 = -6
Austausch (1,7)
G3= G2 +g3 = 2
D(2) = -1 D(8)=-1
g4 = -1-1-0 = -2
Austausch (2,8)
G4 = G3 +g4 = 0
Da Gm > 0, weiterer Pass notwendig, bis
Gm 0 während aller Vertauschungen.
Da Gm > 0, werden die m Vertauschungen
(3,5) und (4,6) durchgeführt.2
5
6
3
1
4
7
8
Lehrstuhl für Informatik 3 - Prof. Dr.-Ing. D. Fey
Vorlesung Einführung digitaler ASIC Entwurf
WS 2010/11 Folie 46
4.2 Layoutsynthese
4.2.1.2 Partitionierungsalgoritmen – Fiduccia-Mattheyses
Gegeben ist ein Graph
mit Knoten (Zellen) und
gewichteten Kanten zwischen beliebigen Knoten.
Gesucht ist die Aufteilung des Graphen in zwei Teilgraphen
(Blöcke) A und B derart,
dass die Anzahl der Netze zwischen beiden Teilgraphen minimiert
und
gleichzeitig ein vorgegebenes Größenverhältnis der durch die
Teilgraphen repräsentierten Blöcke eingehalten wird.
Lehrstuhl für Informatik 3 - Prof. Dr.-Ing. D. Fey
Vorlesung Einführung digitaler ASIC Entwurf
WS 2010/11 Folie 47
4.2 Layoutsynthese
4.2.1.2 Partitionierungsalgoritmen – Fiduccia-Mattheyses
Gewinnwert einer Zelle g(c)
g(c) = FS(c) – TE(c)
wobei
FS(c) die Anzahl der mit der Zelle c verbundenen Netze
darstellt, die nicht mit anderen Zellen im gegenwärtigen
Block der Zelle c verbunden sind (durch die Schnittlinie
kommend nur die Zelle c verbinden) und
TE(c) die Anzahl der mit der Zelle c verbundenen
Netze ist, die nicht die Schnittlinie kreuzen
Je höher der Gewinnwert g(c) einer Zelle c
ist, umso sinnvoller ist es hinsichtlich einer
Minimierung der Schnittmenge, diese Zelle in
den anderen Block zu verschieben.
Zelle 2:
FS(2) = 0 TE(2) = 1 g(2) = -1
Netz b nicht, Netz a
da nicht nur
mit 2, sondern
auch mit 1
verbunden
1
3
4
2
5
ab
cd
e
Zelle 4:
FS(4) = 1 TE(4) = 1 g(4) = 0
Netz c Netz e
Lehrstuhl für Informatik 3 - Prof. Dr.-Ing. D. Fey
Vorlesung Einführung digitaler ASIC Entwurf
WS 2010/11 Folie 48
4.2 Layoutsynthese
4.2.1.2 Partitionierungsalgoritmen – Fiduccia-Mattheyses
Gewinnwert g(c) aller Zellen
Ergebnis der Zellverschiebung
bei Auswahl Zelle 1
1
3
4
2
5
ab
cd
e
1
3
4
2
5
ab
cd
e
Zelle 1: FS(1) = 2 TE(1) = 1 g(1) = 1
Zelle 2: FS(2) = 0 TE(2) = 1 g(2) = -1
Zelle 3: FS(3) = 1 TE(3) = 1 g(3) = 0
Zelle 4: FS(4) = 1 TE(4) = 1 g(4) = 0
Zelle 5: FS(5) = 1 TE(5) = 0 g(5) = 1
Lehrstuhl für Informatik 3 - Prof. Dr.-Ing. D. Fey
Vorlesung Einführung digitaler ASIC Entwurf
WS 2010/11 Folie 49
4.2 Layoutsynthese
4.2.1.2 Partitionierungsalgoritmen – Fiduccia-Mattheyses
Maximaler positiver Gewinn Gm eines Passes
Der maximale positive Gewinn Gm gibt die Folge von m
Verschiebungen innerhalb eines Passes an, die zu einer
maximalen Schnittkostenminimierung führt.
Konkret ergibt sich Gm aus den aufaddierten Gewinnwerten
g von m hintereinander erfolgten Verschiebungen
innerhalb eines Passes.
Pass: Folge von Verschiebungen angewandt auf beliebige
Anfangsverteilung bis jeder Knoten aus G genau einmal für
eine mögliche Verschiebung ausgewählt wurde.
Lehrstuhl für Informatik 3 - Prof. Dr.-Ing. D. Fey
Vorlesung Einführung digitaler ASIC Entwurf
WS 2010/11 Folie 50
4.2 Layoutsynthese
4.2.1.2 Partitionierungsalgoritmen – Fiduccia-Mattheyses
Verhältnisfaktor und Gleichgewichtskriterium
Da beim FM-Algorithmus die Zellen einzeln verschoben
werden, ist eine Berücksichtigung der Partitionierungs-
größen bei jeder Zellenverschiebung notwendig.
Ansonsten könnte eine Partition völlig verschwinden bzw.
gegenüber der anderen Partition zu klein werden.
Mittels eines sog. Verhältnisfaktors r wird ein angestrebtes
Größenverhältnis der Flächen A und B ausgedrückt:
BA
Ar
Lehrstuhl für Informatik 3 - Prof. Dr.-Ing. D. Fey
Vorlesung Einführung digitaler ASIC Entwurf
WS 2010/11 Folie 51
4.2 Layoutsynthese
4.2.1.2 Partitionierungsalgoritmen – Fiduccia-Mattheyses
Verhältnisfaktor und Gleichgewichtskriterium
Mit einem vom Verhältnisfaktor r ableitbaren
Gleichgewichtskriterium lässt sich jede Zellenverschiebung
auf Einhaltung des durch r vorgegebenen
Größenverhältnisses beider Teilflächen verifizieren.
maxmax sVrAsVr
Lehrstuhl für Informatik 3 - Prof. Dr.-Ing. D. Fey
Vorlesung Einführung digitaler ASIC Entwurf
WS 2010/11 Folie 52
4.2 Layoutsynthese
4.2.1.2 Partitionierungsalgoritmen – Fiduccia-Mattheyses
Basiszelle
Die zur Verschiebung ausgewählte Zelle wird als Basiszelle
bezeichnet.
Diese besitzt den maximalen Zellengewinnwert g(c) unter
allen verschiebbaren Zellen und verletzt durch ihre
Verschiebung nicht das Gleichgewichtskriterium.
Zelle 1: FS(1) = 2 TE(1) = 1 g(1) = 1
Zelle 2: FS(2) = 0 TE(2) = 1 g(2) = -1
Zelle 3: FS(3) = 1 TE(3) = 1 g(3) = 0
Zelle 4: FS(4) = 1 TE(4) = 1 g(4) = 0
Zelle 5: FS(5) = 1 TE(5) = 0 g(5) = 1
Basiszelle
Zelle 1 erfüllt
Gleichgewichtskriterium besser als
Zelle 5
(s. später Folie 57)
Lehrstuhl für Informatik 3 - Prof. Dr.-Ing. D. Fey
Vorlesung Einführung digitaler ASIC Entwurf
WS 2010/11 Folie 53
4.2 Layoutsynthese
4.2.1.2 Partitionierungsalgoritmen – Fiduccia-Mattheyses
Fiduccia-Mattheyses-Algorithmus
Schritt 0: Errechnen des Gleichgewichtskriteriums
Schritt 1: Ermitteln des Gewinns g1 jeder Zelle
Schritt 2: i = 1
• Auswahl der Basiszelle c1 mit maximalem Gewinnwert g1,
Verschiebung dieser Zelle
Schritt 3:
• Fixierung der Basiszelle ci
• Gewinnwert-Aktualisierung der Zellen, die durch kritische Netze mit der
Basiszelle ci verbunden sind
– Kritische Netze: Netze, deren Schnittzustand sich durch die Verschiebung
verändert
Lehrstuhl für Informatik 3 - Prof. Dr.-Ing. D. Fey
Vorlesung Einführung digitaler ASIC Entwurf
WS 2010/11 Folie 54
4.2 Layoutsynthese
4.2.1.2 Partitionierungsalgoritmen – Fiduccia-Mattheyses
Schritt 4:
• Wenn alle Zellen fixiert sind, weiter mit Schritt 5, andernfalls
• Auswahl der nächsten Basiszelle ci mit maximalem Gewinnwert gi und
Verschiebung dieser Zelle
• i = i + 1, weiter mit Schritt 3
Schritt 5:
• Ermitteln der besten Verschiebungsfolge c1, c2, .., cm (1 m i), so
dass maximiert wird
• Wenn Gm > 0, weiter mit Schritt 6, andernfalls ENDE
Schritt 6:
• Durchführen aller m Vertauschungen, Beseitigen aller Zellenfixierungen
• Neuer Pass, dazu weiter mit Schritt 1
m
i im gG1Δ
Lehrstuhl für Informatik 3 - Prof. Dr.-Ing. D. Fey
Vorlesung Einführung digitaler ASIC Entwurf
WS 2010/11 Folie 55
4.2 Layoutsynthese
4.2.1.2 Partitionierungsalgoritmen – Fiduccia-Mattheyses
Beispiel:
Schritt 0: Errechnen des Gleichgewichtskriteriums
0,375 * 16 – 5 = 1 | A | 11 = 0,375 * 16 + 5
1
3
4
2
5
A B
ab
cd
e
Gegeben:
Verhältnisfaktor r = 0,375
s(Zelle_1) = 2
s(Zelle_2) = 4
s(Zelle_3) = 1
s(Zelle_4) = 4
s(Zelle_5) = 5.
maxmax sVrAsVr
Lehrstuhl für Informatik 3 - Prof. Dr.-Ing. D. Fey
Vorlesung Einführung digitaler ASIC Entwurf
WS 2010/11 Folie 56
4.2 Layoutsynthese
4.2.1.2 Partitionierungsalgoritmen – Fiduccia-Mattheyses
Schritt 1: Ermitteln der Gewinnwerte jeder Zelle
Zelle 1:
• Zwei Netze (c, d) sind nur mit Zelle 1 in deren Block verbunden und passieren
die Schnittline, d.h. FS(Zelle_1) = 2
• Ein Netz (a) ist mit Zelle 1 verbunden und wird nicht geschnitten, d.h.
TE(Zelle_1) = 1
• g(Zelle_1) = 2 - 1 =1, d.h.
Anzahl der geschnittenen Netze reduziert sich um eins (von drei auf zwei), sollte
Zelle 1 von A nach B verschoben werden
1
3
4
2
5
A B
ab
cd
e
Lehrstuhl für Informatik 3 - Prof. Dr.-Ing. D. Fey
Vorlesung Einführung digitaler ASIC Entwurf
WS 2010/11 Folie 57
4.2 Layoutsynthese
4.2.1.2 Partitionierungsalgoritmen – Fiduccia-Mattheyses
Analoge Berechnung der anderen Zellen:
• Zelle 1: FS(Zelle_1) = 2 TE(Zelle_1) = 1 g(Zelle_1) = 1
• Zelle 2: FS(Zelle_2) = 0 TE(Zelle_2) = 1 g(Zelle_2) = -1
• Zelle 3: FS(Zelle_3) = 1 TE(Zelle_3) = 1 g(Zelle_3) = 0
• Zelle 4: FS(Zelle_4) = 1 TE(Zelle_4) = 1 g(Zelle_4) = 0
• Zelle 5: FS(Zelle_5) = 1 TE(Zelle_5) = 0 g(Zelle_5) = 1
Schritt 2: Auswahl der Basiszelle und Verschiebung
Mögliche Basiszellen: Zelle 1 und Zelle 5
Gleichgewichtskriterium nach Verschiebung von Zelle 1:
A = s(2) = 4
Gleichgewichtskriterium nach Verschiebung von Zelle 5:
A = s(1) + s(2) + s(5) = 11 .
Beide Verschiebungen verletzen somit nicht das Gleichgewichtskriterium
1 A 11
Zelle 1 wird erfüllt Gleichgewichtskriterium besser und wird daher
als Basiszelle ausgewählt und verschoben.
Lehrstuhl für Informatik 3 - Prof. Dr.-Ing. D. Fey
Vorlesung Einführung digitaler ASIC Entwurf
WS 2010/11 Folie 58
4.2 Layoutsynthese
4.2.1.2 Partitionierungsalgoritmen – Fiduccia-Mattheyses
Schritt 3: Zellenfixierung und Gewinnwert-Aktualisierung
Zelle 1 fixieren, neue Anordnung:
Gewinnwert aktualisieren von allen verschiebbaren Zellen, die mit
Zelle 1 verbunden sind:
• Zelle 2: FS(Zelle_2) = 2 TE(Zelle_2) = 0 g(Zelle_2) = 2
• Zelle 3: FS(Zelle_3) = 0 TE(Zelle_3) = 1 g(Zelle_3) = -1
• Zelle 4: FS(Zelle_4) = 0 TE(Zelle_4) = 2 g(Zelle_4) = -2
• Zelle 5: FS(Zelle_5) = 0 TE(Zelle_5) = 1 g(Zelle_5) = -1
Nach Iteration i = 1: zwei Partitionen A1 = { 2 }, B1 = { 1,3,4,5 },
davon fixiert { 1 }
1
3
4
2
5
A B
ab
cd
e
Lehrstuhl für Informatik 3 - Prof. Dr.-Ing. D. Fey
Vorlesung Einführung digitaler ASIC Entwurf
WS 2010/11 Folie 59
4.2 Layoutsynthese
4.2.1.2 Partitionierungsalgoritmen – Fiduccia-Mattheyses
Schritt 4: Auswahl und Verschiebung einer Basiszelle; Zellenfixierung;
Gewinnwert-Aktualisierung
Iteration i = 2
• Gemäß obigem Schritt 3: Zelle 2 mit maximalem Gewinnwert g2 = 2 A = 0,
d.h. Gleichgewichtskriterium nicht erfüllt
• Zelle 3 mit nächstem maximalen Gewinnwert g2 = -1
A = 5, d.h. Gleichgewichtskriterium erfüllt
• Zelle 5 mit nächstem maximalen Gewinnwert g2= -1
A = 9, d.h. Gleichgewichtskriterium erfüllt
• Zelle 3 wird verschoben
Mengenverteilung A2 = { 2,3 }, B2 = { 1,4,5 }, davon fixiert { 1,3 }
1
3
4
2
5
A B
a b
cd
e Zelle 2: FS(2) = 1 TE(2) = 0 g(2) = 1
Zelle 4: FS(4) = 1 TE(4) = 1 g(4) = 0
Zelle 5: FS(5) = 0 TE(5) = 1 g(5) = -1
Lehrstuhl für Informatik 3 - Prof. Dr.-Ing. D. Fey
Vorlesung Einführung digitaler ASIC Entwurf
WS 2010/11 Folie 60
4.2 Layoutsynthese
4.2.1.2 Partitionierungsalgoritmen – Fiduccia-Mattheyses
Iteration i = 3
• g3(Zelle_2) = 1 g3(Zelle_4) = 0 g3(Zelle_5) = -1
• Zelle 2 mit maximalem Gewinnwert g3 = 1
A = 1, d.h. Gleichgewichtskriterium erfüllt
• Zelle 2 wird verschoben, Mengenverteilung A3 = { 3 }, B3 = { 1,2,4,5 }, davon
fixiert { 1,2,3 }
Iteration i = 4
• g4(Zelle_4) = 0 g4(Zelle_5) = -1, wie vorher, da verschobene Zelle 2 nicht mit
Zelle 4 und Zelle 5 verbunden
• Zelle 4 mit maximalem Gewinnwert g4 = 0,
A = 5, d.h. Gleichgewichtskriterium erfüllt
• Mengenverteilung A4 = { 3,4 }, B4 = { 1,2,5 }, davon fixiert {1,2,3,4}
Iteration i = 5
• g5(Zelle_5) = -1, wie vorher
• Zelle 5 mit maximalem Gewinnwert g5 = -1,
A = 10, d.h. Gleichgewichtskriterium erfüllt
• Mengenverteilung A5 = { 3,4,5 }, B5 = { 1,2 }, alle Zellen fixiert
• Pass 1 beendet; weiter mit Schritt 5
Lehrstuhl für Informatik 3 - Prof. Dr.-Ing. D. Fey
Vorlesung Einführung digitaler ASIC Entwurf
WS 2010/11 Folie 61
4.2 Layoutsynthese
4.2.1.2 Partitionierungsalgoritmen – Fiduccia-Mattheyses
Schritt 5: Ermittlung der besten Verschiebungsfolge 1 … m
G1 = g1 = 1
G2 = g1 + g2 = 0
G3 = g1 + g2 + g3 = 1
G4 = g1 + g2 + g3 + g4 = 1
G5 = g1 + g2 + g3 + g4 + g5 = 0.
Maximaler positiver Gewinn in Iterationen 1, 3 und 4.
Aufgrund des ausgewogeneren Gleichgewichtskriteriums
(A = 5) wird Iteration 4 gewählt, d.h. m = 4.
Lehrstuhl für Informatik 3 - Prof. Dr.-Ing. D. Fey
Vorlesung Einführung digitaler ASIC Entwurf
WS 2010/11 Folie 62
4.2 Layoutsynthese
4.2.1.2 Partitionierungsalgoritmen – Fiduccia-Mattheyses
Schritt 6: Verschiebung der ersten m Zellen tatsächlich
durchführen
Da m = 4, werden nur die ersten vier ausgewählten Zellen (Zellen 1,
3, 2, 4) verschoben.
Ergebnis von Pass 1:
Mengenverteilung A = {3,4}, B = {1,2,5}, Schnittkosten von 3 auf 2
reduziert.
B
1
3
4
2
5
Aa
b
cd
e
1
3
4
2
5
A B
ab
cd
e
Lehrstuhl für Informatik 3 - Prof. Dr.-Ing. D. Fey
Vorlesung Einführung digitaler ASIC Entwurf
WS 2010/11 Folie 63
4.2 Layoutsynthese
4.2.1.2 Partitionierungsalgoritmen – Simulated Annealing
KL-Algorithmen finden lokales Optimum abhängig von
Ausgangssituation
Ziel von Simulated Annealing
Globales Optimum zu finden
Durch „Heraushüpfen“ aus lokalem Optimum durch zeitweises
Zulassen verschlechternder Bedingungen
Lösungszustände
KostenAnfangslösung
Lokales
Optimum Globales
Optimum
Lehrstuhl für Informatik 3 - Prof. Dr.-Ing. D. Fey
Vorlesung Einführung digitaler ASIC Entwurf
WS 2010/11 Folie 64
4.2 Layoutsynthese
4.2.1.2 Partitionierungsalgoritmen – Simulated Annealing
Simulated-Annealing-Algorithmus
begin
T = T0 , i = 0 /* Initialisierung */
cur_part = init_part /* Anfangspartitionierung */
cur_cost = COST(cur_part) /* Anfangsqualität */
repeat
repeat
i = i + 1
ai = SELECT(A), bi = SELECT(B)
trial_part = EXCHANGE(ai, bi, cur_part) /* Tauschversuch */
trial_cost = COST(trial_part)
cost = trial_cost – cur_cost
if( cost < 0 ) then /* wenn Verbesserung */
cur_cost = trial_cost /* Tauschdurchführung */
cur_part = MOVE(ai, bi)
else /* ansonsten */
r = RANDOM(0,1) /* Zufallszahl */
if( r < Te
costΔ
) then /* bedingter */
cur_cost = trial_cost /* Tausch */
cur_part = MOVE(ai, bi)
until( Abbruchkriterium, z.B. Gleichgewicht bei T, erreicht )
T = * T /* 0 < < 1 */ /* Temperatur-Reduktion */
until( T < Tmin )
end
Lehrstuhl für Informatik 3 - Prof. Dr.-Ing. D. Fey
Vorlesung Einführung digitaler ASIC Entwurf
WS 2010/11 Folie 65
4.2 Layoutsynthese
4.2.1.2 Partitionierungsalgoritmen – Simulated Annealing
Gegeben: Schaltung mit sechs Zellen und sechs Netzen,
wobei alle Zellen identische Größe besitzen, sowie
Netzliste mit Netzgewichten
Gesucht: Aufteilung in zwei Blöcke A und B mit jeweils drei
Zellen und minimalen Kosten
w6 = 4N6 = (2, 3, 6)
w5 = 1N5 = (1, 5)
w4 = 3N4 = (4, 5)
w3 = 2N3 = (2, 3, 6)
w2 = 2N2 = (1, 2, 5, 6)
w1 = 4N1 = (1, 4, 5)
GewichteNetze
1 4
2 5
3 6
N5
N1
N2
N3
N6
N4
Lehrstuhl für Informatik 3 - Prof. Dr.-Ing. D. Fey
Vorlesung Einführung digitaler ASIC Entwurf
WS 2010/11 Folie 66
4.2 Layoutsynthese
4.2.1.2 Partitionierungsalgoritmen – Simulated Annealing
Parameter des SA-Algorithmus
Anfangstemperatur: T0 = 10, Abbruch bei T < 3,5
Anfangspartitionierung: init_part A{1,2, 3}, B{4, 5, 6}
Anzahl der Austauschversuche pro Temperaturschritt T: 4
Temperaturabnahme: = 0,7
Austauschfunktion EXCHANGE(): Paarweiser Tausch der Zellen
zwischen A und B
Minimierung der Zielfunktion COST(): Summe der Netzgewichte der
geschnittenen Netze
Lehrstuhl für Informatik 3 - Prof. Dr.-Ing. D. Fey
Vorlesung Einführung digitaler ASIC Entwurf
WS 2010/11 Folie 67
4.2 Layoutsynthese
4.2.1.2 Partitionierungsalgoritmen – Simulated Annealing
Ergebnisse der einzelnen IterationenAblauf des Algorithmus:
Zähler
i
T ai, bi cur_cost trial_cost Zufallszahl
r T
cost
e
Δ
Tausch
1 10,00 3,4 13 16 0,21713 0,74082 Ja
2 10,00 2,3 16 16 0,66138 1 Ja
3 10,00 4,6 16 13 Ja
4 10,00 1,2 13 2 Ja
5 7,00 2,5 2 16 0,11209 0,13534 Ja
6 7,00 1,5 16 13 Ja
7 7,00 1,4 13 15 0,33190 0,75148 Ja
8 7,00 2,6 15 15 0,12564 1 Ja
9 4,90 1,3 15 16 0,70105 0,81540 Ja
10 4,90 3,4 16 13 Ja
11 4,90 1,6 13 2 Ja
12 4,90 5,6 2 16 0,49375 0,05743 Nein
13 3,43 1,3 2 13 0,86493 0,04048 Nein
14 3,43 2,5 2 16 0,34371 0,01688 Nein
15 3,43 1,6 2 13 0,73232 0,04048 Nein
16 3,43 1,2 2 13 0,02093 0,04048 Ja
Veranschaulichung ausgewählter Iterationen i:
i = 4 (T = 10):
– Selektierte Zellen zum Tausch sind 1, 2; cur_cost = 13, trial_cost = 2, d.h. Tausch wird akzeptiert
i = 5 (T = 7):
– Selektierte Zellen zum Tausch sind 2, 5; cur_cost = 2, trial_cost = 16, d.h. Zufallszahl wird
generiert: 0,11209
– 0,11209 < e-14/2
= 0,13534, d.h. Tausch wird akzeptiert.
i = 12-15 (T = 4,9 bzw. T = 3,43):
– trial_cost jeweils größer als cur_cost und Zufallszahl r jeweils größer als Tt
e/cos
, d.h.
Vertauschungen nicht akzeptiert
Lehrstuhl für Informatik 3 - Prof. Dr.-Ing. D. Fey
Vorlesung Einführung digitaler ASIC Entwurf
WS 2010/11 Folie 68
4.2 Layoutsynthese
4.2.1.2 Partitionierungsalgoritmen – Simulated Annealing
Veranschaulichung ausgewählter Iterationen i:
i = 4 (T = 10):
Selektierte Zellen zum Tausch sind 1, 2;
cur_cost = 13, trial_cost = 2, d.h. Tausch wird akzeptiertAblauf des Algorithmus:
Zähler
i
T ai, bi cur_cost trial_cost Zufallszahl
r T
cost
e
Δ
Tausch
1 10,00 3,4 13 16 0,21713 0,74082 Ja
2 10,00 2,3 16 16 0,66138 1 Ja
3 10,00 4,6 16 13 Ja
4 10,00 1,2 13 2 Ja
5 7,00 2,5 2 16 0,11209 0,13534 Ja
6 7,00 1,5 16 13 Ja
7 7,00 1,4 13 15 0,33190 0,75148 Ja
8 7,00 2,6 15 15 0,12564 1 Ja
9 4,90 1,3 15 16 0,70105 0,81540 Ja
10 4,90 3,4 16 13 Ja
11 4,90 1,6 13 2 Ja
12 4,90 5,6 2 16 0,49375 0,05743 Nein
13 3,43 1,3 2 13 0,86493 0,04048 Nein
14 3,43 2,5 2 16 0,34371 0,01688 Nein
15 3,43 1,6 2 13 0,73232 0,04048 Nein
16 3,43 1,2 2 13 0,02093 0,04048 Ja
Lehrstuhl für Informatik 3 - Prof. Dr.-Ing. D. Fey
Vorlesung Einführung digitaler ASIC Entwurf
WS 2010/11 Folie 69
4.2 Layoutsynthese
4.2.1.2 Partitionierungsalgoritmen – Simulated Annealing
Veranschaulichung ausgewählter Iterationen i:
i = 5 (T = 7):
• Selektierte Zellen zum Tausch sind 2, 5; cur_cost = 2,
trial_cost = 16, d.h. Zufallszahl wird generiert: 0,11209
• 0,11209 < e-14/7 = 0,13534, d.h. Tausch wird akzeptiert.Ablauf des Algorithmus:
Zähler
i
T ai, bi cur_cost trial_cost Zufallszahl
r T
cost
e
Δ
Tausch
1 10,00 3,4 13 16 0,21713 0,74082 Ja
2 10,00 2,3 16 16 0,66138 1 Ja
3 10,00 4,6 16 13 Ja
4 10,00 1,2 13 2 Ja
5 7,00 2,5 2 16 0,11209 0,13534 Ja
6 7,00 1,5 16 13 Ja
7 7,00 1,4 13 15 0,33190 0,75148 Ja
8 7,00 2,6 15 15 0,12564 1 Ja
9 4,90 1,3 15 16 0,70105 0,81540 Ja
10 4,90 3,4 16 13 Ja
11 4,90 1,6 13 2 Ja
12 4,90 5,6 2 16 0,49375 0,05743 Nein
13 3,43 1,3 2 13 0,86493 0,04048 Nein
14 3,43 2,5 2 16 0,34371 0,01688 Nein
15 3,43 1,6 2 13 0,73232 0,04048 Nein
16 3,43 1,2 2 13 0,02093 0,04048 Ja
Lehrstuhl für Informatik 3 - Prof. Dr.-Ing. D. Fey
Vorlesung Einführung digitaler ASIC Entwurf
WS 2010/11 Folie 70
4.2 Layoutsynthese
4.2.1.2 Partitionierungsalgoritmen – Simulated Annealing
Veranschaulichung ausgewählter Iterationen i:
i = 12-15 (T = 4,9 bzw. T = 3,43):
• trial_cost jeweils größer als cur_cost und Zufallszahl r jeweils größer als
, d.h. Vertauschungen nicht akzeptiertAblauf des Algorithmus:
Zähler
i
T ai, bi cur_cost trial_cost Zufallszahl
r T
cost
e
Δ
Tausch
1 10,00 3,4 13 16 0,21713 0,74082 Ja
2 10,00 2,3 16 16 0,66138 1 Ja
3 10,00 4,6 16 13 Ja
4 10,00 1,2 13 2 Ja
5 7,00 2,5 2 16 0,11209 0,13534 Ja
6 7,00 1,5 16 13 Ja
7 7,00 1,4 13 15 0,33190 0,75148 Ja
8 7,00 2,6 15 15 0,12564 1 Ja
9 4,90 1,3 15 16 0,70105 0,81540 Ja
10 4,90 3,4 16 13 Ja
11 4,90 1,6 13 2 Ja
12 4,90 5,6 2 16 0,49375 0,05743 Nein
13 3,43 1,3 2 13 0,86493 0,04048 Nein
14 3,43 2,5 2 16 0,34371 0,01688 Nein
15 3,43 1,6 2 13 0,73232 0,04048 Nein
16 3,43 1,2 2 13 0,02093 0,04048 Ja
Tte
/cos
Lehrstuhl für Informatik 3 - Prof. Dr.-Ing. D. Fey
Vorlesung Einführung digitaler ASIC Entwurf
WS 2010/11 Folie 71
4.2 Layoutsynthese
4.2.1.2 Partitionierungsalgoritmen – Simulated Annealing
In der 4. Iteration (i = 4) erreicht der SA-Algorithmus einen
Kostenwert von 2, welcher den besten erzielbaren Wert darstellt.
Dieser repräsentiert die Summe der Netzgewichte der
geschnittenen Netze (hier Netz 2 mit w2 = 2).
Wie dem detaillierten Ablauf zu entnehmen ist, wurde
dieses Optimum durch die vorherige Akzeptanz von einer
schlechteren Lösung in der 1. Iteration erreicht.
Die beste Lösung entspricht einer Partitionierung
von A{2, 3, 6} und B{1, 4, 5}.
Lehrstuhl für Informatik 3 - Prof. Dr.-Ing. D. Fey
Vorlesung Einführung digitaler ASIC Entwurf
WS 2010/11 Folie 72
A B
Anfangspartitionierung:
A {1,2,3}, B {4,5,6}
Kosten: 13
Erzielte Lösung:
A {2,3,6}, B {1,4,5}
Kosten: 2
1 4
2 5
3 6
N5
N1
N2
N3
N6
N4
1 4
2 5
3 6
N5
N1
N2
N3
N6
N4
A
B
4.2 Layoutsynthese
4.2.1.2 Partitionierungsalgoritmen – Simulated Annealing
Die beste Lösung entspricht einer Partitionierung von A
{2,3,6} und B {1,4,5}