优化特定指令集的合取范式表达式的算法？

Question

我正在使用 Espresso logic minimizer生成一组 bool 方程的最小化形式。然而，我不是为可编程阵列逻辑生成逻辑(这是 Espresso 通常使用的)，而是希望在标准微处理器上实现这些逻辑。问题是 Espresso 以合取范式生成输出，这对 PAL 来说是完美的，但对 x86 或 PPC 来说不是最佳的。

例如，Espresso 完全忽略 XOR - 在下面的 Espresso 输出中，子表达式 (!B0&!B1&B2&!B3) | (!B0&!B1&!B2&B3) 等同于 (!B0&!B1&(B2^B3))。这种替换确实增加了表达式的门深度/关键路径，但考虑到我正在查看具有足够数量项的表达式以完全饱和周围任何 CPU 的执行资源似乎合理地权衡一些门深度以减少总指令数。我还想扩展它以了解如何使用 ANDC 或 NOR 等指令，这些指令在我感兴趣的某些处理器上可用。

我正在查看的 CNF 表达式示例:

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);

所以，让这成为一个实际的问题；按优先顺序:

你知道 Espresso 的一个选项或扩展可以产生我想要的那种表情吗？

您是否知道有任何 bool 逻辑最小化工具可以理解(或可以教授)各种门类型，而不仅仅是为 PAL 生成 CNF？

您是否知道将上述 CNF 表达式转换为使用其他类型门的表达式的算法？

如果您不知道它的算法，您是否知道或可以想到执行此操作的任何有用的启发式方法？

(而且，以防万一你要建议它 - 测试表明 GCC 和 ICC(或者，我敢打赌，任何其他存在的 C 编译器)不够聪明，无法为我做处理器特定的最小化CNF 表达式 - 这真的非常好，但是检查它们的 -O3 -S 的输出表明它们甚至无法捕获可以使用 XOR 的情况。

Answer 1

最著名的 bool 公式最小化算法是 Quine-McCluskey 算法，它产生最小的 DNF 公式，但计算量大(必然，因为问题在 PTIME 之外，参见 The complexity of Boolean formula minimization, 2007 )。有 a literate Java implementation ;基本概念对于 Prolog 至关重要，因此如果您有任何使用 Prolog 的经验，这个想法应该很容易理解。

后记 有一篇 IEEE 付费文章，Extending Quine-McCluskey for exclusive-or logic synthesis , 摘要:

Various forms of Boolean minimization have been used within electronic engineering degrees as a key part of the syllabus. Typically, Karnaugh maps and Quine-McCluskey methods are the principal exhaustive search techniques for digital minimization at the undergraduate level as they are easy to use and simple to understand. Despite the popularity of these methods, they are not well suited to typical digital circuits. Simple examples of such circuits are parity, adders, gray code generators, and so on. The common factor among these is the Exclusive-Or logic gate. This problem is exacerbated by the increasing importance of Exclusive-Or in modern design. This paper proposes an extension to the Quine-McCluskey method which successfully incorporates Exclusive-Or gates within the minimization process. A number of examples are given to demonstrate the effectiveness of this approach. This technique is easy to master as it can be considered to be an extension to the Quine-McCluskey method.

在查看此方法之前，我一直在考虑如何扩展该方法:您应该能够通过使用与它们相对应的替代版本的解析来合成 XOR 的应用程序。例如，对于 CNF 中的析取子句 F，它不包含子句 A 或 B 中的任何一个原子 F |一个 | ~B 和 F | 〜一个| B，那么你可以用F | 替换它们异或(A,B).