1.2 晶片設計流程與演算法角色#

概念說明#

要理解 EDA 演算法，必須先了解晶片從想法到量產的完整流程。這條流程可以想像成一道「抽象層級不斷下降」的階梯：

系統規格 (Specification)
    ↓  高階合成 (HLS)
RTL (Register Transfer Level, Verilog/VHDL)
    ↓  邏輯合成 (Logic Synthesis)
閘級網表 (Gate-level Netlist)
    ↓  實體設計 (Physical Design: 佈局規劃→佈局→時脈樹→繞線)
版圖 (Layout, GDSII)
    ↓  物理驗證 (DRC/LVS) 與簽核 (Signoff)
交付晶圓廠 (Tape-out)

每個向下的箭頭都由一個（或一組）EDA 演算法驅動。以下逐段說明各階段與其核心演算法。

各階段與核心演算法#

1. 高階合成（HLS）#

把 C/C++/SystemC 描述的演算法轉成 RTL。核心問題是排程（Scheduling）（哪些運算放在哪個時脈週期）與資源分配（Allocation）（需要幾個乘法器、加法器）。常用演算法：列表排程（List Scheduling）、力導向排程（Force-Directed Scheduling）。

2. 邏輯合成#

把 RTL 轉成最佳化的邏輯閘網表。核心演算法：

兩層邏輯最小化：Quine-McCluskey、Espresso 啟發式化簡（第2章）。
多級邏輯優化：因式分解、技術映射（Technology Mapping）（第3章）。
技術映射：把與邏輯無關的網表映射到製程庫中的實際閘（如 FA、AOI21），常用「覆蓋（Covering）」動態規劃。

3. 驗證（與合成並行）#

模擬（Simulation）：事件驅動演算法（第5.1節）。
等價檢查（LEC）：BDD 或 SAT 為基礎（第6章）。
模型檢查：符號模型檢查（第5.3節）。

4. 實體設計（Physical Design）#

這是演算法最密集的階段，依序為：

步驟	問題	代表演算法
佈局規劃 Floorplanning	決定大區塊位置	模擬退火、B* 樹
佈局 Placement	放置數百萬標準胞	最小切割、力導向、解析法(ePlace)
時脈樹合成 CTS	均衡時脈延遲	H-tree、DME 演算法
繞線 Routing	在金屬層拉線	Lee 迷宮、A*、Pattern Routing
簽核 Signoff	時序、功耗、IR 壓降	STA、靜態分析

5. 物理驗證#

DRC（設計規則檢查）本質是幾何計算問題，使用掃描線演算法在 O(n log n) 內找出重疊與間距違規；LVS（佈局與網表比對）是圖同構（Graph Isomorphism）問題的近似版本。

演算法步驟：以「合成到佈局」的資料流為例#

RTL 經過剖析得到運算樹。
邏輯合成做布林優化（用 BDD/SAT 表示與化簡）。
技術映射挑選庫單元，產生閘級網表。
佈局工具讀入網表，以連接圖為輸入，最小化線長。
繞線工具在多層網格圖上做最短路徑搜尋。
STA 在時序圖上做最長路徑分析。

可以看到一條主軸：每個階段都把設計變成一種圖，然後套用該圖上的最佳化演算法。

Python 程式碼範例：簡單的 STA（靜態時序分析）#

靜態時序分析是簽核階段最重要的演算法：在 DAG 上求最長路徑，判斷時脈週期是否夠長。下面用 Python 實作一個迷你 STA：

from collections import defaultdict

class TimingGraph:
    """節點 = 閘的輸出接腳, 邊 = (延遲, 目標節點)"""
    def __init__(self):
        self.edges = defaultdict(list)  # u -> [(delay, v), ...]
        self.nodes = set()

    def add_edge(self, u, v, delay):
        self.edges[u].append((delay, v))
        self.nodes |= {u, v}

    def longest_paths(self):
        """DAG 最長路徑: 拓撲排序 + DP, O(V+E)"""
        indeg = {n: 0 for n in self.nodes}
        for u in self.edges:
            for _, v in self.edges[u]:
                indeg[v] += 1
        q = [n for n in self.nodes if indeg[n] == 0]
        topo = []
        while q:
            u = q.pop()
            topo.append(u)
            for _, v in self.edges[u]:
                indeg[v] -= 1
                if indeg[v] == 0:
                    q.append(v)
        arrive = {n: 0.0 for n in self.nodes}
        for u in topo:
            for d, v in self.edges[u]:
                arrive[v] = max(arrive[v], arrive[u] + d)
        return arrive

# 電路: in -> g1(0.8) -> g2(1.2) -> FF ; in -> g3(0.5) -> FF
tg = TimingGraph()
tg.add_edge("in", "g1", 0.8)
tg.add_edge("in", "g3", 0.5)
tg.add_edge("g1", "g2", 1.2)
tg.add_edge("g2", "FF", 0.3)
tg.add_edge("g3", "FF", 0.3)

arr = tg.longest_paths()
clock_period = 2.0
slack = clock_period - arr["FF"]
print("到達時間:", {k: round(v, 2) for k, v in arr.items()})
print(f"Slack = {slack:.2f} -> {'MET' if slack >= 0 else 'VIOLATED'}")

輸出：

到達時間: {'in': 0.0, 'g1': 0.8, 'g3': 0.5, 'g2': 2.0, 'FF': 2.3}
Slack = -0.30 -> VIOLATED

臨界路徑（critical path）是 in→g1→g2→FF，延遲 2.3ns 超過 2ns 週期，工具會回報違規並提示設計者優化（例如換更快的閘或重組邏輯）。這正是 EDA「分析—回饋」迴圈的具體實現。

複雜度分析#

DAG 最長路徑（STA）：O(V+E)；但含迴路的圖求最長路徑是 NP-hard，這就是 STA 必須在同步電路（DAG）上進行的原因。
邏輯合成中的布林優化：許多子問題（如最小 DNF）是 NP-hard，工業工具採用啟發式。

練習#

在 TimingGraph 中加入反向邊會發生什麼？請說明為什麼含迴路時「拓撲排序 + DP」失效。
實作「臨界路徑回溯」：記錄每個節點的前驅，輸出臨界路徑上的閘名稱清單。
說明為什麼佈局問題是 NP-hard？（提示：可歸約自圖分割或二次指派問題）