6

我正在使用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 的情况）。

4

2 回答 2

6

最著名的布尔公式最小化算法是 Quine-McCluskey 算法，它产生最小的 DNF 公式，但计算量很大（必然地，因为问题在 PTIME 之外，参见布尔公式最小化的复杂性，2007）。有一个识字的Java实现；基本概念对 Prolog 至关重要，因此，如果您对 Prolog 有任何经验，那么这个想法应该很容易实现。

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

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

在查找之前，我一直在考虑如何扩展该方法：您应该能够通过使用与它们相对应的替代版本的分辨率来综合 XOR 的应用程序。例如，对于FCNF 中的析取子句，它不包含子句and中的原子A或，那么您可以将它们替换为。BF | A | ~BF | ~A | BF | XOR(A,B)

于 2009-12-14T10:21:48.800 回答
3

1）您是否考虑过使用超优化来为您选择指令序列？

例如，GNU 超级优化器会制造极短的指令序列，这些指令序列将计算您提供给它的函数的等价物。在您的情况下，您将提供一个实现感兴趣的布尔方程的函数。

这些工具通常通过从最小的开始枚举可能的计算空间来操作，并确定单个计算是否符合您的计算目标。他们不一定能为非常复杂的指令提供解决方案（更不用说最佳解决方案了），但是如果少量的指令能够成功，他们通常会找到一个（不寻常的！）非常有效的序列。XOR/NOR/ANDC 很容易在 GNU 超级优化器的范围内。

2）您可以尝试使用带有正确代数等价集的代数简化器。我们使用了我们的DMS 软件再造工具包，一个接受任意重写规则并理解交换律和结合律的程序转换引擎，以实现涉及 XOR 和 NOR 等各种运算符的布尔简化器。您需要规则应用程序、爬山算法（用最少的操作员爬山）和回溯算法。如果表达式不太复杂，则使用深度优先迭代深化搜索可以找到最佳解决方案；使用分支定界搜索，您可以快速找到解决方案，然后尝试最小化其大小。你甚至有一个相对较好的启发式度量：操作数到目前为止还没有包含在计算中。等式简化器的最大问题是它不会考虑特定指令集可用的寄存器约束或机会。

3) 您可以在可用的布尔指令集上实现自己的搜索（迭代深化、分支和绑定），并包含约束。（这在某种程度上回到了超级优化器所做的事情）。我这样做是为了计算在 x86 上实现乘以常数的最小指令序列，最多占用 3 个寄存器并利用 3 操作数指令，例如（加载有效地址）LEA X，[Y+K* Z] 在寄存器 X、Y、Z 上，常数 K=1、2、4、8、ADD X、Y、SUB X、Y、MOV 和 NEG 指令。如果你用任何合理的语言将它编码为递归程序，你可以在几百行中编写一个。（它会产生一些真正松鼠的序列）。

于 2009-11-04T03:13:37.750 回答