Layoutsynthese elektronischer Schaltungen -
Grundlegende Algorithmen für die Entwurfsautomatisierung

Jens Lienig
2. Auflage, 2016, 275 S., Springer-Verlag Berlin Heidelberg
 

ISBN 978-3-662-49814-9, eBook 978-3-662-49815-6,
DOI 10.1007/978-3-662-49815-6

 

Link zu Springer / SpringerLink (eBook) / Amazon.de / Thalia / SLUB

 

 

 

 

 

 
Über dieses Lehrbuch

 

Moderne elektronische Produkte enthalten Schaltkreise mit Millionen von Transistoren sowie Leiterplatten höchster Packungsdichte. Der Layoutentwurf eines derartigen elektronischen Systems, d. h. die Übertragung der Schaltung in die konkrete Anordnung von Bauelementen und Leiterbahnen, ist nur noch mit rechnergestützten Entwurfssystemen möglich, da die Komplexität bei Handhabung traditioneller Methoden vom Ingenieur nicht mehr überblickt werden kann. Dieses Buch stellt leicht verständlich und anschaulich die Wirkungsweisen und die grundlegenden Algorithmen vor, die „unter der Haube" von Entwurfssystemen für die Layoutsynthese ablaufen. Damit vermittelt das Buch die Fähigkeit, sowohl einfache Entwurfsprogramme selbst zu schreiben als auch zu erkennen, wie ein kommerzielles Layout-Entwurfssystem arbeitet.

 

Dem Autor gelingt es, die Brücke zwischen der Welt der Algorithmen, also dem „Innenleben" von modernen Entwurfssystemen, und deren Anwendung zu schlagen. Zu jedem der wesentlichen Schritte bei der Layoutsynthese erfolgt in übersichtlichen Kapiteln zuerst eine Problembeschreibung sowie die Vorstellung von Begriffen und Optimierungszielen. Danach wird auf die bedeutsamsten Algorithmen eingegangen, die den entsprechenden Entwurfswerkzeugen zugrunde liegen. Zahlreiche Beispiele und Aufgaben mit Lösungen dienen der Erhöhung der Anschaulichkeit.

 

Umschlag   Vorwort   Inhaltsverzeichnis   Flyer   Errata

 

Buchrezensionen:  Design&Elektronik   Newsletter edaCentrum   F&M (2006)   Mechatronik (2016)

 

Englisch-sprachige Ausgabe (2011):  VLSI Physical Design: From Graph Partitioning to Timing Closure  [Book's webpage], in SLUB vorhanden.

 

Chinesisch-sprachige Ausgabe (2014):  国际电气工程先进技术译丛·超大规模集成电路物理设计:从图分割到时序收敛, in SLUB vohanden.

 

Foliensätze zu den Kapiteln

 

Kapitel 1
Einführung


PDF   (2,7MB)
PPTX (2,8MB)

Kapitel 2
Partitionie-
rung 

PDF   (0,9MB)
PPTX (1,3MB)

Kapitel 3
Floorplanning


PDF   (1,9MB)
PPTX (2,9MB)

Kapitel 4
Platzierung


PDF   (0,9MB)
PPTX (1,2MB)

Kapitel 5
Global-
verdrahtung


PDF   (1,0MB)
PPTX (0,7MB)

Kapitel 6
Fein-
verdrahtung


PDF   (1,0MB)
PPTX (0,9MB)

Kapitel 7
Flächen-
verdrahtung


PDF   (1,6MB)
PPTX (1,4MB)

Kapitel 8
Kompaktierung


PDF   (0,4MB)
PPTX (0,5MB)

 

 

Inhalt

 

1     Einführung   Dieses Buch stellt Algorithmen zur Automatisierung der Layoutsynthese vor. Unter der Layoutsynthese wird dabei die rechnergestützte Überführung der Netzliste einer Schaltung in die geometrische Anordnung der Zellen bzw. Bauelemente und Verbindungsleitungen, die sog. Layoutdarstellung, verstanden. Kapitel 1 führt in die wesentlichen Methoden, Entwicklungsabläufe und Begrifflichkeiten bei der Entwurfsautomatisierung und der Layoutsynthese ein.

1.1      Entwurfsautomatisierung in der Elektronik

1.2      Hinweise zum Buch

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

 

2     Partitionierung   Eine komplexe Gesamtschaltung kann oft nicht auf einem Verdrahtungsträger implementiert werden. Damit ist eine Aufteilung in einzelne Schaltungsblöcke notwendig, die sich dann beispielsweise als separate ICs realisieren lassen. Die Aufgabe der Partitionierung besteht darin, eine Schaltung in Teilschaltungen, sog. Partitionen oder Blöcke, aufzuteilen, wobei u.a. die Verknüpfungen der Blöcke untereinander zu minimieren sind. Das wesentliche Optimierungsziel bei der Partitionierung besteht somit in einer Schaltungsaufteilung, bei der so wenig wie möglich Verbindungen zwischen den resultierenden Blöcken erzeugt werden.

2.1      Einführung

2.2      Begriffsbestimmungen

2.3      Optimierungsziele

2.4      Partitionierungsalgorithmen

 

3     Floorplanning   Das Floorplanning betrachtet die Teilschaltungen der Partitionierung (Kap. 2), um sie durch Festlegen bisher nicht bestimmter Parameter für die nachfolgenden Entwurfsschritte vorzubereiten. Die Aufgabe des Floorplanning besteht damit darin, das Ergebnis der Schaltungspartitionierung so aufzubereiten, dass jeder dabei erstellte Block intern platziert und verdrahtet werden kann. Dazu sind (1) die Abmessungen bzw. Seitenverhältnisse der einzelnen Blöcke, und evtl. auch der Topzelle, festzulegen, (2) die Positionen der Außenanschlüsse in den einzelnen Blöcken zu bestimmen (Pinzuordnung) und (3) die Positionen dieser Blöcke innerhalb der Topzelle zu definieren.

3.1      Einführung

3.2      Optimierungsziele

3.3      Begriffsbestimmungen

3.4      Algorithmen für das Floorplanning

3.5      Pinzuordnung (Pin Assignment)

 

4     Platzierung   Nachdem man die Gesamtschaltung in einzeln zu bearbeitende Schaltungsblöcke zerlegt hat (Partitionierung, Kap. 2) und von diesen die Anordnung und die Abmessungen sowie Pinzuordnungen ermittelt wurden (Floorplanning, Kap. 3), erfolgt als nächstes die Platzierung der Zellen u.a. Schaltungselemente innerhalb der Blöcke. Die Aufgabe der Platzierung ist damit die Anordnung der einzelnen Schaltungselemente auf der zur Verfügung stehenden Layoutfläche unter Berücksichtigung von Randbedingungen (u.a. Überlappungsfreiheit) und Optimierungszielen (z.B. minimale Verbindungslänge).

4.1      Einführung

4.2      Optimierungsziele

4.3      Platzierungsalgorithmen

 

5     Globalverdrahtung   Bei der Verdrahtung sind alle Zellen- bzw. Bauelementeanschlüsse gleichen Potentials, die also zu einem Netz gehören, miteinander zu verbinden. Dies beinhaltet das Festlegen von Verdrahtungswegen sowie die Zuordnung der Leiterzugsegmente zu Verdrahtungsebenen. Die enorme Komplexität moderner Schaltkreise verhindert, dass man sofort eine detaillierte Verdrahtung durchführen kann. Hier wird die Verdrahtung in zwei Schritte, die Globalverdrahtung (global routing) und die Feinverdrahtung (detailed routing), aufgespalten. Bei der in diesem Kapitel behandelten Globalverdrahtung werden ungefähre Verbindungswege auf einer Layoutoberfläche festgelegt. Dies geschieht durch Zuweisung der Netzsegmente in Verdrahtungsregionen (global cells, gcells) unter Berücksichtigung der jeweiligen Verdrahtungskapazitäten dieser Regionen.

5.1      Einführung

5.2      Begriffsbestimmungen

5.3      Optimierungsziele

5.4      Abbildung von Verdrahtungsregionen

5.5      Ablauf der Globalverdrahtung

5.6      Algorithmen für die Globalverdrahtung

 

6     Feinverdrahtung   Die Feinverdrahtung folgt auf die Globalverdrahtung, um die Verdrahtung abzuschließen. Die Aufgabe der Feinverdrahtung besteht darin, die bei der Globalverdrahtung einer Verdrahtungsregion zugeordneten Netzsegmente in dieser Region detaillierte Verdrahtungswege und -ebenen zuzuweisen.

6.1      Einführung

6.2      Begriffsbestimmungen

6.3      Horizontaler und vertikaler Verträglichkeitsgraph

6.4      Optimierungsziele

6.5      Algorithmen für die Kanalverdrahtung

6.6      Switchbox-Verdrahtung

6.7      OTC-Verdrahtung

 

7     Flächenverdrahtung   Wenn keine Aufspaltung in Global- und Feinverdrahtung erfolgt, ist die Verdrahtung in nur einem Schritt durchzuführen. Dabei werden  keine Verdrahtungsregionen erzeugt, sondern man betrachtet die gesamte Layoutfläche. Daher spricht man hier von einer Flächenverdrahtung (area routing), welche in diesem Kapitel behandelt wird. Hierbei verlegt man die Netze sofort endgültig, d.h. mit ihren finalen Koordinaten. Dies ist bei analogen Schaltkreisen, bei Leiterplatten und gegebenenfalls auch bei MCMs der Fall. Innerhalb dieses Kapitels wird auch auf die Verdrahtung von speziellen Netzen, wie Stromversorgungs- und Taktnetze, eingegangen.

7.1      Einführung

7.2      Begriffsbestimmungen

7.3      Festlegung der Netzreihenfolge

7.4      Manhattan und euklidische Metrik

7.5      Verdrahtung der Versorgungsnetze

7.6      Optimierungsziele

7.7      Sequentielle Verdrahtungsalgorithmen

7.8      Quasiparallele Verdrahtung

7.9      Dreidimensionale Verdrahtung

7.10    X-Verdrahtung

 

8     Kompaktierung   Nach der Platzierung und Verdrahtung erfolgt oftmals eine Kompaktierung. Das Ziel besteht hier darin, das Layout unter Einhaltung sämtlicher Entwurfsregeln in seinem Flächenanspruch zu minimieren, also eine Layoutoptimierung durchzuführen. Neben der Kompaktierung eines bereits entwurfsregelgerechten Layouts kommen Kompaktoren auch bei der symbolischen Layoutentwicklung zum Einsatz, wo die Layoutelemente, z.B. Transistoren und deren Verbindungen, nur in ihren räumlichen Beziehungen zueinander abgebildet sind (Stick-Diagramm). Sämtliche Abstands- und andere Technologieregeln sind damit erst durch ein Kompaktierungswerkzeug zu implementieren.

8.1      Einführung

8.2      Begriffsbestimmungen

8.3      Symbolisches Layout

8.4      Kompaktierungsalgorithmen

 

A     Lösungen zu den Aufgaben

B     Begriffe, Symbole, Datenformate

 

 

 Impressum
Letzte Änderung: 03.09.2020