1.1 什麼是 EDA#

概念說明#

EDA（Electronic Design Automation，電子設計自動化）是指利用電腦軟體來協助工程師設計、驗證與製造積體電路（IC）的技術與工具總稱。現代一顆先進晶片內含數百億個電晶體，若沒有 EDA 工具，靠人力根本不可能完成設計。EDA 工程師的核心工作是：將抽象的設計意圖（如 Verilog 程式碼），經過一連串自動化轉換，最終變成可以送進晶圓廠的版圖檔案（GDSII）。

從演算法的角度看，EDA 其實是一門「把理論電腦科學應用到工業規模」的學問：

邏輯化簡：布林代數、Quine-McCluskey 演算法（第2章）
資料結構：二分決策圖 BDD（第3章）
圖論：佈局、繞線、時脈樹（第7~9章）
搜尋與最佳化：模擬退火、A* 搜尋（第7、8章）
形式方法：SAT 求解、模型檢查（第5、6章）

這些演算法面臨的共同挑戰是規模：一個 NVIDIA GPU 的設計可能包含上千萬個邏輯閘，任何演算法都必須在可接受的時間與記憶體內處理如此龐大的資料。因此 EDA 演算法的三個設計準則是：

可擴展性（Scalability）：演算法複雜度必須接近線性或多項式，且能平行化。
近似與啟發式：許多 EDA 問題是 NP-hard（如佈局、繞線、SAT），工業上採用啟發式求得好而不必然最佳的解。
增量計算（Incremental Update）：設計反覆修改，好的演算法只重算受影響的部分。

EDA 的三大領域#

領域	主要工作	代表演算法
前端（邏輯設計）	RTL 合成、邏輯優化、驗證	布林化簡、BDD、SAT
後端（實體設計）	佈局、繞線、時脈樹、電源	圖分割、迷宮繞線、Dijkstra
驗證	模擬、等價檢查、模型檢查	事件驅動模擬、SAT、BDD

演算法步驟：EDA 設計迴圈#

不論哪個領域，EDA 工具的基本運作都是一個「轉換—分析—回饋」迴圈：

輸入：讀取設計描述（RTL、網表、版圖）與約束（時脈、面積、功耗）。
轉換（Transform）：套用演算法將設計轉換到更低的抽象層級（合成）或更佳的品質（優化）。
分析（Analyze）：估算轉換後設計的品質指標（QoR）：時序、面積、功耗、線長。
判斷（Decide）：若滿足約束則輸出；否則回到第 2 步調整參數或回溯。

Python 程式碼範例：一個迷你 EDA 轉換迴圈#

下面的程式用一個極簡的「閘數統計與面積估算」例子示範 EDA 工具的資料結構：網表（Netlist）。網表是 EDA 中最核心的中間表示——用「閘」與「線」構成的有向圖。

from collections import defaultdict

class Netlist:
    """極簡網表：節點為邏輯閘，邊為訊號線"""
    def __init__(self):
        self.gates = {}                      # name -> (type, inputs)
        self.fanout = defaultdict(list)      # net -> [下游閘]

    def add_gate(self, name, gtype, *inputs):
        self.gates[name] = (gtype, list(inputs))
        for i in inputs:
            self.fanout[i].append(name)

    def topo_order(self):
        """拓撲排序：保證先算輸入再算輸出，複雜度 O(V+E)"""
        indeg = {g: 0 for g in self.gates}
        for gtype, ins in self.gates.values():
            for i in ins:
                if i in indeg:
                    indeg[g] += 1
        queue = [g for g, d in indeg.items() if d == 0]
        order = []
        while queue:
            g = queue.pop()
            order.append(g)
            for f in self.fanout[g]:
                indeg[f] -= 1
                if indeg[f] == 0:
                    queue.append(f)
        return order

    def evaluate(self, pi_values):
        """依拓撲序模擬整個電路"""
        val = dict(pi_values)
        for g in self.topo_order():
            gtype, ins = self.gates[g]
            vs = [val[i] for i in ins]
            if gtype == "AND":   val[g] = all(vs)
            elif gtype == "OR":  val[g] = any(vs)
            elif gtype == "NOT": val[g] = not vs[0]
            elif gtype == "NAND": val[g] = not all(vs)
        return val

# 建立電路: y = (a AND b) OR (NOT c)
n = Netlist()
n.add_gate("g1", "AND", "a", "b")
n.add_gate("g2", "NOT", "c")
n.add_gate("y",  "OR",  "g1", "g2")

for a, b, c in [(0,0,0), (1,0,0), (1,1,0), (1,1,1)]:
    r = n.evaluate({"a": bool(a), "b": bool(b), "c": bool(c)})
    print(f"a={a} b={b} c={c} -> y={int(r['y'])}")

輸出：

a=0 b=0 c=0 -> y=1
a=1 b=0 c=0 -> y=1
a=1 b=1 c=0 -> y=1
a=1 b=1 c=1 -> y=1

這個例子展示了 EDA 的基本樣貌：用圖表示電路、用圖演算法（拓撲排序）驅動計算。後續章節的每個工具，本質上都是對這張圖做更精巧的轉換與分析。

複雜度分析#

拓撲排序：O(V + E)，V 為閘數、E 為線數。
全掃描模擬：O(指標數 × 電路規模)，這正是模擬驗證成本高的原因（第5章將討論改進方法）。

練習#

請修改 Netlist 類別，加入 XOR 閘的支援，並用一個 2 輸入 XOR 電路驗證真值表。
統計一個網表的「最大扇入」（單一閘最多輸入線數），說明其複雜度。
查閱資料：Synopsys、Cadence、Siemens EDA 三大 EDA 廠商各以哪些工具聞名？開源工具 Yosys 與它們的差別何在？