3.4 兩級邏輯優化：Quine-McCluskey 與 Espresso 的啟發式展開#

邏輯優化的第一個黃金時代#

高階綜合把 C 語言變成 RTL，接下來的問題是：RTL 裡的布林函數怎樣用最少的閘實現？這個問題的第一個系統性答案比積體電路還早——1950 年代，兩級邏輯（two-level logic）最小化就已經有了完整理論。所謂兩級，是指「AND 平面接 OR 平面」的結構：函數寫成積項之和（Sum of Products, SOP），每個積項是一層 AND，求和是一層 OR。PLA（Programmable Logic Array）、PROM、乃至 PAL/GAL，都是這個結構的矽實現。在 FPGA 的 LUT 出現之前，兩級邏輯是可程式邏輯的代名詞，而優化兩級邏輯的演算法——Quine-McCluskey 與 Espresso——是 EDA 史上第一批真正商業化的核心演算法。

真值表與最小化的目標#

一個 \(n\) 輸入布林函數由 \(2^n\) 列的真值表定義。SOP 形式中，每個積項（product term / implicant 蘊含項）是若干輸入文字的 AND；若一個蘊含項所覆蓋的 minterm（最小項）都使函數為 1，它是合法的；不被任何更大的蘊含項包含的稱為質蘊含項（prime implicant）。最小化的目標有兩層：先求覆蓋所有 ON-set minterm 的最少質蘊含項個數，再在項數相同時求文字（literal）總數最少。這直接對應 PLA 的面積：項數 = 乘積項列數，文字數 = 輸入連線數。

Quine-McCluskey：精確最小化的極限#

Willard Quine 於 1952 年（兩篇論文）與 Edward McCluskey 於 1956 年（Bell Telephone Labs，其博士論文即完成此工作）建立了至今仍是精確最小化標準的兩階段演算法。

第一階段：枚舉所有質蘊含項。從 \(2^n\) 個 minterm 出發，反覆做相鄰合併——兩個僅在一個位元上不同的項可以合併（如 \(ab\bar{c}d\) 與 \(ab\bar{c}\bar{d}\) 合併為 \(ab\bar{c}\) ），不能合併者即質蘊含項。以位元表示法實作，每輪合併把項數大約減半，但總工作量是指數級的：質蘊含項個數本身可以達到約 \(3^n/\sqrt{n}\) 。

第二階段：質蘊含項圖表法（prime implicant chart）求最小覆蓋。先挑出本質質蘊含項（essential prime implicants，獨自覆蓋某個 minterm 者），剩餘未覆蓋的 minterm 轉化為集合覆蓋問題（set cover），用 Petrick 氏法（列舉所有覆蓋組合）或分支限界求解。集合覆蓋是 NP-hard 的，但對小規模問題精確可解。

Quine-McCluskey 的歷史地位有二：它證明了兩級最小化在數學上是良定義的（有唯一正確答案），同時也證明了它是計算上不可擴展的。 \(n\) 到 15、16 個輸入就會耗盡 1960 年代以至於今日的運算資源。這個「精確但爆炸」的困境，正是啟發式時代的前奏。

Espresso：啟發式展開的傑作#

1970 年代末至 1980 年代，UC Berkeley 的 Robert Brayton（1980 年代初自 IBM Watson 研究中心轉任 Berkeley）、Gary Hachtel、Curtis McMullen、Alberto Sangiovanni-Vincentelli 等人發展了 Espresso 系列演算法（Espresso-II 於 1984 年發表於 IEEE Transactions on CAD，Brayton、Hachtel、McMullen、Sangiovanni-Vincentelli 合著的《Logic Minimization Algorithms for VLSI Synthesis》同年出版，成為邏輯綜合的聖經）。Espresso 不追求精確最小，而是以一組幾何直覺強烈的局部操作反覆迭代，實務上得到與精確解非常接近（常常相等）的結果，速度卻快了幾個數量級。

Espresso 的核心循環是 expand–irreducible–reduce：

while 覆蓋無改善:
    EXPAND:   把每個積項盡量「長大」（刪文字），吃掉鄰居
    IRREDUNDANT: 刪除冗餘積項（其 minterm 已被其他項覆蓋）
    REDUCE:   把沒長好的項縮回，騰出空間讓下一輪擴張改走別的路

Expand 是靈魂。給定一個積項（在 cube 幾何中是一個「立方體」， \(\{0,1,-\}^n\) 中的元素），expand 沿每個維度嘗試把 \(\{0,1\}\) 變成 don't care \(-\) ，前提是擴張後的 cube 不含任何 OFF-set minterm（不覆蓋任何輸出為 0 的點）。Espresso 採用 cube 代數的隅角（cofactor/shannon expansion）技巧高效檢查可擴張性，而且以啟發式選擇擴張方向——這個貪婪的「盡量吃」操作，正是精確演算法指數爆炸的啟發式解藥。 Irreducible（也稱 irredundant）階段則用集合覆蓋的啟發式去掉冗餘項。 Reduce 階段是 Espresso 相對於簡單爬山法的關鍵：把某些項縮小後重新 expand，讓搜尋能逃離局部最佳——這是一種早期的迭代改善/退火式思維，也預告了後來 simulated annealing 在 EDA 的盛行。

Espresso 的變體 Espresso-EXACT 提供精確最小化（以 branch-and-bound 展開），證明了 Espresso 啟發式的品質：在大多數 benchmark 上，啟發式結果與精確解只差 0%–5%。另一個重要工程貢獻是 Espresso 的表示法：不用真值表，而用 ON-set / OFF-set / DC-set（don't care）三個 cube 集合，配合 BDD 前身的 trie 與高效 cube 運算，使數十輸入的函數變得可處理。此外，多輸出函數被統一處理（共用積項跨輸出共享），don't care 集合（來自輸入不可達狀態與輸出無關緊要值）被充分利用——後者在與下一節的多級優化銜接時尤為重要。

為什麼 Espresso 曾經如此重要：PLA 與 Standard Cell 的交會#

Espresso 的商業價值建立在兩個行業基礎上。其一是 PLA 世代：1980 年代，PLA 是控制邏輯（尤其是微處理器的微碼控制、狀態機）的主流實現，Berkeley 圍繞 PLA 發展了一整套工具（PLASPEC、PLATO 等），Espresso 是其優化核心；工業界（如 Altera 的早期 PLD、各家 microcode 控制器）大量使用。其二，即使進入 standard cell 時代，兩級形式的 SOP 仍是許多工具內部的中間表示——SIS 系統（下一節）內部就保留 SOP 以便做全域品質估計。

經濟與制度層面：1980 年代中期，Berkeley 以象徵性費用授權 Espresso 給工業界，幾乎每家 EDA 公司與 IC 部門都內嵌了它（或其衍生版）。這種「大學免費授權 + 工業落地」的模式，成為後來 SIS、乃至 ABC 與開源 EDA 的先例——Espresso 是第一個證明「頂尖大學演算法可以直接變成工業標準」的 EDA 案例，也建立了 Berkeley 在邏輯綜合領域二十年的霸權。1986 年新創的 Synopsys 以 timing-driven 邏輯綜合（Design Compiler，見 3.6 節）接棒，但 Espresso 的 cube 演算法與 don't care 框架被原封不動地繼承。

兩級的理論極限#

兩級邏輯有其結構天花板。許多函數（如加法器、奇偶函數、多數函數）的 SOP 質蘊含項是指數多的，但多級實現（分解成子函數、共享中間結果）卻是線性的——例如 XOR 鏈在兩級形式是指數爆炸，在多級只是一串 XOR 閘。當 1980 年代 standard cell 庫成熟、閘的種類不再只有 AND/OR、互連延遲開始主導時，兩級優化的前提（面積正比於項數）失效了。業界需要一個能表達並優化任意深度網路的理論與工具。

下一節 3.5，我們走進多級邏輯優化的世界：Berkeley 的 MIS 與 SIS、algebraic 與 Boolean division 的分野、decompose/extract/resubstitute 三大操作，以及為什麼它們定義了此後三十年的邏輯綜合。