48
1 Layoutsynthese 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

Gliederung Kapitel 1 – Einführung

  • Upload
    eyad

  • View
    56

  • Download
    0

Embed Size (px)

DESCRIPTION

Gliederung Kapitel 1 – Einführung. 1.1Entwurfsautomatisierung in der Elektronik (EDA) 1.2Hinweise 1.3Bedeutung der Entwurfsautomatisierung 1.4Entwicklung der Entwurfsautomatisierung 1.5Übersicht über den Entwurfsprozess 1.6Entwurfsstile 1.7Layoutebenen 1.8Entwurfsregeln - PowerPoint PPT Presentation

Citation preview

Page 1: Gliederung Kapitel 1 – Einführung

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

Page 2: Gliederung Kapitel 1 – Einführung

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

Page 3: Gliederung Kapitel 1 – Einführung

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

Page 4: Gliederung Kapitel 1 – Einführung

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

Page 5: Gliederung Kapitel 1 – Einführung

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

Page 6: Gliederung Kapitel 1 – Einführung

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.

Page 7: Gliederung Kapitel 1 – Einführung

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

Page 8: Gliederung Kapitel 1 – Einführung

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

Page 9: Gliederung Kapitel 1 – Einführung

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)

Page 10: Gliederung Kapitel 1 – Einführung

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

Page 11: Gliederung Kapitel 1 – Einführung

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

Page 12: Gliederung Kapitel 1 – Einführung

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

Page 13: Gliederung Kapitel 1 – Einführung

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

Page 14: Gliederung Kapitel 1 – Einführung

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

Page 15: Gliederung Kapitel 1 – Einführung

15Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 1: Einführung

1.5.5 Layoutsynthese: Digitalentwurf

Page 16: Gliederung Kapitel 1 – Einführung

16Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 1: Einführung

1.5.5 Layoutsynthese: Analogentwurf

Page 17: Gliederung Kapitel 1 – Einführung

17Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung Kapitel 1: Einführung

1.5.5 Layoutsynthese: Leiterplattenentwurf

Page 18: Gliederung Kapitel 1 – Einführung

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

Page 19: Gliederung Kapitel 1 – Einführung

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)

Page 20: Gliederung Kapitel 1 – Einführung

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

Page 21: Gliederung Kapitel 1 – Einführung

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

Page 22: Gliederung Kapitel 1 – Einführung

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

Page 23: Gliederung Kapitel 1 – Einführung

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

Page 24: Gliederung Kapitel 1 – Einführung

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

Page 25: Gliederung Kapitel 1 – Einführung

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

Page 26: Gliederung Kapitel 1 – Einführung

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

Page 27: Gliederung Kapitel 1 – Einführung

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

Page 28: Gliederung Kapitel 1 – Einführung

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

Page 29: Gliederung Kapitel 1 – Einführung

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

Page 30: Gliederung Kapitel 1 – Einführung

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

Page 31: Gliederung Kapitel 1 – Einführung

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

Page 32: Gliederung Kapitel 1 – Einführung

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

Page 33: Gliederung Kapitel 1 – Einführung

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

Page 34: Gliederung Kapitel 1 – Einführung

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

Page 35: Gliederung Kapitel 1 – Einführung

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

Page 36: Gliederung Kapitel 1 – Einführung

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

Page 37: Gliederung Kapitel 1 – Einführung

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

Page 38: Gliederung Kapitel 1 – Einführung

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

Page 39: Gliederung Kapitel 1 – Einführung

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

Page 40: Gliederung Kapitel 1 – Einführung

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)

Page 41: Gliederung Kapitel 1 – Einführung

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)

Page 42: Gliederung Kapitel 1 – Einführung

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

Page 43: Gliederung Kapitel 1 – Einführung

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

Page 44: Gliederung Kapitel 1 – Einführung

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

Page 45: Gliederung Kapitel 1 – Einführung

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

Page 46: Gliederung Kapitel 1 – Einführung

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

Page 47: Gliederung Kapitel 1 – Einführung

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

Page 48: Gliederung Kapitel 1 – Einführung

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