Post on 05-Apr-2015
transcript
1Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 1: Einführung
Gliederung Kapitel 1 – Einführung
1.1 Entwurfsautomatisierung in der Elektronik (EDA)
1.2 Hinweise
1.3 Bedeutung der Entwurfsautomatisierung
1.4 Entwicklung der Entwurfsautomatisierung
1.5 Übersicht über den Entwurfsprozess
1.6 Entwurfsstile
1.7 Layoutebenen
1.8 Entwurfsregeln
1.9 Layoutsynthese als Optimierungsproblem
1.10 Rechenkomplexität der Layoutsynthese
1.11 Einteilung von Entwurfsalgorithmen
1.12 Lösungsqualität von Entwurfsalgorithmen
1.13 Graphentheoretische Grundbegriffe
1.14 Häufig verwendete Layoutbegriffe
2Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 1: Einführung
1.1 Entwurfsautomatisierung in der Elektronik (EDA)
Entwicklung von Methoden, Algorithmen und Datenstrukturen zur Automatisierung des Entwurfs elektronischer Baugruppen (Schaltkreise, Hybridbaugruppen, Leiterplatten)
Einsatz von Computerprogrammen (Software) beim Entwurf einer elektronischen Baugruppe
Entwurfsautomatisierung = Electronic Design Automation (EDA):
3Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 1: Einführung
1.1 Entwurfsautomatisierung in der Elektronik (EDA)
Herausbildung der EDA-Industrie in den 80er und 90er Jahren, heutiger geschätzter Jahresumsatz 4 Milliarden US-Dollar
Bedeutendste EDA-Firmen (2006): Cadence, Synopsys, Mentor
Wichtige Konferenzen:– Design, Automation and Test in Europe (DATE)
– Design Automation Conference (DAC)
– International Conference on Computer-Aided Design (ICCAD)
– PCB Design Conference West/East
4Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 1: Einführung
1.2 Hinweise
Behandlung von Algorithmen zur Automatisierung der Layoutsynthese (von der Netzliste bis zum fertigen, optimierten Layout), also „Wie funktionieren Programme zum Entwurf einer elektronischen Baugruppe? Wie werden diese Programme erstellt, wie kann man sie modifizieren?“
Überwiegend Methoden der Layoutsynthese von digitalen Schaltungen, da höherer Automatisierungsgrad als bei analogen Schaltungen
Berücksichtigung aller Hierarchie-Ebenen von elektronischen Baugruppen (Schaltkreise, Multichip-Module, Leiterplatten), jedoch Fokusierung auf den Schaltkreis-Bereich
5Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 1: Einführung
1.2 Hinweise
T. Lengauer: „Combinatorial Algorithms for Integrated Circuit Layout“, B. G. Teubner Stuttgart, 1990
S. M. Sait, H. Youssef: „VLSI Physical Design Automation“, World Scientific Publishing Co. Pte. Ltd., 1999, 2001
N. Sherwani: „Algorithms for VLSI Physical Design Automation (Third Edition)“, Kluwer Academic Publishers, 1999, 2003
S. H. Gerez: „Algorithms for VLSI Design Automation“, John Wiley and Sons, 1999, 2000
Literatur
J. Lienig: „Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung“, Springer Verlag, 2006
Weiterführende Literatur
6Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 1: Einführung
1.3 Bedeutung der Entwurfsautomatisierung: Moore‘s Law
Que
lle:
Moo
re:
„Cra
mm
ing
more
com
ponents
onto
inte
gra
ted
cir
cuit
s" E
lect
roni
cs,
Vol
. 38
, N
o. 8
, 19
65
Moore’s Law
1965 stellte Gordon Moore (Fairchild) fest, dass sich die Anzahl der Transistoren in einer integrierten Schaltung alle 12 Monate verdoppelt. 10 Jahre später präzisierte er seine Aussagen dahingehend, dass diese Verdopplung aller 18 Monate eintritt, was als Moore’s Law in die Geschichte einging.
7Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 1: Einführung
1.3 Bedeutung der Entwurfsautomatisierung: Entwurfsschere
1981
1983
1985
1987
1989
1991
1993
1995
1997
1999
2001
2003
2005
2007
2009
10 000
1 000
100
10
1
0.1
0.01
0.001
100 000
10 000
1 000
100
10
1
0.1
0.01
Potential Design Complexity and Designer Productivity
Des
ign
Co
mp
lex
ity
Lo
gic
Tra
ns
isto
rs p
er
Ch
ip(M
illio
n)
Des
ign
er P
rod
uct
ivit
y(1
000
) T
ran
s./S
taff
- M
on
th
Logic Tr./ChipTr./Staff-Month
Equlvalent Added Complexity
58% Yr. compoundedComplexity growth rate
21% Yr. compoundProductivity growth rate
Nac
h S
IA R
oadm
ap
8Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 1: Einführung
EDA-Firmen: Software-Entwickler (Tool-Entwickler)
Entwicklung von Strategien, Algorithmen sowie Software zur Erstellung und
Weiterentwicklung von Entwurfswerkzeugen
Firmen der Elektrotechnik/Elektronik: – CAD-Tool-Manager in einer Unterstützungsabteilung (Tool-Support) für den
IC/LP-Entwurf
– Anwender eines CAD-Tools (z.B. in einer Entwicklungsabteilung für den
Schaltkreisentwurf)
Entwicklung von Strategien, Algorithmen und Software zur Anpassung der kommerziell erworbenen Entwurfswerkzeuge an die konkreten Aufgabenstellungen innerhalb der Firma
1.3 Bedeutung der Entwurfsautomatisierung
Notwendigkeit von EDA-Kenntnissen
9Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 1: Einführung
1.4 Entwicklung der Layoutsynthese
Zeitraum Entwurfswerkzeuge
1950 bis 1965 Manueller Entwurf
1965 bis 1975 Layout-Editoren, erste Platzierungs- und Verdrahtungswerkzeuge bei LPs
1975 bis 1985 Ausgereifte Platzierungswerkzeuge (IC, LP), detaillierte Herausbildung von Entwurfsschritten, Entwicklung von Algorithmen für alle Entwurfsschritte
1985 bis 1990 Erste „Performance-Driven“-Entwurfswerkzeuge, Entwicklung von Parallelalgorithmen für den Layoutentwurf, Ausreifen der den Algorithmen zugrunde liegenden Theorien (Graphentheorie, Lösungskomplexität usw.)
1990 bis 2000 Erste „Over-the-Cell“ (OTC)-Verdrahtung, 3D- bzw. Mehrlagen-Entwurf (insbesondere Verdrahtung) gewinnt schnell an Dominanz, Ausreifen der Schaltungssynthese, verdrahtungszentrierter Entwurf und Modellierung erlangen Bedeutung, Parallelisierung der Entwurfsschritte
2000 bis heute Aufkommen des fertigungszentrierten Entwurfs (DFM, Design for manufacturability), Strukturbreiten unterhalb der Lichtwellenlänge zwingen zu Optical Proximity Correction (OPC) und anderen Layoutmodifikationen, Reuse-orientierter Entwurf, d.h. verstärkte Wiederverwendung von entwickelten und erprobten Schaltungsmodulen, Einsatz von IP-Modulen (IP: Intellectual property)
10Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 1: Einführung
Kapitel 1 – Einführung
1.1 Entwurfsautomatisierung in der Elektronik (EDA)
1.2 Hinweise
1.3 Bedeutung der Entwurfsautomatisierung
1.4 Entwicklung der Entwurfsautomatisierung
1.5 Übersicht über den Entwurfsprozess
1.6 Entwurfsstile
1.7 Layoutebenen
1.8 Entwurfsregeln
1.9 Layoutsynthese als Optimierungsproblem
1.10 Rechenkomplexität der Layoutsynthese
1.11 Einteilung von Entwurfsalgorithmen
1.12 Lösungsqualität von Entwurfsalgorithmen
1.13 Graphentheoretische Grundbegriffe
1.14 Häufig verwendete Layoutbegriffe
11Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 1: Einführung
1.5 Übersicht über den Entwurfsprozess
VerhaltensentwurfLogischer Entwurf
Layoutsynthese
Layoutverifikation
Chip
ENTITY test isport a: in bit;
end ENTITY test;
Herstellung
Systemspezifikation
Architekturentwurf
Schaltungsentwurf
Verpackung/Test
12Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 1: Einführung
1.5 Übersicht über den Entwurfsprozess
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
13Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 1: Einführung
1.5.5 Layoutsynthese
Layoutsynthese
Floorplanning
Platzierung
Verdrahtung
Kompaktierung
Partitionierung
Überführung einer Netzliste unter Nutzung von Technologie- und Bibliotheksinformationen in die reale geometrische Abbildung einer Schaltung
14Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 1: Einführung
1.5.5 Layoutsynthese
Gegeben sei eine Menge von Zellen/Bauelementen und eine Menge von Verbindungen zwischen ihnen (Netzliste) sowie technologische und Zellen/Bauelemente-Informationen
Gesucht ist eine optimierte Platzierung der Zellen/Bauelemente und die Ausführung der Verbindungen zwischen ihnen (Verdrahtung) unter Beachtung von Randbedingungen und Optimierungszielen
Überführung einer Netzliste unter Nutzung von Technologie- und Bibliotheksinformationen in die reale geometrische Abbildung einer Schaltung
Bibliothek
15Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 1: Einführung
1.5.5 Layoutsynthese: Digitalentwurf
16Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 1: Einführung
1.5.5 Layoutsynthese: Analogentwurf
17Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 1: Einführung
1.5.5 Layoutsynthese: Leiterplattenentwurf
18Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 1: Einführung
Kapitel 1 – Einführung
1.1 Entwurfsautomatisierung in der Elektronik (EDA)
1.2 Hinweise
1.3 Bedeutung der Entwurfsautomatisierung
1.4 Entwicklung der Entwurfsautomatisierung
1.5 Übersicht über den Entwurfsprozess
1.6 Entwurfsstile
1.7 Layoutebenen
1.8 Entwurfsregeln
1.9 Layoutsynthese als Optimierungsproblem
1.10 Rechenkomplexität der Layoutsynthese
1.11 Einteilung von Entwurfsalgorithmen
1.12 Lösungsqualität von Entwurfsalgorithmen
1.13 Graphentheoretische Grundbegriffe
1.14 Häufig verwendete Layoutbegriffe
19Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 1: Einführung
1.6 Entwurfsstile
Kundenspezifischer Entwurfsstil (Full-custom approach)
Standardisierter Entwurfsstil (Semi-custom approach)
– Zellenbasierter Entwurf, wie der Standardzellen- und Makrozellen-Entwurf
– Arraybasierter Entwurf, wie der Entwurf von Gate-Arrays bzw. Field Programmable Gate-Arrays (FPGAs)
20Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 1: Einführung
1.6.1 Kundenspezifischer Entwurf: Layouteditor
Drawing Tools
Layer Palette
Mouse Buttons Bar
Layout Windows
ToolbarMenu Bar
Status Bar
Cell Browser
Locator
Text Windows
21Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 1: Einführung
1.6.2 Standardzellen-Entwurf
IN OUT
0 1
1 0
1 0
1 1
OR INV NORNANDAND
IN1 IN2 OUT
0 0 0
1 0 0
0 1 0
1 1 1
IN1 IN2 OUT
0 0 0
1 0 1
0 1 1
1 1 1
IN1 IN2 OUT
0 0 1
1 0 0
0 1 0
1 1 0
IN1 IN2 OUT
0 0 1
1 0 1
0 1 1
1 1 0
22Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 1: Einführung
Kontakt
Vdd
GND
OUT
IN2
p-Kanal-Transistor
n-Kanal-Transistor
Metallebene
Polyebene
IN1OUT
IN2
IN1
OUTIN1
Vdd
GND
IN2
Diffusionsschicht
23Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 1: Einführung
Power (Vdd)-Rail
Ground (GND)-Rail
Kontakt
Vdd
GND
OUT
IN2
p-Kanal-Transistor
n-Kanal-Transistor
Metallebene
Polyebene
IN1OUT
IN2
IN1
OUTIN1
Vdd
GND
IN2
Diffusionsschicht
24Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 1: Einführung
1.6.2 Standardzellen-Entwurf
A
A‘
Durchgangszelle
Padzelle
Versorgungspad(Masse, Ground)
GND
Vdd
Standard-zellen
Verdrahtungs-kanäle
25Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 1: Einführung
1.6.3 Makrozellen-Entwurf
GND
Vdd
PLARAM
Standardzellenblock
RAM
PLA
Verdrahtungs-bereiche
Versorgungspad(Masse, Ground)
Padzelle
26Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 1: Einführung
1.6.4 Gate-Array-Entwurf
GND
Vdd
Switchbox
Versorgungspad(Masse, Ground)
Vertikaler Kanal
Horizontaler Kanal
Padzelle
27Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 1: Einführung
1.6.4 Gate-Array-Entwurf: FPGA
LB LB LB
SB SB
LB LB LB
SB SB
LB LB LB
LB LB LB
SB SB
LB LB LB
SB SB
LB LB LB
LB LB
SB SB
LB LB LB
SB SB
LB LB LB
Zelle, logischer Block
Switchbox
28Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 1: Einführung
1.6.4 Gate-Array-Entwurf: FPGA
LB LB LB
SB SB
LB LB LB
SB SB
LB LB LB
LB LB LB
SB SB
LB LB LB
SB SB
LB LB LB
LB LB
SB SB
LB LB LB
SB SB
LB LB LB
Zelle, logischer Block
Switchbox Verbindung
LB
29Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 1: Einführung
1.7 Layoutebenen
Kontakt (contact cut)
Metal1 (metal1)
Polyebene (polysilicon)
Diffusionsschicht (p/n diffusion)
Vdd
GND
Via (via)
Metal2 (metal2)
Inverter-Zelle
Externe Anschluss- verdrahtung
30Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 1: Einführung
1.8 Entwurfsregeln
Minimale Weite a
Minimaler Abstand b c d
Minimale Überlappung e
a
b
e
d
c
Minimale Weitenregeln (Minimum width)
Minimale Abstandsregeln (Minimum separation)
Minimale Überlappungsregeln (Minimum overlap)
Lambda
31Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 1: Einführung
1.9 Layoutsynthese als Optimierungsproblem
Layoutentwurf ist komplexes Optimierungsproblem mit verschiedenen Optimierungszielen, wie z.B. minimale Chipfläche A und minimale Verbindungslänge L
Optimierungsziele stehen häufig in Konkurrenz zueinander und sind mathematisch schwer fassbar, daher Abbildung als Zielfunktion (Kostenfunktion), wobei die einzelnen Ziele gewichtet eingehen, z.B.Z = w1 * A + w2 * L
w1 und w2 sind Wichtungsfaktoren
32Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 1: Einführung
1.9 Layoutsynthese als Optimierungsproblem
Bei der Layoutsynthese sind Randbedingungen einzuhalten
Technologische Randbedingungen werden aus der zur Herstellung benutzten Technologie und deren Grenzwerten abgeleitet (technologisch bedingte Abstands-, Breiten- und Überlappungsregeln)Beispiel: Minimale Breiten- und Abstandswerte
Elektrische Randbedingungen gewährleisten das angestrebte elektrische Verhalten der Baugruppe (auch funktionale Randbedingungen genannt)Beispiel: Maximal erlaubte Signalverzögerung einer Verbindung
Entwurfsmethodische Randbedingungen werden eingeführt, um die Komplexität bzw. den Schwierigkeitsgrad des Entwurfs abzumildern (auch geometrische Randbedingungen genannt)Beispiel: Vorzugsrichtungen für die Verdrahtung
33Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 1: Einführung
Probleme der Layoutsynthese gehören zur Klasse der NP-harten Probleme:
Aufgrund der Komplexität des Entwurfsproblems und der damit verbundenen sehr großen Rechenzeiten können mit deterministischen Algorithmen keine optimalen Lösungen zeiteffektiv gefunden werden.
Beispiel: Platzierung von n Bauelementen derart hintereinander, dass die Gesamtverbindungslänge minimiert wird– Lösungsraum besteht aus n! Möglichkeiten– Wenn 1 µs pro Platzierungsermittlung benötigt wird, wären bei n = 20
Bauelementen 77 147 Jahre Rechenzeit nötig, um durch Einbeziehung aller Lösungen das Optimum zu ermitteln!
1.10 Rechenkomplexität der Layoutsynthese
34Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 1: Einführung
Ausweg: Nutzung von heuristischen Algorithmen, die dem globalen Optimum möglichst nahe kommen.
Im Gegensatz zu einem „Brute-Force“-Algorithmus, der die beste aller denkbaren Lösungsmöglichkeiten anstrebt, sucht ein heuristischer Algorithmus unter Einbeziehung von möglichst intelligenten Methoden (Hilfswissen) nur einen Teil des Lösungsraumes ab.
Dabei kommt es darauf an, ein hinreichend gutes, nicht notwendig optimales Ergebnis in akzeptabler Zeit zu finden.
1.10 Rechenkomplexität der Layoutsynthese
35Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 1: Einführung
1.11 Einteilung von Entwurfsalgorithmen
Aufgabe
Konstruktiver Algorithmus
Iterativer Algorithmus
N
Y
Abbruchkriteriumerfüllt ?
Ausgabe der besten Lösung
Anfangslösung
36Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 1: Einführung
Kapitel 1 – Einführung
1.1 Entwurfsautomatisierung in der Elektronik (EDA)
1.2 Hinweise
1.3 Bedeutung der Entwurfsautomatisierung
1.4 Entwicklung der Entwurfsautomatisierung
1.5 Übersicht über den Entwurfsprozess
1.6 Entwurfsstile
1.7 Layoutebenen
1.8 Entwurfsregeln
1.9 Layoutsynthese als Optimierungsproblem
1.10 Rechenkomplexität der Layoutsynthese
1.11 Einteilung von Entwurfsalgorithmen
1.12 Lösungsqualität von Entwurfsalgorithmen
1.13 Graphentheoretische Grundbegriffe
1.14 Häufig verwendete Layoutbegriffe
37Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 1: Einführung
1.13 Graphentheoretische Grundbegriffe
B
C
Graph
A
B
G
F
DE
E
C
A
D
F
A
B
C
MultigraphHypergraph
Hyperkante
KanteKnoten
38Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 1: Einführung
1.13 Graphentheoretische Grundbegriffe
Gerichtete Graphen
Maschen
A
B
C E G
F
D
A
B
C E G
F
D
A B
Pfad A-C-E-G
Vollständiger Graph: Jeweils eine Kante existiert zwischen beliebigen Knotenpaaren
Zusammenhängender Graph: Mindestens ein Pfad existiert zwischen beliebigen Knotenpaaren
39Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 1: Einführung
1.13 Graphentheoretische Grundbegriffe
Baum: zusammenhängender und maschenfreier Graph
A
B C D
E F G H I J K
A
B
C
E G
F
D
Ungerichteter Baum Gewurzelter Baum
Blätter
Wurzel
40Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 1: Einführung
1.13 Graphentheoretische Grundbegriffe
Rektilinearer minimaler Spannbaum dreier Anschlusspunkte A, B, C
B (2, 6)
A (2, 1)
C (6, 4)
41Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 1: Einführung
1.13 Graphentheoretische Grundbegriffe
Rektilinearer minimaler Steinerbaum dreier Anschlusspunkte A, B, C
B (2, 6)
A (2, 1)
C (6, 4)
Steinerpunkt
S (2, 4)
42Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 1: Einführung
Kapitel 1 – Einführung
1.1 Entwurfsautomatisierung in der Elektronik (EDA)
1.2 Hinweise
1.3 Bedeutung der Entwurfsautomatisierung
1.4 Entwicklung der Entwurfsautomatisierung
1.5 Übersicht über den Entwurfsprozess
1.6 Entwurfsstile
1.7 Layoutebenen
1.8 Entwurfsregeln
1.9 Layoutsynthese als Optimierungsproblem
1.10 Rechenkomplexität der Layoutsynthese
1.11 Einteilung von Entwurfsalgorithmen
1.12 Lösungsqualität von Entwurfsalgorithmen
1.13 Graphentheoretische Grundbegriffe
1.14 Häufig verwendete Layoutbegriffe
43Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 1: Einführung
1.14 Häufig verwendete Layoutbegriffe
(A: Net1)
(B: Net2)
(C: Net5)
(NAND[1]: IN1 Net1, IN2 Net2, OUT Net3)
(NAND[2]: IN1 Net1, IN2 Net2, OUT Net4)
(NOR[1]: IN1 Net3, IN2 Net4, OUT Net5)
A
B
NAND[1]
NAND[2]
NOR[1]
(Net1: A, NAND[1].IN1, NAND[2].IN1)
(Net2: B, NAND[1].IN2, NAND[2].IN2)
(Net3: NAND[1].OUT, NOR[1].IN1)
(Net4: NAND[2].OUT, NOR[1].IN2)
(Net5: NOR[1].OUT, C)
C
Net1
Net5
Net2Net4
Net3
Pinorientierte Netzliste
Netzorientierte Netzliste
44Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 1: Einführung
1.14 Häufig verwendete Layoutbegriffe
Verbindungsgraph
1
2
3
6
A
B
NAND[1]
NAND[2]
NOR[1] C
4
5
A
B
NAND[1]
NAND[2]
NOR[1]
C
45Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 1: Einführung
1.14 Häufig verwendete Layoutbegriffe
Verbindungsmatrix
1
2
3
6
A
B
NAND[1]
NAND[2]
NOR[1] C
4
5
A
B
NAND[1]
NAND[2]
NOR[1]
C
0100006
1011005
0102114
0120113
0011002
0011001
654321
46Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 1: Einführung
1.14 Häufig verwendete Layoutbegriffe
n nnyyxxd 1212
Abstandsdefinition zweier Punkte P1 (x1,y1) und P2 (x2,y2)
mit n = 2 Euklidische Metrik, n = 1 Manhattan-Metrik, n < 1 Sub-Manhattan-Metrik
P1 P2
47Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 1: Einführung
1.14 Häufig verwendete Layoutbegriffe
n nnyyxxd 1212
mit n = 2 Euklidische Metrik, n = 1 Manhattan-Metrik
Abstandsdefinition zweier Punkte P1 (x1,y1) und P2 (x2,y2)
P1
P2
48Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 1: Einführung
Zusammenfassung Kapitel 1 – Einführung
1.1 Entwurfsautomatisierung in der Elektronik (EDA)
1.2 Hinweise
1.3 Bedeutung der Entwurfsautomatisierung
1.4 Entwicklung der Entwurfsautomatisierung
1.5 Übersicht über den Entwurfsprozess
1.6 Entwurfsstile
1.7 Layoutebenen
1.8 Entwurfsregeln
1.9 Layoutsynthese als Optimierungsproblem
1.10 Rechenkomplexität der Layoutsynthese
1.11 Einteilung von Entwurfsalgorithmen
1.12 Lösungsqualität von Entwurfsalgorithmen
1.13 Graphentheoretische Grundbegriffe
1.14 Häufig verwendete Layoutbegriffe