Verschiedene Shannon-Zerlegungen und deren Leistungsfähigkeit in Benchmarks

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

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.