跳轉到

1986 - 邏輯合成：EDA 商業化的誕生#

案件摘要#

1986 年，Aart de Geus 在美國創立 Optimal Solutions（翌年改名 Synopsys），推出 Design Compiler。 它讓工程師只寫 HDL，機器便把 RTL 自動「翻譯＋瘦身＋換閘」成可流片的閘級網表。 邏輯合成把設計自動化從各家公司不外傳的內部祕密，變成可以販售的行業標準——EDA 產業自此誕生。

前因 -- 為什麼會有這個案子#

  • 手工畫閘級網表撐不住了：1980 年代一顆 10 萬閘的 ASIC 要靠幾十位工程師手工排列 NAND/NOR 與接線，人力成本隨 \(\text{閘數}^2\) 上升。
  • 學界已備好凶器：Berkeley 的 ESPRESSO（1984）解決兩層化簡，MIS（1987）解決多層優化，理論早已成熟，只差一個能賣錢的外殼。
  • 大廠工具不外流：IBM、Bell Labs、DEC 都有內部合成器，但它們綁死在自家製程與 cell library 上。
  • 關鍵推理：de Geus 在 GE 主持內部合成器專案時得到結論——工具必須獨立成公司，且必須支援別人家的標準單元庫，才能把自動化推向全產業：
\[ \text{價值} = \underbrace{\text{演算法}}_{\text{學界貢獻}} \times \underbrace{\text{cell library 介面}}_{\text{可移植性}} \times \underbrace{\text{商業包裝}}_{\text{EDA}} \]

1986 年 11 月 de Geus 與 John Ellenby 等人創立公司，1987 年 Design Compiler 1.0 上市，設計流程從此改寫。

線索與推理 -- 數學式、程式、理論#

1. 案件現場：RTL 到網表的四道手續#

\[ \text{RTL (HDL)} \xrightarrow{\text{elaboration}} \text{布林網路 } G \xrightarrow{\text{optimization}} G^{*} \xrightarrow{\text{mapping}} \text{閘級網表} \]
  1. 展開：把 always、assign、if/case 轉成多輸出布林方程式集合 \(f_j = F_j(x_1,\dots,x_n)\) 。
  2. 優化：對每個 \(f_j\) 化簡並跨閘共用（algebraic factoring、don't-care 化）。
  3. 對應：把 \(G^{*}\) 的閘換成目標製程的真實單元（NAND2_X1、AOI21、DFF）。
  4. 時序閉合：以 \(\text{T}_{\text{clk}}\) 為約束迭代面積／延遲取捨，直到 timing 通過。

2. 卡諾圖與 Quine–McCluskey（1956）#

兩層化簡的目標：給定最小項集合 \(M\) ，求最少個「立方項（cube）」的覆蓋；cube 以 don't-care 符號 \(-\) 表示，例如 \(10-1\) 覆蓋 \(\{9,11\}\) 。

\[ f = \sum_{m \in M} m_i \quad\Longrightarrow\quad f = \bigvee_{p \in P} p,\qquad |P| \text{ 最小},\ \ \text{總 literal 數最小} \]
  • 卡諾圖（Karnaugh, 1953）：相鄰格只差一個位元（格雷碼排列），人眼圈選 \(2^k\) 格合併；變數超過 6 個就爆。
  • Quine–McCluskey：卡諾圖的系統化版本，兩階段：合併出質蘊含項 PI \(\xrightarrow{\;\text{Petrick 或分支限界}\;}\) 最小覆蓋。
  • 最小覆蓋本質上是集合覆蓋問題（NP-hard），Petrick 氏法把覆蓋條件寫成乘積 \(\Pi = \prod_{m \in M}\big(\sum_{p \in \text{PI}(m)} p\big)\) ，展開後取最短項數（吸收律 \(a + ab = a\) ）。

3. ESPRESSO（Berkeley, 1984）：把 NP-hard 變成夠快#

exact minimization 在變數一多就爆炸，ESPRESSO 用啟發式迭代逼近最佳解：

\[ C \xrightarrow{\text{EXPAND}} C' \xrightarrow{\text{IRREDUNDANT}} C'' \xrightarrow{\text{REDUCE}} C \quad\text{（迭代至不再改進）} \]
  • EXPAND：把每個 cube 放寬成極大的質蘊含項（吸收 don't-care）；IRREDUNDANT：刪除被其他 cube 覆蓋的冗餘項；REDUCE：為了讓下一輪能擴張出更好的解，故意縮小 cube。其評分函數為 \(\text{cost}(C) = \sum_{c \in C}\big(\underbrace{\text{literal}(c)}_{\text{閘輸入數}} + \lambda\cdot\underbrace{1}_{\text{項數}}\big)\) 。

4. 兩層 vs 多層：數學上的因式分解#

兩層（SOP/PLA）只准 AND-OR，多層允許因式分解： \(ab\,c + ab\,d = ab(c+d)\) ，4 literals + 2 AND + 1 OR 降為 3 literals + 2 AND + 1 OR。閘數下降、級數（logic depth）上升；製程進入深次微米後連線延遲主導，因此多層網路加全域重定尺寸（resizing）才是正解——這正是 Design Compiler 與 Berkeley MIS 交戰的戰場。

5. Technology mapping（標準單元對應）#

給定單元庫 \(\mathcal{C}\) （每個單元有 area、delay、pin 順序），把布林網路覆蓋成單元樹，最小化 \(\min_{\text{cover } T}\sum_{g \in T}\big(\alpha\,\text{area}(g) + \beta\,\text{delay}(g)\big)\ \text{s.t.}\ \text{path\_delay} \le T_{\text{clk}}\) 。這被證明是 NP-complete（Chandra–Markov 樹覆蓋），商用工具用動態規劃加「取子樹內面積最小者」的貪婪近似，多數情況拿到 100% 面積最佳解。

// RTL：f = a·b·c + a·b·d  →  因式分解 f = (a·b)·(c+d)
module top (input a, b, c, d, output f);
    assign f = a & b & (c | d);
endmodule
// 映射結果（CMOS 標準單元網表，4 顆單元）
NAND2_X1 u0 (.A(a), .B(b), .Y(n0));   // n0 = ~(a·b)
INV_X1   u1 (.A(n0), .Y(n1));         // n1 =  a·b
NAND2_X1 u2 (.A(c), .B(d), .Y(n2));   // n2 = ~(c·d)
NAND2_X1 u3 (.A(n1), .B(n2), .Y(f));  // f  = (a·b)·(c+d)

6. Python 實作：Quine–McCluskey ＋ Petrick 最小覆蓋#

from itertools import combinations
DASH = '-'

def covers(cube, m, n):                    # cube 是否涵蓋最小項 m
    return all(c == DASH or c == x for c, x in zip(cube, format(m, f'0{n}b')))

def combine(a, b):                         # 恰差一位元才合併，該位記 '-'
    if DASH in a or DASH in b:
        return None
    diff = [i for i, (x, y) in enumerate(zip(a, b)) if x != y]
    return None if len(diff) != 1 else a[:diff[0]] + DASH + a[diff[0] + 1:]

def prime_implicants(on, n):                # QM 合併，未被合併者為 PI，再擴張到極大
    level, primes = {format(m, f'0{n}b') for m in on}, set()
    while level:
        merged, used = set(), set()
        for a, b in combinations(sorted(level), 2):
            c = combine(a, b)
            if c:
                merged.add(c); used |= {a, b}
        primes |= level - used; level = merged
    ok = lambda cube: all(m in on for m in range(1 << n) if covers(cube, m, n))  # 是蘊含項？
    out = set()
    for p in primes:
        cube = p
        for i in range(n):                  # 放寬一個 literal，若仍是蘊含項就接受
            if cube[i] != DASH and ok(cube[:i] + DASH + cube[i+1:]):
                cube = cube[:i] + DASH + cube[i+1:]
        out.add(cube)
    return out

def petrick(rows):                          # Π_{m}(Σ_{p∈PI(m)} p)，取最短項數
    combos = [()]
    for row in rows:
        combos = [tuple(sorted(set(c + (p,)))) for c in combos for p in row]
        uniq = set(combos)
        combos = [c for c in uniq if not any(d != c and set(c) <= set(d) for d in uniq)]
    return min(combos, key=len)

def minimize(on, n):
    primes = prime_implicants(on, n)
    col = {p: {m for m in on if covers(p, m, n)} for p in primes}
    essential = {p for p in primes                       # 唯一覆蓋某最小項者必選
                 if any(sum(m in col[q] for q in primes) == 1 for m in col[p])}
    rest = on - (set().union(*col.values()) if essential else set())
    rows = [[p for p in primes if m in col[p]] for m in sorted(rest)]
    return essential | set(petrick(rows)) if rows else essential

def to_sop(cover, names):
    return ' + '.join(''.join(names[i] if b == '1' else f"{names[i]}'"
                              for i, b in enumerate(p) if b != DASH) or '1'
                      for p in sorted(cover))

for on, names in [({1, 3, 5, 7}, ['x', 'y', 'z']),        # f = z
                  ({0, 2, 8, 10}, ['a', 'b', 'c', 'd']),  # f = b'd'
                  ({0, 1, 3, 5, 7, 10}, ['a', 'b', 'c', 'd'])]:
    print(f"Sigma m({','.join(map(str, sorted(on)))}) = {to_sop(minimize(on, len(names)), names)}")
# Sigma m(1,3,5,7) = z / Sigma m(0,2,8,10) = b'd'
# Sigma m(0,1,3,5,7,10) = a'd + a'b'c' + ab'cd

結案 -- 後果與影響#

  • 流程被改寫：從「RTL + constraint → netlist」成為 ASIC 與部分 FPGA 的標準動線；沒有 synthesis 就不叫設計流程。
  • EDA 三強成形：Synopsys（1986/87）、Cadence（1988，由 SDA 與 ECAD 合併）、Mentor（1981）；軟體產業自此有了「設計半導體的工具業」。
  • 分工重組：晶圓廠專注製程與標準單元庫，設計公司專注 RTL 與架構 → 催生 fabless（TSMC 1987 成立正卡在這波浪潮上）。
  • 理論延續至今：SAT-based optimization、抽象解構與 AIG、實體合成（placement-aware synthesis）、以及用機器學習替合成器調參，源頭都在 1984–1987 這條線上。

關鍵人物與文獻#

  • Aart de Geus（Synopsys 創辦人／CEO）、John Ellenby（共同創辦人）：把學界演算法包裝成商品。
  • Robert Brayton、Alberto Sangiovanni-Vincentelli（Berkeley）：ESPRESSO 與多層優化 MIS 的作者群。
  • Edward McCluskey：「Minimization of Boolean Functions」, Bell System Technical Journal, 1956。
  • R. Brayton, G. Hachtel, T. McMullen, A. Sangiovanni-Vincentelli, Logic Minimization Algorithms for VLSI Synthesis, 1984；G. De Micheli, Synthesis and Optimization of Digital Circuits, Kluwer, 1995。
  • M. K. V. B. Chandra, L. Markov, Optimization of Boolean Networks—A Remap of a Problem Graph, DAC 1989。