10.1 機器學習在EDA的應用#

概念說明#

傳統 EDA 演算法以精確數學模型（Elmore delay、HPWL、SAT、MNA）為核心，但它們有共同的瓶頸：模型與真實物理/製造之間的落差，以及搜尋空間大到無法窮舉。機器學習（ML）在兩個方向切入：

更準的代理模型（surrogate model）：以神經網路學習「設計特徵 → PPA（功耗/效能/面積）」的映射，取代昂貴的模擬或 STA。例如以 GNN（圖神經網路）直接在 netlist 圖上預測擁塞、繞線資源需求；以 GCN 預測寄生電容；繞線前的 congestion 預測可省去 GR-DR 迭代。Google 的晶片佈局論文（2021, Nature）以強化學習做巨塊（macro）擺放，把「放置決策序列」建模為馬可夫決策過程，以 policy gradient 訓練——雖然學界對其基線比較有爭議，但確實開啟了 RL-for-placement 的研究熱潮。
更好的搜尋策略：合成中的邏輯優化序列（如 ABC 的 resyn、resyn2、resyn3 各種 script 組合）傳統上靠人挑，ML 可學「哪個序列對這個設計最有效」（如貝葉斯優化、強化學習選擇動作）。驗證中的覆蓋率收斂（見 5.1 的 bias 回饋）也可由 RL 接手。

ML 在 EDA 的獨特挑戰：(1) 資料稀缺——一個晶片的設計資料是公司機密且樣本極少，難以像影像那樣做大資料訓練；(2) 分佈漂移——換製程節點或換設計風格，模型立刻失準；(3) 正確性要求——EDA 的答案錯了就是流片失敗，ML 通常只能「預測 + 用精確工具驗證」，無法單獨擔綱。因此目前的主流範式是 ML-in-the-loop：ML 提供快速估計與候選排序，精確演算法做最終確認。

演算法步驟（GNN 擁塞預測 + 用於繞線引導）#

把 netlist 編碼為異質圖：節點 = 單元（特徵：類型、面積、層數）、邊 = net（特徵：扇出、驅動強度）。
訓練資料：歷史設計的「佈局後、繞線後」真實擁塞圖。
GNN 訊息傳遞：k 層圖卷積聚合鄰域特徵，輸出每個 GCell 的預測擁塞。
推論：對新設計的佈局做預測，得到擁塞熱圖。
下游使用：全局繞線的邊成本加上「預測擁塞懲罰」，或提前對熱區做單元散開（placement refinement）。

Python 程式碼範例#

以下用一個極簡的「訊息傳遞」GNN（純 numpy，不依賴框架）示範 netlist 特徵學習的骨架：以隨機初始化的權重聚合鄰居資訊，輸出每節點的擁塞預測分數。

import numpy as np

def build_graph(nets, n_cells):
    """netlist -> 鄰接串列（net 展開成團）"""
    adj = [[] for _ in range(n_cells)]
    for net in nets:
        for a in net:
            for b in net:
                if a != b:
                    adj[a].append(b)
    return [sorted(set(x)) for x in adj]

def features_of(cells, nets_of):
    """節點特徵：[面積, 扇出數, 是否時脈]"""
    return np.array([[c.get("area", 1.0) / 10.0,
                      nets_of[i] / 5.0,
                      1.0 if c.get("is_clk") else 0.0]
                     for i, c in enumerate(cells)])

def gnn_forward(F, adj, W1, W2, layers=3):
    """簡化 GNN：H' = relu(鄰居平均 @ W1 + 自身 @ W1)，最後線性到分數"""
    H = F
    for _ in range(layers):
        Hn = H.copy()
        for v in range(len(H)):
            if adj[v]:
                agg = H[adj[v]].mean(axis=0) @ W1 + H[v] @ W1
                Hn[v] = np.maximum(0, agg)
        H = Hn
    return H @ W2        # 每節點一個擁塞分數

def train_demo():
    rng = np.random.default_rng(0)
    cells = [{"area": rng.uniform(1, 10), "is_clk": rng.random() < 0.05}
             for _ in range(50)]
    nets = []
    for _ in range(30):
        k = rng.integers(2, 5)
        nets.append(list(rng.choice(50, k, replace=False)))
    nets_of = {i: 0 for i in range(50)}
    adj = build_graph(nets, 50)
    for net in nets:
        for c in net:
            nets_of[c] += 1
    F = features_of(cells, nets_of)
    W1 = rng.normal(0, 0.5, (3, 3))
    W2 = rng.normal(0, 0.5, (3, 1))
    scores = gnn_forward(F, adj, W1, W2).ravel()
    top = np.argsort(-scores)[:5]
    print("預測擁塞風險 Top-5 單元:")
    for i in top:
        print(f"  cell{i:2d}  分數={scores[i]:.3f}  "
              f"扇出={nets_of[i]}  面積={cells[i]['area']:.1f}")
    return scores, nets

scores, nets = train_demo()

# 模擬「真實擁塞」：以實際繞線使用量為標籤（示範訓練迴圈的資料流）
usage = {}
for net in nets:
    for c in net:
        usage[c] = usage.get(c, 0) + 1
true_hot = sorted(usage, key=lambda c: -usage[c])[:5]
print("\n實際高使用量 Top-5:", true_hot)
print("（訓練目標即為讓 scores 與此類真實標籤的排序一致）")

輸出示意：

預測擁塞風險 Top-5 單元:
  cell12  分數=1.842  扇出=4  面積=8.7
  cell31  分數=1.655  扇出=4  面積=6.2
  ...
實際高使用量 Top-5: [12, 31, 7, 44, 3]
（訓練目標即為讓 scores 與此類真實標籤的排序一致）

範例展示 ML-in-EDA 的資料流：netlist → 圖特徵 → GNN 分數 → 與真實標籤（實際繞線使用量）比對 → 反向傳播更新權重。真實系統中 scores 會被佈局器/繞線器當作先驗，直接改變演算法的搜尋順序。

複雜度分析#

GNN 訊息傳遞：O(L·(|V|·d² + |E|·d))，L 為層數、d 為特徵維度。
推論速度：一次前向在毫秒~秒級，比執行完整 GR-DR 迭代快 10³~10⁵ 倍——這是代理模型的價值。
訓練：瓶頸在「標籤取得」（需跑完整流程），遷移學習與自監督是當前研究重點。

練習#

把 gnn_forward 的聚合從 mean 改成 max-pooling，觀察對高扇出節點分數的影響。
實作簡單的訓練迴圈：以「實際使用量歸一化」為標籤，用梯度下降更新 W1、W2（100 輪），量測 Top-5 預測的命中率。
查閱 Google 的 RL 佈局論文與其後的重現性研究，以 300 字整理「RL 佈局目前與傳統工具的真實差距」。