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
- Einleitung
- Entwurf analoger Schaltungen
- Topologie-Synthese
- Motivation
- Isomorphieprüfung analoger Schaltungen
- Prüfung der Übereinstimmung zweier Schaltungen
- Graphentheoretische Grundlagen
- Das Problem des Graphisomorphismus und dessen Komplexität
- Komplexitätsklassen
- Die Komplexität von GI
- Lösungsansätze für das Isomorphieproblem im wissenschaftlichen Kontext
- Allgemeine Ansätze und Ideen
- Invarianten als Grundkriterien für Isomorphie
- Backtracking-Algorithmen
- Kanonische Bezeichner
- Partitionierung eines Graphen
- State of the Art in der Praxis: NAUTY
- Ansätze für die Isomorphieprüfung von Schaltungen
- Anwendungsbereiche
- Begünstigende Unterschiede zum allgemeinen Isomorphie-Problem
- Evaluation existierender Algorithmen
- Algorithmus zur Generierung einzigartiger Schaltungen
- Beschreibung des Algorithmus
- Aufnahme einer Schaltung in die Datenbank
- Eigenschaften der Schaltung extrahieren
- Isomorphieprüfung
- Beispiel
- Isomorphe Schaltungen
- Symmetrische nicht-isomorphe Graphen
- Berechnung eines Hashwertes
- Evaluation
- Das Framework zur Analogsynthese
- Ergebnisse nach Ohlrichs Methode
- Ergebnisse des Algorithmus mit Verwendung von Graph-Invarianten
- Ergebnisse mit Hashing
- Evaluation der Topologie-Synthese
- Analyse der Laufzeit
- Fazit und Ausblick
- Fazit
- Ausblick
Zielsetzung und Themenschwerpunkte
Die Diplomarbeit von Linda Luy befasst sich mit der effizienten Isomorphieprüfung von analogen Schaltungen. Sie untersucht bestehende Verfahren zur Isomorphieprüfung und entwickelt eine neue Methode zur Beschleunigung dieses Prozesses. Der Fokus liegt auf der Anwendung dieser Verfahren im Kontext der konstruktiven Topologiesynthese, die die automatische Generierung von analogen Schaltungen auf Transistorebene ermöglicht.
- Entwicklung eines neuen Ansatzes zur Isomorphieprüfung von analogen Schaltungen
- Verbesserung der Laufzeit bestehender Isomorphie-Algorithmen
- Anwendung des Algorithmus im Kontext der konstruktiven Topologiesynthese
- Evaluation der entwickelten Methode anhand von realen Beispielen
- Analyse der Komplexität des Isomorphieproblems für analoge Schaltungen
Zusammenfassung der Kapitel
- Kapitel 1: Einleitung: Dieses Kapitel führt in die Thematik des Entwurfs analoger Schaltungen ein und erläutert die Bedeutung der Topologie-Synthese. Es stellt die Motivation für die Arbeit und die Forschungslücke dar, die durch die Arbeit geschlossen werden soll.
- Kapitel 2: Isomorphieprüfung analoger Schaltungen: In diesem Kapitel werden die Grundlagen der Isomorphieprüfung analoger Schaltungen und die graphentheoretischen Grundlagen erklärt. Es werden auch die Komplexität des Graphisomorphismus-Problems und verschiedene Komplexitätsklassen behandelt.
- Kapitel 3: Lösungsansätze für das Isomorphieproblem im wissenschaftlichen Kontext: Dieses Kapitel präsentiert verschiedene Lösungsansätze für das Isomorphieproblem, die im wissenschaftlichen Kontext angewendet werden. Es behandelt Invarianten, Backtracking-Algorithmen, kanonische Bezeichner, Partitionierung von Graphen und den Stand der Technik in der Praxis.
- Kapitel 4: Algorithmus zur Generierung einzigartiger Schaltungen: Dieses Kapitel beschreibt den neu entwickelten Algorithmus zur Generierung einzigartiger Schaltungen. Es erklärt die Schritte des Algorithmus, wie die Aufnahme einer Schaltung in die Datenbank, die Extraktion von Eigenschaften und die Isomorphieprüfung.
- Kapitel 5: Evaluation: Dieses Kapitel präsentiert die Ergebnisse der Evaluation des entwickelten Algorithmus anhand realer Beispiele. Es untersucht die Leistung des Algorithmus in verschiedenen Szenarien und analysiert die Laufzeit.
Schlüsselwörter
Die Arbeit befasst sich mit den Themenbereichen analoge Schaltungsentwurf, Topologie-Synthese, Isomorphieprüfung, Graphentheorie, Komplexitätstheorie, Algorithmenentwicklung und Evaluation. Wichtige Begriffe sind unter anderem: Schaltkreis, Graphisomorphismus, Invarianten, Backtracking, kanonische Bezeichner, Hashing, Laufzeit, Effizienz, Automatisierung.
- Quote paper
- Dipl.-Inf. Linda Fremuth (Author), 2011, Effiziente Isomorphieprüfung von analogen Schaltungen, Munich, GRIN Verlag, https://www.grin.com/document/1297634
