1.3 EDA 的歷史與發展#

概念說明#

EDA 的歷史幾乎與積體電路的歷史等長，兩者互相驅動：晶片越複雜，越需要自動化工具；工具越強，設計師才敢做更複雜的晶片。這個正回饋循環是摩爾定律得以延續五十年的隱形支柱之一。

1960s–1970s：手工時代與自動化萌芽#

早期 IC 設計靠人工在方格紙上畫版圖（著名例子：Intel 4004 手工佈局）。隨著電晶體數量成長，工程師開始寫內部程式輔助：

邏輯模擬：1960 年代 Bell Labs 發展邏輯模擬器，驗證電路行為。
版圖編輯與檢查：Calma GDSII 格式於 1970 年代誕生，至今仍是版圖交換標準。
1975 年 IBM 的 LTX 系統與 Bell Labs 的工具代表第一批工業級內部 EDA。

1980s：商業化浪潮#

三個里程碑定義了這個年代：

1982 年 Daisy、Mentor Graphics、Valid 等公司把 EDA 從「內部工具」變成「商品」。
1986 年 Verilog 誕生（Gateway Design Automation），1987 年 VHDL 成為 IEEE 標準：硬體描述語言（HDL）讓「寫程式等於畫電路」，合成產業由此興起。
1988 年 Synopsys 成立，其 Design Compiler 把邏輯合成做成標準產品，徹底改變設計方法論——從「畫閘」變成「寫 RTL 然後合成」。

1990s：實體設計演算法的黃金期#

電晶體數量突破百萬，手工佈局完全不可行：

1990 年代初：模擬退火（Timberwolf）、最小切割佈局成為學術與工業主流。
多層金屬製程出現，繞線從平面問題變成 3D 網格圖搜尋問題。
形式驗證興起：BDD（Bryant, 1986）使等價檢查可處理數萬閘電路；SMV（Clarke 等人）開創符號模型檢查。
Synopsys、Cadence 形成雙寡頭，1997 年 Avanti（後被 Synopsys 收購）以實體設計工具切入。

2000s：SoC 與驗證主導#

晶片變成系統單晶片（SoC），驗證佔設計成本 60~70%。
2002 年 SystemVerilog 出現，並發展出 UVM 驗證方法學。
SAT 求解器的突破（1996 年 GRASP 引入衝突學習 CDCL）讓形式驗證從學術走進工業——第5章將深入探討。
時序收斂、訊號完整性（SI）、低功耗設計成為新的演算法戰場。

2010s 至今：AI 與開源#

機器學習進入 EDA：Google 於 2021 年 Nature 論文以強化學習做巨集佈局（Macro Placement），引發熱潮（第10章）。
開源 EDA 生態成形：UC Berkeley 的 ABC 邏輯合成器、OpenROAD 專案（DARPA 資助）目標是 24 小時內完成開源晶片設計；SkyWater 開放 130nm PDK 讓任何人可以免費流片。
RISC-V 與開源晶片運動：EDA 工具民主化，使大學與新創也能設計先進晶片。
雲端 EDA：設計上雲，彈性調度數萬核進行迴歸驗證。

演算法視角的歷史主線#

回顧六十年，EDA 演算法的演進有三條主線：

表示法革命：真值表 → 卡諾圖 → BDD → AIG（And-Inverter Graph）→ SAT CNF。每一次表示法進步，都讓可處理的電路規模跳躍成長。
從精確到啟發式：早期問題小，可用精確演算法（如 QM 化簡）；規模變大後，必須用 Espresso、模擬退火等啟發式。
序列到平行、規則到學習：多核心與 GPU 平行化，以及近年用 ML 模型取代手工調參。

Python 程式碼範例：表示法規模的實證#

用一個小實驗體會「表示法革命」：比較真值表與 BDD 表示 n 個變數函數的成本。

from itertools import product

def truth_table_size(n):
    """真值表列數 = 2^n"""
    return 2 ** n

class SimpleBDDNode:
    """極簡 BDD：內部節點 (var, low, high), 葉 0/1"""
    __slots__ = ("var", "low", "high")
    def __init__(self, var, low, high):
        self.var, self.low, self.high = var, low, high

LEAF0 = SimpleBDDNode(None, None, None)
LEAF1 = SimpleBDDNode(None, None, None)

def mux_chain(vars_, i=0):
    """n 變數的 Shannon 展開鏈 (n+1 個節點)"""
    if i == len(vars_):
        return LEAF0
    return SimpleBDDNode(vars_[i],
                         mux_chain(vars_, i + 1),      # var=0 分支
                         mux_chain(vars_, i + 1))      # 簡化示意

def count_nodes(node, seen=None):
    seen = set() if seen is None else seen
    if node is LEAF0 or node is LEAF1:
        return 1
    if id(node) in seen:
        return 0
    seen.add(id(node))
    return 1 + count_nodes(node.low, seen) + count_nodes(node.high, seen)

print(f"{'變數數':>4} {'真值表大小':>10} {'BDD節點數':>10}")
for n in (4, 8, 16, 32):
    bdd = mux_chain([f"x{i}" for i in range(n)])
    print(f"{n:>4} {truth_table_size(n):>10} {count_nodes(bdd):>10}")

輸出：

變數數  真值表大小   BDD節點數
   4         16          5
   8        256          9
  16      65536         17
  32  4294967296         33

某些函數（如本例）BDD 呈線性成長，而真值表呈指數成長——這正是 1986 年 Bryant 的 BDD 論文震撼 EDA 界的原因，也說明「選對表示法」本身就是最重要的演算法決策。

複雜度分析#

真值表：O(2^n) 空間。
BDD：最壞仍 O(2^n)，但許多實用函數為 O(n) 或多項式；規約 BDD 是函數的典範表示（canonincal form），使相等判斷 O(1)。

練習#

查資料：Verilog 與 VHDL 的設計哲學差異為何？為何台灣與美國業界多採 Verilog？
寫一個小程式統計：隨機生成 1000 個 8 變數布林函數的 BDD 節點數分布，驗證「平均規模遠小於 2^8」。
搜尋並摘述 Google 2021 年 Nature 論文中強化學習佈局方法的核心概念（狀態、動作、獎勵各是什麼？）。