Verschiedene Shannon-Zerlegungen und deren Leistungsfähigkeit in Benchmarks

Inhaltsverzeichnis

Abstract

Danksagung

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 Funktion 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: TeilOnSet02(), 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.1 Abbildungsverzeichnis
6.2 Tabellenverzeichnis
6.3 Abkürzungsverzeichnis
6.4 Literaturverzeichnis
6.5 Inhalt der Begleit-DVD
6.6 Funktionen in veröffentlichten Benchmarks

Abstract

Das Thema "Heuristiken für die Shannon-Zerlegung" ist an zwei Personen vergeben worden. In dieser Arbeit lautet der Schwerpunkt "Implementierung (in C/C++) und Benchmarks". Die andere Arbeit kon­zentriert sich dagegen auf die Theorie und Literaturrecherge.

Die rekursive, also wiederholte Anwendung der Shannon-Zerlegung dient zusammen mit zwischenge­schalteten 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 Hin­weise liefern wo, sprich bei welcher Eingabevariablen, diejeweils nächste Shannon-Zerlegung stattfin­den soll. Durch die Shannon-Zerlegung entstehen aus einer Funktionjeweils zwei einfachere Subfunk­tionen, die eine Eingabevariable weniger besitzen. Die Heuristiken stellen keine exakte Minimierungs­methode 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 bestim­men 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 Oen und len 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 l-3 (Heuristik O ist die "most-binate"-Spaltenauswahl des Originals) und Benchmarkprogrammen ergänzt wurde, kennt da­gegen nur len in den Ausgabevariablen. Es arbeitet also nur mit dem OnSet (denjenigen Zeilen von Wahrheitstafeln mit Ausgabe=l). Bei Heuristik l und 2 (2 = zufällig verkleinerter Input, sonst wie Heu­ristik l) soll eine der Shannon-Teilfunktionen einen minimalen Definitionsbereich haben. Bei Heuristik 3 soll dagegen die Übereinstimmung der Definitionsbereiche beider Shannon-Teilfunktionen maximal sein. Die an zufallsgenerierten Eingabefunktionen mit selbstgeschriebenen C/C++Programmen durch­geführten Minimierungen und Benchmarks zeigten Folgendes:

- gute Übereinstimmung mit alten Messungen in (Eigen l999) bezüglich Heuristik O
- stärkere Reduktionen (an Termen) in prozenual größeren OnSets
- geringe Unterschiede zwischen den Heuristiken O und l
- geringere Leistungsfähigkeit bei hohem Zeitbedarf in Heuristik 3
- Funktionsverfälschung und Don't Care-Problematik bei Heuristik 2
- sehr starker Anstieg der benötigten Rechenzeit mit zunehmender Zahl von Eingabevariablen

Zusammenfassend kann festgestellt werden, dass Verfahren, wie sie in dieser Arbeit implementiert, an­gewandt und Benchmarks unterzogen wurden, die heutigen Anforderungen nicht erfüllen können. Heu­tige Schaltungen, die boolsche Funktionen realisieren, müssen nicht nur so minimiert werden, dass die Chipfläche klein wird, sondern auch die Durchlaufzeit (dynamische Schaltungen sollen hohe Schaltfre­quenzen erlauben und stabil laufen) und der Energieverbrauch. Außerdem müssen Don't Cares (unbe­kannte oder nicht interessierende Werte) in den Ausgabevariablen möglich sein und außer OnSets auch die anderen Set-Typen in die Minimierung einfließen. Dies ist für aktuellere Verfahren gegeben. Aus di­daktischer Sicht macht die Befassung mit alten Verfahren trotzdem Sinn, da die Algorithmen über­schaubar und in einer zeitlich sehr begrenzten Arbeit realisierbar bleiben und wichtige Grundlagen-Ver- fahren der Informatik, wie die Shannon-Zerlegung, lebendig erfahrbar werden.

Danksagung

An dieser Stelle möchte ich Herrn Prof. Keller für die rasche Bereitstellung eines Themas für meine Abschlussarbeit danken. Angesichts der starken Nachfrage an Abschlussthemen und der geringen per­sonellen Ausstattung der FernUniversität für die Betreuung solcher Arbeiten war das sicherlich kein leichtes Unterfangen. Dieser Umstand führte auch zur Vergabe des Themas "Heuristiken für die Shannon-Zerlegung" an zwei Personen. Ich bin dankbar, den Teil mit dem Schwerpunkt "Implementie­rung und Benchmarks" bekommen zu haben. Damit hatte ich im Gegensatz zu der anderen Arbeit auch die Möglichkeit zu umfangreicher praktischer Programmierung und konnte meine alten C/C++ Kennt­nisse um solche über aktuelle Ergänzungen/Standards erweitern und auffrischen. Dankbar bin ich auch, dass ich durch die Programmierung und häufigere Anwendung meines Benchmark-Programms einen wichtigen Baustein der Informatik, wie die Shannon-Zerlegung, hautnah "erleben" durfte.

Meiner Familie danke ich für ihre Geduld, die sie aufbringen musste, wenn ich durch die Beschäftigung mit dieser Abschlussarbeit für ihre Anliegen keine Zeit hatte.

Weiterhin danke ich der Technischen Universität Darmstadt, deren Bibliothek und deren Kittler Student Center (im Fachbereich E-Technik) mit dem Präsenzbestand insbesondere zur Technischen Informatik und auch älteren Minimierungsmethoden von boolschen Funktionen ich intensiv nutzen konnte.

1 Einleitung

Für die kostengünstige, performante und stabile Implementierung Boolscher Funktionen in Hardware­bausteinen wie z.B. PLA oder FPGA ist es wichtig, Boolsche Funktionen auf kompakte Darstellungen zu reduzieren.

Darstellungen solcher Funktionen erfolgen z.B. mittels AND, OR und NOT Verknüpfungen ihrer Para­meter, Disjunktiver Normalform/Sum Of Products - SOP, Konjunktiver Normalform/Product Of Sums - POS, Wahrheitstabellen, vieler verschiedener Formen von Binary Decision Diagrams BDD (= Bran­ching Programs BP) wie OBDD, ROBDD, BMD, ZDD/ZBDD, FDD/KFDD, PDD, MTBDD, SBDD, EVBDD, ...

Neben der möglichst kompakten Darstellung, die mit einer kleinen Fläche auf dem Chip und damit ge­ringeren Hardwarekosten korrespondiert ist für dynamische Schaltungen mit Speichern das zeitliche Verhalten und damit die minimale Durchlaufzeit zwischen Ein- und Ausgang wichtig. In dieser Arbeit sollten aber nur statische Schaltungen ohne Speicher betrachtet werden.

Bei der Zerlegung von Boolschen Funktionen (als Ansatz "teile und herrsche") werden fortgesetzt Funktionen in je zwei einfachere (ein Parameter wird durch Konstante 0 oder 1 ersetzt) miteinander verknüpfte zerlegt. Diese Vereinfachung erfolgt vor einer Synthese für eine Hardwareimplementierung Solche Zerlegungen in einfachere Teile (Kofaktoren) erfolgen etwa mittels Shannon, Positive Davio, Negative Davio oder deren Mischformen Reed-Muller und Kronecker. Für diese Arbeit war nur die Shannon-Zerlegung gefragt.

Entscheidend für die Größe (Länge der Formel, Fläche auf dem Hardwarechip) der Funktion nach mehreren Zerlegungen ist die Reihenfolge in der die Zerlegungen in jeweils zwei Subfunktionen / Ko­faktoren vorgenommen werden. In dieser Arbeit sollen dazu drei verschiedene Auswahlverfahren (Heu­ristiken 1-3) für die Parameter von Funktionen implementiert, für bestimmte (Muster-) Funktionen die sich ergebende Größe gemessen (Benchmark) und verglichen werden: untereinander und mit weiteren bekannten Verfahren / Heuristiken. Parallel zur Shannon-Zerlegung erfolgt eine Reduktion von Termen. Terme lassen sich einsparen, wenn sie von anderen überdeckt werden. Formeln lassen sich vereinfachen wenn Terme in beiden Kofaktoren einer Shannon-Zerlegung vorkommen. Die in dieser Arbeit behandelten heuristischen Verfahren erreichen nicht so starke Reduktionen wie deterministische Reduktionsverfahren wie Quine-McCluskey, brauchen dafür aber auch weniger Rechenzeit. Dieses deterministische Verfahren ist nur für "kleinere" Funktionen realisierbar, da die Rechenzeit für "große" Funktionen inakzeptabel lang wird.

Die in dieser Arbeit behandelten Heuristiken 1-3 sind der aus dem Simplify-Algorithmus (im Folgen­den Heuristik 0 genannt) ähnlich. Diesen Verfahren ist gemein, dass sie nur die 1-Menge (OnSet = Zei­len von Wahrheitstafeln, deren Ausgangsvariable den Wert 1 aufweist) verarbeiten und von allen ande­ren Zeilen der zugehörigen Wahrheitstafel angenommen wird, dass sie zur 0-Menge (OffSet = Zeilen mit Ausgangsvariable = 0) gehören. Ein aufwendigeres heuristisches Verfahren, dass auch mit Don't Care-Mengen (2-Menge) ungewisser oder uninteressanter Ausgabevariablen umgeht, ist das Espresso­Verfahren. Dieser Nachfolger der Heuristik 0 ist auch noch in aktuellen Vereinfachungsverfahren für Boolsche Funktionen wie z.B. ABC enthalten. Die aktuellen Verfahren (ABC und Vorgänger wie SIS) arbeiten alle mit Heuristiken und Binären Decision Diagrams (BDD).

Wie veröffentlichte Benchmarkergebnisse z.B. in (Sasao & Fujita 1996) und in (Brayton 1984) für "Espresso" zeigen, ist eine gewählte Zerlegungsstrategie (Heuristik) nicht für beliebige Funktionen gleich gut. Bei diesen Benchmarks sind Funktionen mit vielen Eingabevariablen und mehreren Ausga­bevariablen involviert. In dieser Arbeit soll aber nur eine einzige Ausgabevariable betrachtet werden. Daher werden die zu untersuchenden Funktionen (genauer: deren Wahrheitstafeln) per Zufallsgenerator erzeugt und der Wert (0 oder 1) der Ausgabevariablen hängtjeweils vom Wert ab, den der Zufallsgene­rator liefert. Die Schwelle, bei deren Überschreiten die Ausgangsvariable auf 1 gesetzt wird, wird flexibel gewählt und bestimmt so die Größe der 1-Sets. Für Simplify (sprich für eine Heuristik 0) und Zufallsgenerator-erzeugte Funktionen hat David Eigen Benchmarks in (Eigen 1999) veröffentlicht, die in dieser Arbeit mit solchen zu Heuristik 0-3 verglichen werden. Die Benchmarks konzentrieren sich auf die Größen der reduzierten Formeln (als Anzahl von Termen). Rechenzeit spielt eine geringere Rolle und ist aufgrund der raschen HW-Weiterentwicklung ohnehin nicht mit Werten vergleichbar, die vor vielen Jahren veröffentlicht wurden.

Ein Größenvergleich mit OBDD ist insofern einfach, da aktuelle Verfahren der Funktionsvereinfachung wie ABC und deren Vorgänger wie SIS alle OBDD-basierte Vereinfachungsverfahren enthalten und Benchmarks über das Einlesen von Funktionsdefinitionen aus Dateien z.B. mittels Programmable Logic Array-(PLA)-Dateiformat wie in dieser Arbeit vorsehen.

2 Grundlagen

2.1 Darstellungen binärer Funktionen

Binäre Funktionen können mit verschiedenen Mitteln dargestellt werden:

- als Formel mit UND, ODER, NOT-VerknüpfUngen von Eingangsvariablen z.B. für 4 Eingabe- (A, B, C und D) und eine einzige Ausgabevariable f, wobei die UND-Verknüpfung auch als Multiplikation (* oder nichts) oder "&", die ODER-Verknüpfung als Addition (+) oder "|" und die Negation als Balken über dem Ausdruck oder vorangestelltem Ausrufezeichen oder nachge­stelltem Apostroph dargestellt werden kann: f = (A' * B') + (C *D ) = (NOT A AND NOT B)) OR (C AND D) = (A' & B') | (C & D) = (!A * !B) + (C * C), (die letzte Schreibweise wird z.B. von ABC's Funktion "write_eqn()" erzeugt)
- als Wahrheitstabelle (= Wahrheitstafel, engl. Truth Table) wie in Tabelle 1:

Abbildung in dieser Leseprobe nicht enthalten

Tabe’le 1: Wahrheitstafel für Funktion mit 4 Eingabevariablen

- Oder bei nur einer Ausgangsvariablen wie hier kann die Wahrheitstabelle allein durch die letzte Spalte von unten nach oben gelesen (siehe Funktion "read_truth -x" von ABC) repräsentiert werden als einzelne Binärzahl: f= 1000100010001111

- Disjunktive Normalform D-NF = Sum Of Products - SOP = ODER-Verknüpfung der den Funktionswert 1 ergebenden Zeilen (Produkte = UND-Verknüpfungen/Minterme aller ggf. ne­gierten Eingangsvariablen),alsodesON-sets:f = A'B'C'D' + A'B'C'D + A'B'CD' + A'B'CD + A'BCD + AB'CD + ABCD

- Konjunktive NF (Product Of Sums - POS), hier als Off-Set, also derjenigen Zeilen der Wahr­heitstafel mit f=0 oder f =1; f = (A+B+C+D)* (A+B+C+D')* (A+B+C'+D)* (A+B+C'+D')* (A+B'+C'+D')* (A'+B+C'+D')* (A'+B'+C'+D')

- Matrixförmige Karnaugh Veitch Maps - siehe (Hoffmann 2010). In ABC kann nach Definition der Funktion z.B. mit "read_truth -x 1000100010001111" die zugehörige Karnaugh Map folgen­dermaßen erzeugt werden: "print_kmap" - siehe Tabelle 2.

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 2: Karnaugh Map mit 4 Eingabevariablen in ABC gedruckt

- Reduzierte Gleichungen in denen irrelevante Variablen durch "-" oder "2" dargestellt werden. Die Terme darin korrespondieren mit 1er-Flächen in Karnough Maps. Die erste Spalte obiger Map ist durch A'B'-- und die dritte Zeile durch --CD beschreibbar. In ABC kann nach Definition der Funktion z.B. mit "read_truth -x 1000100010001111" und Reduktion mit "sis full_simplify -m nocomp" auch die reduzierte Darstellung mit "show" angezeigt werden (wenn Graphviz' dot und Ghostgum gsview32 oder gsview64 installiert und in "abc.rc" richtig konfiguriert wurden). Siehe Abbildung 1:

Abbildung in dieser Leseprobe nicht enthalten

- Graphen, insbesondere (Ordered)Binary Decision Diagrams mit ihren vielen Varianten: x(0)BDD - siehe z.B. (Knuth 2009) oder (Sasao & Fujito 1996). In ABC kann nach Definition der Funktion z.B. mit "read_truth -x 1000100010001111" und Überführung in eine interne BDD-Darstellung mit "bdd" der Graph mit "show_bdd" angezeigt werden (wenn Graphviz' dot und Ghostgum gsview32 oder gsview64 installiert und in "abc.rc" konfiguriert wurden). Siehe Abbildung 2:

Abbildung in dieser Leseprobe nicht enthalten

2.2 Shannon Zerlegung/Erweiterung

Nach Auswahl einer Eingangsvariablen wird die Boolsche Funktion F() an der gewählten Stelle in zwei einfachere sogenannte Kofaktoren zerlegt, die diese Variable selbst nicht mehr enthalten und aus der ur­sprünglichen Funktion entstehen, indem dort diese Variable einmal durch eine ’1’ und ein anderes Mal durch eine ’0’ ersetzt wird. Der erste Kofaktor wird mit der ausgewählten Eingangvariablen xi , der zweite mit ihrem Komplement, der negierten Eingangsvariablen, multipliziert und beide Produkte (Konjunktionen = UND-Verknüpfungen) addiert (Disjunktion = ODER-Verknüpfung) - siehe auch (Becker 2005) und (Hoffmann 2010):

Abbildung in dieser Leseprobe nicht enthalten

Neben dieser originären Shannon Zerlegung gibt es noch weitere hier nicht behandelte Verknüpfungen beider Kofaktoren in Davio-, Reed-Muller- und Exclusiv-ODER (XOR)-Zerlegungen.

2.3 Zerlegung und Reduktion boolscher Funktionen

In den Programmen dieser Arbeit wird die Shannon Zerlegung rekursiv, also vielfach durchgeführt, bis die Kofaktoren bestimmte Eigenschaften haben. Vor neuerlichen Zerlegungen werden Möglichkeiten, die Ausdrücke zu vereinfachen und die Anzahl der Terme zu reduzieren, genutzt. Die Formelverein­fachungen werden anhand des Simplify-Algorithmus beschrieben, da sie unabhängig von einer Heu­ristik sind. Die verschiedenen Heuristiken dienen der Auswahl der Variable für die nächste Shannon­Zerlegung, welche unterschiedliche Terme mit UND-verknüpften Variablen liefern, die unterschiedlich erfolgreiche Reduktionen zur Folge haben können. Die Herangehensweise, Reduktionen zu versuchen, Term-Überdeckung und Term-Wiederholung in Kofaktoren ausnutzen, ist aber gleich.

Shannon-Zerlegung kann einen binären Baum beginnend an der Wurzel (= erste ausgewählte Eingangs­variable) in Richtung 0- und 1-Blatt mit nur einer Variablen je Tiefenstufe erzeugen. Eine andere Er­zeugung solcher Bäume aufgrund von Monomen (Min-Termen in SOP / Wahrheitstabellen oder Max­termen in POS) erfolgt in Gegenrichtung von den 0-/1-Blättern zur Wurzel hin. Kofaktoren entsprechen den zwei Teilbäumen unter einem Knoten. Die Reduktion von OBDD umfasst die Entfernung von Knoten mit identischen 0- und 1-Nachfolgern und von isomorphen Knoten. Ein exaktes Verfahren, die "Branch and Bound"- Methode zur Minimierung von BDD, ist in (Molitor & Scholl 1999) zu finden.

Die exakte Vereinfachung zu einer eindeutigen minimalen Formel-Darstellung kann mittels Quine- McCluskey Algorithmus (einschließlich Patricks Methode) erfolgen - siehe (Becker, 2005). Heu­ristische Vereinfachungsverfahren sind z.B. das in (Brayton 1984) detailliert beschriebene und für diese Arbeit wichtige Simplify-Verfahren sowie das Espresso-Verfahren. Letzteres wurde auch in (Molitor & Scholl 1999) kurz beschrieben, ausführlicher in (Rudell 1986). Espresso ist auch nach Jahrzehnten noch in aktuelleren Verfahren als eine Vor-OBDD-Option enthalten. Fan-In- (von Malik et.al. - maximale Entfernung eines Knotens von primären Eingängen)) und Gewichts-(von Minato et.al. - Ausgangsge­wichte als Summe Gewichte getriebener Eingänge) Heuristiken und deren dynamische Verbesserung von Entscheidungsgraphen durch Sifting und Fenster Permutationen wie sie in (Molitor & Scholl 1999) und (Meinel & Theobald 1998) beschrieben sind, bestimmen die Variablenordnung in neueren OBDD- orientierten Verfahren.

In dieser Arbeit wird die heuristische Variablenauswahl (für die nächste Shannon-Zerlegung) und die Vereinfachung von Ausdrücken durch Reduktion der Terme nach dem Vorbild des Simplify-Algorith­mus - ergänzt um die geforderten Heuristiken 1-3- ausführlicher behandelt.

2.4 Benchmarks

In (Brayton 1984) zu Espresso oder mit dem Espresso nutzenden SIS aus dem Kurs "CSEE E6861y - Computer-Aided Design of Digital Systems" vom Frühjahr 2016 an der Columbia Universität http://www.cs.columbia.edu/~cs6861/ sind Sammlungen Boolscher Funktionen mit ihren Wahrheitsta­bellen im PLA-Format enthalten - siehe auch den Anhang dieser Arbeit. Die Größen entstehender Schaltkreise wurden nach der Reduktion in Benchmarks gemessen und veröffentlicht.

Neuere Benchmarks mit ISCAS, LGSynth, ITC und IWLS Funktionenzusammenstellungen (sets) von https://ddd.fit.cvut.cz/prj/Benchmarks/ verwenden auch andere Funktionsdefinitionen als Wahrheitsta­bellen in PLA-Dateien. Die Benchmarks nutzen viele Funktionen, die in Formaten wie SLIF, BLIF, VHDL, Verilog, PLA, KISS(2), ... definiert sind. Neuere Verfahren und Tools sind nicht nur für sta­tische Logikschaltungen, sondern auch für ihre dynamischen Erweiterungen mit Latches und Flip-Flops (= Sequential Networks), also ihr zeitliches Verhalten relevant. Der Schaltungsentwurf wird auch auf konkrete Hardware-Technologie gemappt und dafür optimale Schaltungs- Größen-,Timings und Ener- gieverbräuche ermittelt. An der University of California at Berkeley hat dazu eine Entwicklung über folgende Systeme von alt zu neu stattgefunden: Espresso, MIS, SIS, VIS, ABC. Der für diese Arbeit in C/C++ implementierte Simplify-Algorithmus und die Erweiterungen für die geforderten Heuristiken 1­3 gehören in die Vor-Espresso-Zeit.

Auch andere Universitäten wie z.B. die Carnegie Mellon (OBDD-Paket von D. Long) und von Colora­do at Bolder (CUDD-Paket/C-Bibliothek von F. Somenzi für Decision Diagrams) haben Software ent­wickelt, die die in Bäumen/DD repräsentierten Boolschen Funktionen manipulieren (reduzieren, in andere Typen konvertieren, anzeigen,...) - siehe (Meinel & Theobald 1998).

Die in üblichen Benchmarks verwendeten Funktionen haben viele Ausgabevariablen und viele Ein­gabevariablen). Da diese Arbeit nur Funktionen mit einer einzigen binären Ausgabevariablen unter­suchen soll, wird bei Funktionen mit mehreren nur die jeweils erste Ausgabevariable berücksichtigt. Vorzugsweise werden künstliche Funktionen per Zufallsgenerator erzeugt, die nur eine Ausgabeva­riable haben. Diese Arbeit konzentriert sich vornehmlich auf das Größen-Ergebnis der Zerlegung/ Minimierung, während veröffentlichte Benchmarks stattdessen Größen-, Timing- und Energie-Ergeb­nisse der Reduktion und des Technologie-Mappings bewerten. Da Minimierungsverfahren ähnlich dieser Arbeit vor recht langer Zeit aktuell waren, wurden für zugehörige Benchmarks wesentlich lang­samere Rechner verwendet. Auch deshalb sind eigene Ergebnisse mit veröffentlichten nicht mehr ver­gleichbar - ausgenommen von (Eigen 1999).

3 Implementierung

Die Programmieraufgaben dieser Arbeit waren in C/C++ zu erledigen. Freier C-Code ist insbesondere für aktuelle Verfahren der Funktionsvereinfachung, Hardware-Synthese und Verifikation in ABC, aber auch in SIS, CUDD für BDD, Espresso, ... enthalten. Da die Aufgabenstellung recht alte Verfahren zum Gegenstand hat, was didaktisch wegen der besseren Überschaubarkeit der Algorithmen Sinn macht, und es aufwändig und fehleranfällig ist, aus großen Software Systemen wie ABC kleine Stücke herauszupicken, die dann vermutlich nicht autark arbeiten können, wurde der Neuentwicklung des C/C++ - Codes der Vorzug gegeben. Als Entwicklungsumgebung (IDE) wurde "Code::Blocks" in der Version 16.01 mit einem GNU GCC Kompiler (mingw32-gcc und mingw32-g++) mit eingeschaltetem 2011er ISO-Standard für C++ verwendet - siehe (Griffith, 2002)

Für die Generierung der Programmdokumentation (auf der Begleit-DVD zu dieser Arbeit) wurde Doxygen in der Version 1.8.13 in Verbindung mit GraphViz (dot) Version 2.38 und Ghostgum Gsview Version 5.0 verwendet. Doxygen wertet die C/C++ Kommentare zu Beginn von Funktionen aus, wenn diese wie in dieser Arbeit mit "/**" statt nur mit "/*" eingeleitet werden und kopiert sie in die generierte Dokumentation. Die Graphen in dieser Arbeit wurden mit GNUplot Version 5.0 programmiert oder mit Dia Version 0.97 gezeichnet. Die Arbeit an sich wurde mit Libre Office Version 5.1 (Komponenten Writer und Calc) erstellt. Alle verwendeten Tools sind Open-Source-Software und funktionieren glei­chermaßen unter MS-Windows und Linux (Kofler, 2016).

Für die Überprüfung der Arbeitsweise der Programme und der Zwischenergebnisse in Variablen wurde nicht nur der GNU-Debugger (Haltepunkte, Einzelschritt, ...) verwendet, sondern über Preprozessor­Direktive "#define" auch zwei Variablen DEBUG12 gesetzt. Wenn eine oder beide gesetzt sind, er­scheint im Ausgabefenster sehr viel mehr Information als ohne.

3.1 Simplify-Algorithmus mit Heuristik 0

(Brayton 1984) beschreibt in Kapitel 3 einen Algorithmus zur Vereinfachung von Boolschen Funktio­nen: Simplify nutzt dabei die Shannon-Zerlegung. (Eigen 1999) vergleicht Quine-McCluskey, Simplify und, im Ansatz, Espresso und weist für die beiden erstgenannten eigene Benchmarkergebnisse bezüg­lich der Reduktion der Zahl der Terme und der Rechenzeit aus. Der exakte Quine McCluskey Algorith­mus bringt dabei stärkere Reduktionen der Zahl der Terme (und Literale), benötigt aber sehr viel mehr Rechenzeit als das heuristische Simplify und ist bei vielen Eingangsvariablen (bei David Eigen waren es nur maximal 10) zu aufwändig. (Eigen 1999) liefert auch Java Code für die Funktionen innerhalb von Simplify. Simplify bekommt als Input die Zeilen der Wahrheitstabelle, die eine '1' als Funktions­resultat haben (also das sogenannte OnSet) ohne die Spalte für die Ausgangsvariable als Vektor. Im Rahmen dieser Arbeit wurde der Simplify-Algorithmus in C/C++ implementiert, um weitere Heuristi­ken 1-3 zur Auswahl der Spalt-Variablen, Funktionsgenerator, Benchmarkprogramme und Hilfsfunk­tionen für das Drucken von Wahrheitstabellen von Funktionen zumindest während des Debuggings, ... ergänzt.

3.1.1 Algorithmus im Überblick

Statt ein Header-File mit allen Funktionsdeklarationen undje Funktion eine Quelldatei, diejeweils 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 Aus­gabe = 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:

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3: Ablauf und Zusammenhang der Funktionen im Simplify-Algorithmus mit Dia erstellt

Für einen Überblick über Funktionen, ihre Parameter und Rückgabewerte seien hier auch ihre Forward­Deklarationen im Hauptprogramm main() gezeigt, die bei einer Aufteilung auf viele Quelldateien in eine Headerdatei zu schreiben wären:

Abbildung in dieser Leseprobe nicht enthalten

Funktionsdefinitionen können mit ttGen() zufalls-generiert oder mit read_pla() aus pla-Datei eingelesen werden. Mit write_pla() können Funktionen vor und nach Reduktionen durch verschiedene Heuristiken in Dateien geschrieben und darüber in Tools wie Espresso, SIS, ABC, ... verarbeitet (z.B. zur Kontrolle von Heuristik 1-3) werden.

Bei einfachen Funktionen (mit z.B. nur 3 Eingangsvariablen) erreichen alle Heuristiken (HO=Original- Simplify mit binate_select(), H1 mit binate_select_1() bis H3 mit binate_select_3()) nach wenigen Rekursionen das gleiche Reduktionsergebnis, das exakter Reduktion entspricht.

Unterschiede in den reduzierten Versionen, der Anzahl der benötigten Rekursionen, den dabei jeweils ausgewählten Spaltennummern, den Reduktionsgraden (aus Einsparung von Termen) und nötiger Rechenzeit werden erst bei Funktionen mit mehr Eingangsvariablen sichtbar.

Simplify führt rekursiv Shannon-Zerlegungen der Funktion in ihre Kofaktoren durch bis sich eine unate

Funktion ergibt. Eine uñate boolsche Funktion hat in jeder Spalte der Wahrheitstabelle zu einer Ein­gangsvariablen nur len oder nur Oen (oder auch zusätzlich 2en für don't cares, die ja passend als Oen oder len ausgelegt werden können). In Programmen wie ABC werden Don't cares bei den Eingangsva­riablen auch als "-" dargestellt. Da die Programme dieser Arbeit mit Vektoren von Integern arbeiten, wird dagegen die "2" gewählt, die ABC ebenfalls als Don't care interpretiert. Eine unate Funktion ist monoton in all ihren Eingangsvariablen. Eine solche Funktion wird durch "unate_simplify()" verein­facht, indemjeder Implikant/Term, der in anderen enthalten ist (also von anderen überdeckt wird), ent­fernt wird.

Die Eingangsvariable (splittingVar), für die die nächste Shannon-Zerlegung stattfinden soll, wird mit "binate_select()" ermittelt. Eine Funktion, die (noch) nicht unate ist, wird binate genannt. Die Spalten der Wahrheitstabelle zu ihren Eingangsvariablen enthalten Oen und len gemischt. "binate_select()" er­mittelt die (splitting-)Variable für die die Funktion am stärksten binate ist, also Anzahl(Oen) + An­zahlen) ein Maximum ist. Damit ist für die gewählte splitting-Variable die Anzahl der relevanten Zeilen aus zugehöriger Wahrheitstabelle maximal. Dies sei Heuristik HO genannt.

3.1.2 Funktion main()

Der Startpunkt eines jeden C/C++ Programms ist die Funktion main(). Diese Funktion enthält min­destens den Aufruf von simplify() mit einer Funktionsdefinition, die z.B. mit ttGen() + dec2bin() + OnSet() generiert oder mit read_pla() aus einer PLA-Datei eingelesen wurde. In main() kann auch die Funktion benchmark() aufgerufen werden, die viele Funktionen generiert, in PLA-Dateien dokumen­tiert, die Funktionen mit verschiedenen Heuristiken vereinfacht und die Ergebnisse aufzeichnet.

Im folgenden Beispiel für main() wird die zu vereinfachende Funktion "f' als On-Set, mit allen Termen (Zeilen aus der Wahrheitstafel) die zum Ergebnis = 1 führen, definiert. "f" hat 3 Eingangsvariablen und wird mit der Heuristik 0 (Original des Simplify-Algorithmus) vereinfacht. Das Minimierungsergebnis wurde manuell in ABC geprüft (siehe //-Kommentare) und mit der Funktion OnSetVergleich() auch automatisch. OnSetVergleich() schreibt dazu vor und nach der Minimierung PLA-Dateien, erzeugt in ABC daraus Wahrheitstafeln und vergleicht diese dann bitweise.

Abbildung in dieser Leseprobe nicht enthalten

3.1.3 Funktionen simplify(), unate() und cofactor()

Die Gleichung 1, die die Shannon-Zerlegung der Funktion in zwei Kofaktoren beschreibt, wird durch den Aufruf der Funktion merge() realisiert. Dieser Aufruf steht in der Funktion simplify() und die Para­meter von merge() enthalten wiederrum zwei Aufrufe vom simplify() für die zwei Kofaktoren hO und hl und die zugehörige Spalt-Variable - hier findet also die Rekursion der Shannon-Zerlegung statt:

Abbildung in dieser Leseprobe nicht enthalten

Die Rekursionen enden dort, wo in simplify() festgestellt wird, dass eine Teilfunktion inzwischen unate geworden ist und gegebenenfalls mit unate_simplify() vereinfacht werden kann. Zum Pseudo-Code von simplify() siehe Abbildung 4:

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 4: Pseudocodefür simplify() nach (Eigen 1999)

Dies wurde mit folgendem C/C++ Code realisiert - die Debug-Abschnitte, die bei gesetzten DEBUG- Variablen alle möglichen Informationen anzeigen, wurden dabei weggelassen. Die zu minimierende Funktion muss als OnSet (nur die Zeilen der Wahrheitstafel, die die Ausgabe=l erzeugen, ohne die Ausgabespalte, also nur Eingabespalten) in Form eines Vektors eines Vektors von Integern (0, l oder 2 für Don’t Care Eingaben) eingespeist werden.

Abbildung in dieser Leseprobe nicht enthalten

unate() prüft, ob das die minimierende Funktion definierende OnSet ausschließlich unate Spalten be­sitzt. Eine Funktion ist nur unate, wenn alle Eingabespalten unate sind. Jede Spalte darf also nur ein­heitlich Oen oder len enthalten, aber keine Mischung aus beiden. Don't cares (= 2er) sind neben len oder Oen auch erlaubt, da sie passend ausgelegt werden können: also als l, wenn sonst nur len in der Spalte vorhanden sind, oder als O, wenn sonst nur Oen in der Spalte Vorkommen.

In der äußeren for-Schleife werden daher alle Spalten (von Spaltennummer O beginnend) durchgegan­gen. In einer inneren for-Schleife werden für die aktuelle Spalte alle Zeilen ausgewertet. Sobald ein Wert gefunden wird, der weder "2" ist, noch mit einem vorherigen Wert übereinstimmt und auch der vorherige Wert keine "2" war, ist die Spalte und damit die ganze Funktion nicht mehr unate. Es wird abgebrochen und ein "false" zurückgegeben:

Abbildung in dieser Leseprobe nicht enthalten

Beim Aufruf von merge() in sinplify() stehen in der Parameterliste von merge() neue simplify()-Auf- rufe über die Kofaktoren der zu minimierenden Funktion. Im Original Simplify-Algorithmus wird cofactor() nur innerhalb von simplify() aufgerufen, und soll deshalb hier behandelt werden. Es wird aber nach der Erweiterung auf die Heuristiken 1-3 auch dort in binate_select_123() verwendet.

cofactor()

Außer der zu spaltenden Funktion, braucht cofactor() auch noch die Stelle der Spaltung (Spaltennum­mer) und den Wert (true oder false) der in dieser Spalte zu suchenden Einträge. “cofactorQ“ liefert nur einen der beiden zu einer Zerlegung gehörenden Kofaktoren zurück. Um beide zusammengehörenden Kofaktoren (f_xi und f_xi' für die Zerlegung in Spalte i) zu bekommen, muss die Funktion cofactor() zweimal aufgerufen werden. Beide Aufrufe erfolgen mit gleicher Funktion und gleicher Spaltennum­mer, aber einmal mit Wert "true" und ein anderes Mal mit Wert "false". In die Spalte, an der die Spaltung in Kofaktoren stattfand, wird eine "2" als Don't Care eingetragen. Da auch vorher schon 2en in den Eingabespalten vorhanden sein können, finden sich die Zeilen, die in einen Kofaktor gehören, nicht einfach als solche, die in der relevanten Spalte eine 1 oder eine 0 haben:

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 4: Kofaktoren zu Shannon-Zerlegungen an allen Spalten

3.1.4 Funktionen merge() und intersect()

In merge() wird versucht, die Funktion zu vereinfachen, indem Terme (Implikanten), die in beiden Ko­faktoren enthalten sind, aus diesen entfernt und in eine neue Subfunktion h2 verschoben werden, denn es gilt Gleichung 2:

Abbildung in dieser Leseprobe nicht enthalten

Weiterhin wird in merge() geprüft, ob ein Implikant eines Kofaktors einen des anderen Kofaktors über­deckt (engl, covers) also im Bild von Kamaugh Maps das ler-Gebiet des einen Implikanten das ler-Ge- biet des anderen als Teilgebiet enthält, Die eigentliche Prüfung findet durch die Funktion “contains()‘‘ statt, Überdeckte Terme/Implikanten werden mit der gleichen Begründung wie in Gleichung 2 ebenfalls aus den beiden Kofaktoren entfernt und in die Subfunktion h2 verschoben, Abbildung 5 zeugt den Pseudocode von merge():

Da merge() von simplify() (und damit auch simplify() selbst in der Parameterliste von merge() ) immer

wieder rekursiv aufgerufen wird, wurde eine globale statische Variable "NumRecur" außerhalb aller Funktionen deklariert und definiert (=0), die in merge() inkrementiert wird, so dass am Ende des Pro­grammlaufs die Anzahl der Rekursionen auswertbar ist. Noch detailliertere Informationen über die Re­kursionen enthält der Vektor "slitVarVec" an den die Spaltennummer "splittingVar" (die von den Aufru­fen von binate_select...() stammt) für die Position der Shannon-Zerlegung in jedem Durchlauf von merge() angefügt wird:

Abbildung in dieser Leseprobe nicht enthalten

Wenn ein neuer Durchlauf der Minimierung der Funktion, etwa mit anderer Heuristik, stattfinden soll, müssen beide zunächst zurückgesetzt werden:

NumRecur=0; splitVarVec.clear();

Neben der rekursiven Shannon-Zerlegung hat merge() den Zweck die Funktion zu vereinfachen (zu re­duzieren), indem Terme, die in gleicher Weise in beiden Kofaktoren h0 und hl vorhanden sind, dort ge­löscht und in einen neuen Vektor h2 verschoben werden, der später nicht wie die Kofaktoren mit zuge­hörigen 0 und l Werten der Spalt-Variablen zum Schnitt gebracht wird (in intersect() ):

Abbildung in dieser Leseprobe nicht enthalten

Eine weitere Reduzierung der Funktion erfolgt, wenn Terme in einem Kofaktor Terme im anderen Ko­faktor überdecken, also allgemeiner sind. Dann wird der überdeckte (speziellere) Term vom Kofaktor in den Vektor h2 verschoben. Beide Reduzierungen gehen auf Gleichung 2 zurück.

Abbildung in dieser Leseprobe nicht enthalten

Die eigentliche Überprüfung auf Überdeckung wird von contains() geleistet. Contains() wird in glei­cher Weise von unate_simplify() verwendet, wo darauf näher eingegangen wird.

Nach der Reduktion müssen entsprechend dem Shannon'schen Entwicklungssatz die verbleibenden bei­den Kofaktoren mit der Spalt-Variablen und ihrer Negation UND-verknüpft werden. Die vorher aus den Kofaktoren nach h2 verschobenen Terme müssen dem Ergebnis durch ODER-Verknüpfung auch noch hinzugefügt werden, sodass aus Gleichung 1 folgende Gleichung 3 wird:

Abbildung in dieser Leseprobe nicht enthalten

Die UND-Verknüpfung von Spalt-Variable und zugehörigem Kofaktor leistet die Funktion intersect(). Da sie nur hier von der Funktion merge() aus zweimal aufgerufen wird, soll sie an dieser Stelle behan­delt werden.

intersect()

Die Terme der Funktion enthalten Integerwerte 0 (für False), 1 (für True) oder 2 (für Don't care) und sollen mit boolschen Werten UND-verknüpft werden. Das geht leichter wenn der boolsche Wert "value" des Eingabeparameters von intersect(Funktion, Spalt-Variablen-Nr, value) in Integerwerte über­setzt wird. Dazu dienen die beiden Integer-Variablen "notVal" und "loweredVal", die je nach "value" folgende Werte (siehe Tabelle 5) haben:

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 5: Umsetzung boolscher Variablen "value" in zwei Integer-Variablen für intersect()

Wenn ein Implikant der Eingabefunktion an der Stelle der Spalt-Variablen eine "2" besitzt (dieja als 0 oder 1 ausgelegt werden darf), wird sie durch "loweredVal" als Integer-Äquivalent des boolschen Wer­tes von "value" ersetzt. Wenn an dieser Stelle aber eine 0 oder 1 steht und diese gleich "NotVal" (dem Integer-Äquivalent des boolschen Wertes von NOT(value) ) ist, dann wird der Term/Implikant aus der Eingabefunktion entfernt:

Abbildung in dieser Leseprobe nicht enthalten

[...]