1986-SIS邏輯合成框架#
案件摘要#
Espresso（1984）把兩級邏輯化簡做到極致，但真正的電路是多級網路——兩級表示在中間節點數上指數爆炸。1986-92 年，Berkeley 的 Brayton、Rudell、Sangiovanni-Vincentelli、Chen 等人先後發表 MIS 與 SIS：把多級合成拆成一套可組合的演算法工具箱——代數因式分解、核心提取（kernel extraction）、再代入（resubstitution）、節點最小化——讓「RTL 描述 → 優化的多級門級網表」全自動化。同期（1986-87），Aart de Geus 從 GE 出走創立 Synopsys，把這套學術成果商品化為 Design Compiler——「合成」從學術課題變成晶片設計流程的中樞神經，整個 ASIC 產業的工作方式自此改寫。
前因 -- 為什麼會有這個案子#
- 兩級表示的極限：任意函數的兩級 SOP 可需指數積項（如 \(n\) 位奇偶函數需 \(2^{n-1}\) 項）；多級（含中間變數）可指數級縮小：
\[ f = x_1 y_1 + x_2 y_2 + \cdots + x_n y_n \quad \text{（多級：} \Sigma \text{ 樹形網路，} O(n) \text{ 閘）} \]
- RTL 時代來臨：Verilog/VHDL（1984-85）讓設計者寫行為描述，「RTL 自動變閘級」成為迫切需求——語言就緒，缺引擎。
- Espresso 只處理兩級：多級的因式分解、共用子表達式提取是全新案件類型。
- GE 的實戰經驗：de Geus 在 GE 研究邏輯合成（SOLO 工具），深知工業需求與學術演算法的落差——商業化的缺口。
線索與推理 -- 數學式、程式、理論#
核心：代數分解的演算法工具箱#
多級合成的本質：找共用子表達式、提取為中間節點、反覆化簡。SIS 的工具箱：
- 核心提取（kernel extraction）：對每個 SOP 求所有「核心」（不可再代數分解的子積項式），找出被多處共用的核心提取為新節點：
\[ f = a b c + a b d + e b c + e b d \Rightarrow f = (a + e)(b)(c + d) \quad (\text{提取 } (a+e), (c+d)) \]
- 代數因式分解（algebraic factoring）：用「代數除法」（多項式除法、不展開布林恆等式）遞迴化簡；
- 再代入（resubstitution）：用既有節點的函數重寫目標節點，刪除冗餘；
- 節點最小化：每個節點的局部 SOP 用 Espresso 化簡。
雙表示法的張力：SOP vs 多級#
| 表示 | 優點 | 缺點 |
|---|---|---|
| 兩級 SOP | 結構簡單、延遲可預估（兩級延遲） | 積項可能指數多 |
| 多級網路 | 面積/延遲可大幅縮小 | 結構複雜、優化難 |
SIS 的推理：兩級演算法（Espresso）作為子程序，嵌在多級框架裡——每次局部化簡都呼叫 Espresso，全域結構由代數分解管理。這個「層次化的演算法組合」是合成框架的工程哲學。
布林方法 vs 代數方法#
- 代數方法：把布林式當多項式處理，快但保守（忽略 \(x \cdot \bar{x} = 0\) ）；
- 布林方法：用布林恆等式（如 don't-care 條件）可更激進化簡，但需 SAT/BDD 支援。 SIS 兩者兼備——這個張力一直延續到 ABC（2005）的 SAT sweeping。
Synopsys 的商業化推理#
de Geus 的洞察：RTL → 閘級的自動化會把設計者的生產力放大一個數量級。Design Compiler（1987-88）以「合成 + 時序驅動」為賣點，把 SIS 的學術演算法工程化（加入時序約束、庫映射、增量編譯）——學術與商業的合流自此成為 EDA 產業的標準劇本。
結案 -- 後果與影響#
- RTL 合成革命：Design Compiler 成為 ASIC 流程中樞，設計者從畫閘級圖改寫 RTL——設計生產力提升一個數量級，直接支撐 1990s 的 SoC 潮。
- 合成學科成形：SIS 的演算法工具箱（kernel extraction、resubstitution、don't-care 優化）成為教科書標準，Berkeley 成為合成聖地。
- 開源閉環：SIS 開源給學界，培養一代合成研究者；其思想延續到 ABC（2005）與 OpenROAD（2019）。
- de Geus 的產業版圖：Synopsys 自此成為 EDA 頭牌，合成、模擬、簽核一條龍——SIS 的學術基因在商業工具中延續三十年。
關鍵人物與文獻#
- Robert K. Brayton, Alberto Sangiovanni-Vincentelli：Berkeley，合成理論宗師。
- Aart J. de Geus：GE→Synopsys 創辦人，RTL 合成商業化。
- 文獻：
- R. K. Brayton, R. Rudell, A. Sangiovanni-Vincentelli, A. R. Wang, "MIS: A Multiple-Level Logic Optimization System," IEEE Trans. CAD 6, 1062 (1987).
- E. M. Sentovich et al., "SIS: A System for Sequential Circuit Synthesis," Memorandum UCB/ERL, UC Berkeley, 1992.
- A. J. de Geus, "Logic Synthesis Speeds ASIC Design," IEEE Spectrum, 1986.