Reduzierung der Wahrheitstabelle auf ternäre Logikoperationen, vpternlog

Wie man eine Wahrheitstabelle in eine Folge von vpternlog Anweisungen übersetzt.

1. Übersetze die Wahrheitstabelle in eine logische Formel; Verwenden Sie z. B. Logic Friday.
2. Speichern Sie die logische Formel im Synopsys-Gleichungsformat (.eqn). Z. B. verwendete ich ein Netzwerk mit 6 Eingangsknoten A bis F, zwei Ausgangsknoten F0 und F1 und eine etwas komplizierte (nicht unabhängige) boolesche Funktion.

Inhalt von BF_Q6.eqn:

3. Verwenden Sie "ABC: Ein System zur sequentiellen Synthese und Verifizierung" des Berkeley Verification and Synthesis Research Centers. Ich habe die Windows-Version verwendet. Holen Sie ABC hier .

In ABC starte ich:

Möglicherweise müssen Sie choice; if -K 3; ps mehrere Male ausführen, um bessere Ergebnisse zu erzielen.

Die resultierende BF_Q6.bench enthält die 3-LUTs für einen FPGA:

4. Dies kann mechanisch in C ++ übersetzt werden:

Die Frage bleibt, ob der resultierende C ++ Code optimal ist. Ich glaube nicht, dass diese Methode (oft) die kleinsten Netzwerke von 3-LUTs ergibt, einfach weil dieses Problem NP-schwer ist. Außerdem ist es nicht möglich, ABC über die Befehlsparallelität zu informieren, und es ist nicht möglich, die Reihenfolge der Variablen so zu priorisieren, dass Variablen, die später verwendet werden, nicht an der ersten Position der LUT sind (da der erste Quelloperand überschrieben wird) das Ergebnis). Aber der Compiler kann schlau genug sein, um solche Optimierungen durchzuführen.

ICC18 gibt folgende Assembly:

ICC18 kann die Reihenfolge der Variablen in const auto n22 = _mm512_ternarylogic_epi64(F, n12, n16, 0xd9); in vpternlogq zmm15, zmm3, zmmword ptr[r11], 0CBh so ändern, dass die Variable F nicht überschrieben wird. (Aber komischerweise aus der Erinnerung 3 mal abgerufen ...)

Abgesehen davon, dass ich es dem Compiler überlasse, oder die hand-welligen Vorschläge im zweiten Abschnitt meiner Antwort, siehe HJLebbink antwortet mit FPGA Logik-Optimierungs-Tools. (Diese Antwort endete mit der Bounty, weil sie keine Antwort von irgendjemand anderem erhielt; sie ist nicht wirklich bounty-worthy.: / Ich schrieb sie, bevor es eine Bounty gab, aber ich habe nichts anderes hinzuzufügen.)

ICC18 optimiert verkettete _mm512_and/or/xor_epi32 intrinsics in vpternlogd -Anweisungen, gcc / clang jedoch nicht.

Auf Godbolt für diese und eine kompliziertere Funktion einige Eingaben mehrfach :

gcc -O3 -march=skylake-avx512 nächtliches Build

ICC18 -O3 -march=skylake-avx512

IDK, wie gut es ist, optimale Lösungen auszuwählen, wenn jede Variable mehrmals in verschiedenen Unterausdrücken verwendet wird.

Um zu sehen, ob es einen guten Job macht, müssen Sie die Optimierung selbst machen.   Sie möchten Mengen von 3 Variablen finden, die zu einem einzigen booleschen Wert kombiniert werden können, ohne diese 3 Variablen irgendwo anders im Ausdruck zu benötigen.

Ich denke, dass es für eine Wahrheitstabelle mit mehr als drei Eingängen möglich ist, nicht auf diese Weise in eine kleinere Wahrheitstabelle zu vereinfachen, wo eine der Spalten das Ergebnis einer ternären Kombination von drei ist die Eingänge. z.B. Ich denke, es ist nicht garantiert, dass es möglich ist, eine 4-Input-Funktion zu vpernlog + AND, OR oder XOR zu vereinfachen.

Ich befürchte definitiv, dass Compiler drei Eingaben zur Kombination auswählen können, die nicht so viel Vereinfachung wie eine andere Auswahl von drei ergeben.

Es kann sogar optimal sein, dass ein Compiler mit einer binären Operation oder zwei Paaren für eine Ternäroperation beginnt, besonders wenn dies eine bessere ILP ermöglicht.

Sie könnten wahrscheinlich einen Brute-Force-Wahrheitstabellen-Optimierer schreiben, der nach Triplets von Variablen sucht, die kombiniert werden können, um eine kleinere Tabelle nur für das ternäre Ergebnis und den Rest der Tabelle zu erstellen. Aber ich bin mir nicht sicher, ob ein gieriger Ansatz die besten Ergebnisse garantiert. Wenn es mehrere Möglichkeiten zum Kombinieren mit der gleichen Anzahl von Instruktionen gibt, sind sie wahrscheinlich nicht alle gleichwertig für ILP (Instruction Level Parallelism) .