Dipl.-Ing. Tilo Meister

Pinzuordnungs-Algorithmen zur Optimierung der Verdrahtbarkeit beim hierarchischen Layoutentwurf

Dokumente und Dateien

Hinweis

Bitte nutzen Sie beim Zitieren immer folgende Url:

http://nbn-resolving.de/urn:nbn:de:bsz:14-qucosa-96764

Kurzfassung in Deutsch

Sie entwickeln Entwurfssysteme für elektronische Baugruppen? Dann gehören für Sie die mit der Pinzuordnung verbundenen Optimierungskriterien - die Verdrahtbarkeit im Elektronikentwurf - zum Berufsalltag.
Um die Verdrahtbarkeit unter verschiedenen Gesichtspunkten zu verbessern, werden in diesem Buch neu entwickelte Algorithmen vorgestellt. Sie ermöglichen erstmals die automatisierte Pinzuordnung für eine große Anzahl von Bauelementen in hochkomplexen Schaltungen. Alle Aspekte müssen in kürzester Zeit exakt erfasst, eingeschätzt und im Entwurfsprozess zu einem optimalen Ergebnis geführt werden.
Die beschriebenen Methoden reduzieren den Entwicklungsaufwand für elektronische Systeme auf ein Minimum und ermöglichen intelligente Lösungen auf der Höhe der Zeit.

Die vorliegende Arbeit behandelt die Optimierung der Pinzuordnung und die dafür notwendige Verdrahtbarkeitsvorhersage im hierarchischen Layoutentwurf. Dabei werden bekannte Methoden der Verdrahtbarkeitsvorhersage aus allen Schritten des Layoutentwurfs zusammengetragen, gegenübergestellt und auf ihre Eignung für die Pinzuordnung untersucht. Dies führt schließlich zur Entwicklung einer Vorhersagemethode, die speziell an die Anforderungen der Pinzuordnung angepasst ist.
Die Pinzuordnung komplexer elektronischer Geräte ist bisher ein vorwiegend manueller Prozess. Es existieren also bereits Erfahrungen, welche jedoch weder formalisiert noch allgemein verfügbar sind. In den vorliegenden Untersuchungen werden Methoden der Pinzuordnung algorithmisch formuliert und damit einer Automatisierung zugeführt. Besondere Merkmale der Algorithmen sind ihre Einsetzbarkeit bereits während der Planung des Layouts, ihre Eignung für den hierarchisch gegliederten Layoutentwurf sowie ihre Fähigkeit, die Randbedingungen differenzieller Paare zu berücksichtigen.
Die beiden untersuchten Aspekte der Pinzuordnung, Verdrahtbarkeitsvorhersage und Zuordnungsalgorithmen, werden schließlich zusammengeführt, indem die neue entwickelte Verdrahtbarkeitsbewertung zum Vergleichen und Auswählen der formulierten Zuordnungsalgorithmen zum Einsatz kommt.

Kurzfassung in Englisch

This work deals with the optimization of pin assignments for which an accurate routability prediction is a prerequisite. Therefore, this contribution introduces methods for routability prediction. The optimization of pin assignments, for which these methods are needed, is done after initial placement and before routing. Known methods of routability prediction are compiled, compared, and analyzed for their usability as part of the pin assignment step. These investigations lead to the development of a routability prediction method, which is adapted to the specific requirements of pin assignment.
So far pin assignment of complex electronic devices has been a predominantly manual process. Hence, practical experience exists, yet, it had not been transferred to an algorithmic formulation. This contribution develops pin assignment methods in order to automate and improve pin assignment. Distinctive characteristics of the thereby developed algorithms are their usability during layout planning, their capability to integrate into a hierarchical design flow, and the consideration of differential pairs.
Both aspects, routability prediction and assignment algorithms, are finally brought together by using the newly developed routability prediction to evaluate and select the assignment algorithms.

weitere Metadaten

übersetzter Titel
(Englisch)
Pin Assignment Algorithms for Improved Routability in Hierarchical Layout Synthesis
Schlagwörter
(Deutsch)
Pinzuordnung, Verdrahtbarkeit, Verdrahtungsvorhersage, Entwurfsautomatisierung, Layoutentwurf, Layoutsynthese, Physischer Entwurf, EDA, CAD
Schlagwörter
(Englisch)
Pin Assignment, Pinout, Terminal Assignment, Routability, Layout Synthesis, Electronic Design Automation, EDA, CAD
SWD SchlagworteElektrotechnik, Elektronik, CAD
DDC Klassifikation537, 600, 620
RVK KlassifikationZN 4125, ZN 4904
Institution(en) 
HochschuleTechnische Universität Dresden
FakultätFakultät Elektrotechnik und Informationstechnik
InstitutInstitut für Feinwerktechnik und Elektronik-Design
BetreuerProf. Dr.-Ing. habil. Jens Lienig
Dipl.-Ing. Gisbert Thomke
GutachterProf. Dr.-Ing. habil. Jens Lienig
Prof. Dr.-Ing. Jürgen Scheible
DokumententypDissertation
SpracheDeutsch
Tag d. Einreichung (bei der Fakultät)05.12.2011
Tag d. Verteidigung / Kolloquiums / Prüfung10.02.2012
Veröffentlichungsdatum (online)12.10.2012
persistente URNurn:nbn:de:bsz:14-qucosa-96764
Inhaltsverzeichnis1 Einleitung
1.1 Layoutentwurfsprozess elektronischer Baugruppen
1.2 Ziel der Arbeit
2 Grundlagen
2.1 Pinzuordnung
2.1.1 Definitionen
2.1.2 Freiheitsgrad
2.1.3 Komplexität und Problemgröße
2.1.4 Optimierungsziel
2.1.5 Randbedingungen
2.2 Reale Entwurfsbeispiele der Pinzuordnung
2.2.1 Hierarchieebenen eines Personal Computers
2.2.2 Multi-Chip-Module auf Hauptplatine
2.3 Einteilung von Algorithmen der Pinzuordnung
2.3.1 Klassifikation nach der Einordnung in den Layoutentwurf
2.3.2 Klassifikation nach Optimierungsverfahren
2.3.3 Zusammenfassung
2.4 Verdrahtbarkeitsvorhersage
2.4.1 Definitionen
2.4.2 Vorhersagegenauigkeit und zeitlicher Rechenaufwand
2.4.3 Methoden der Verdrahtbarkeitsvorhersage
3 Stand der Technik
3.1 Pinzuordnung
3.1.1 Einordnung in den Layoutentwurf
3.1.2 Optimierungsverfahren
3.2 Verdrahtbarkeitsvorhersage
3.2.1 Partitionierbarkeit
3.2.2 Verdrahtungslänge
3.2.3 Verdrahtungsweg
3.2.4 Verdrahtungsdichte
3.2.5 Verdrahtungsauslastung und Overflow
3.2.6 Manuelle optische Bewertung
3.2.7 Interpretation und Wichtung der Kriterien
4 Präzisierung der Aufgabenstellung
5 Pinzuordnungs-Algorithmen
5.1 Voraussetzungen
5.2 Topologische Heuristiken
5.2.1 Wiederholtes Unterteilen
5.2.2 Kreuzungen minimieren
5.2.3 Projizieren auf Gerade
5.3 Lineare Optimierung
5.4 Differenzielle Paare
5.5 Pinzuordnung in Hierarchieebenen
5.6 Nutzen der Globalverdrahtung
5.6.1 Methode
5.6.2 Layout der Ankerkomponenten
5.7 Zusammenfassung
6 Verdrahtbarkeitsbewertung während der Pinzuordnung
6.1 Anforderungen
6.2 Eignung bekannter Bewertungskriterien
6.2.1 Partitionierbarkeit / Komplexitätsanalyse
6.2.2 Verdrahtungslängen
6.2.3 Verdrahtungswege
6.2.4 Verdrahtungsdichte
6.2.5 Verdrahtungsauslastung
6.2.6 Overflow
6.2.7 Schlussfolgerung
6.3 Probabilistische Verdrahtungsdichtevorhersage
6.3.1 Grenzen probabilistischer Vorhersagen
6.3.2 Verdrahtungsumwege
6.3.3 Verdrahtungsdichteverteilung
6.3.4 Gesamtverdrahtungsdichte und Hierarchieebenen
6.4 Bewertung der Verdrahtungsdichteverteilung
6.4.1 Maßzahlen für die Verdrahtbarkeit eines Netzes
6.4.2 Maßzahlen für die Gesamtverdrahtbarkeit
6.5 Zusammenfassung
7 Pinzuordnungs-Bewertung
7.1 Anforderungen
7.2 Kostenterme
7.3 Normierung
7.3.1 Referenzwerte für Eigenschaften der Verdrahtungsdichte
7.3.2 Referenzwerte für Verdrahtungslängen
7.3.3 Referenzwerte für Signalkreuzungen
7.4 Gesamtbewertung der Verdrahtbarkeit
7.5 Priorisierung der Kostenterme
7.6 Zusammenfassung
8 Ergebnisse
8.1 Verdrahtbarkeitsbewertung
8.1.1 Charakteristik der ISPD-Globalverdrahtungswettbewerbe
8.1.2 Untersuchte probabilistische Schätzer
8.1.3 Kriterien zum Bewerten der Vorhersagegenauigkeit
8.1.4 Vorhersagegenauigkeit der probabilistischen Schätzer
8.2 Pinzuordnungs-Bewertung
8.2.1 Vollständige Analyse kleiner Pinzuordnungs-Aufgaben
8.2.2 Pinzuordnungs-Aufgaben realer Problemgröße
8.2.3 Differenzielle Paare
8.2.4 Nutzen der Globalverdrahtung
8.2.5 Hierarchieebenen
8.3 Zusammenfassung
9 Gesamtzusammenfassung und Ausblick

Verzeichnisse
Zeichen, Benennungen und Einheiten
Abkürzungsverzeichnis
Glossar

Anhang
A Struktogramme der Pinzuordnungs-Algorithmen
A.1 Wiederholtes Unterteilen
A.2 Kreuzungen minimieren
A.3 Projizieren auf Gerade
A.4 Lineare Optimierung
A.5 Zufällige Pinzuordnung
A.6 Differenzielle Paare
A.7 Pinzuordnung in Hierarchieebenen
A.8 Nutzen der Globalverdrahtung
B Besonderheit der Manhattan-Länge während der Pinzuordnung
C Weitere Ergebnisse
C.1 Multipinnetz-Zerlegung
C.1.1 Grundlagen
C.1.2 In dieser Arbeit angewendete Multipinnetz-Zerlegung
C.2 Genauigkeit der Verdrahtungsvorhersage
C.3 Hierarchische Pinzuordnung

Literaturverzeichnis
Externe Referenzhttp://www.vdi-verlag.de/
Die Printausgabe der Dissertation erscheint im VDI Verlag in der Reihe Fortschritt-Berichte VDI, Reihe 9 Elektronik ; 391 (ISBN 9783183391097).

Hinweis zum Urheberrecht

Diese Website ist eine Installation von Qucosa - Quality Content of Saxony!
Sächsische Landesbibliothek Staats- und Universitätsbibliothek Dresden