跳轉到

1.4 圖與超圖：把幾百萬個電晶體變成數學物件#

1970 年代初，Bell Labs 的走廊裡流傳著一個笑話：「物理學家研究真空管，數學家研究圖論，而我們必須同時做兩件事。」這句玩笑背後是一場悄悄發生的認識論革命：當 Kirkpatrick 與 Kernighan 等人開始把積體電路的佈局問題寫成圖論問題時，他們其實是在做一件前所未有的工作——把一個物理對象（矽晶片上的金屬與摻雜）翻譯成純數學對象（頂點與邊），並且相信這個翻譯「不失真到足以指導工程」。這種翻譯的成功與失敗，決定了此後六十年 EDA 演算法的天花板。

從電路到圖：頂點與邊的第一次相遇#

把電路變成圖，第一步是抽象。一顆積體電路的網表（netlist）描述了兩件事：一堆電路單元（cell，電晶體或邏輯閘），以及一堆線網（net，把單元之間的端點連起來的電氣連接）。最直覺的圖表示是：每個 cell 是一個頂點 \(v_i\) ，每條 net 若只連接兩個 cell 就是一條邊 \(e = (v_i, v_j)\) 。這個圖模型在 1960 年代的雙極體電路時代大致夠用，因為當時的互連以兩端為主。

但 MOS 電路一出現，這個模型就崩潰了。一個 NAND 閘的輸入端可以連到五個不同的邏輯閘的輸出，一條時脈線網更是串連全晶片幾萬個端點。「三端以上的連接」是圖無法自然表達的——圖的邊只有兩個端點。若硬要表示，只能把一條 k 端 net 拆成 \(\binom{k}{2}\) 條邊的完全圖，但這會帶來我們下面要談的建模災難。

超圖：Karp 的另一個遺產#

處理多端連接的正確數學物件是超圖（hypergraph）：一個超圖 \(H = (V, E)\) 中，每條超邊（hyperedge） \(e \in E\) 是頂點集 \(V\) 的一個任意子集，大小不受限制。超圖的概念可追溯到 Berge 於 1970 年出版的《Graphes et hypergraphes》一書的系統化，而它在組合優化中的重要性——尤其是 Karp 1972 年論文中討論的 Steiner Tree 問題——正是多端連接問題的數學原型。

在 EDA 裡，netlist 就是超圖：每個 net 是一條超邊，連接它所有 pin 所在的 cell。partitioning 問題於是成為「超圖分割」（hypergraph partitioning），目標是最小化被切斷的超邊數目（cut nets）。這個問題比圖分割更難，也更能反映真實成本——這就是為什麼 Kernighan–Lin 之後，Fiduccia–Mattheyses 與 1997 年的 hMetIS（Karypis 與 Kumar）都必須以超圖為模型。

Clique model 與 net model：一條線的兩種算法身分#

把超圖「降級」成圖的兩種常見做法，孕育了 EDA 文獻裡一個著名的建模爭論。

clique model 把一條 k 端 net 拆成完全圖 \(K_k\) ，共 \(\binom{k}{2}\) 條邊。net model（也叫 star model 或 hyperedge model）則保留超邊本身，或等價地引進一個虛擬「星形節點」連到所有端點。兩者的差異在線長估計上至關重要。佈局演算法的目標函數通常是 HPWL（half-perimeter wire length，半周長線長）：對一條 net，先計算其所有 pin 的 bounding box，再取

\[ L_e = \frac{w_e + h_e}{2} \]

其中 \(w_e\) 與 \(h_e\) 分別是 bounding box 的寬與高；總線長是所有 net 之和

\[ L = \sum_{e \in E} L_e = \sum_{e \in E} \frac{w_e + h_e}{2} \]

HPWL 之所以成為事實標準，是因為假設曼哈頓繞線（Manhattan routing）、單一 Steiner 點位於 bounding box 內時，它是 Steiner tree 長度的合理下界與近似（經驗上誤差約 10–30%，視 net 大小而異）。而當我們用 clique model 把 net 拆成完全圖時，若直接把 \(\binom{k}{2}\) 條邊的 HPWL 加總，k 端 net 的權重會被放大 \((k-1)\) 倍——這就是著名的「k 端 net 權重膨脹」問題。補救方法有兩種：一種是除以 \((k-1)\) （clique 均一化），一種是直接用 net model 的 bounding-box HPWL。兩種選擇會導致佈局結果的系統性差異：clique model 傾向把大 net 的端點拉近（因為邊多、懲罰大），net model 則對所有 net 一視同仁。哪個「更對」沒有數學答案，取決於後續繞線器實際的 cost 函數。

這個爭論看似技術細節，卻揭示了 EDA 演算法的一個根本困境：數學模型的每一個選擇，都是對物理現實的一次簡化，而簡化的代價往往在下游幾個階段才顯現。 1990 年代的學術界曾為此辯論多年，直到 ISPD 與 DAC 論文逐步累積實證，才形成「用 net model 做 global placement、用 clique model 做 partitioning 較合理」的經驗共識。

從幾何到邏輯：BDD 之前的圖表示#

圖與超圖不只用於實體設計，它們也是邏輯表示的先驅。在 1986 年 Randy Bryant 的 BDD（Binary Decision Diagram，二元決策圖）成名之前，邏輯函數的圖表示歷史同樣精彩。1959 年，C. Y. Lee 在 Bell Labs 發表的《Representation of Switching Circuits by Binary-Decision Programs》首次系統化二元決策程式；1978 年，Akers 把它整理成今日的 BDD 雛形。在這之前，邏輯函數的表示主流是真值表（指數大小）與布林代數式（大小依賴代數形式），兩者都對「自動化」不友善——沒有一個標準的資料結構可以支援相等判斷與操作。

1970 年代中期，另一種圖表示在 Bell Labs 與 IBM 的內部工具中流行：邏輯電路的 DAG（有向無環圖）表示，每個節點是一個邏輯閘，邊是訊號依賴。這個 DAG 直到今天仍是所有邏輯合成工具的內部表示（如 ABC 的 AIG，And-Inverter Graph）。DAG 的問題是「同一個函數有無窮多種表示」，因此等價判斷與優化都困難；BDD 的革命在於它對固定變數順序提供了正規形（canonical form），使相等判斷變成 \(O(1)\) 。從 DAG 到 BDD 的演進，是 EDA 演算法史上「資料結構決定演算法命運」的最佳範例。

為什麼建模如此重要：三個歷史教訓#

回顧歷史，超圖建模的成功與失敗給我們三個教訓。第一，模型決定演算法的適用範圍：把 netlist 當圖的超圖分割演算法（如 hMetIS）與把 netlist 當超圖的演算法，在真實電路上表現差異顯著。第二，模型決定目標函數的物理意義：HPWL 是一種近似，它的誤差在高扇出 net 上最大，這促使 1990 年代後期出現以 Steiner tree 長度或 Elmore delay 為目標的 placement 研究路線。第三，模型決定問題的複雜度：clique model 把超圖變成稠密圖，看似「更多資訊」實則製造了虚假的最短路徑；這提醒我們，資訊愈多不見得愈好，重點是資訊的正確性。

還有一個更廣的視角：從圖到超圖的演進，反映了 EDA 演算法從「純數學借來的框架」走向「為晶片量身定做的數學」的成熟過程。1960 年代的 EDA 研究者從圖論教科書找工具；1990 年代的研究者則開始為晶片問題發明新的數學物件。這個成熟過程的另一個表徵，是邏輯領域從布林代數的傳統，逐漸長出一套 EDA 專屬的資料結構與演算法生態。

下一章，我們就來講這段「布林的遺產」：從 George Boole 的邏輯代數、Claude Shannon 把它變成電路的語言，到 Shannon expansion、Quine–McCluskey 與 Bryant 的 BDD——看看純數學的抽象遊戲，如何在百年後成為晶片設計自動化的脊樑。