4.4 Globalverdrahtung
4.4.1 Einführung4.4.1.1 Allgemeines Verdrahtungsproblem4.4.1.2 Globalverdrahtung
4.4.2 Begriffsbestimmungen
4.4.3 Optimierungsziele4.4.3.1 Kundenspezifischer Entwurf
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
1
4.4.3.1 Kundenspezifischer Entwurf4.4.3.2 Standardzellen-Entwurf4.4.3.3 Gate-Array-Entwurf
4.4.4 Abbildung von Verdrahtungsregionen
4.4.5 Ablauf der Globalverdrahtung
4.4.6 Algorithmen für die GlobalverdrahtungSteinerbaum-Verdrahtung
4.4.1.1 Allgemeines Verdrahtungsproblem
VerhaltensentwurfLogischer Entwurf
Floorplanning
ENTITY test isport a: in bit;
end ENTITY test;Partitionierung
Systemspezifikation
Architekturentwurf
Schaltungsentwurf
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
2
Layoutsynthese
Layoutverifikation
Chip
Platzierung
Verdrahtung
Kompaktierung
Herstellung
Verpackung/Test
4.4.1.1 Allgemeines Verdrahtungsproblem
CA
43
21
4
1
Netzliste:
Netze mit den durch sie jeweils zu verbindenden Bauelemente-Anschlüssen
N1 = {C4, D6, B3}
N2 = {D4, B4, C1, A4} NN NN
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
3
DB
3
4
1654
N2 = {D4, B4, C1, A4}
N3 = {C2, D5}
N4 = {B1, A1, C3}
N1N2 N3N4
HorizontaleVerdrahtungs-ebene
VertikaleVerdrahtungs-ebene
Via
Technologie-Informationen:
AbstandsregelnBreitenregeln usw.
4.4.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
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
4
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.
4.4.1.1 Allgemeines Verdrahtungsproblem
Flächen-verdrahtung
Global-verdrahtung
Fein-verdrahtung
Spezial-verdrahtung
Zweistufige Verdrahtung
Verdrahtungsverfahren
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
5
verdrahtungverdrahtung verdrahtung verdrahtung
Zuordnung derVerdrahtung zuVerdrahtungs-regionen(Kap. 4.4)
Verdrahtunginnerhalb derVerdrahtungs-regionen(Kap. 4.5)
Verdrahtungauf gesamter Layoutflächeohne vorherigeZuweisung(s. Literatur)
Verdrahtungder Versor-gungs- undTaktnetze(s. Literatur)
4.4.1.2 Globalverdrahtung
Bei der Globalverdrahtung werden ungefähreVerbindungswege auf einer Layoutoberflächefestgelegt.
Dies geschieht meist durch Zuweisung der Netzsegmente in sog. Verdrahtungsregionen
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
6
Netzsegmente in sog. Verdrahtungsregionenunter Berücksichtigung der jeweiligen Verdrahtungskapazitäten dieser Regionen.
4.4.1.2 Globalverdrahtung
CA
43
21
31
1
4
CA
43
21
4
1C
A
43
21
4
31
1
N1N2 N3N4
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
7
DB
3
4
1654
Globalverdrahtung
DB
3
4
1654
Feinverdrahtung
DB
3
4
1654
4.4.2 Begriffsbestimmungen
Kanal (Channel)
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
8
Standardzellenlayout (Zweilagen-Verdrahtung)
4.4.2 Begriffsbestimmungen
Verdrahtungskanal
Kanal (Channel)
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
9
Verdrahtungskanal
Verdrahtungskanal
Standardzellenlayout (Zweilagen-Verdrahtung)
4.4.2 Begriffsbestimmungen
2 2 2 23 34
Standard-zelle
Standard-zelle
Standard-zelle
Verdrahtungskanal
Kapazität (Capacity)
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
10
1 1 2 23 43
dpitchh
Standard-zelle
Standard-zelle
Standard-zelle
Verdrahtungskanal
Verdrahtungskanal
4.4.2 Begriffsbestimmungen
2 3
3
22
VertikalerKanal
HorizontalerHorizontalerKanal
Switchbox (Zweilagen-Verdrahtung)
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
11
1 23
21
2
VertikalerKanal
HorizontalerKanalKanal
4.4.2 Begriffsbestimmungen
2D- und 3D-Switchboxen3D-Switchbox: parallele Verdrahtungsfläche, z.B. Flip-Chip2D-Switchbox: von vier Seiten Anschlüsse
M5
M4
Pin auf der Unterseite einer 3D-Switchbox
2D- und 3D-Switchboxen
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
12
M3
M2
M1
3D-Switchbox
2D-Switchbox
Pin auf Kanalgrenze
Pin auf der Oberseiteeiner Zelle
Kanal
4.4.2 Begriffsbestimmungen
3
22 HorizontalerHorizontaler
2 3
T-Kreuzung (T-Junction, Zweilagen-Verdrahtung)
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
13
1 23
21
2
VertikalerAnschlusskanal
HorizontalerBasiskanal
HorizontalerBasiskanal
4.4.3.1 Optimierungsziele beim kundenspezi-fischen Entwurf
Festlegen der VerdrahtungsreihenfolgeZunächst Kanäle und Switchboxen bestimmenDanach Reihenfolge der Verdrahtung festlegen
B
A
C
D
E
B
A
C
D
E
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
14
H
V
A D H
F V
F
C E
H
B
A
B
FA
C
D
E
FA
1
2
3
4
54
3
251
4.4.3.2 Optimierungsziele beim Standard -zellen -Entwurf
A
A
Durchgangs-zellen
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
15
A
A
A
Variable Kanalhöhen(Zweilagen-Verdrahtung)
4.4.3.2 Optimierungsziele beim Standard -zellen -Entwurf
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
16
Steinerbaum mit minimalerVerbindungslänge
Steinerbaum mit minimalerAnzahl von Reihendurchquerungen
4.4.3.3 Optimierungsziele beim Gate-Array-Entwurf
Zellengrößen und deren Positionen fest vorgegebenZ.B. FPGA
Damit auch Kanal-Kapazitäten fest
Beispiel für nicht machbare Verdrahtung
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
17
Kanal-spuren
Nicht-verleg-baresNetz
4.4.4 Abbildung von Verdrahtungsregionen
Kanal-Verbindungsgraph
4
5
4
5
Kanal-Verbindungsgraph (Channel Connectivity Graph)
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
18
1 2 3 6
7
8
9 1 2 3 6
7
8
9
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.
4.4.4 Abbildung von Verdrahtungsregionen
Switchbox-Verbindungsgraph
1 4
5 9
11
12
1 4
5 9
11
12
Switchbox-Verbindungsgraph (Channel Intersection Graph)
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
19
2
3
6
7
8
10 13
14
2
3
6
7
8
10 13
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.
4.4.4 Abbildung von Verdrahtungsregionen
Gittergraph
1 2 3 4 5
6 7 8 9 10
1 2 3 4 5
6 7 8 9 10
Gittergraph (Grid Graph Model)
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
20
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25
11 12 13 14 15
16 17 18 19 20
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.
4.4.5 Ablauf der Globalverdrahtung
1. Festlegung der Verdrahtungsregionen (Region definition)
2. Zuordnung der Netze zu den Verdrahtungsregionen (Region assignment)
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
21
3. Evtl. Anschluss-Zuweisung (Pin assignment)
4.4.6 Algorithmen für die Globalverdrahtung
Sequentielle Netzbetrachtungz.B. Steinerbaum-VerdrahtungGlobalverdrahtung im Verbindungsgraphen und Dijkstra-Algorithmus, (Netze nacheinander verdrahten
Parallele Netzbetrachtung durch hierarchische Aufteilung (Hierarchical decomposition)
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
22
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
Stochastische Wegsuche-Algorithmenwie z.B. Simulated Annealing und evolutionäre Algorithmen
4.4.6 Algorithmen für die Globalverdrahtung
Sequentielle NetzbetrachtungMeisten Algorithmen zur Feinverdrahtung sind sequentiellDaher erforderlich Multi-Pin-Netze in Netzsegmente aufzuteilenDies muss vor der Feinverdrahtung geschehen -> Aufgabe der Globalverdrahtung
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
23
Sequentielle Netzbetrachtung gliedert sich in folgende Schritte
Steinerbaum-Verdrahtung bzw. Globalverdrahtung im Verbindungsgraphen und Dijkstra-Algorithmus
4.4.6.1 Steinerbaum -Verdrahtung
VorbemerkungenGegeben seien die p Pins eines Netzes auf einem HV-RasterEin Rasterbaum heißt rektilinearer Steinerbaum (RST), wenn er alle p Pins und beliebig viele Rasterpunkte als Knoten enthältKnoten des RST, die nicht Pins des Netzes sind, heißen
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
24
Knoten des RST, die nicht Pins des Netzes sind, heißen Steinerknoten
Pinknoten
B (2, 6)
A (2, 1)
C (6, 4)
Steinerknoten
S (2, 4)
4.4.6.1 Steinerbaum -Verdrahtung
Eigenschaften des minimalen rektilinearenSteinerbaums (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
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
25
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)
4.4.6.1 Steinerbaum -Verdrahtung
Beispiel minimaler rektilinearer Spanbaum und minimaler rektilinearer Steinerbaum
B (2, 6) B (2, 6)
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
26
A (2, 1)
C (6, 4)
A (2, 1)
C (6, 4)S (2, 4)
Minimaler rektilinearer Steinerbaum (MRST)
Minimaler rektilinearer Spannbaum
4.4.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
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
27
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
4.4.6.1 Steinerbaum -Verdrahtung
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
28
Hanan-Punkte ( ) Minimaler rektilinearerSteinerbaum
GitterlinienPinknoten
4.4.6.1 Steinerbaum -Verdrahtung
Für Globalverdrahtung mittels SteinerbäumeGroblayoutraster erforderlich
• Gittergraph-Modell anlegen
Standardzellen-Anordnung• Horizontale Gitterlinien verlaufen durch Zellenmitte• Vertikale Gitterlinien sollten Größe der horizontalen aufweisen
Kontaktpunkte im Zellenmittelpunkt
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
29
Kontaktpunkte im Zellenmittelpunkt
Globale Zellen Netzanschlüsse im Zellenmittelpunkt
Netzanschlüsse
4.4.6.1 Steinerbaum -Verdrahtung
Folgenden Schritte
A A
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
30
Steinerbaum-Anschluss-Punkte (Pinknoten)
Zugewiesene Verdraht-ungsregionen und Durchgangszellen
A A
A
A
A A A
A
A
A A
Minimaler rektilinearerSteinerbaum
Sequentieller Steinerbaum-Algorithmus
4.4.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
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
31
Bei mehr als vier Anschlüssen ist Ergebnis von suboptimaler Qualität
4.4.6.1 Steinerbaum -Verdrahtung
Ablauf 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)
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
32
2. Bestimmen des Anschlusses mit minimalem M-Abstand zur aktuellen MRST-Menge, Verbinden dieses Anschlusses durch minimale M-Pfade auf dem minimale umschreibenden Rechteck (es gibt höchstens zwei).
4.4.6.1 Steinerbaum -Verdrahtung
Falls der in Schritt 2 erzeugte M-Pfad im Steinerknoten einer von zwei MRST-Alternativen endet, Löschen der anderen (Eliminierung einer Masche im Graphen der MRST-Menge)
Falls noch nicht alle Anschlüsse abgearbeitet sind: Wenn mehr als zwei Maschen existierenLöschen von willkürlich einer MRST-Alternative und weiter mit Schritt 2.
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
33
mit Schritt 2. Andernfalls, d.h. alle Anschlüsse wurden abgearbeitet, Eliminieren aller noch vorhandenen Maschen durch Löschen je einer MRST-Alternative.
ENDE.
4.4.6.1 Steinerbaum -Verdrahtung : Beispiel
1
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
34
4.4.6.1 Steinerbaum -Verdrahtung : Beispiel
1
2
1Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
35
1
4.4.6.1 Steinerbaum -Verdrahtung : Beispiel
1
2
3
1Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
36
2
1
4.4.6.1 Steinerbaum -Verdrahtung : Beispiel
1
2
3 1
2
3
1 2Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
37
2 2
41 2
4.4.6.1 Steinerbaum -Verdrahtung : Beispiel
1
2
3 1
2
31
2
3
1 2 3Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
38
2 2
4
5
2
41 2 3
4.4.6.1 Steinerbaum -Verdrahtung : Beispiel
1
2
3 1
2
3
4
5
1
2
3
41 2 3
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
39
1
2
3
4
56
4
4.4.6.1 Steinerbaum -Verdrahtung : Beispiel
1
2
3 1
2
3
4
5
1
2
3
41 2 3
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
40
1
2
3
4
56
7
1
2
3
4
56
4 5
4.4.6.1 Steinerbaum -Verdrahtung : Beispiel
1
2
3 1
2
3
4
5
1
2
3
41 2 3
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
41
1
2
3
4
56
7
1
2
3
4
56
7
1
2
3
4
56
4 5 6
4.4.6.1 Steinerbaum -Verdrahtung : Beispiel
1
2
3 1
2
3
4
5
1
2
3
41 2 3
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
42
1
2
3
4
56
7
1
2
3
4
56
7
1
2
3
4
56
4 5 6
4.4.6.2 Globalverdrahtung im Verbindungs-graphen
Geht zurück auf Rothermel und Mlynski, 1983Berücksichtigt ungleichförmige Zellen/Bauelemente, daher für kundenspezifischen IC-Entwurf und MCMs geeignet
Ablauf (Übersicht):
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
43
Ablauf (Übersicht):
(1) Verdrahtungsregionen
1 2 3
4 5 6 7
8 9
10 11 12
B
A
B
A
(2) Graphendarstellung
1 2 3
4
2,2
4,2
1,2
2,7
4,2
1,2 1,2
5 68
4,2
7
2,2
4,2
9
10
4,2
1,5
11 12
(3) Wegsuche im Graphen
4
2,2
4,2
1,2
2,7
4,2
0,1 1,2
5 68
3,1
7
2,2
4,2
9
10
4,2
0,4
11 12
4.4.6.2 Globalverdrahtung im Verbindungs-graphen
1 2 3
4
5
6
7
8
9 1 2 3
4
5
6
7
8
9
Kanal-Verbin-dungs-graph
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
44
8 8
1
2
3
4
5
6
7
8
9
10
11
12
13
14
1
2
3
4
5
6
7
8
9
10
11
12
13
14
Switch-box-Verbin-dungs-graph
4.4.6.2 Globalverdrahtung im Verbindungs-graphen
Kanal-Verbindungsgraph
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
45 Switchbox-Verbindungsgraph
4.4.6.2 Globalverdrahtung im Verbindungs-graphen
Bestimmung der Verdrahtungsregionen
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
46
Horizontale Zellenkanten Vertikale Zellenkanten ZweidimensionalesKanalmodell
4.4.6.2 Globalverdrahtung im Verbindungs-graphen
Übertragung in Graphendarstellung
8 17 21 23
1
2
8
9
17
18
21 23
1
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
47
2
3
4
5
67
9
101112
131415
16
18
19
20 22
24
25
2627
3
4
5
6
7
10
11 12
13 14 15
16
19
20 22
24
25
26
27
4.4.6.2 Globalverdrahtung im Verbindungs-graphen
Horizontale und vertikale Verdrahtungskapazität eintragen
Horizontale Aufnahmekapazität der Region 1
Vertikale Aufnahmekapazität der Region 1
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
48
2
3
4
5
67
8
9
101112
13 1415
16
17
18
19
20
21
22
23
24
25
2627
1
2
3
4
5
6
7
8
9
10
11 12
13 14 15
16
17
18
19
20
21
22
23
24
25
26
27
1,2
2 Spuren
1 S
pur
1
4.4.6.2 Globalverdrahtung im Verbindungs-graphen
Ergebnis
8 17 21 23
1
2
8
9
17
18
21 231,2
2,2
1,3
2,3
1,1
2,1
1,11,4
1
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
49
2
3
4
5
67
9
101112
131415
16
18
19
20 22
24
25
2627
3
4
5
6
7
10
11 12
13 14 15
16
19
20 22
24
25
26
27
2,2
2,2
3,2
1,2
1,2
2,1
3,1
1,1
2,1
3,1 3,1
4,1
3,1
6,1
3,1
1,1
1,1
3,4
1,8
4.4.6.2 Globalverdrahtung im Verbindungs-graphen
Ablauf 1. Festlegen der Verdrahtungsregionen und Abbildung in einem Verbindungsgraphen2. Festlegen der Netzreihenfolge3. Anschluss-Reservierung für alle Netze4. Netzauswahl und Globalverdrahtung dieses Netzes:
• a) Aufheben der Anschluss-Reservierungen
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
50
• 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.
Beispiel 1
Globalverdrahtung derNetze A-A und B-B
l
1 2 3
4 5 6 7
89B
A
B
Aw
1 2 3
4
4,2
1,2
4,2
1,2 1,2
5 68
4,2
7
4,2
9
4,2
1,5
4.4.6.2 Globalverdrahtung im Verbindungs-graphen
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
51
10 11 12 2,2 2,7 2,2
10 11 12
Beispiel 1
Globalverdrahtung derNetze A-A und B-B
l
1 2 3
4 5 6 7
89
10 11 12
B
A
B
Aw
1 2 3
4
2,2
4,2
1,2
2,7
4,2
1,2 1,2
5 68
4,2
7
2,2
4,2
9
10
4,2
1,5
11 12
4.4.6.2 Globalverdrahtung im Verbindungs-graphen
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
52
B
AB
A
0,1
3,1
0,4
1 2 3
4
2,2
4,2
1,2
2,7
4,2
1,2
5 68
7
2,2
4,2
9
10
4,2
11 12
Beispiel 1
Globalverdrahtung derNetze A-A und B-B
l
1 2 3
4 5 6 7
89
10 11 12
B
A
B
Aw
1 2 3
4
2,2
4,2
1,2
2,7
4,2
1,2 1,2
5 68
4,2
7
2,2
4,2
9
10
4,2
1,5
11 12
B
A
A
1 2 3
4 1,2 0,1 1,2
5 6
3,1
7
4,24,2
0,4
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
53
AB
B
A
B
A
2,2
4,2
2,7
4,2
5 68
2,2
9
10 11 12
1
4 1,2 0,1
5 6
4,2
0,4
2 3
1,1
3,1
1,7
4,1
1,1
8
2,1
7
1,1
3,1
9
10
11 12
Beispiel 1
Globalverdrahtung derNetze A-A und B-B
l
4.4.6.2 Globalverdrahtung im Verbindungs-graphen
Ergebnis
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
54
1 2 3
4 5 6 7
89
10 11 12
B
A
B
Aw
B
A
B
A
1 2 3
3,1 3,4 3,3
1,4 1,1 1,4 1,3
3,4 3,1 3,3
45 6 7
8 9 10
B
AB
A
4 5 7
8
6
9 10
1 2 3
Beispiel 2
Feststellung der VerdrahtbarkeiteinerPlatzierung
AB
4 7
1 2 3
1 2 3
3,1 3,4 3,3
0,3 0,1 0,4 0,245 6 7
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
55
B
AB
A
4 5 7
8
6
9 10
1 2 3
?1 2 3
3,1 3,4 3,3
0,3 0,1 0,4 0,2
3,4 3,1 2,2
45 6 7
8 9 10
BA
4 5 7
8
6
9 10
0,3 0,1 0,4 0,2
3,4 3,1 2,2
4
8 9 10
1 2 3
3,1 3,4 3,3
1,4 1,1 1,4 1,3
3,4 3,1 3,3
45 6 7
8 9 10
B
AB
A
4 5 7
8
6
9 10
1 2 3Beispiel
Feststellung der VerdrahtbarkeiteinerPlatzierung
AB
4 7
1 2 3
1 2 3
3,1 3,4 3,3
0,3 0,1 0,4 0,245 6 7
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
56
B
AB
A
4 5 7
8
6
9 10
1 2 3
BA
4 5 7
8
6
9 10
0,3 0,1 0,4 0,2
3,4 3,1 2,2
4
8 9 10
1 2 3
2,0 2,3 3,3
0,2 0,0 0,3 0,2
2,3 2,0 2,2
45 6 7
8 9 10
B
AB
A
4 5 7
8
6
9 10
1 2 3Beispiel 2
Feststellung der VerdrahtbarkeiteinerPlatzierung
4.4.6.2 Globalverdrahtung im Verbindungs-graphen
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
57
B
AB
A
4 5 7
8
6
9 10
1 2 3
4.4.6.3 Finden kürzester Weg
Dijkstra-AlgorithmusS. Literatur Stud-on
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
58
4.5 Feinverdrahtung
4.5.1 Einführung
4.5.2 Begriffsbestimmungen
4.5.3 Horizontaler und vertikaler Verträglichkeitsgraph4.5.3.1 Horizontale Verträglichkeitsdarstellung
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
59
4.5.3.1 Horizontale Verträglichkeitsdarstellung4.5.3.2 Vertikale Verträglichkeitsdarstellung
4.5.4 Optimierungsziele
4.5.5 Algorithmen für die Kanalverdrahtung4.5.5.1 Left-Edge-Algorithmus
4.5.1 Einführung
VerhaltensentwurfLogischer Entwurf
ENTITY test isport a: in bit;
end ENTITY test;Partitionierung
Systemspezifikation
Architekturentwurf
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
60
Layoutsynthese
Layoutverifikation
Chip
Floorplanning
Platzierung
Verdrahtung
Kompaktierung
Herstellung
Schaltungsentwurf
Verpackung/Test
4.5.1 Einführung
Die Aufgabe der Feinverdrahtung besteht darin, die bei der Globalverdrahtung einer Verdrahtungsregion zugeordneten Netzsegmente in dieser Region detaillierte Verdrahtungswege und -ebenenzuzuweisen.
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
61
4.4.1.1 Allgemeines Verdrahtungsproblem
Flächen-verdrahtung
Global-verdrahtung
Fein-verdrahtung
Spezial-verdrahtung
Zweistufige Verdrahtung
Verdrahtungsverfahren
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
62
verdrahtungverdrahtung verdrahtung verdrahtung
Zuordnung derVerdrahtung zuVerdrahtungs-regionen(Kap. 4.4)
Verdrahtunginnerhalb derVerdrahtungs-regionen(Kap. 4.5)
Verdrahtungauf gesamter Layoutflächeohne vorherigeZuweisung(s. Literatur)
Verdrahtungder Versor-gungs- undTaktnetze(s. Literatur)
4.5.2 Begriffsbestimmungen
Kanal- und Switchbox-Verdrahtung
2 2 23 34
4
2
25
5
Vertikaler Kanal
Hor
izon
tale
rK
anal
5
2
4
2
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
63
1 1 2 23 3
Vertikaler Kanal
4.5.2 Begriffsbestimmungen
Anschluss-
Kanalverdrahtung Standardzellen-Reihe
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
64
Power Rail
Kanal
Anschluss-pin
4.5.2 Begriffsbestimmungen
Zellfläche
2 2 23 34
3-Ebenen-OTC-VerdrahtungOTC: Over the cell
2 2 23 34
2-Ebenen-Kanalverdrahtung
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
65
1 1 2 23 3
1 1 2 23 3 Zellfläche
Metal3
Via
Metal1
Metal2
4.5.2 Begriffsbestimmungen
Anschlussreihen (oben und unten) werden durch zwei Mengen gekennzeichnet, bei denen die Netznummer der jeweiligen Spaltenposition zugewiesen ist.Null markiert dabei ein nicht angeschlossenes Pin.Anschlüsse mit der gleichen Nummer sind Anschlüsse des gleichen Netzes und miteinander zu verbinden.Oft werden zur Anschlusskennzeichnung Vektoren TOP(k)
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
66
und BOT(k) benutzt, welche die Gitterpositionen an der Ober- (TOP) und Unterseite (BOT) des Kanals in der Spalte k repräsentieren.
• Beispiel:
− TOP = [0,2,4,5,2,6] bzw. TOP(1) = 0, TOP(2) = 2, …
− BOT = [1,3,5,3,5,1] bzw. BOT(1) = 1, BOT(2) = 3, …
0 2 4 5 2 6
1 3 5 3 5 1
4.5.2 Begriffsbestimmungen
Spalten
Kan
albr
eite
2 2 23 34
a b c d e f g
1Vertikales Segment(Zweigsegment, Branch)
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
67
Spuren, Zeilen
Kan
albr
eite
1 1 2 23 3
2
3
Pinanschlüsse
Horizontales Segment(Stammsegment, Trunk)
(Zweigsegment, Branch)
4.5.2 Begriffsbestimmungen
Annahme: eine Ebene für die horizontale Verdrahtung. Sollten zwei horizontale Segmente verschiedener Netze keine Spalten-Überlappung haben, also nicht denselben Horizontalbereich beanspruchen, so können sie auf gleicher Spur platziert werden und sind damit „horizontal verträglich“. Ansonsten sind für beide Netze unterschiedliche Spuren zu reservieren.
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
68
Horizontale Verträglichkeit
1
1
2
2
4.5.2 Begriffsbestimmungen
1 23
Horizontal nichtverträglich
Horizontale Verträglichkeit
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
69
1 2 3
Horizontal verträglich
4.5.2 Begriffsbestimmungen
Sollte nur eine vertikale Ebene zur Verfügung stehen, so dürfen sich zwei Netze nicht auf einer vertikalen Spalte überlappen. Der von „oben“ kommende Anschluss muss also rechtzeitig „aufhören“, um sich mit dem von „unten“ kommenden nicht zu überlagern. Das horizontale Segment eines Netzes, welches am oberen Anschluss einer Spalte angeschlossen ist, muss über dem
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
70
Anschluss einer Spalte angeschlossen ist, muss über dem horizontalen Segment eines Netzes liegen, welches mit dem unteren Anschluss dieser Spalte verbunden ist.
Vertikale Verträglichkeit2
12
1
4.5.2 Begriffsbestimmungen
211 2
1 2
Vertikale Verträglichkeit
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
71
Vertikal nicht verträglich
2 1
Vertikalverträglich
2 12 1
4.5.3 Horizontaler und vertikaler Verträglichkeitsgraph
Jedes Kanalverdrahtungsproblem Mittels zweier Verträglichkeitsgraphen modellierbarDiese bilden horizontale und vertikale Verträglichkeit ab
Damit vor Beginn der eigentlichen Kanalverdrahtung die minimale benötigte Spuranzahl und die eventuelle Konfliktsituationen
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
72
die eventuelle Konfliktsituationen
vorhersehbar
Beide Graphen steuern bei einigen AlgorithmenVerdrahtungsreihenfolge und Verdrahtungsanordnung
4.5.3.1 Horizontale Verträglichkeitsdarstellung
Das horizontale Segment eines Netzes wird durch den äußeren linken und rechten Netzpunkt festgelegt.S(k) sei die Menge der Netze, deren horizontale Segmente die Vertikalspalte k schneiden. Jedes S(k) enthält die Netze, die in Spalte k
• nach oben und unten angeschlossen werden und • die Netze, deren Anschlüsse links und rechts von k liegen und
damit die Spalte k schneiden.
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
73
damit die Spalte k schneiden.
1 3 5 3 5 1 6 8 8 70
0 2 4 5 2 76 0 4 0 0
Spalte a b c d e f g h i j l
S(b) = {1, 2, 3}
4.5.3.1 Horizontale Verträglichkeitsdarstellung
Da sich die horizontalen Segmente verschiedener Netze nicht überlagern dürfen, ist es nicht erlaubt, zwei Netze aus S(k) in der Spalte k auf der gleichen Horizontalspur zu platzieren.Diese Bedingung muss in jeder Vertikalspalte eingehalten werden.Minimale Spuranzahl des Kanals = maximale Mengengröße S(k) (k = a, b,…)
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
74
S(k) (k = a, b,…)
0 2 4 5 2 76 0 4 0 0
1 3 5 3 5 1 6 8 8 70
Spalte a b c d e f g h i j l
S(b) = {1, 2, 3}
4.5.3.1 Horizontale Verträglichkeit: Zonendarstellung
0 2 4 5 2 76 0 4 0 0
1 3 5 3 5 1 6 8 8 70
Spalte a b c d e f g h i j l
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
75
21
34
56
78
0 2 4 5 2 76 0 4 0 0
1 3 5 3 5 1 6 8 8 70
4.5.3.1 Horizontale Verträglichkeit: Zonendarstellung
S(c) S(f) S(g) S(i)
0 2 4 5 2 76 0 4 0 0
1 3 5 3 5 1 6 8 8 70
Spalte a b c d e f g h i j l
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
76
21
34
5
78
S(c) S(f) S(g) S(i)
0 2 4 5 2 76 0 4 0 0
1 3 5 3 5 1 6 8 8 70
6
4.5.3.1 Horizontale Verträglichkeit: Zonendarstellung
S(c) S(f) S(g) S(i)
0 2 4 5 2 76 0 4 0 0
1 3 5 3 5 1 6 8 8 70
Spalte a b c d e f g h i j l
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
77
21
34
5
78
S(c) S(f) S(g) S(i)
S(c) S(f) S(g) S(i)1234
67
8
5
0 2 4 5 2 76 0 4 0 0
1 3 5 3 5 1 6 8 8 70
6
4.5.3.1 Horizontale Verträglichkeit: Zonendarstellung
0 2 4 5 2 76 0 4 0 0
1 3 5 3 5 1 6 8 8 70
Spalte a b c d e f g h i j l
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
78
S(c) S(f) S(g) S(i)1234
67
8
5
Minimale Spuranzahl des Kanals = 5
4.5.3.1 Horizontale Verträglichkeit: Graphendarstellung
1 7
0 2 4 5 2 76 0 4 0 0
1 3 5 3 5 1 6 8 8 70
Spalte a b c d e f g h i j l
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
79
5
3
4
2
6
8 S(c) S(f) S(g) S(i)1234
67
8
5
4.5.3.2 Vertikale Verträglichkeitsdarstellung
In einem vertikalen Verträglichkeitsgraphen repräsentiert ein Knoten i ∈ V das Netz i.Eine gerichtete Kante bzw. ein gerichteter Pfad zwischen
• den Knoten i und j • Dann liegen Anschlusspin des Netzes i auf der oberen
Kanalkante (TOP) sowie das Anschlusspin des Netzes j auf der unteren Kanalkante (BOT) auf gleicher Spaltenposition
Damit muss das horizontale Segment des Netzes i über dem
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
80
Damit muss das horizontale Segment des Netzes i über dem des Netzes j liegen, damit keine vertikale Überlappung in der betreffenden Anschlussspalte entsteht.
2
1
1
2
4.5.3.2 Vertikale Verträglichkeitsdarstellung
0 2 4 5 2 76 0 4 0 0
1 3 5 3 5 1 6 8 8 70
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
81
2
5
3
4
1
6
7
8Vertikaler Verträglichkeitsgraph (Vertical Constraint Graph, VCG)
4.5.3.2 Vertikale Verträglichkeitsdarstellung
1 2 2
1
1 2 2
Netzaufsplittung
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
82
2 0 12
2 1Zyklischer Konflikt
Netzaufsplittung
4.5.3.2 Vertikale Verträglichkeitsdarstellung
Schlussfolgerungen aus horizontaler (HCG) und vertikaler Verträglichkeitsdarstellung (VCG)
Der HCG gibt die minimal benötigte Spuranzahl an
Diese Spuranzahl ist aber nur realistisch, sollte der VCG keine Schleifen enthalten
Sollte der VCG keine Schleifen enthalten, dann kann jedes
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
83
Sollte der VCG keine Schleifen enthalten, dann kann jedes Netz mit einem horizontalen Segment verdrahtet werden (keine Netzaufsplittungen)
Die Zuordnung der horizontalen Segmente zu den einzelnen Spuren ergibt sich aus dem VCG, da nur so Überlappungen bei den vertikalen Anschluss-Segmenten vermieden werden
Die Belegung einer Spur mit mehreren Netzen ergibt sich aus dem HCG, da dieser horizontal nicht-überlappende Netze angibt
4.5.5.1 Left-Edge-Algorithmus
AblaufAufbau des VCG und HCG (Zonendarstellung)Aktuelle Spur j = 1 (obere Spur)Für aktuelle Spur j
• Für alle Netze ohne Vorgänger im VCG, Platzierung des am weitesten links liegenden Netzes in der Zonendarstellung auf Spur j und anschließend weitere nicht-überlappende (lt.
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
84
Spur j und anschließend weitere nicht-überlappende (lt. Zonendarstellung) und vorgängerlose Netze (lt. VCG)
• Löschen aller platzierten Netze im VCG und in der Zonendarstellung
Aktuelle Spur j = j + 1. Falls noch Netze im VCG vorhanden sind, weiter mit Schritt 3ENDE.
4.5.5.1 Left-Edge-Algorithmus: Beispiel
0 1 4 5 1 76 0 4 9 10 10
2 3 5 3 5 2 6 8 9 8 7 9
1. Aufbau des VCG und HCG (Zonendarstellung)
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
85
1
5
3
104
2
6
7
8
9
1 7
2 8
3 9
4 10
5 6
4.5.5.1 Left-Edge-Algorithmus: Beispiel
1 7
2 8
3 9
4 10
5 6
5
3
4
6
7
8
9
101
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
86
2. Aktuelle Spur j = 1 (obere Spur)
3. Für aktuelle Spur j
a) Für alle Netze ohne Vorgänger im VCG, Platzierung des am weitesten links liegenden Netzes in der Zonendarstellung auf Spur j und anschließend weitere nicht-überlappende und vorgängerlose Netze
Spur j = 1: Netz 10Netz 1
2
3. b) Löschen aller platzierten Netze (1, 10) in VCG und Zonendarstellung
4.5.5.1 Left-Edge-Algorithmus: Beispiel
5
3
4
6
7
8
9
7
8
3 9
4
5 6
2
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
87
3. Für aktuelle Spur j
a) Für alle Netze ohne Vorgänger im VCG, Platzierung des am weitesten links liegenden Netzes in der Zonendarstellung auf Spur j und anschließend weitere nicht-überlappende und vorgängerlose Netze
Spur j = 2:
Aktuelle Spur j = j + 1, falls noch Netze in VCG, weiter mit 3.
2
Netz 4
3. b) Löschen aller platzierten Netze (4) in VCG und Zonendarstellung
4.5.5.1 Left-Edge-Algorithmus: Beispiel
5
3 6
7
8
9
7
8
3 9
5 6
2
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
88
3. Für aktuelle Spur j
a) Für alle Netze ohne Vorgänger im VCG, Platzierung des am weitesten links liegenden Netzes in der Zonendarstellung auf Spur j und anschließend weitere nicht-überlappende und vorgängerlose Netze
Spur j = 3:
Aktuelle Spur j = j + 1, falls noch Netze in VCG, weiter mit 3.
2
Netz 5 Netz 7
3. b) Löschen aller platzierten Netze (5, 7) in VCG und Zonendarstellung
4.5.5.1 Left-Edge-Algorithmus: Beispiel
3 68
98
3 9
6
2
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
89
3. Für aktuelle Spur j
a) Für alle Netze ohne Vorgänger im VCG, Platzierung des am weitesten links liegenden Netzes in der Zonendarstellung auf Spur j und anschließend weitere nicht-überlappende und vorgängerlose Netze
Spur j = 4:
Aktuelle Spur j = j + 1, falls noch Netze in VCG, weiter mit 3.
2
Netz 3 Netz 6 Netz 9
3. b) Löschen aller platzierten Netze (3, 6, 9) in VCG und Zonendarstellung
4.5.5.1 Left-Edge-Algorithmus: Beispiel
2
8
2 8
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
90
3. Für aktuelle Spur j
a) Für alle Netze ohne Vorgänger im VCG, Platzierung des am weitesten links liegenden Netzes in der Zonendarstellung auf Spur j und anschließend weitere nicht-überlappende und vorgängerlose Netze
Spur j = 5:
Aktuelle Spur j = j + 1, falls noch Netze in VCG, weiter mit 3.
2
Netz 2 Netz 8
3. b) Löschen aller platzierten Netze (2, 8) in VCG und Zonendarstellung
4.5.5.1 Left-Edge-Algorithmus: Beispiel
Verdrahtungsergebnis
0 1 4 5 1 76 0 4 9 10 10
j = 1
2
3
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
91
2 3 5 3 5 2 6 8 9 8 7 9
4
5
4.5.5.2 Left-Edge-Algorithmus -Zusammenfassung
ZusammenfassungEinfache HeuristikNachteil: erfordert schleifenfreien VCG, also keine vertikalen zyklischen Anschlusskonflikte
1
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
92
1 2
2 0 1
1
2
0
4.5.5.2 Left-Edge-Algorithmus -Zusammenfassung
Verdrahtungsregionen werden als Kanäle bezeichnet, sofern die Netzanschlüsse an zwei gegenüberliegenden Seiten angeordnet sind, und als Switchboxen, wenn sich Anschlüsse an allen vier Seiten befinden
Klassische Kanaldefinition verliert aufgrund
Vorlesung Einführung in ASIC-DesignWS 2009/10
Prof. Dr.-Ing.Dietmar Fey
LehrstuhlInformatik 3 -Rechnerarchitektur
93
Klassische Kanaldefinition verliert aufgrund Ebenenzunahme an Bedeutung
Mehrlagen (Multilayer)-Verdrahtung oftmals mit zellenunabhängigen Verdrahtungsbereichen (Verdrahtungsregion, Tile, Box usw.)