Algorithmen für Ausdrücke konjunktive Normalform für bestimmte Befehlssätze zu optimieren?

Question

Ich bin mit Espresso Logik minimizer eine minimierte Form eines Satzes von boolean zu erzeugen Gleichungen. Doch anstatt Logik für eine programmierbare Array-Logik zu erzeugen (was Espresso normalerweise verwendet wird), suche ich diese auf einem Standard-Mikroprozessor zu implementieren. Das Problem ist, dass Espresso Ausgabe in konjunktive Normalform erzeugt, die für ein PAL, aber nicht optimal für ein x86 oder PPC perfekt ist.

Zum Beispiel, Espresso ignoriert XOR ganz - in der unten Espresso-Ausgang, der subexpression (!B0&!B1&B2&!B3) | (!B0&!B1&!B2&B3) entspricht (!B0&!B1&(B2^B3)). Diese Substitution hat die Gate-Tiefe / kritischen Pfad des Ausdrucks erhöhen, aber wenn man bedenkt, dass ich auf Ausdrücke mit einer ausreichenden Anzahl von Begriffen bin auf der Suche, um vollständig die Ausführungsressourcen jeder CPU zu sättigen um es vernünftig scheint eine gewisse Tiefe Tor abzuwägen zur Reduzierung die gesamte Anzahl der Anweisungen. Ich würde auch gerne um es zu erweitern, um zu verstehen, wie Anweisungen wie ANDC verwenden oder NOR, die auf einigen Prozessoren für mich von Interesse zur Verfügung stehen.

Beispiel der CNF Ausdrücke Ich betrachte:

O0 = (B0&!B1&!B2&B3) | (!B0&B1&B2&B3) | (!B0&!B1&B2&B3) | (B1&!B3) | (!B0 &!B2&!B3);

O1 = (B0&B1&!B2&B3) | (B0&!B1&B2&!B3) | (B0&B1&B2&!B3) | (!B0&!B1&B2&!B3) | (!B0&!B1&!B2&B3) | (!B0&!B1&B2&B3) | (!B0&!B2&!B3);

O2 = (B0&!B1&!B2&B3) | (B0&!B1&B2&!B3) | (B0&B1&B2&B3) | (!B0&B1&!B3) | (!B0&!B2&B3) | (!B0&!B1&B2&B3);

O3 = (!B0&B1&!B2&!B3) | (B0&B1&B2&B3) | (!B0&B1&B2&B3) | (B0&B1&B2&!B3) | (B0&!B1&!B2) | (!B0&!B1&B2&!B3) | (!B0&!B1&!B2&B3);

Also, um dies eine tatsächliche Frage; in der Reihenfolge ihrer Präferenz:

Kennen Sie eine Option oder Erweiterung von Espresso, die die Art von Ausdrücken produzieren ich will?

Sie wissen, ein Werkzeug für Boolesche Logik Minimierung, die versteht (oder gelehrt werden kann) verschiedene Gate-Typen, anstatt nur CNF für PALs produzieren?

Kennen Sie einen Algorithmus für wie die von CNF Ausdrücke Umwandlung oben auf Ausdrücke mit zusätzlichen Arten von Toren?

Wenn Sie eines Algorithmus wissen nicht, für sie, wissen Sie, oder denken Sie an, jegliche nützliche Heuristik in dies zu tun?

(Und, falls Sie würden es vorschlagen - Tests zeigen, dass GCC und ICC (oder, ich würde wetten, andere C-Compiler existiert) sind nicht intelligent genug für mich, die prozessorspezifischen Minimierung zu tun aus die CNF Ausdrücke -. das wäre wirklich sehr schön, aber für sie beide die Ausgabe von O3 -S Prüfung zeigt, dass sie nicht einmal die Fälle fangen können, wo XOR verwendet werden kann)

Answer 1

Die meisten bekannten Algorithmus für Boolesche Formel Minimierung der Quine-McCluskey-Algorithmus, der die kleinste DNF Formel ergibt, ist aber teuer Rechen (notwendigerweise, da das Problem außerhalb PTIME ist, vgl Die Komplexität der booleschen Formel Minimierung 2007 ). Es gibt eine gebildete Java-Implementierung ; Das Grundkonzept ist entscheidend für Prolog, also wenn Sie keine Erfahrung mit Prolog haben, sollte die Idee leicht genug kommen.

Postscript Es ist ein IEEE-paywalled Artikel, Erweiterung Quine-McCluskey für exklusiv-oder Logiksynthese , abstract:

  

Verschiedene Formen der Boolesche Minimierung haben innerhalb Elektronik Grad als ein wesentlicher Bestandteil des Lehrplans verwendet. Karnaugh Karten und Quine-McCluskey Methoden sind die wichtigsten erschöpfenden Suchtechniken für digitale Minimierung während des Studium der Regel, da sie einfach zu bedienen und einfach zu verstehen. Trotz der Popularität dieser Methoden, sie sind nicht gut geeignet, um typische digitale Schaltungen. Einfache Beispiele solcher Schaltungen sind Parität, Addierern, Gray-Code-Generatoren, und so weiter. Der gemeinsame Faktor unter dieser ist das Exklusiv-Oder-Logik-Gatter. Dieses Problem wird durch die zunehmende Bedeutung von Exklusiv-Oder in modernem Design verschärft. Dieser Artikel schlägt eine Erweiterung der Quine-McCluskey Methode, die Exklusiv-ODER-Gatter innerhalb des Minimierungsprozesses erfolgreich integriert. Eine Reihe von Beispielen sollen die Wirksamkeit dieses Ansatzes zu demonstrieren. Diese Technik ist einfach zu meistern, wie es in Betracht gezogen werden kann, um eine Erweiterung der Quine-McCluskey Methode sein.

Ich hatte gedacht, wie das Verfahren zu verlängern, bevor ich dies sah: Sie sollten über eine alternative Version der Resolution zur Synthetisierung Anwendungen von XOR der Lage sein, die sie entspricht. Zum Beispiel für eine disjunktive Klausel F in einer CNF, die sie durch A weder die Atom B oder F | A | ~B, von der Klauseln F | ~A | B und F | XOR(A,B) enthält, dann ersetzen Sie können.

Answer 2

1) Haben Sie darüber nachgedacht mit Superoptimization Befehlssequenzen für Sie zu wählen?

Als Beispiel stellt die GNU superoptimizer extrem kurze Befehlssequenzen, die das Äquivalent einer Funktion berechnen werden Sie es schaffen. In Ihrem Fall würden Sie eine Funktion bieten die Boolesche Gleichung von Interesse durchführt.

Diese Werkzeuge arbeiten oft durch den Raum der möglichen Berechnungen Aufzählen mit dem kleinsten beginnen, und zu entscheiden, ob eine individuelle Berechnung Ihrer Berechnung Ziel übereinstimmt. Sie können nicht unbedingt bieten Lösungen (geschweige denn optimal sind) für sehr komplexe Anweisungen, aber wenn eine bescheidene Anzahl von Instruktionen erfolgreich sein wird sie finden oft ein (Ungewöhnlich!) Und sehr effiziente Folge. XOR / NOR / ANDC würde in Rahmen der GNU superoptimizer leicht sein.

2) Sie könnten versuchen, eine algebraische simplifier mit der rechten Menge der algebraischen Äquivalenzen zur Verfügung gestellt werden. Wir haben unsere DMS Software Reengineering Toolkit , ein Programm Transformations-Engine verwendet, die akzeptiert willkürliche Rewrite-Regeln und versteht kommutative und assoziative Gesetze, boolean Vereinfacher zu implementieren, die verschiedenen Operatoren wie XOR beinhalten und NOR. Sie müssen die Regel-Applikators und einen Hill-Climbing-Algorithmus (den Hügel mit der geringsten Anzahl von Betreibern Klettern) und einen Backtracking-Algorithmus. Mit einer Tiefe-ersten iterativen Vertiefung Suche können Sie eine optimale Lösung zu finden, wenn der Ausdruck nicht zu komplex ist; mit einem Zweig und gebundener Suche Suche können Sie eine Lösung schnell und dann versuchen, finden die Größe zu minimieren. Sie haben sogar eine relativ gute hueristic Maßnahme: Operanden bisher nicht in die Berechnung einbezogen. Das größte Problem mit einer equational simplifier ist, dass es nicht in Betracht, die Register Zwänge und Möglichkeiten mit Ihrem spezifischen Befehlssatz nehmen.

3) Sie können Ihre eigene Suche (iterative Vertiefung, Zweig und gebunden) über die Sätze von Booleschen Anweisungen zur Verfügung, und sind die Einschränkungen umzusetzen. (Dies ist immer etwas zurück, was die superoperoptimizers tun). Ich habe diesen minimale Befehlsfolgen zu berechnen getan zu implementieren Multiplizierens mit konstant auf x86, einen Anteil von bis zu 3 Registern und unter Ausnutzung von 3-Operanden-Befehlen, wie beispielsweise (load effektiver Adresse) LEA X, [Y + K * Z] auf Register X, Y, Z mit der konstante K = 1,2,4,8, ADD X, Y, SUB X, Y, MOV und NEG Anweisungen. Wenn Sie dies als eine rekursive Programm in jeder angemessenen Sprache Code können Sie Code ein in ein paar hundert Zeilen. (Es produziert einige wirklich squirrely Sequenzen).