In dieser Arbeit werden bereits existierende Verfahren zur Isomorphieprüfung analoger Schaltungen untersucht und weiterentwickelt, sodass eine erhebliche Geschwindigkeitszunahme erreicht wird.
Im Rahmen des Forschungsprojektes "Syntheseunterstützter Entwurf analoger Schaltungen" (SyEnA) wurde in der Professur für
Entwurfsmethodik ein Verfahren zur konstruktiven Topologiesynthese entwickelt. Das Projekt befasst sich mit der Erarbeitung von innovativen Methoden zur Automatisierung des analogen Schaltungsentwurfs.
Dieses ermöglicht die automatische Generierung von Schaltungen auf Transistorebene. Während des Generierungsprozesses besteht die Notwendigkeit auszuschließen, dass innerhalb des definierten Designraumes Schaltungen doppelt oder mehrfach generiert werden und somit überflüssige Überprüfungen dieser Schaltungen in weiteren Entwicklungsschritten folgen. Solche
Schaltungen lassen sich durch Isomorphieprüfung eliminieren.
Inhaltsverzeichnis
1 Einleitung
1.1 Entwurf analoger Schaltungen
1.2 Topologie-Synthese
1.3 Motivation
2 Isomorphieprüfung analoger Schaltungen
2.1 Prüfung der Übereinstimmung zweier Schaltungen
2.2 Graphentheoretische Grundlagen
2.3 Das Problem des Graphisomorphismus und dessen Komplexität
2.3.1 Komplexitätsklassen
2.3.2 Die Komplexität von GI
3 Lösungsansätze für das Isomorphieproblem im wissenschaftlichen Kontext
3.1 Allgemeine Ansätze und Ideen
3.1.1 Invarianten als Grundkriterien für Isomorphie
3.1.2 Backtracking-Algorithmen
3.1.3 Kanonische Bezeichner
3.1.4 Partitionierung eines Graphen
3.1.5 State of the Art in der Praxis: NAUTY
3.2 Ansätze für die Isomorphieprüfung von Schaltungen
3.2.1 Anwendungsbereiche
3.2.2 Begünstigende Unterschiede zum allgemeinen Isomorphie-Problem
3.2.3 Evaluation existierender Algorithmen
4 Algorithmus zur Generierung einzigartiger Schaltungen
4.1 Beschreibung des Algorithmus
4.1.1 Aufnahme einer Schaltung in die Datenbank
4.1.2 Eigenschaften der Schaltung extrahieren
4.1.3 Isomorphieprüfung
4.2 Beispiel
4.2.1 Isomorphe Schaltungen
4.2.2 Symmetrische nicht-isomorphe Graphen
4.2.3 Berechnung eines Hashwertes
5 Evaluation
5.1 Das Framework zur Analogsynthese
5.2 Ergebnisse nach Ohlrichs Methode
5.3 Ergebnisse des Algorithmus mit Verwendung von Graph-Invarianten
5.4 Ergebnisse mit Hashing
5.5 Evaluation der Topologie-Synthese
5.6 Analyse der Laufzeit
6 Fazit und Ausblick
6.1 Fazit
6.2 Ausblick
Zielsetzung & Themen
Die vorliegende Arbeit zielt darauf ab, einen effizienten Algorithmus zur Isomorphieprüfung analoger Schaltungen zu entwickeln, um redundante, mehrfach generierte Schaltungen innerhalb eines Topologie-Synthese-Frameworks frühzeitig zu eliminieren und somit den Entwurfsprozess zu beschleunigen.
- Automatisierter Entwurf analoger Schaltungen
- Graphentheoretische Repräsentation von Schaltungen
- Methoden der Isomorphieprüfung (Backtracking, Kanonische Bezeichner)
- Beschleunigung der Dubletten-Eliminierung durch Hashing und Invarianten
- Evaluation der Laufzeit und Effizienz gegenüber existierenden Verfahren
Auszug aus dem Buch
4.1.3 Isomorphieprüfung
Nachdem überprüft wurde, ob zwei Schaltungen den gleichen Hashwert besitzen, die gleiche Anzahl an Bauelement- und Netzknoten sowie Port- und Knotentypen haben und dass ihre initiale Partitionierung übereinstimmt, startet die eigentliche Isomorphieprüfung, da bis zu diesem Punkt in Betracht gezogen werden kann, dass eine Isomorphie bestehen könnte.
Die Vorgehensweise wird in Algorithmus 4 gezeigt. Es werden die initialen Partitionen zweier zu vergleichender Schaltungen c1 und c2 betrachtet, die durch Funktion 15 ermittelt wurden. Hier werden die Pinknoten für den weiteren Verlauf wie Netzknoten gehandhabt, so dass wir in Algorithmus 4 tatsächlich lediglich zwei verschiedene Verfahrensweisen für Netz- und Bauelementknoten betrachten. Wie bei Ohlrich folgt die Auswahl der zwei kleinsten korrespondierenden Knotenmengen, um aus diesen Startknoten für die Überprüfung zu wählen. Für c1 ist dabei ein Startknoten s1 ∈ c1 fix und für c2 sind alle Knoten dieser Äquivalenzklasse potenzielle Kandidaten für ein Matching mit s1. Zu Beginn wird allerdings zufällig einer dieser Knoten s2 ∈ c2 gewählt und die Annahme getroffen, dass ein Matching zwischen s1 und s2 besteht. Knoten, für die ein Matching existiert, erhalten keine neue Markierungen im weiteren Verlauf des Algorithmus. Deren Partition ist einelementig und fix für den Rest der Durchläufe. Beide Knoten werden in eine Queue Q zur weiteren Bearbeitung eingefügt. Alle folgenden Schritte beziehen sich auf die Elemente, die in Q enthalten sind und werden bei allen noch enthaltenen Knoten ausgeführt und abgearbeitet, bis die Queue keine Elemente mehr enthält.
Zusammenfassung der Kapitel
1 Einleitung: Diese Einleitung erläutert die zunehmende Komplexität beim Entwurf analoger Schaltungen und die Notwendigkeit zur Automatisierung mittels Topologie-Synthese.
2 Isomorphieprüfung analoger Schaltungen: Es werden die graphentheoretischen Grundlagen sowie das allgemeine Problem des Graphisomorphismus und dessen Komplexität dargelegt.
3 Lösungsansätze für das Isomorphieproblem im wissenschaftlichen Kontext: Dieses Kapitel vergleicht klassische Backtracking-Ansätze und die Verwendung kanonischer Bezeichner und evaluiert aktuelle Forschung für analoge Schaltungen.
4 Algorithmus zur Generierung einzigartiger Schaltungen: Hier wird der neue Algorithmus, der auf Hashing und Partitionierung basiert, detailliert beschrieben und anhand von Beispielen veranschaulicht.
5 Evaluation: Die Performance des Algorithmus wird hinsichtlich Laufzeit, Vergleichsanzahl und Effizienz der Eliminationsschritte gegenüber der Methode von Ohlrich evaluiert.
6 Fazit und Ausblick: Die Arbeit fasst die erzielten Effizienzgewinne zusammen und gibt Anregungen für zukünftige Optimierungen, wie eine parallele Ausführung oder verbesserte Datenstrukturen.
Schlüsselwörter
Topologie-Synthese, Isomorphieprüfung, Graphisomorphismus, Analoger Schaltungsentwurf, Backtracking, Kanonische Bezeichner, Graphpartitionierung, Hashing, Algorithmische Effizienz, Automatisierung, Schaltungsoptimierung, Design-Framework
Häufig gestellte Fragen
Worum geht es in dieser Arbeit grundsätzlich?
Die Arbeit behandelt die automatisierte Erkennung und Eliminierung von identischen analogen Schaltungen, die während eines Topologie-Synthese-Prozesses mehrfach generiert wurden.
Was sind die zentralen Themenfelder?
Zentrale Themen sind die Graphentheorie, die Isomorphieprüfung bei Schaltkreisen sowie moderne algorithmische Verfahren zur Effizienzsteigerung in EDA-Tools (Electronic Design Automation).
Was ist das primäre Ziel der Arbeit?
Das primäre Ziel ist es, einen effizienten Algorithmus zu entwerfen, der durch Vorfilterung und intelligente Markierungen (Hashing) die Laufzeit der Isomorphieprüfung im Vergleich zum Stand der Technik signifikant senkt.
Welche wissenschaftliche Methode wird verwendet?
Es werden bipartite Graphen zur Schaltungsrepräsentation verwendet und Verfahren zur Knotenpartitionierung kombiniert mit einem eigens entwickelten Hashing-Ansatz für die schnelle Identifikation von Isomorphie implementiert.
Was wird im Hauptteil der Arbeit behandelt?
Der Hauptteil gliedert sich in die theoretische Fundierung der Graphentheorie, die Analyse bestehender Algorithmen, eine detaillierte technische Beschreibung des neuen Ansatzes sowie eine umfangreiche empirische Evaluation basierend auf einem Framework zur Synthese analoger Schaltungen.
Welche Schlüsselwörter charakterisieren die Arbeit?
Die Arbeit ist durch Begriffe wie Topologie-Synthese, Isomorphieprüfung, Graphisomorphismus, Hashing und algorithmische Effizienz gekennzeichnet.
Wie unterscheidet sich der neue Algorithmus von bisherigen Ansätzen wie dem von Ohlrich?
Der neue Ansatz führt eine initiale "Erstauslese" durch Graphen-Invarianten und eine spezielle Hashfunktion ein, wodurch bei sehr vielen Schaltungen die aufwendige vollständige Isomorphieprüfung bereits im Vorfeld vermieden werden kann.
Warum ist das Hashing in diesem spezifischen Anwendungsfall besonders effizient?
Die Hashwerte berechnen sich aus der initialen Partitionierung, die bereits funktionale Aspekte wie Pintypen und Portmarkierungen einbezieht: Bei unterschiedlichen Hashwerten kann eine Isomorphie sofort ausgeschlossen werden, was die Anzahl der nötigen Vergleiche um über 99% reduziert.
- Citation du texte
- Dipl.-Inf. Linda Fremuth (Auteur), 2011, Effiziente Isomorphieprüfung von analogen Schaltungen, Munich, GRIN Verlag, https://www.grin.com/document/1297634
