用于优化特定指令集的连接法线形式表达式的算法？

Question

我正在使用Espresso逻辑最小化器来生成一组布尔方程的最小化形式.然而,我不是为可编程阵列逻辑(通常用于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的选项或扩展名会产生我想要的那种表达吗？

您是否知道任何可以理解(或可以教授)各种门类型的布尔逻辑最小化工具,而不仅仅是为PAL制作CNF？

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

如果你不知道它的算法,你知道或者可以想到任何有用的启发式方法吗？

(并且,以防万一你建议它 - 测试显示GCC和ICC(或者,我敢打赌,现有的任何其他C编译器)都不够聪明,不能从CNF表达式为我做特定于处理器的最小化 - 这真的很不错,但是检查两个-O3 -S的输出显示它们甚至无法捕捉到可以使用XOR的情况.

Answer 1

布尔公式最小化最着名的算法是Quine-McCluskey算法,它产生最小的DNF公式,但计算成本高(必然,因为问题在PTIME之外,参见布尔公式最小化的复杂性,2007).有一个有文化的Java实现 ; 基本概念对Prolog至关重要,所以如果您对Prolog有任何经验,那么这个想法应该很容易实现.

后记有一篇IEEE-paywalled文章,将Quine-McCluskey扩展为独占或逻辑综合,摘要:

在电子工程学位中使用各种形式的布尔最小化作为教学大纲的关键部分.通常,卡诺图和Quine-McCluskey方法是本科水平数字最小化的主要搜索技术,因为它们易于使用且易于理解.尽管这些方法很受欢迎,但它们并不适合典型的数字电路.这种电路的简单示例是奇偶校验,加法器,格雷码生成器等.其中的共同因素是Exclusive-Or逻辑门.Exclusive-Or在现代设计中的重要性日益增加,这一问题更加严重.本文提出了Quine-McCluskey方法的扩展,该方法在最小化过程中成功地结合了Exclusive-Or门.举例说明了这种方法的有效性.这种技术很容易掌握,因为它可以被认为是Quine-McCluskey方法的扩展.

在我查看之前,我一直在考虑如何扩展该方法:您应该能够通过使用与它们对应的替代版本的分辨率来合成XOR的应用程序.例如,对于一个析取子句F在CNF,不含有任一原子的A,或者B,从子句F | A | ~B和F | ~A | B,然后就可以通过替换它们F | XOR(A,B).