[VLSI CAD] 两级逻辑化简难以实现的原因

TL;DRDR

• 要"精确"求解两阶逻辑最小化问题，必然会采用Quine–McCluskey(QM)算法路径。
• QM算法的瓶颈在于覆盖(最小列覆盖)阶段。
  • 由于覆盖问题属于NP完全问题， “最优解”不再是数值而是证明问题。
  • SAT问题几乎不成问题，因其本质属于决策问题。

EDA通过启发式+剪枝+分支界定法快速生成“足够好的解。

什么是两级逻辑最小化？

场景

假设存在三个开关。

• A： 开关1
• B：开关2
• C：开关3

灯泡F在以下三种情况下点亮：

1. A=0, B=0, C=1 → A'B'C
2. A=0, B=1, C=1 -> A'BC
3. A=1, B=0, C=1 -> AB'C

即，F = A'B'C + A'BC + AB'C

👉 3个AND + 1个OR
👉 冗长无谓。

将此简化的过程即为优化过程。

仔细观察三个表达式可知：

• C始终为1
• A、B可自由变换

即 F = C(A'B' + A'B + AB')

进一步缩减内部部分，

A'B' + A'B = A'(B' + B) = A'

即，F = C(A' + AB')

再整理如下。

A' + AB' = A' + B'

最终结果（两级逻辑最小化）

F = (A' + B')C

AND、OR的数量减少，表达式也简化了。 这意味着在硬件层面，单元和互连数量减少了。

简而言之

不要逐条书写灯泡点亮的条件，
只需保留并归纳共同条件。

这就是两级逻辑简化法。

更学术地说：

将给定的布尔函数(f)用最少的积项(SOP)表示。

此时核心材料是：

• minterm：真值表中(f=1)的输入组合（或扩展立方体前的节点）
• prime implicant：无法进一步合并的"最大立方体"
• 目标：用prime implicant完全覆盖所有(f=1)的minterm， 同时将选定的素数（或成本）最小化

QM（Quine–McCluskey）的运作机制（精确解法）

上图中编号4为主体。

求解B的最小列转换问题（单位转换问题）

首先了解量子力学（QM）。

灯泡问题重启

灯泡F点亮的情况仅有三种。

1. A熄灭，B熄灭， C 亮起
2. A 熄灭，B 亮起，C 亮起
3. A 亮起，B 熄灭，C 亮起

现在我们这样理解：

“存在灯泡亮起的精确开关状态列表。”

什么是奎因-麦克卢斯基法则？

这是计算机仅凭规则自动组合条件的机制。

规则仅有一条：

当灯泡点亮的两种情况
仅有一个开关不同时，
该开关无关紧要。

1️⃣ 首次合并（仅开关1不同时）

情况1 vs 情况2

• A: 均关闭
• C: 均开启
• 仅B不同

B不重要
“A关闭，C开启即可”

仅此条件即可

• (A=0, B=0, C=1)
• (A=0, B=1, C=1)
  同时解释两种情况

情况1 vs 情况3

• B: 均关闭状态
• C: 均开启状态
• 仅A状态不同

A状态无关紧要
“B关闭，C开启即可”

仅需满足此条件即可

• (A=0, B=0, C=1)
• (A=1, B=0, C=1)
  两种情况可同时说明

情况2 vs 情况3

• A也不同
• B也不同

两个开关不同时
根据量子力学规则无法合并

2️⃣ 再次检查是否可合并

当前剩余条件为两项：

• 条件 X：“A无关紧要，B处于关闭状态，C处于开启状态”
• 条件 Y：“A关闭，B无关，C开启”

比较两者：

• A不同
• B不同

因两个开关状态不同，
无法进一步合并

3️⃣ 最终剩余的说明

因此灯泡点亮的条件是：

C处于开启状态，
且A处于关闭状态或
B处于关闭状态

即，F = C(A' + B')

这正是Quine–McCluskey算法的本质

• ✔️ 完整列举所有"点亮情况"
• ✔️ 自动合并仅需改变单个开关即可满足的条件
• ✔️ 无法继续合并时停止操作
• ✔️ 剩余条件遵循最小逻辑原则

在灯泡点亮的条件中，
若仅需改变单个开关仍能点亮，
则该开关可忽略不计。

将此规则贯彻到底的方法即为Quine–McCluskey算法。Quine–McCluskey(QM)的计算量呈指数级增长。
变量稍有增加，计算机便不堪重负。为什么？ 情况数量太疯狂了

假设变量数量为n，可能的输入情况：2ⁿminterm最大数量：2ⁿ

例：6变量 → 64种10变量 → 1,024种15变量 → 32,768种20变量 → 1,048,576种QM处理的是“涵盖所有开启情况”
在此阶段已彻底解决2️⃣ QM进行“所有双比较”

QM的本质在于：“这个最小项和那个最小项是否仅有1位不同？”

即：当最小项有M个时比较次数≈M²

例：1,000个 → 100万次比较10,000个 → 1亿次比较30,000个 → 9亿次比较3️⃣ 真正的地狱是“Prime Implicant选择”

量子力学的最糟部分是最后阶段。Prime implicant数量激增“这个能覆盖所有minterm吗？”的探索这本质是集合覆盖问题NP-难问题，必须穷尽所有情况才能得出答案什么是SAT？

SAT（布尔可满足性）正是这个核心问题：“是否存在使该逻辑式为TRUE的输入赋值方案？哪怕仅存在一种？”

存在则为SAT，不存在则为UNSAT。
核心在于这是Yes/No(存在性)问题。为何SAT在实际工作中表现良好，而优化却始终困难？

这里正是许多人感到困惑的点，但结论其实很简单。(1) SAT属于decision(存在)类型，因此“找到一个解即结束”SAT求解器仅需找到一个解即可终止。若为UNSAT，则通过累积证明（实际应用中采用冲突驱动学习）来展示"不可行性"，从而强化剪枝效率。因此即使未遍历所有情况，早期退出现象也频繁发生。(2) 优化需要 需要“最优性证明”才能终结

优化真正的要求是这样的。“证明不存在更优解。”

即：找到比初始解更优的解只是起点必须证明不存在更优解才能称之为"全局最优"

其难点在于最终需要广泛排除组合空间。

仅以我们刚才看到的三个灯泡示例，就需要进行多次计算。 然而观察2020年后设计的智能手机半导体，其内置晶体管数量已突破100亿个。(3) SAT求解优化的标准技巧，即“迭代”过程较为耗时

将优化问题转化为SAT的典型方法：设置"成本 ≤ k"等约束条件，求解SAT问题若成立则缩小k值重新求解SAT若不成立则增大k值或终止（=二分搜索/迭代收紧法）

即，并非仅求解一次SAT，而是多次求解。 而且k值越小，约束条件越严格，往往难度越大。(4) EDA通常并非单目标优化，而是更复杂的混合问题

实际工程中的EDA通常包含：时序/面积/功耗/ 拥塞/可布线性…等多目标约束约束条件也存在边界/模式等多重条件成本函数并非连续，而是呈现“突突”变化的崎岖地形

因此“最优”一词变得更具风险。
多数情况下，“最佳发现/基准改进”才是更诚实的表述。“枚举与优化”的差异SAT（存在性问题）: “是否存在至少一个满足解？” → 找到一个即可终止优化问题：“是否满足最小/最大条件？” → 需证明“不存在”更优解才结束

即，优化要求的是不存在证明(no better solution)，而非值查找。QM的覆盖表规模过于庞大。minterms数量约为~ (2^n) (行数)primes数量约为~ (3^n/n) (列数)且最小覆盖问题属于NP完全问题

具体表现为：情况数量庞大在众多素数中选择“最小组合”的瞬间将引发组合爆炸

因此QM虽能提供“精确最小值”的方案，但当规模扩大时，在工业现场难以应用。因此在工业现场中，启发式方法采用“"足够好且稳定"的解从免费确定的情况开始固定：essential prime缩减情况表本身：dominance / equality最终剩余的核心情况：cyclic core

经过所有缩减后残留的"环状结构"即为cyclic core。
此后通常采用：分支界限法通过构建启发式算法生成“优质界限”结论： EDA中困难之处不在于“计算”，而在于“最优性证明”

双层逻辑化简是绝佳的教学案例。
因为仅需解决一次NP完全覆盖问题，就能轻松推导出EDA全流程（布局/布线/调度/…）的现实困境。EDA是工程学。
目标在于实现"快速、稳定且指标优化"。

检查清单：

• 是否存在实际的最优性保证证明？
• 问题规模(n)是多少？
• 对比基准是启发式基准还是"最优"基准？
• 目标函数是什么？（仅计时？ 仅面积？仅功率？)
• 是否存在种子重复/分布？（验证稳健性）
• 因此是否可复现？

若不了解全局最优解，"相较最优解提升50%"的表述便不成立。
实际EDA评估通常采用以下标准：

1. PPA：面积/功耗/时序（WNS/TNS等）的绝对值是否优于现代方法论？
2. 基准对比改进（现状 vs 目标）：相较于前次运行/选项/工具的提升幅度
3. 鲁棒性： 在种子/边界条件变更时结果是否稳定
4. 运行时效率