Gliederung Kapitel 5 – Globalverdrahtung
5.1 Einführung
5.1.1 Allgemeines Verdrahtungsproblem
5.1.2 Globalverdrahtung
5.2 Begriffsbestimmungen
5.3 Optimierungsziele
5.3.1 Kundenspezifischer Entwurf
5.3.2 Standardzellen-Entwurf
5.3.3 Gate-Array-Entwurf
5.4 Abbildung von Verdrahtungsregionen
5.5 Ablauf der Globalverdrahtung
5.6 Algorithmen für die Globalverdrahtung
5.6.1 Steinerbaum-Verdrahtung
5.6.2 Globalverdrahtung im Verbindungsgraphen
5.6.3 Wegsuche mit dem Dijkstra-Algorithmus
Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung
Kapitel 5: Globalverdrahtung
1
5.1.1
Allgemeines Verdrahtungsproblem
Systemspezifikation
Architekturentwurf
ENTITY test is
port a: in bit;
end ENTITY test;
Verhaltensentwurf
Logischer Entwurf
Schaltungsentwurf
Layoutsynthese
Partitionierung
Floorplanning
Platzierung
Layoutverifikation
Verdrahtung
Herstellung
Kompaktierung
Verpackung/Test
Chip
Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung
Kapitel 5: Globalverdrahtung
2
5.1.1
Allgemeines Verdrahtungsproblem
Netzliste:
Netze mit den durch sie
jeweils zu verbindenden
BauelementeAnschlüssen
3
N2 = {D4, B4, C1, A4}
N3 = {C2, D5}
N4 = {B1, A1, C3}
4
C
1
1
A
N1 = {C4, D6, B3}
Horizontale
Verdrahtungsebene
2
4
N4
N2
1
B
N3 N1
3
Via
4
4
Vertikale
Verdrahtungsebene
5
6
D
TechnologieInformationen:
Abstandsregeln
Breitenregeln usw.
Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung
Kapitel 5: Globalverdrahtung
3
5.1.1
Allgemeines Verdrahtungsproblem
Bei der Verdrahtung sind alle Zellen- bzw. Bauelementeanschlüsse gleichen
Potentials, die damit zu einem Netz gehören, miteinander zu verbinden.
Dies beinhaltet das Festlegen von Verdrahtungswegen sowie die Zuordnung
der Leiterzugsegmente zu Verdrahtungsebenen.
Dabei sind Randbedingungen (z.B. Kreuzungsfreiheit) einzuhalten und
Optimierungsziele (z.B. minimale Verbindungslänge) anzustreben.
Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung
Kapitel 5: Globalverdrahtung
4
5.1.1
Allgemeines Verdrahtungsproblem
Verdrahtungsverfahren
Zweistufige
Verdrahtung
Globalverdrahtung
Feinverdrahtung
Flächenverdrahtung
Spezialverdrahtung
Zuordnung der
Verdrahtung zu
Verdrahtungsregionen
(Kap. 5)
Verdrahtung
innerhalb der
Verdrahtungsregionen
(Kap. 6)
Verdrahtung
auf gesamter
Layoutfläche
ohne vorherige
Zuweisung
(Kap. 7)
Verdrahtung
der Versorgungs- und
Taktnetze
(Kap. 7)
Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung
Kapitel 5: Globalverdrahtung
5
5.1.2
Globalverdrahtung
Bei der Globalverdrahtung werden ungefähre Verbindungswege auf einer
Layoutoberfläche festgelegt.
Dies geschieht meist durch Zuweisung der Netzsegmente in sog.
Verdrahtungsregionen unter Berücksichtigung der jeweiligen
Verdrahtungskapazitäten dieser Regionen.
Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung
Kapitel 5: Globalverdrahtung
6
5.1.2
Globalverdrahtung
3
1
4
C
1
A
11
2
4
1
B
4
4
Globalverdrahtung
AA
44
11
5
D
6
44
1
22
CC
N4
3
33
BB
N3 N1
N2
33
44
44
55
DD
66
Feinverdrahtung
Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung
Kapitel 5: Globalverdrahtung
7
5.2
Begriffsbestimmungen
Kanal (Channel)
Standardzellenlayout (Zweilagen-Verdrahtung)
Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung
Kapitel 5: Globalverdrahtung
8
5.2
Begriffsbestimmungen
Kanal (Channel)
Verdrahtungskanal
Verdrahtungskanal
Standardzellenlayout (Zweilagen-Verdrahtung)
Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung
Kapitel 5: Globalverdrahtung
9
5.2
Begriffsbestimmungen
Kapazität (Capacity)
Standardzelle
2
Standardzelle
2
3
4
Standardzelle
2
3
2
Verdrahtungskanal
dpitch h
Verdrahtungskanal
1
3
1
2
Standard- Standardzelle
zelle
Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung
2
3
4
Standardzelle
Kapitel 5: Globalverdrahtung
10
5.2
Begriffsbestimmungen
Switchbox (Zweilagen-Verdrahtung)
Vertikaler
Kanal
2
3
3
Horizontaler 2
Kanal
2
1
3
Horizontaler
Kanal
1 2
Vertikaler
Kanal
Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung
Kapitel 5: Globalverdrahtung
11
5.2
Begriffsbestimmungen
M5
M4
2D- und 3DSwitchboxen
3D-Switchbox
2D-Switchbox
Pin auf der Oberseite
einer Zelle
Pin auf
Kanalgrenze
Kanal
M3
M2
Nach Sherwani, N.: Algorithms for VLSI Physical Design Automation
Pin auf der Unterseite
einer 3D-Switchbox
M1
Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung
Kapitel 5: Globalverdrahtung
12
5.2
Begriffsbestimmungen
Verdrahtungsregion (Tile, Box)

Kanal- und klassische Switchboxdefinition
nur bei Zweilagen-Verdrahtung sinnvoll

Mehrlagen-Verdrahtung oftmals mit
zellenunabhängigen Verdrahtungsbereichen
(Verdrahtungsregion, Tile, Box usw.) auf
allen Ebenen zur Netzzuweisung
Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung
Kapitel 5: Globalverdrahtung
13
5.2
Begriffsbestimmungen
Verdrahtungsregion (Tile, Box)
bei Makrozellen
Metal1
Metal3
Metal2
Metal4
Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung
Kapitel 5: Globalverdrahtung
usw.
14
5.2
Begriffsbestimmungen
Verdrahtungsregion (Tile, Box)
bei Standardzellen
Metal3
Metal1
(Zellenebene)
Metal2
(Anschlussebene)
Metal4
Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung
Kapitel 5: Globalverdrahtung
usw.
15
5.2
Begriffsbestimmungen
Verdrahtungsregion (Tile, Box)
bei Back-to-back-Standardzellen
Metal3
Metal1
(Back-to-backZellenebene)
Metal2
(Anschlussebene)
Metal4
Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung
Kapitel 5: Globalverdrahtung
usw.
16
5.2
Begriffsbestimmungen
T-Kreuzung (T-Junction, Zweilagen-Verdrahtung)
2
3
3
Horizontaler 2
Basiskanal
2
1
3
Horizontaler
Basiskanal
1 2
Vertikaler
Anschlusskanal
Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung
Kapitel 5: Globalverdrahtung
17
Kapitel 5 – Globalverdrahtung
5.1 Einführung
5.1.1 Allgemeines Verdrahtungsproblem
5.1.2 Globalverdrahtung
5.2 Begriffsbestimmungen
5.3 Optimierungsziele
5.3.1 Kundenspezifischer Entwurf
5.3.2 Standardzellen-Entwurf
5.3.3 Gate-Array-Entwurf
5.4 Abbildung von Verdrahtungsregionen
5.5 Ablauf der Globalverdrahtung
5.6 Algorithmen für die Globalverdrahtung
5.6.1 Steinerbaum-Verdrahtung
5.6.2 Globalverdrahtung im Verbindungsgraphen
5.6.3 Wegsuche mit dem Dijkstra-Algorithmus
Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung
Kapitel 5: Globalverdrahtung
18
5.3.1
Optimierungsziele beim kundenspezifischen Entwurf
Festlegen der Verdrahtungsreihenfolge
V
D
B
C
A
C
E
F
A
H
D
B
E
F
5
H
D
B
4
1 5 C 2 E
A 1 B D 4 H
A
F 3V
3
F
C 2 E
Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung
Kapitel 5: Globalverdrahtung
19
5.3.2
Optimierungsziele beim Standardzellen-Entwurf
Durchgangszellen
A
A
Variable
Kanalhöhen
(ZweilagenVerdrahtung)
A
A
A
Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung
Kapitel 5: Globalverdrahtung
20
5.3.2
Optimierungsziele beim Standardzellen-Entwurf
Steinerbaum mit minimaler
Verbindungslänge
Steinerbaum mit minimaler
Anzahl von Reihendurchquerungen
Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung
Kapitel 5: Globalverdrahtung
21
5.3.3
Optimierungsziele beim Gate-Array-Entwurf
Kanalspuren
Nichtverlegbares
Netz
Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung
Kapitel 5: Globalverdrahtung
22
Kapitel 5 – Globalverdrahtung
5.1 Einführung
5.1.1 Allgemeines Verdrahtungsproblem
5.1.2 Globalverdrahtung
5.2 Begriffsbestimmungen
5.3 Optimierungsziele
5.3.1 Kundenspezifischer Entwurf
5.3.2 Standardzellen-Entwurf
5.3.3 Gate-Array-Entwurf
5.4 Abbildung von Verdrahtungsregionen
5.5 Ablauf der Globalverdrahtung
5.6 Algorithmen für die Globalverdrahtung
5.6.1 Steinerbaum-Verdrahtung
5.6.2 Globalverdrahtung im Verbindungsgraphen
5.6.3 Wegsuche mit dem Dijkstra-Algorithmus
Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung
Kapitel 5: Globalverdrahtung
23
5.4
Abbildung von Verdrahtungsregionen
Kanal-Verbindungsgraph (Channel Connectivity Graph)
4
4
5
5
1 2
3
6
9
1
2
3
7
8
6
9
7
8
Graph G = (V, E), wobei jeder Kanal durch einen Knoten V repräsentiert
wird. Eine Kante E zwischen zwei Knoten modelliert die Nachbarschaft der
durch die Knoten repräsentierten Kanäle.
Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung
Kapitel 5: Globalverdrahtung
24
5.4
Abbildung von Verdrahtungsregionen
Switchbox-Verbindungsgraph (Channel Intersection Graph)
1
4
5
2
9
8
1
12
6
7
3
11
5
2
10
13
14
4
9
12
10
13
6
7
3
11
8
14
Graph G = (V, E), wobei die Switchboxen als Knoten V modelliert werden.
Zwischen den Knoten befindet sich eine Kante E, wenn sich die
Switchboxen auf gegenüberliegenden Seiten ein und desselben Kanals
befinden.
Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung
Kapitel 5: Globalverdrahtung
25
5.4
Abbildung von Verdrahtungsregionen
Gittergraph (Grid Graph Model)
1
2
3
4
5
1
2
3
4
5
6
7
8
9
10
6
7
8
9
10
11
12
13
14
15
11
12
13
14
15
16
17
18
19
20
16
17
18
19
20
21
22
23
24
25
21
22
23
24
25
Graph G = (V, E), wobei sog. globale Zellen, welche gleichverteilte
Layoutbereiche darstellen, durch Knoten V und ihre Nachbarschaft durch
Kanten E modelliert werden.
Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung
Kapitel 5: Globalverdrahtung
26
5.5
Ablauf der Globalverdrahtung
1. Festlegung der Verdrahtungsregionen (Region definition)
2. Zuordnung der Netze zu den Verdrahtungsregionen (Region assignment)
3. Evtl. Anschluss-Zuweisung (Pin assignment)
Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung
Kapitel 5: Globalverdrahtung
27
Kapitel 5 – Globalverdrahtung
5.1 Einführung
5.1.1 Allgemeines Verdrahtungsproblem
5.1.2 Globalverdrahtung
5.2 Begriffsbestimmungen
5.3 Optimierungsziele
5.3.1 Kundenspezifischer Entwurf
5.3.2 Standardzellen-Entwurf
5.3.3 Gate-Array-Entwurf
5.4 Abbildung von Verdrahtungsregionen
5.5 Ablauf der Globalverdrahtung
5.6 Algorithmen für die Globalverdrahtung
5.6.1 Steinerbaum-Verdrahtung
5.6.2 Globalverdrahtung im Verbindungsgraphen
5.6.3 Wegsuche mit dem Dijkstra-Algorithmus
Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung
Kapitel 5: Globalverdrahtung
28
5.6
Algorithmen für die Globalverdrahtung

Sequentielle Netzbetrachtung, wie z.B. Steinerbaum-Verdrahtung,
Globalverdrahtung im Verbindungsgraphen und mittels des DijkstraAlgorithmus, bei denen die Netze nacheinander verdrahtet werden.

Parallele Netzbetrachtung durch hierarchische Aufteilung (Hierarchical
decomposition) des Layouts in sukzessive immer kleinere „Quadranten“.
In jedem Schritt erfolgt eine Zuweisung der Netze auf diese Regionen
(Parallelbearbeitung von Netzen).

Numerische Methoden, bei denen das Globalverdrahtungsproblem in
Form eines Gleichungssystems abgebildet wird. Damit lassen sich jeweils
sämtliche Verdrahtungswege eines Netzes betrachten.

Stochastische Wegsuche-Algorithmen, wie z.B. Simulated Annealing und
evolutionäre Algorithmen.
Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung
Kapitel 5: Globalverdrahtung
29
5.6
Algorithmen für die Globalverdrahtung

Steinerbaum-Verdrahtung

Globalverdrahtung im Verbindungsgraphen

Dijkstra-Algorithmus
Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung
Kapitel 5: Globalverdrahtung
30
5.6.1
Steinerbaum-Verdrahtung
Vorbemerkungen

Gegeben seien die p Pins eines Netzes auf einem HV-Raster. Ein Rasterbaum
heißt rektilinearer Steinerbaum (RST), wenn er alle p Pins und beliebig viele
Rasterpunkte als Knoten enthält. Knoten des RST, die nicht Pins des Netzes
sind, heißen Steinerknoten.
B (2, 6)
Steinerknoten
S (2, 4)
C (6, 4)
A (2, 1)
Pinknoten
Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung
Kapitel 5: Globalverdrahtung
31
5.6.1
Steinerbaum-Verdrahtung
Vorbemerkungen

Gegeben seien die p Pins eines Netzes auf einem HV-Raster. Ein Rasterbaum
heißt rektilinearer Steinerbaum (RST), wenn er alle p Pins und beliebig viele
Rasterpunkte als Knoten enthält. Knoten des RST, die nicht Pins des Netzes
sind, heißen Steinerknoten.
Eigenschaften des minimalen rektilinearen Steinerbaums (MRST):

Die Zahl s der Steinerknoten ist 0  s  p-2 (p … Anzahl der Pinknoten)

Der Knotengrad von Pinknoten ist 1, 2, 3 oder 4, der Knotengrad von
Steinerknoten 3 oder 4

Der MRST eines Netzes liegt stets innerhalb des umschließenden Rechtecks
aller Pins dieses Netzes

Für die Länge gilt LMRST  LMR (LMR … halber Umfang des umschließenden
Rechtecks)
Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung
Kapitel 5: Globalverdrahtung
32
5.6.1
Steinerbaum-Verdrahtung
B (2, 6)
B (2, 6)
S (2, 4)
C (6, 4)
A (2, 1)
Minimaler rektilinearer
Spannbaum
C (6, 4)
A (2, 1)
Minimaler rektilinearer
Steinerbaum (MRST)
Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung
Kapitel 5: Globalverdrahtung
33
5.6.1
Steinerbaum-Verdrahtung
Hanan-Punkte (Hanan Points)

Zur Erzeugung eines minimalen Steinerbaums aus einem Spannbaum sind
Steinerknoten einzuführen, welche die Gesamtverbindungslänge verkürzen

M. Hanan zeigte 1966, dass sämtliche Steinerknoten eines optimalen
rektilinearen Steinerbaumes auf den Kreuzungspunkten der Gitterlinien liegen,
die von den Pinknoten gebildet werden

Diese Punkte werden als Hanan-Punkte bezeichnet

Damit können alle weiteren Punkte ignoriert werden, was den Suchraum stark
einschränkt
Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung
Kapitel 5: Globalverdrahtung
34
5.6.1
Steinerbaum-Verdrahtung
Pinknoten
Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung
Kapitel 5: Globalverdrahtung
35
5.6.1
Pinknoten
Steinerbaum-Verdrahtung
Gitterlinien
Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung
Kapitel 5: Globalverdrahtung
36
5.6.1
Pinknoten
Steinerbaum-Verdrahtung
Gitterlinien
Hanan-Punkte ( )
Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung
Kapitel 5: Globalverdrahtung
37
5.6.1
Pinknoten
Steinerbaum-Verdrahtung
Gitterlinien
Hanan-Punkte ( )
Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung
Minimaler rektilinearer
Steinerbaum
Kapitel 5: Globalverdrahtung
38
5.6.1
Globale Zellen
Steinerbaum-Verdrahtung
Netzanschlüsse
Netzanschlüsse im Zellenmittelpunkt
Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung
Kapitel 5: Globalverdrahtung
39
5.6.1
Steinerbaum-Verdrahtung
Steinerbaum-AnschlussPunkte (Pinknoten)
Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung
Kapitel 5: Globalverdrahtung
40
5.6.1
Steinerbaum-Verdrahtung
Steinerbaum-AnschlussPunkte (Pinknoten)
Minimaler rektilinearer
Steinerbaum
Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung
Kapitel 5: Globalverdrahtung
41
5.6.1
Steinerbaum-Verdrahtung
A
A
A
A
A
A
A
Steinerbaum-AnschlussPunkte (Pinknoten)
Minimaler rektilinearer
Steinerbaum
A
A
A
A
Zugewiesene Verdrahtungsregionen und Durchgangszellen
Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung
Kapitel 5: Globalverdrahtung
42
5.6.1
Steinerbaum-Verdrahtung
A
A
A
A
A
A
A
Steinerbaum-AnschlussPunkte (Pinknoten)
Minimaler rektilinearer
Steinerbaum
A
A
A
A
Zugewiesene Verdrahtungsregionen und Durchgangszellen
Sequentieller Steinerbaum-Algorithmus
Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung
Kapitel 5: Globalverdrahtung
43
5.6.1
Steinerbaum-Verdrahtung
Sequentieller Steinerbaum-Algorithmus

Sequentielle Einbeziehung von Pin- und Hanan-Punkten in den Baumaufbau

Optimaler Steinerbaum bei bis zu vier Pinanschlüssen
Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung
Kapitel 5: Globalverdrahtung
44
5.6.1
Steinerbaum-Verdrahtung
Sequentieller Steinerbaum-Algorithmus
1. Ermitteln des Anschlusspaars mit minimalem Manhattan (M)-Abstand und
Erzeugung des minimal umschreibenden Rechtecks (MR), d.h. Generierung
von (höchstens) zwei alternativen minimalen rektilinearen Steinerbäumen
(MRST).
2. Bestimmen des Anschlusses mit minimalem M-Abstand zur aktuellen MRSTMenge, Verbinden dieses Anschlusses durch minimale M-Pfade auf dem MR
(es gibt höchstens zwei).
3. Falls der in Schritt 2 erzeugte M-Pfad im Steinerknoten einer von zwei MRSTAlternativen endet, Löschen der anderen (Eliminierung einer Masche im
Graphen der MRST-Menge).
4. Falls noch nicht alle Anschlüsse abgearbeitet sind: Wenn mehr als zwei
Maschen existieren, Löschen von willkürlich einer MRST-Alternative und weiter
mit Schritt 2. Andernfalls, d.h. alle Anschlüsse wurden abgearbeitet, Eliminieren
aller noch vorhandenen Maschen durch Löschen je einer MRST-Alternative.
ENDE.
Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung
Kapitel 5: Globalverdrahtung
45
5.6.1
Steinerbaum-Verdrahtung: Beispiel
1
Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung
Kapitel 5: Globalverdrahtung
46
5.6.1
Steinerbaum-Verdrahtung: Beispiel
1
2
1
Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung
Kapitel 5: Globalverdrahtung
47
5.6.1
Steinerbaum-Verdrahtung: Beispiel
3
1
2
1
Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung
Kapitel 5: Globalverdrahtung
48
5.6.1
Steinerbaum-Verdrahtung: Beispiel
3
1
2
1
3
1
2
2
4
Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung
Kapitel 5: Globalverdrahtung
49
5.6.1
Steinerbaum-Verdrahtung: Beispiel
3
1
2
1
3
1
2
2
3
1
2
4
3
4
5
Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung
Kapitel 5: Globalverdrahtung
50
5.6.1
Steinerbaum-Verdrahtung: Beispiel
3
1
2
3
1
2
1
2
3
1
2
4
3
4
5
3
1
2
4
6
4
5
Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung
Kapitel 5: Globalverdrahtung
51
5.6.1
Steinerbaum-Verdrahtung: Beispiel
3
1
2
3
1
2
1
3
1
2
2
4
3
4
5
3
1
2
4
6
3
1
2
4
5
6
5
4
5
7
Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung
Kapitel 5: Globalverdrahtung
52
5.6.1
Steinerbaum-Verdrahtung: Beispiel
3
1
2
3
1
2
1
3
1
2
2
4
3
4
5
3
1
2
4
6
3
1
2
4
5
6
5
7
3
1
2
4
5
6
6
4
5
7
Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung
Kapitel 5: Globalverdrahtung
53
5.6.1
Steinerbaum-Verdrahtung: Beispiel
3
1
2
3
1
2
1
3
1
2
2
4
3
4
5
3
1
2
4
6
3
1
2
4
5
6
5
7
3
1
2
4
5
6
6
4
5
7
Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung
Kapitel 5: Globalverdrahtung
54
5.6.2
Globalverdrahtung im Verbindungsgraphen
4
4
KanalVerbindungsgraph
5
5
1 2
3
6
9
1
2
3
7
1
2
11
9
8
1
12
6
7
3
8
4
5
9
7
8
SwitchboxVerbindungsgraph
6
5
2
10
13
14
4
Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung
9
12
10
13
6
7
3
11
8
14
Kapitel 5: Globalverdrahtung
55
5.6.2
Globalverdrahtung im Verbindungsgraphen
KanalVerbindungsgraph
SwitchboxVerbindungsgraph
Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung
Kapitel 5: Globalverdrahtung
56
5.6.2
Globalverdrahtung im Verbindungsgraphen

Rothermel und Mlynski, 1983

Berücksichtigt ungleichförmige Zellen/Bauelemente, daher für
kundenspezifischen IC-Entwurf und MCMs geeignet
Ablauf (Übersicht):
A
1
2
3
6
7
B
4
5
10
9
B
11
2
3
4,2
4,2
4,2
4,2
A
8
1
4 1,2
1,5
1,2
5
6
8 4,2
4,2
0,4
0,1
1,2 7
5
6
1,2 7
4 1,2
4,2 9
8 4,2
12
(1) Verdrahtungsregionen
3,1
2,2
2,7
2,2
10
11
12
(2) Graphendarstellung
4,2 9
2,2
2,7
2,2
10
11
12
(3) Wegsuche im Graphen
Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung
Kapitel 5: Globalverdrahtung
57
5.6.2
Globalverdrahtung im Verbindungsgraphen
Verdrahtungsregionen
Horizontale Zellenkanten
Vertikale Zellenkanten
Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung
Zweidimensionales Kanalmodell
Kapitel 5: Globalverdrahtung
58
5.6.2
Globalverdrahtung im Verbindungsgraphen
Graphendarstellung
1
8
17
2
9
18
3
10
4 1112
21
19
23
8
17
2
9
18
3
10
24
5 13 1415 20 22
25
6
7
26
27
16
1
4
11
12
5
13
14
19
15
6
7
21
20
23
24
22
25
26
16
Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung
27
Kapitel 5: Globalverdrahtung
59
5.6.2
Globalverdrahtung im Verbindungsgraphen
Horizontale Aufnahmekapazität
der Region 1
Vertikale Aufnahmekapazität
der Region 1
1 Spur
2 Spuren
1
8
17
2
9
18
3
10
4 1112
21
19
23
8
17
2
9
18
3
10
24
5 13 1415 20 22
25
6
7
26
27
16
1 1,2
4
11
12
5
13
14
19
15
6
7
21
20
23
24
22
25
26
16
Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung
27
Kapitel 5: Globalverdrahtung
60
5.6.2
Globalverdrahtung im Verbindungsgraphen
1
8
17
2
9
18
3
10
4 1112
21
19
23
8 1,3
17 1,1 21 1,4 23 1,1
2
9
2,3
18
1,1
19 4,1
3
24
5 13 1415 20 22
25
6
7
26
27
16
1 1,2
2,2
10
2,2
12
4 2,2 11 2,1 2,1
15
13 14
5
3,2
6
3,1
3,1
3,1
20
3,1
24 6,1
22
3,4
25
3,1
26 1,1
1,2
7 1,2
2,1
16
Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung
1,8
27
Kapitel 5: Globalverdrahtung
1,1
61
5.6.2
Globalverdrahtung im Verbindungsgraphen
Ablauf
1. Festlegen der Verdrahtungsregionen und Abbildung in einem
Verbindungsgraphen
2. Festlegen der Netzreihenfolge
3. Anschluss-Reservierung für alle Netze
4. Netzauswahl und Globalverdrahtung dieses Netzes:
a) Aufheben der Anschluss-Reservierungen
b) Auswahl einer zu verdrahtenden 2-Punkt-Verbindung
c) Suchen des kürzesten Pfads im Verbindungsgraphen. ABBRUCH, falls kein Weg
existiert, sonst weiter mit Schritt d
d) Aktualisierung der Verdrahtungskapazitäten entsprechend der durch den Pfad
benötigten Ressourcen
e) Falls noch nicht alle Pins des Netzes abgearbeitet sind, weiter mit Schritt b
5. Falls noch nicht alle Netze verdrahtet sind, weiter mit Schritt 4, sonst ENDE.
Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung
Kapitel 5: Globalverdrahtung
62
l
w
A
1
2
3
4,2
4,2
1,5
1,2
1,2
7
5
6
4,2
9
2
3
4,2
6
7
4 1,2
9
8 4,2
B
Beispiel
4
Globalverdrahtung der
Netze A-A und B-B
1
5
A
8
10
B
11
12
Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung
2,2
2,7
2,2
10
11
12
Kapitel 5: Globalverdrahtung
63
l
w
A
1
2
3
4,2
4,2
1,5
1,2
1,2
7
5
6
4,2
9
2
3
4,2
6
7
4 1,2
9
8 4,2
B
Beispiel
4
Globalverdrahtung der
Netze A-A und B-B
1
5
A
8
B
10
11
12
A
2,2
2,7
2,2
10
11
12
1
2
3
4,2
3,1
4,2
0,4
0,1
1,2
5
6
B
4 1,2
A
B
Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung
8 4,2
7
4,2 9
2,2
2,7
2,2
10
11
12
Kapitel 5: Globalverdrahtung
64
l
w
A
1
2
3
4,2
4,2
1,5
1,2
1,2
7
5
6
4,2
9
2
3
4,2
6
7
4 1,2
9
8 4,2
B
Beispiel
4
Globalverdrahtung der
Netze A-A und B-B
1
5
A
8
B
10
11
12
A
2,2
2,7
2,2
10
11
12
1
2
3
4,2
3,1
4,2
0,4
0,1
1,2
5
6
B
4 1,2
A
B
8 4,2
A
7
4,2 9
2,2
2,7
2,2
10
11
12
1
2
3
4,2
2,1
3,1
0,4
0,1
1,1
5
6
B
4 1,2
A
B
Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung
8 3,1
7
4,1 9
1,7
1,1
10 1,1
Kapitel 5: Globalverdrahtung
11
12
65
l
w
A
1
Beispiel
4
Globalverdrahtung der
Netze A-A und B-B
2
3
6
7
B
5
A
8
9
B
10
11
12
A
B
A
B
Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung
Kapitel 5: Globalverdrahtung
66
Beispiel
Feststellung der
Verdrahtbarkeit
einer
Platzierung
1
2
3
5
6
7
A
B
4
1
2
3
3,1
3,4
3,3
5
6
7
4 1,4
1,1
3,4
3,1
3,3
8
9
10
1,4
1,3
B
8
A
9
1
2
10
4
2
3
3,1
3,4
3,3
3
A
B
1
5
5
7
6
6
7
4 0,3
0,1
3,4
3,1
2,2
8
9
10
0,4
0,2
B
8
A
9
1
?
2
10
4
8
3
3,1
3,4
3,3
5
5
9
2
3
A
B
1
6
7
4 0,3
0,1
3,4
3,1
2,2
8
9
10
0,4
0,2
7
6
B
A
10
Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung
Kapitel 5: Globalverdrahtung
67
Beispiel
Feststellung der
Verdrahtbarkeit
einer
Platzierung
1
2
3
5
6
7
A
B
4
1
2
3
3,1
3,4
3,3
5
6
7
4 1,4
1,1
3,4
3,1
3,3
8
9
10
1,4
1,3
B
8
A
9
1
2
10
4
2
3
3,1
3,4
3,3
3
A
B
1
5
5
7
6
6
7
4 0,3
0,1
3,4
3,1
2,2
8
9
10
0,4
0,2
B
8
A
9
1
2
10
4
2
3
2,0
2,3
3,3
3
5
A
B
1
5
6
7
4 0,2
0,0
2,3
2,0
2,2
8
9
10
0,3
0,2
7
6
B
8
9
A
10
Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung
Kapitel 5: Globalverdrahtung
68
Beispiel
Feststellung der
Verdrahtbarkeit
einer
Platzierung
1
2
3
5
6
7
A
B
4
B
8
A
9
1
10
2
3
6
7
A
B
4
5
B
8
9
A
10
Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung
Kapitel 5: Globalverdrahtung
69
5.6.3
Wegsuche mit dem Dijkstra-Algorithmus

Suche im Graphen nach einem optimalen Weg gemäß beliebiger
Wichtungskriterien

Gegeben sei ein Graph mit den Wichtungskriterien w1, w2, … als
Kantenkosten sowie ein Start- und ein Zielknoten

Die Wegkosten seien die Summe der Kantenkosten eines Pfades

Drei Mengen:
 Menge 1 enthält alle Knoten des Graphen, die im Verlauf des
Wegsucheprozesses noch nicht untersucht wurden
 Menge 2 enthält die Knoten, die zwar schon untersucht wurden, aber es
steht noch aus, ob die mit ihnen verbundenen Wegkosten vom Startknoten
aus optimal sind
 Menge 3 enthält die Knoten, bei denen der optimale Weg vom Startknoten
aus bereits ermittelt wurde

Ziel erreicht, wenn Zielknoten in Menge 3 auftaucht, anschließend
Rückverfolgung
Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung
Kapitel 5: Globalverdrahtung
70
5.6.3
Wegsuche mit dem Dijkstra-Algorithmus

Wesentliches Merkmal: eingeschränkte Indizierung der Knoten, da Knoten
nicht von allen Vorgängerknoten, sondern nur von Knoten mit besten
Wegkosten (optimaler Weg) indiziert werden

Vorteil: aus einer Menge von Wegen wird immer der bezüglich beliebig
vieler Optimierungskriterien optimale Weg gefunden
Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung
Kapitel 5: Globalverdrahtung
71
5.6.3
Wegsuche mit dem Dijkstra-Algorithmus
Ablauf
1. Der Startknoten wird in die Menge 3 eingeordnet und ist damit der aktuelle
Knoten.
2. Ermittlung eines Nachfolgers (Nachbarn) des aktuellen Knotens.
3. Gehört der Nachfolgerknoten schon zur Menge 3, dann weiter mit Schritt 7.
4. Bestimmung der Wegkosten (z.B. w1 und w2) bis zum Nachfolgerknoten (Addition
mit denen des aktuellen Knotens).
5. Ist der Nachfolgerknoten Element der Menge 1, Überführung desselben in die
Menge 2 und weiter mit Schritt 7.
6. Der Nachfolgerknoten befindet sich bereits in der Menge 2, es sind also schon
Wegkosten zum Nachfolgerknoten bekannt. Falls die neuen Wegkosten gemäß
den Optimierungskriterien besser als die alten sind, werden die alten durch die
neuen Wegkosten ersetzt; sonst sind die neuen wieder zu streichen.
Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung
Kapitel 5: Globalverdrahtung
72
5.6.3
Wegsuche mit dem Dijkstra-Algorithmus
Ablauf (2)
7. Wenn noch weitere Nachfolger (Nachbarn) des aktuellen Knotens existieren,
weiter mit Schritt 2.
8. Bestimmung eines Knotens aus der Menge 2, der die besten Wegkosten (z.B. w1
und w2) besitzt. Dieser Knoten geht in die Menge 3 über und stellt den neuen
aktuellen Knoten dar.
9. Wenn der aktuelle Knoten nicht der Zielknoten ist, weiter mit Schritt 2; ansonsten
ist der Zielknoten auf optimalem Weg (gemäß z.B. w1 und w2) erreicht.
10. Vom Zielknoten ausgehend, ist die Wegfindung innerhalb der Menge 3 mittels
Rückverfolgungsindex durchzuführen. ENDE.
Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung
Kapitel 5: Globalverdrahtung
73
5.6.3
VS
1
Wegsuche mit dem Dijkstra-Algorithmus: Beispiel
1,4
8,6
4
8,8
9,7
2
2,6
1,4
3,2
5
2,8
2,8
3
9,8
Gesucht ist der kostenminimale Weg
(Wegkosten (∑w1 + ∑w2)  min.) von
Vs (Knoten 1) zu Vz (Knoten 8).
7
8
VZ
4,5
6
3,3
9
Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung
Kapitel 5: Globalverdrahtung
74
VS
1
1,4
8,6
4
8,8
9,7
2
2,6
1,4
5
2,8
9,8
Menge 3
(1)
3,2
2,8
3
Menge 2
7
8
VZ
4,5
6
3,3
9
Aktueller Knoten: 1
Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung
Kapitel 5: Globalverdrahtung
75
1
1,4
4
8,8
7
Menge 2
N (2) 8,6
8,6
9,7
2
2,6
1,4
3,2
5
2,8
2,8
3
9,8
W (4) 1,4
8
3,3
(1)
W (4) 1,4
Angabe von Rückverfolgungsindex (Knoten) ∑w1, ∑w2
4,5
6
Menge 3
9
Aktueller Knoten: 1
Nachbarknoten: 2, 4
Beste Wegkosten in Menge 2: Knoten 4
Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung
Kapitel 5: Globalverdrahtung
76
VS
1
1,4
4
8,8
Menge 2
7
N (2) 8,6
8,6
9,7
2
2,6
1,4
3,2
5
2,8
2,8
3
9,8
W (4) 1,4
8
VZ
N (5) 10,11
W (7) 9,12
4,5
6
3,3
Menge 3
(1)
W (4) 1,4
N (2) 8,6
9
Angabe von Rückverfolgungsindex (Knoten) ∑w1, ∑w2
Aktueller Knoten: 4
Nachbarknoten: 1, 5, 7
Beste Wegkosten in Menge 2: Knoten 2
Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung
Kapitel 5: Globalverdrahtung
77
VS
1
1,4
4
8,8
Menge 2
7
N (2) 8,6
8,6
9,7
2
2,6
1,4
3,2
5
2,8
2,8
3
9,8
W (4) 1,4
8
VZ
4,5
6
3,3
Menge 3
(1)
N (5) 10,11
W (7) 9,12
W (4) 1,4
N (3) 9,10
W (5) 10,12
N (2) 8,6
9
N (3) 9,10
Angabe von Rückverfolgungsindex (Knoten) ∑w1, ∑w2
Aktueller Knoten: 2
Nachbarknoten: 1, 3, 5
Beste Wegkosten in Menge 2: Knoten 3
Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung
Kapitel 5: Globalverdrahtung
78
VS
1
1,4
4
8,8
Menge 2
7
N (2) 8,6
8,6
9,7
2
2,6
1,4
3,2
5
2,8
2,8
3
9,8
W (4) 1,4
8
VZ
4,5
6
3,3
Menge 3
(1)
N (5) 10,11
W (7) 9,12
W (4) 1,4
N (3) 9,10
W (5) 10,12
N (2) 8,6
W (6) 18,18
N (3) 9,10
9
Aktueller Knoten: 3
Nachbarknoten: 2, 6
Beste Wegkosten in Menge 2: Knoten 5
N (5) 10,11
Angabe von Rückverfolgungsindex (Knoten) ∑w1, ∑w2
Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung
Kapitel 5: Globalverdrahtung
79
VS
1
1,4
4
8,8
Menge 2
7
N (2) 8,6
8,6
9,7
2
2,6
1,4
3,2
5
2,8
2,8
3
9,8
W (4) 1,4
8
VZ
4,5
6
3,3
Menge 3
(1)
N (5) 10,11
W (7) 9,12
W (4) 1,4
N (3) 9,10
W (5) 10,12
N (2) 8,6
W (6) 18,18
N (3) 9,10
9
N (6) 12,19
Aktueller Knoten: 5
Nachbarknoten: 2, 4, 6, 8
Beste Wegkosten in Menge 2: Knoten 7
W (8) 12,19
N (5) 10,11
W (7) 9,12
Angabe von Rückverfolgungsindex (Knoten) ∑w1, ∑w2
Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung
Kapitel 5: Globalverdrahtung
80
VS
1
1,4
4
8,8
Menge 2
7
N (2) 8,6
8,6
9,7
2
2,6
1,4
3,2
5
2,8
2,8
3
9,8
W (4) 1,4
8
VZ
4,5
6
3,3
Menge 3
(1)
N (5) 10,11
W (7) 9,12
W (4) 1,4
N (3) 9,10
W (5) 10,12
N (2) 8,6
W (6) 18,18
N (3) 9,10
9
N (6) 12,19
Aktueller Knoten: 7
Nachbarknoten: 4, 8
Beste Wegkosten in Menge 2: Knoten 8
W (8) 12,19
N (8) 12,14
N (5) 10,11
W (7) 9,12
N (8) 12,14
Angabe von Rückverfolgungsindex (Knoten) ∑w1, ∑w2
Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung
Kapitel 5: Globalverdrahtung
81
VS
1
1,4
4
8,8
Menge 2
7
N (2) 8,6
8,6
9,7
2
2,6
1,4
3,2
5
2,8
2,8
3
9,8
W (4) 1,4
8
4,5
6
3,3
VZ
Menge 3
(1)
N (5) 10,11
W (7) 9,12
W (4) 1,4
N (3) 9,10
W (5) 10,12
N (2) 8,6
W (6) 18,18
N (3) 9,10
9
N (6) 12,19
Rückverfolgung
W (8) 12,19
N (8) 12,14
N (5) 10,11
W (7) 9,12
N (8) 12,14
Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung
Kapitel 5: Globalverdrahtung
82
VS
1
1,4
4
9,12
7
12,14
2
5
8
3
6
9
VZ
Kostenminimaler Weg VS – VZ mit
Wegkosten (12, 14) über die Knoten
1 – 4 – 7 – 8.
Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung
Kapitel 5: Globalverdrahtung
83
Zusammenfassung Kapitel 5 – Globalverdrahtung
5.1 Einführung
5.1.1 Allgemeines Verdrahtungsproblem
5.1.2 Globalverdrahtung
5.2 Begriffsbestimmungen
5.3 Optimierungsziele
5.3.1 Kundenspezifischer Entwurf
5.3.2 Standardzellen-Entwurf
5.3.3 Gate-Array-Entwurf
5.4 Abbildung von Verdrahtungsregionen
5.5 Ablauf der Globalverdrahtung
5.6 Algorithmen für die Globalverdrahtung
5.6.1 Steinerbaum-Verdrahtung
5.6.2 Globalverdrahtung im Verbindungsgraphen
5.6.3 Wegsuche mit dem Dijkstra-Algorithmus
Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung
Kapitel 5: Globalverdrahtung
84

PPT