Die rekursive, also wiederholte Anwendung der Shannon-Zerlegung dient zusammen mit zwischengeschalteten Reduktionsschritten wie der Extraktion doppelter und überdeckter Terme der Minimierung boolscher Funktionen, so dass sich diese durch möglichst einfache Formelausdrücke oder Decision Diagrams darstellen und auf minimaler Chip-Fläche realisieren lassen. Heuristiken sollen dabei Hinweise liefern wo, sprich bei welcher Eingabevariablen, die jeweils nächste Shannon-Zerlegung stattfinden soll. Durch die Shannon-Zerlegung entstehen aus einer Funktion jeweils zwei einfachere Subfunktionen, die eine Eingabevariable weniger besitzen. Die Heuristiken stellen keine exakte Minimierungsmethode dar. Im Gegensatz zur exakten und maximalen Minimierung z.B. nach dem Quine- McCluskey-Algorithmus, erreichen heuristische Verfahren geringere Reduktionsgrade. Zwar werden weniger Terme in den Formeln eingespart, dafür sind die heuristischen Verfahren aber wesentlich schneller und bei vielen Eingabevariablen das einzig Praktikable. Benchmarks in dieser Arbeit bestimmen die Einsparung an Formel-Termen, die Anzahl nötiger Rekursionsschritte und die benötigte Rechenzeit.
Die rekursive Shannon-Zerlegung ist ein sehr altes Verfahren. Das bekannteste Verfahren dazu war der Simplify-Algorithmus mit der Heuristik der Spaltung von Funktionen an der "most-binate" Position, für die die Summe an 0en und 1en einer Eingabespalte einer Wahrheitstafel – genauer: ihrem OnSet – maximal ist. Ein bekannteres heuristisches Verfahren, allerdings mit ganz anderer Vorgehensweise (Komplementbildung, Maximierung von Don't Cares, ...) ist Espresso (II), das auf Simplify folgte und Vorgänger für Verfahren wie SIS und ABC war, in denen es bis heute noch aufrufbar ist. Espresso war wohl auch das erste Verfahren, das im Gegensatz zu Simplify und den Heuristiken, die Gegenstand dieser Arbeit sind, mit Don't Cares in Ausgabevariablen umgehen kann.
Simplify, das in dieser Arbeit in C/C++ neu implementiert und durch Heuristiken 1-3 (Heuristik 0 ist die "most-binate"-Spaltenauswahl des Originals) und Benchmarkprogrammen ergänzt wurde, kennt dagegen nur 1en in den Ausgabevariablen. Es arbeitet also nur mit dem OnSet (denjenigen Zeilen von Wahrheitstafeln mit Ausgabe=1). Bei Heuristik 1 und 2 (2 = zufällig verkleinerter Input, sonst wie Heuristik 1) soll eine der Shannon-Teilfunktionen einen minimalen Definitionsbereich haben. [...]
Inhaltsverzeichnis
1 Einleitung
2 Grundlagen
2.1 Darstellungen binärer Funktionen
2.2 Shannon Zerlegung/Erweiterung
2.3 Zerlegung und Reduktion boolscher Funktionen
2.4 Benchmarks
3 Implementierung
3.1 Simplify-Algorithmus mit Heuristik 0
3.1.1 Algorithmus im Überblick
3.1.2 Funktion main()
3.1.3 Funktionen simplify(), unate() und cofactor()
3.1.4 Funktionen merge() und intersect()
3.1.5 Funktion binate_select() zur Spaltenauswahl in Heuristik 0
3.1.6 Funktionen unate_simplify() und contains()
3.2 Heuristiken 1-3 in Simplify hinzufügen
3.2.1 Heuristik 1 + 2 mit binate_select_12()
3.2.2 Heuristik 3 mit binate_select_3(), ttUeberein() und vektorGleich()
3.3 Benchmark-Programme
3.3.1 Funktionen OnSet() und OffSet()
3.3.2 Funktionen ttGen() und dec2bin()
3.3.3 Funktionen benchmark() und zeit01MS()
3.3.4 Funktionen write_pla(), read_pla() - eigene und von ABC, SIS, ...
3.3.5 Programme für Heuristik 2: TeilOnSet0(), benchmark22()
3.3.6 Prüfung gegen ABC mit Funktion (On)SetVergleich()
4 Ergebnisse
4.1 Vergleich zu David Eigens Benchmarks mit Heuristik 0
4.2 Benchmarks zu Heuristiken 0, 1 und 3
4.3 Benchmarks zu Heuristiken 2 (und 1)
4.3.1 Benchmarks mit benchmark2() mit TeilOnSet0()
4.3.2 Benchmarks mit benchmark22() mit TeilOnSet2()
5 Auswertung und Ausblick
6 Anhänge
6.5 Inhalt der Begleit-DVD
6.6 Funktionen in veröffentlichten Benchmarks
Zielsetzung & Themen
Die Arbeit befasst sich mit der Optimierung und Implementierung von Heuristiken für die Shannon-Zerlegung zur effizienten Minimierung boolscher Funktionen in Hardware-Bausteinen, wobei der Fokus auf der Leistungsfähigkeit von C/C++-Implementierungen und einem umfassenden Benchmarking liegt.
- Entwicklung und Implementierung von Heuristiken (0-3) zur Shannon-Zerlegung.
- Vergleich der Reduktionseffizienz und Rechenzeit gegenüber existierenden Ansätzen.
- Automatisierte Testumgebung und Benchmark-Programme für boolsche Funktionen.
- Analyse der Performance unter Verwendung von C/C++, SIS und ABC.
Auszug aus dem Buch
3.1.1 Algorithmus im Überblick
Statt ein Header-File mit allen Funktionsdeklarationen und je Funktion eine Quelldatei, die jeweils die Headerdatei inkludiert, anzulegen, befinden sich alle Funktionen in einer einzigen Quelldatei "shannonXX.cpp" (XX=Versionsnummer). Diese enthält Hauptprogramm main() und alle Routinen für diesen Algorithmus (simplify(), unate(), binate_select(), binate_select_13(), contains(), cofactor(), unate_simplify(), merge(), intersect() ) sowie Hilfsprogramme zur Ausgabe (TermOut(), TToutput() ) und zum Generieren von Eingangsfunktionen (genauer: den Zeilen von Wahrheitstafeln, die zur Ausgabe = 1 führen z.B. mit dec2bin() ) wie auch Benchmarkprogramme.
Das folgende vom Autor mit Dia gezeichnete Diagramm in Bild 3 zeigt grob den Zusammenhang der Funktionen im Simplify-Algorithmus:
Zusammenfassung der Kapitel
1 Einleitung: Beschreibt die Motivation zur effizienten Darstellung boolscher Funktionen in Hardware und die Relevanz der Shannon-Zerlegung für kompakte Schaltkreise.
2 Grundlagen: Führt in die mathematischen und informationstechnischen Grundlagen ein, einschließlich der Darstellungsformen boolscher Funktionen und der Shannon-Zerlegung.
3 Implementierung: Detailreiche Erläuterung der C/C++-Programmierung, des Simplify-Algorithmus sowie der Integration und Validierung der Heuristiken 1 bis 3.
4 Ergebnisse: Präsentiert die statistische Auswertung und den Leistungsvergleich der entwickelten Heuristiken anhand einer Vielzahl von Benchmark-Funktionen.
5 Auswertung und Ausblick: Kritische Reflexion der Ergebnisse, Bewertung der Effektivität verschiedener Heuristiken und Empfehlungen für künftige Optimierungsansätze.
6 Anhänge: Umfasst formale Verzeichnisse, Abkürzungen, Literatur sowie die Dokumentation der Begleit-DVD und der verwendeten Testdaten.
Schlüsselwörter
Shannon-Zerlegung, boolsche Funktionen, Hardware-Minimierung, C++, Simplify-Algorithmus, Benchmarking, Wahrheitstabelle, Heuristiken, Logik-Synthese, Optimierung, Schaltkreisentwurf, PLA, SIS, ABC, Datenstrukturen
Häufig gestellte Fragen
Worum geht es in dieser Arbeit?
Die Arbeit untersucht die effiziente Minimierung boolscher Funktionen mittels Shannon-Zerlegung und implementiert hierzu verschiedene Heuristiken in C/C++.
Welche zentralen Themenfelder werden bearbeitet?
Die Schwerpunkte liegen auf der algorithmischen Zerlegung boolscher Ausdrücke, der Implementierung dieser Verfahren in Software und der systematischen Leistungsbewertung mittels Benchmarks.
Was ist das primäre Ziel der Forschung?
Das Ziel ist die Implementierung und der Leistungsvergleich von Heuristiken zur Reduktion boolscher Formeln, um eine kompaktere Chip-Fläche bei der Hardware-Realisierung zu erreichen.
Welche wissenschaftliche Methode wird angewendet?
Es wird eine analytische und experimentelle Methode verwendet: Implementierung von Algorithmen, Generierung von Testdaten mittels Zufallsgeneratoren und quantitativer Vergleich der Ergebnisse hinsichtlich Reduktionsgrad und Rechenzeit.
Was wird im Hauptteil behandelt?
Der Hauptteil widmet sich der technischen Implementierung in C++, der Detaillierung des Simplify-Algorithmus, der Integration spezieller Heuristiken und dem Aufbau der Benchmark-Umgebung.
Welche Schlüsselwörter charakterisieren die Arbeit?
Zu den Kernbegriffen zählen Shannon-Zerlegung, boolsche Funktionen, C++, Simplify-Algorithmus, Benchmarking und Logik-Synthese.
Wie unterscheidet sich Heuristik 3 von den anderen Heuristiken?
Heuristik 3 ist auf eine maximale Übereinstimmung der Definitionsbereiche beider Kofaktoren ausgerichtet, was sie rechenintensiver, aber in bestimmten Fällen effektiver macht.
Warum spielt das SIS/ABC-Programm eine Rolle?
Diese Werkzeuge dienen als externe Referenz und Validierungsinstanz, um die Qualität und Richtigkeit der eigenen Implementierungen im Bereich der Logik-Synthese zu prüfen.
Welche Bedeutung hat die Begleit-DVD?
Sie enthält den Quellcode der Implementierung sowie die umfangreichen Testdaten und Benchmark-Ergebnisse, die für die Nachvollziehbarkeit der Arbeit essenziell sind.
Was ist die Schlussfolgerung bezüglich der Heuristiken?
Es zeigt sich ein Trade-off zwischen Rechenzeit und Reduktionsgüte, wobei Heuristik 0 und 1 meist ein ausgewogeneres Verhältnis bieten als die komplexere Heuristik 3.
- Quote paper
- Rainer Stickdorn (Author), 2017, Verschiedene Shannon-Zerlegungen und deren Leistungsfähigkeit in Benchmarks, Munich, GRIN Verlag, https://www.grin.com/document/433442
