73
1 Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung Gliederung Kapitel 4 – Platzierung 4.1 Einführung 4.2 Optimierungsziele 4.2.1 Gewichtete Gesamtverbindungslänge 4.2.2 Maximale Schnittanzahl 4.2.3 Lokale Verdrahtungsdichte 4.2.4 Signalverzögerungen 4.3 Platzierungsalgorithmen 4.3.1 Min-Cut-Platzierung 4.3.2 Min-Cut-Platzierung mit Anschlussfestlegung 4.3.3 Quadratische Platzierung 4.3.4 Kräfteplatzierung mittels ZFT-Position 4.3.5 Simulated Annealing 4.3.6 Weitere Platzierungsalgorithmen 4.4 Aktuelle Platzierungswerkzeuge

Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung1 Gliederung Kapitel 4 – Platzierung

Embed Size (px)

Citation preview

Page 1: Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung1 Gliederung Kapitel 4 – Platzierung

1Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung

Gliederung Kapitel 4 – Platzierung

4.1 Einführung

4.2 Optimierungsziele

4.2.1 Gewichtete Gesamtverbindungslänge

4.2.2 Maximale Schnittanzahl

4.2.3 Lokale Verdrahtungsdichte

4.2.4 Signalverzögerungen

4.3 Platzierungsalgorithmen

4.3.1 Min-Cut-Platzierung

4.3.2 Min-Cut-Platzierung mit Anschlussfestlegung

4.3.3 Quadratische Platzierung

4.3.4 Kräfteplatzierung mittels ZFT-Position

4.3.5 Simulated Annealing

4.3.6 Weitere Platzierungsalgorithmen

4.4 Aktuelle Platzierungswerkzeuge

Page 2: Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung1 Gliederung Kapitel 4 – Platzierung

2Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung

4.1 Einführung

VerhaltensentwurfLogischer Entwurf

Layoutsynthese

Layoutverifikation

Chip

Floorplanning

Platzierung

Verdrahtung

Kompaktierung

ENTITY test isport a: in bit;

end ENTITY test;Partitionierung

Herstellung

Systemspezifikation

Architekturentwurf

Schaltungsentwurf

Verpackung/Test

Page 3: Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung1 Gliederung Kapitel 4 – Platzierung

3Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung

4.1 Einführung

Die Aufgabe der Platzierung ist die Anordnung der einzelnen Schaltungselemente (z.B. Zellen und Bauelemente) auf der zur Verfügung stehenden Layoutfläche unter Berücksichtigung von

Randbedingungen (u.a. Überlappungsfreiheit) und

Optimierungszielen (z.B. minimale Verbindungslänge).

Page 4: Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung1 Gliederung Kapitel 4 – Platzierung

4Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung

4.3 Begriffsbestimmungena) Schaltungs- beispiel

b) Eindimensionale Platzierung (Reihenanordnung)

1

2

4

5

3

6

7 8

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

56487231

Page 5: Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung1 Gliederung Kapitel 4 – Platzierung

5Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung

4.3 Begriffsbestimmungen

Page 6: Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung1 Gliederung Kapitel 4 – Platzierung

6Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung

1

2

3

5

47

6

8

9

10

12

11 1

2

354

7

6 8

912

11

10

Page 7: Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung1 Gliederung Kapitel 4 – Platzierung

7Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung

Globale Platzierung: Zellen werden den Mittelpunkten von Platzierungsbereichen (Tiles, Bins usw.) zugewiesen

Detailplatzierung / Feinplatzierung: Zellen werden ohne Überlappungen platziert

Page 8: Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung1 Gliederung Kapitel 4 – Platzierung

8Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung

Kapitel 4 – Platzierung

4.1 Einführung

4.2 Optimierungsziele

4.2.1 Gewichtete Gesamtverbindungslänge

4.2.2 Maximale Schnittanzahl

4.2.3 Lokale Verdrahtungsdichte

4.2.4 Signalverzögerungen

4.3 Platzierungsalgorithmen

4.3.1 Min-Cut-Platzierung

4.3.2 Min-Cut-Platzierung mit Anschlussfestlegung

4.3.3 Quadratische Platzierung

4.3.4 Kräfteplatzierung mittels ZFT-Position

4.3.5 Simulated Annealing

4.3.6 Weitere Platzierungsalgorithmen

4.4 Aktuelle Platzierungswerkzeuge

Page 9: Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung1 Gliederung Kapitel 4 – Platzierung

9Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung

4.2 Optimierungsziele

Gesamtverbindungslänge Anzahl der geschnittenen Netze

Lokale Verdrahtungsdichte

Signalverzögerungen

Page 10: Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung1 Gliederung Kapitel 4 – Platzierung

10Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung

Länge halber Netz-umfang = 9

4

5

Halber Umfang desminimal umschließenden Rechtecks (Semi-perimeter method)

Kompletter Graph (Complete graph)

Länge kompletter Graph * 2 / Pinanzahl = 14,5

36

5

3

8

4

Minimale Kette (Minimum chain)

Kettenlänge = 12

3

3

6

4.2.1 Optimierungsziel: Gesamtverbindungslänge

Abschätzung der Verdrahtungslängen bei Mehrpunktnetzen

Nac

h S

ait,

S.

M.,

You

ssef

, H

.: V

LSI

Phy

sica

l Des

ign

Aut

omat

ion

Page 11: Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung1 Gliederung Kapitel 4 – Platzierung

11Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung

Quelle-Senken-Verbindung (Source to sink connection)

Minimaler rektilinearer Spannbaum (Minimum rectilinear spanning tree)

Steinerbaum-Abschätzung (Steiner tree approximation)

Quelle-Senken-Länge= 15

83

4

Spannbaum-Länge = 11

3

3

5

Steinerbaum-Länge = 10

3 16

Nac

h S

ait,

S.

M.,

You

ssef

, H

.: V

LSI

Phy

sica

l Des

ign

Aut

omat

ion

4.2.1 Optimierungsziel: Gesamtverbindungslänge

Abschätzung der Verdrahtungslängen bei Mehrpunktnetzen (2)

Page 12: Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung1 Gliederung Kapitel 4 – Platzierung

12Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung

Netze GewichtN1 = (A, B, D1) w1 = 2N2 = (C, D2, F1) w1 = 4N3 = (F2, E) w1 = 1

33314472)( Nn

nn dwPL

A

B

C

D

E

F

4.2.1 Optimierungsziel: Gewichtete Gesamtverbindungslänge – Beispiel

Page 13: Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung1 Gliederung Kapitel 4 – Platzierung

13Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung

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

4.2.2 Optimierungsziel: Anzahl der geschnittenen Netze – Beispiel

Page 14: Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung1 Gliederung Kapitel 4 – Platzierung

14Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung

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

4.2.2 Optimierungsziel: Anzahl der geschnittenen Netze – Beispiel

Page 15: Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung1 Gliederung Kapitel 4 – Platzierung

15Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung

4.2.3 Optimierungsziel: Lokale Verdrahtungsdichte

A1A1

A2A2

Page 16: Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung1 Gliederung Kapitel 4 – Platzierung

16Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung

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

4.2.3 Optimierungsziel: Lokale Verdrahtungsdichte – Beispiel

Page 17: Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung1 Gliederung Kapitel 4 – Platzierung

17Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung

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

4.2.3 Optimierungsziel: Lokale Verdrahtungsdichte – Beispiel

Page 18: Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung1 Gliederung Kapitel 4 – Platzierung

18Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung

4.1 Einführung

4.2 Optimierungsziele

4.2.1 Gewichtete Gesamtverbindungslänge

4.2.2 Maximale Schnittanzahl

4.2.3 Lokale Verdrahtungsdichte

4.2.4 Signalverzögerungen

4.3 Platzierungsalgorithmen

4.3.1 Min-Cut-Platzierung

4.3.2 Min-Cut-Platzierung mit Anschlussfestlegung

4.3.3 Quadratische Platzierung

4.3.4 Kräfteplatzierung mittels ZFT-Position

4.3.5 Simulated Annealing

4.3.6 Weitere Platzierungsalgorithmen

4.4 Aktuelle Platzierungswerkzeuge

Kapitel 4 – Platzierung

Page 19: Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung1 Gliederung Kapitel 4 – Platzierung

19Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung

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

Analytische Vorgehensweisen: Nutzung von mathematischen Methoden (z.B. lineare Gleichungssysteme) zur

Abbildung und Optimierung des Platzierungsproblems

Beispiel: Quadratische Platzierung

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 werden

Beispiel: Simulated Annealing

4.3 Platzierungsalgorithmen

Page 20: Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung1 Gliederung Kapitel 4 – Platzierung

20Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung

StochastischPartitionierend Analytisch

Quadratische PlatzierungMin-Cut-Platzierung Platzierung mit SA

4.3 Platzierungsalgorithmen

Page 21: Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung1 Gliederung Kapitel 4 – Platzierung

21Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung

4.3.1 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 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)

Page 22: Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung1 Gliederung Kapitel 4 – Platzierung

22Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung

Quadratur-Platzierung(Quadrature placement)

Halbierungs-Platzierung (Bisection placement)

Reihen-/Halbierungs-Platzierung (Slice/bisection placement)

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

Nac

h S

ait,

S.

M.,

You

ssef

, H

.: V

LSI

Phy

sica

l Des

ign

Aut

omat

ion

4.3.1 Min-Cut-Platzierung

Page 23: Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung1 Gliederung Kapitel 4 – Platzierung

23Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung

Min-Cut-Algorithmus (Quadratur Platzierung)

1. Aufteilung der Layoutfläche in zwei Teilflächen mit senkrechter oder horizontaler Schnittrichtung.

2. Anwendung eines geeigneten Algorithmus, z.B. des KL- oder FM-Algorithmus, zur optimierten Verteilung der Zellen auf die beiden Teilflächen.

3. Aufteilung in neue Teilflächen und jeweils Initialzuordnung der Zellen auf diese. Alternierender Wechsel zwischen senkrechter und horizontaler Schnittrichtung.

4. ENDE, falls jede Teilfläche genau eine Zelle enthält, sonst weiter mit Schritt 2.

4.3.1 Min-Cut-Platzierung

Page 24: Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung1 Gliederung Kapitel 4 – Platzierung

24Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung

Gegeben:

Gesucht: 4 x 2 Platzierung mit minimaler Netzlänge

1

2

3

4

5 6

4.3.1 Min-Cut-Platzierung: Beispiel

Page 25: Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung1 Gliederung Kapitel 4 – Platzierung

25Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung

4.3.1 Min-Cut-Platzierung: Beispiel

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

1

2

3

4

5 6

c1

z.B. KL-Algorithmus

Page 26: Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung1 Gliederung Kapitel 4 – Platzierung

26Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung

Horizontaler Schnitt c2L: T={1,4}, B={2,0}

1

2 0

4

Horizontaler Schnitt c2R: T={3,5}, B={6,0}

3 5

60

1

20

4 5 3

06

c3L c3R

1 4 5 3

2 6

c2Lc2R

1

2 3

0

4 5

6

0

c1

Page 27: Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung1 Gliederung Kapitel 4 – Platzierung

27Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung

4.3.1 Min-Cut-Platzierung

Vorteile:

Sehr schnell

Kostenfunktion kann beliebig erweitert werden, d.h. auch für Timing-driven Placement anwendbar

Von Natur aus hierarchisch, daher für große Schaltungen nutzbar

Nachteile:

Viele Verschiebungen ohne Auswirkungen

Oft Zufallsfaktoren eingeschlossen, daher nicht immer deterministisch

Unterhalb bestimmter Partitionsgröße andere Ansatz zur Platzierung sinnvoll

Nur sequentielle Optimierung, d.h. die Optimierung bezieht sich immer nur auf die Zuordnung zur jeweils betrachteten Schnittlinie

Page 28: Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung1 Gliederung Kapitel 4 – Platzierung

28Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung

4.3.2 Min-Cut-Platzierung mit Anschlussfestlegung

2

1

4

3

2

1

3

4

1

2 4

3

1

2

4

3

p

R2

R1

R2

R1

2

1

43

2

1

43

Mit Anschlussfestlegung (Terminal Propagation)

Page 29: Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung1 Gliederung Kapitel 4 – Platzierung

29Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung

4.3.2 Min-Cut-Platzierung mit Anschlussfestlegung: Beispiel

1 2 4

3

Page 30: Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung1 Gliederung Kapitel 4 – Platzierung

30Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung

4.3.2 Min-Cut-Platzierung mit Anschlussfestlegung: Beispiel

1 2 4

3

L R

43

21

Page 31: Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung1 Gliederung Kapitel 4 – Platzierung

31Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung

4.3.2 Min-Cut-Platzierung mit Anschlussfestlegung: Beispiel

1 2 4

3

L R

43

21

2

1

RL2

L1

43

x

43

21

Page 32: Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung1 Gliederung Kapitel 4 – Platzierung

32Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung

4.3.2 Min-Cut-Platzierung mit Anschlussfestlegung: Beispiel

2

1

4

3 1

2 4

3

p

R2

R1

2

1

43

x

Page 33: Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung1 Gliederung Kapitel 4 – Platzierung

33Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung

4.3.2 Min-Cut-Platzierung mit Anschlussfestlegung: Beispiel

2

1

4

3

2

1

3

4

1

2 4

3

1

2

4

3

p

R2

R1

R2

R1

2

1

43

x

2

1

43

Page 34: Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung1 Gliederung Kapitel 4 – Platzierung

34Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung

4.3.2 Min-Cut-Platzierung mit Anschlussfestlegung: Beispiel

L R

N1

p1

p2

p3

Page 35: Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung1 Gliederung Kapitel 4 – Platzierung

35Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung

4.3.3 Quadratische Platzierung

Euklidische Verbindungslänge geht quadratisch in Kostenfunktion ein:

Netze dazu in Zweipunkt-Verbindungen zerlegt, Kostenfunktion ist die Summe der gewichteten quadratischen Abstände, Minimierung dieser Summe

Analogie: Federmodell

jede quadratische Zweipunkt-Länge entspricht Energie einer Feder zwischen beiden Punkten (Energie einer Feder ist proportional zum Quadrat ihrer Auslenkung)

quadratische Kostenfunktion verkörpert Gesamtenergie des Federsystems; deren Ableitung ist die Gesamtkraft des Systems

System sucht Zustand minimaler Energie, also minimale Summe der Abstandsquadrate

damit Zellen im Kräftegleichgewicht hinsichtlich der die Verdrahtung repräsentierenden Kräfte

n

jijijiij yyxxcPL

1,

22

2

1)(

Page 36: Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung1 Gliederung Kapitel 4 – Platzierung

36Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung

4.3.3 Quadratische Platzierung

Euklidische Verbindungslänge geht quadratisch in Kostenfunktion ein:

Vorgehensweise:

Vektor-/Matrixschreibweise:

mit XT und YT Vektoren der Dimension n der x- bzw. y-Koordinaten der n Zellen, C Verbindungsmatrix, Kx und Ky Koordinatenvektoren der nicht verschiebbaren Zellen/Außenanschlüsse sowie Konstante k

Globales Minimum und damit platzierungsoptimale x- und y-Koordinaten der Zellen lassen sich durch partielle Ableitung von L(P) bestimmen:

Ergebnis: viele Zellenüberlappungen

n

jijijiij yyxxcPL

1,

22

2

1)(

kKYKXCYYCXXPL yT

xTTT

2

1)(

0)(

und0)(

yx

KCYY

PLKCX

X

PL

Page 37: Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung1 Gliederung Kapitel 4 – Platzierung

37Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung

4.3.3 Quadratische Platzierung

Quadratische Platzierung lässt sich weiter unterteilen, je nachdem, wie die Zellenüberlappungen beseitigt/vermieden werden

Kraftbasierte quadratischePlatzierung

Überlappungsfreiheit: Verfeinerung vonSchwerpunktsnebenbedingungen (führt zu „Quadratic Programming“)und damit rekursive Zerteilung in Platziergebiete

Überlappungsfreiheit: zusätzliche Kräfte

Quadratische Platzierung mitSchwerpunktsnebenbedingungen

Page 38: Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung1 Gliederung Kapitel 4 – Platzierung

38Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung

4.3.3 Quadratische Platzierung

Vorteile:

Schnelle analytische Lösung

Auch für große Problemgrößen geeignet

Nachteile:

Pads notwendig (liefert triviale Lösung ohne Pads)

Hierarchischer Ansatz schwierig zu realisieren

Page 39: Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung1 Gliederung Kapitel 4 – Platzierung

39Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung

4.3.4 Kräfteplatzierung mittels ZFT-Position

Kräfteplatzierung

Bei der Kräfteplatzierung werden die zu platzierenden Zellen analog einem mechanischen System aus mit Federn verbundenen Körpern betrachtet.

Dabei üben miteinander verbundenen Körper (Zellen) eine Anziehungskraft zueinander aus, wobei diese Kraft direkt proportional zur Entfernung zwischen den Körpern ist.

Ergebnis: Kräftegleichgewicht bzw. energieminimaler Zustand

Page 40: Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung1 Gliederung Kapitel 4 – Platzierung

40Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung

4.3.4 Kräfteplatzierung mittels ZFT-Position

Kräfteplatzierung und quadratische Platzierung

Energie einer Feder ist proportional zum Quadrat ihrer Auslenkung

Ermittlung der energieminimalen Positionen von Zellen, die mit Federn verbunden sind, ist daher identisch zur Minimierung der Summe der Quadrate der euklidischen Abstände (quadratische Platzierung)

Unterscheidung in der Zellenbetrachtung: Während bei der quadratischen Platzierung die Zellenplatzierungen durch gleichzeitige Berücksichtigung aller Zellen ein einem aus der quadratischen Kostenfunktion abgeleiteten Gleichungssystem ermittelt werden (Überlappungen!), erfolgt die Zellenplatzierung bei der Kräfteplatzierung mittels ZFT-Position durch sequentielle Zellenverschiebungen

Page 41: Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung1 Gliederung Kapitel 4 – Platzierung

41Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung

Angenommen, eine Zelle a ist mit einer Zelle b verbunden. Die Anziehungskraft zwischen beiden Zellen ergibt sich aus dem Produkt von Wichtung und Länge der Verbindung

(bzw. , da parallel ist).

Analog gilt für eine Zelle i, die mit mehreren Zellen 1 … j verbunden ist

wobei wij die Wichtung der Verbindung und dij deren Länge sind.

j

ijiji dwF

abab dwF

abab dwF F

abd

4.3.4 Kräfteplatzierung mittels ZFT-Position

Page 42: Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung1 Gliederung Kapitel 4 – Platzierung

42Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung

1

2

3

4i

min4i4i3i3i2i2i1i1ii dwdwdwdwF

ZFT-Position

4.3.4 Kräfteplatzierung mittels ZFT-Position

Zero-Force-Target (ZFT)-Position einer Zelle i

Page 43: Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung1 Gliederung Kapitel 4 – Platzierung

43Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung

Anwendung bei der Platzierung:

Für jede Zelle werden die auf sie wirkenden Kräfte berechnet, um diese Zelle i dann in ihrer jeweiligen ZFT-Position (xi

0, yi0) zu platzieren.

Diese lässt sich ermitteln, indem die in x- und in y-Richtung wirkenden Kräfte zu Null gesetzt werden:

Die Umstellung dieser Gleichungen nach xi0 und yi

0 liefert

0j

0i

0jij xxw 0

j

0i

0jij yyw

j ij

jij0i w

xwjx

j ij

j jij0i w

ywy Berechnung der ZFT-Position einer Zelle i,

welche mit den Zellen 1 … j verbunden ist

4.3.4 Kräfteplatzierung mittels ZFT-Position

Page 44: Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung1 Gliederung Kapitel 4 – Platzierung

44Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung

0 1 2

1

2

In2

In3

In1

Out

In1

In2

In3

Out1

4.3.4 Kräfteplatzierung mittels ZFT-Position: Beispiel (ZFT-Position)

Page 45: Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung1 Gliederung Kapitel 4 – Platzierung

45Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung

4.3.4 Kräfteplatzierung mittels ZFT-Position: Beispiel (ZFT-Position)

Page 46: Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung1 Gliederung Kapitel 4 – Platzierung

46Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung

0 1 2

1

2

In2

In3

In1

Out

1

4.3.4 Kräfteplatzierung mittels ZFT-Position: Beispiel (ZFT-Position)

Page 47: Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung1 Gliederung Kapitel 4 – Platzierung

47Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung

Algorithmus zur Kräfteplatzierung mittels ZFT-Position

1. Ermitteln einer willkürlichen Anfangsplatzierung

2. Auswahl einer Zelle (z.B. diejenige mit maximalem Verbindungsgrad) und Berechnen ihrer ZFT-Position

wenn ZFT-Position frei, dann Verschiebung zu dieser

wenn ZFT-Position belegt, Anwendung einer der nachfolgenden Belegungsoptionen

3. Weiter mit Schritt 2 und neuer Zelle, bis Abbruchkriterium erreicht ist.

4.3.4 Kräfteplatzierung mittels ZFT-Position

Page 48: Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung1 Gliederung Kapitel 4 – Platzierung

48Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung

Optionen bei bereits erfolgter Belegung einer ZFT-Position

(p: zu verschiebende Zelle, q: Zelle in der ZFT-Position)

Verschieben von p zu einer freien Zellenposition möglichst nahe zu q.

Berechnen der Kostenveränderung bei Austausch von p mit q. Sollten sich die Gesamtkosten, wie z.B. die gewichtete Gesamtverbindungslänge L(P) verringern, werden p und q in ihren Positionen vertauscht.

4.3.4 Kräfteplatzierung mittels ZFT-Position

Page 49: Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung1 Gliederung Kapitel 4 – Platzierung

49Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung

Netze GewichtN1 = (1, 3) w1 = 2N2 = (2, 3) w2 = 1

Gegeben:

1 32

0 1 2

4.3.4 Kräfteplatzierung mittels ZFT-Position: Beispiel

Page 50: Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung1 Gliederung Kapitel 4 – Platzierung

50Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung

Netze GewichtN1 = (1, 3) w1 = 2N2 = (2, 3) w2 = 1

Gegeben:

Zelle p ZFT-Positionvon Zelle p

L(P) vor Vertauschung

L(P) /Anordnungnach Vertauschung

3 012

1102j j

j jij03

iw

xwx L(P) = 5 L(P) = 5

Zelle q

1

Damit keine Vertauschung von 3 und 1.

1 32

0 1 2

3 12

4.3.4 Kräfteplatzierung mittels ZFT-Position: Beispiel

Page 51: Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung1 Gliederung Kapitel 4 – Platzierung

51Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung

Netze GewichtN1 = (1, 3) w1 = 2N2 = (2, 3) w2 = 1

Gegeben:

Zelle p ZFT-Positionvon Zelle p

L(P) vor Vertauschung

L(P) /Anordnungnach Vertauschung

3 012

1102j j

j jij03

iw

xwx L(P) = 5 L(P) = 5

22

1

21j ij

j jij02

w

xwx L(P) = 3

Vertauschung von 2 und 3.

L(P) = 5

Zelle q

1

3

Damit keine Vertauschung von 3 und 1.

1 32

0 1 2

3 12

1 23

4.3.4 Kräfteplatzierung mittels ZFT-Position: Beispiel

Page 52: Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung1 Gliederung Kapitel 4 – Platzierung

52Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung

Optionen bei bereits erfolgter Belegung einer ZFT-Position

(p: zu verschiebende Zelle, q: Zelle in der ZFT-Position)

Verschieben von p zu einer Zellenposition möglichst nahe zu q.

Berechnen der Kostenveränderung bei Austausch von p mit q. Sollten sich die Gesamtkosten, wie z.B. die gewichtete Gesamtverbindungslänge L(P) verringern, werden p und q in ihren Positionen vertauscht.

„Chain move“: Die Zelle p wird auf die belegte Position verschoben und die Zelle q auf die nächstliegende Position bewegt. Sollte diese von einer Zelle r bereits belegt sein, so wird r auf die zu ihr nächstliegende Position verschoben. Dies wird solange fortgeführt, bis eine freie Position gefunden ist.

„Ripple move“: Die Zelle p wird auf die belegte Position verschoben und eine neue ZFT-Position für q berechnet. Diese Prozedur (ripple: „zurecht kämmen“) führt man solange fort, bis alle Zellen platziert sind.

4.3.4 Kräfteplatzierung mittels ZFT-Position

Page 53: Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung1 Gliederung Kapitel 4 – Platzierung

53Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung

4.3.4 Kräfteplatzierung mittels ZFT-Position

Vorteile:

Einfach zu implementieren

Gut geeignet zur Detailplatzierung

Nachteile:

Nicht für große Problemgrößen geeignet (da im Gegensatz zur quadratischen Platzierung immer nur eine Zelle betrachtet wird)

Hierarchischer Ansatz schwierig zu realisieren

Page 54: Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung1 Gliederung Kapitel 4 – Platzierung

54Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung

Zeit

Kosten

Analogie zum Abkühlungsprozess von metallischen Schmelzen (energieminimales Atomgitter)

Modifikation einer Anfangsplatzierung durch Tausch von zufällig ausgewählten Zellen

Wenn Kosten verbessert werden, wird Tausch ausgeführt

Bei keiner Kostenverbesserung wird Tausch mit temperaturabhängiger (d.h. abnehmender) Wahrscheinlichkeit ausgeführt

4.3.5 Simulated Annealing

Page 55: Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung1 Gliederung Kapitel 4 – Platzierung

55Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung

4.3.5 Simulated Annealing

Page 56: Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung1 Gliederung Kapitel 4 – Platzierung

56Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung

Vorteile:

Kann globales Optimum finden (bei „genügend“ Zeit)

Kann mehrere Optimierungsziele berücksichtigen (Wichtungsfaktoren)

Gut geeignet zur Detailplatzierung

Nachteil:

Sehr langsame Lösungskonvergenz

4.3.5 Simulated Annealing

Page 57: Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung1 Gliederung Kapitel 4 – Platzierung

57Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung

Zuordnung zu Einbauplätzen (z.B. bei Gate-Arrays)

Neuronale Netzwerke

Evolutionäre Algorithmen

Timing-driven Placement / Performance-driven Placement

4.3.6 Weitere Platzierungsalgorithmen

Page 58: Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung1 Gliederung Kapitel 4 – Platzierung

58Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung

K. M. Hall stellte 1970 eine elegante Lösung für die quadratische Platzierung ohne Pads und damit auch für das Zuweisen von Zellen auf Einbauplätzen in Gate-Arrays vor

4.3.6 Weitere Platzierungsalgorithmen: Zuordnung zu Einbauplätzen

Page 59: Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung1 Gliederung Kapitel 4 – Platzierung

59Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung

4.3.6 Zuordnung zu Einbauplätzen: Beispiel

1

4

2 3

65

Page 60: Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung1 Gliederung Kapitel 4 – Platzierung

60Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung

1

4

2 3

65

4.3.6 Zuordnung zu Einbauplätzen: Beispiel

Page 61: Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung1 Gliederung Kapitel 4 – Platzierung

61Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung

1

4

2 3

65

4.3.6 Zuordnung zu Einbauplätzen: Beispiel

Page 62: Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung1 Gliederung Kapitel 4 – Platzierung

62Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung

-1

y

x1

1

-1

1

2

3

4

5

6

1

5

2 4

36

4.3.6 Zuordnung zu Einbauplätzen: Beispiel

Page 63: Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung1 Gliederung Kapitel 4 – Platzierung

63Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung

4.3.6 Weitere Platzierungsalgorithmen: Neuronale Netzwerke

Gewichtete Summe

F:

x1

x2

x3

xn

w1

w2

w3

wn

OUT = F(NET)NET

Nac

h S

ait,

S.

M.,

You

ssef

, H

.: V

LSI

Phy

sica

l Des

ign

Aut

omat

ion

Prinzipieller Aufbau eines künstlichen Neurons

Page 64: Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung1 Gliederung Kapitel 4 – Platzierung

64Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung

4.3.6 Weitere Platzierungsalgorithmen: Neuronale Netzwerke

x1

x2

x3

OUT1

OUT2

OUT3

Page 65: Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung1 Gliederung Kapitel 4 – Platzierung

65Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung

Kapitel 4 – Platzierung

4.1 Einführung

4.2 Optimierungsziele

4.2.1 Gewichtete Gesamtverbindungslänge

4.2.2 Maximale Schnittanzahl

4.2.3 Lokale Verdrahtungsdichte

4.2.4 Signalverzögerungen

4.3 Platzierungsalgorithmen

4.3.1 Min-Cut-Platzierung

4.3.2 Min-Cut-Platzierung mit Anschlussfestlegung

4.3.3 Quadratische Platzierung

4.3.4 Kräfteplatzierung mittels ZFT-Position

4.3.5 Simulated Annealing

4.3.6 Weitere Platzierungsalgorithmen

4.4 Aktuelle Platzierungswerkzeuge

Page 66: Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung1 Gliederung Kapitel 4 – Platzierung

66Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung

4.4 Aktuelle Platzierungswerkzeuge

Kraftbasierte quadratischePlatzierung

Quadratische Platzierung mitSchwerpunkts-nebenbedingungen

StochastischPartitionierend Analytisch

Quadratische PlatzierungMin-Cut-Platzierung Platzierung mit SA

Page 67: Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung1 Gliederung Kapitel 4 – Platzierung

67Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung

4.4 Aktuelle Platzierungswerkzeuge

Capo

UCLA, University of Michigan, open source

Globaler Platzierungsalgorithmus, der auf rekursivem Min-Cut-Bisection-Schnittmodell unter Nutzung des Fiduccia-Mattheyses (FM) –Partionierungsalgorithmus beruht. Detailplatzierung mittels SA.

Dragon

Northwestern University, UCLA

Min-Cut-Platzierer mit Congestion-Minimization (Verdrahtungsoptimierung)

StochastischPartitionierend Analytisch

Min-Cut-Platzierung

Page 68: Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung1 Gliederung Kapitel 4 – Platzierung

68Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung

4.4 Aktuelle Platzierungswerkzeuge

Nicht-linearePlatzierung

Quadratische Platzierung

Kostenfunktion ist nicht-linear, z.B. durch Modellierung der Netzlänge mit einer Log-Sum-Exponential-Funktion

StochastischPartitionierend Analytisch

Page 69: Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung1 Gliederung Kapitel 4 – Platzierung

69Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung

4.4 Aktuelle Platzierungswerkzeuge

APlace

UCSD

Netzlänge (Kostenfunktion) wird mit einer Log-Sum-Exponential-Funktion ausgedrückt, Modulüberlappung mit einer „Bell-shaped“-Funktion modelliert.

mPL

UCLA

Netzlänge (Kostenfunktion) wird mit einer Log-Sum-Exponential-Funktion ausgedrückt, Modulüberlappung mit elektrostatischem Potential modelliert.

Nicht-linearePlatzierung

Quadratische Platzierung

StochastischPartitionierend Analytisch

Page 70: Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung1 Gliederung Kapitel 4 – Platzierung

70Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung

4.4 Aktuelle Platzierungswerkzeuge

Kraftwerk

TU München

FAR, mFAR

UCSB

FastPlace

Iowa State University

Kraftbasierte quadratische Platzierung

Quadratische Platzierung

StochastischPartitionierend Analytisch

Page 71: Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung1 Gliederung Kapitel 4 – Platzierung

71Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung

4.4 Aktuelle Platzierungswerkzeuge

Gordian

TU München, Module werden nach ihrer Lage den Platziergebieten zugeteilt

BonnPlace

Universität Bonn, Modulzuordnung zu Platziergebieten mittels „Transportation Algorithm“, Entkopplung durch „Terminal Propagation“ (damit parallelisierbar)

NTUplace

National Taiwan University, mittels Graphenpartitionierer wird Netzliste zerschnitten und Module Platziergebieten zugeordnet

Quadratische Platzierung mit Schwerpunktsnebenbedingungen

Quadratische Platzierung

StochastischPartitionierend Analytisch

Page 72: Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung1 Gliederung Kapitel 4 – Platzierung

72Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung

4.4 Aktuelle Platzierungswerkzeuge

TimberWolf

University of Seattle

Kommerzielles Platzierungspaket, in den 80er Jahren vorgestellt

Ursprünglich Standardzellen, aktuelle Versionen schließen andere Platzierungsaufgaben (z.B. Makrozellen) mit ein

Platzierung mit SA

StochastischPartitionierend Analytisch

Page 73: Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung1 Gliederung Kapitel 4 – Platzierung

73Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 4: Platzierung

4.1 Einführung

4.2 Optimierungsziele

4.2.1 Gewichtete Gesamtverbindungslänge

4.2.2 Maximale Schnittanzahl

4.2.3 Lokale Verdrahtungsdichte

4.2.4 Signalverzögerungen

4.3 Platzierungsalgorithmen

4.3.1 Min-Cut-Platzierung

4.3.2 Min-Cut-Platzierung mit Anschlussfestlegung

4.3.3 Quadratische Platzierung

4.3.4 Kräfteplatzierung mittels ZFT-Position

4.3.5 Simulated Annealing

4.3.6 Weitere Platzierungsalgorithmen

4.4 Aktuelle Platzierungswerkzeuge

Zusammenfassung Kapitel 4 – Platzierung