5.3 ePlace 與 RePlAce：靜電力類比的密度懲罰函數#

GORDIAN 與 force-directed 時代的分析式擺放有一個共同的尷尬：密度處理靠啟發式——釘扎、bin 指派、經驗排斥力——整個方法沒有一個統一的目標函數，收斂與否端看調參功夫。2012 年，加州大學聖地牙哥分校（UCSD）的 Andrew B. Kahng 與其學生 Cherokee（Jason）Cheng 在 ISPD 2012 發表了 ePlace 的第一篇論文（Cheng, Kahng, Mamanov, Wang, "ePlace: Electrostatics-based Placement Techniques for Integrated Circuits"），隨後在 ICCAD 2015 發表處理 mixed-size（大型 macro 與小 cell 混擺）的 ePlace-MS。這組工作把密度處理從啟發式變成嚴格的數學，是過去二十年擺放演算法最具影響力的突破之一。

核心類比：cell 是正電荷#

ePlace 的想法極為漂亮：把每個 cell 想成一塊帶正電的導體板，面積正比於 cell 面積，分布在晶片平面上；再想像晶片四周有一圈接地導體牆。根據靜電學，同號電荷互相排斥，而接地邊界會提供束縛。若我們能把 cell 想成會滑動的電荷，靜電力自然會把它們推散開來，同時邊界把整體約束在晶片範圍內——這正是「密度均勻化」所需的一切性質。

形式化如下。以核函數 \(\phi(x,y)\) （在原始論文中是高斯核，半徑隨迭代縮小）把離散的 cell 疊加成連續的電荷密度：

\[ \rho(x, y) = \sum_i A_i\, \phi(x - x_i,\, y - y_i) + \text{(邊界外的鏡像電荷)} \]

其中 \(A_i\) 是 cell 面積。目標密度 \(\bar{\rho}\) 是電路總面積除以可用面積。然後解泊松方程（Poisson equation）求電位：

\[ \nabla^2 \phi = -\frac{\rho - \bar{\rho}}{\epsilon} \]

電位 \(\phi\) 的負梯度就是電場 \(E = -\nabla\phi\) ，而每個 cell 所受的靜電力 \(F_i = A_i\, E(x_i, y_i)\) 。整個流程如下：

初始化 cell 座標 p
while not converged:
    1. 以高斯核疊加, 計算電荷密度場 ρ
    2. 解泊松方程 ∇²φ = -(ρ - ρ̄)/ε, 得電位 φ 與電場 E = -∇φ
    3. 總力 F = 線長梯度(-∇f_WL) + 靜電力 A·E
    4. 沿 F 更新座標 (梯度流 / 擬牛頓步)
    5. 依密度收斂程度調整線長權重 λ (ePlace 的溢出排程)
return p

注意泊松方程中用的是 \(\rho - \bar{\rho}\) （超出平均密度的「多餘電荷」），這使電場只在密度不均時出現——密度完全均勻時系統只剩線長項在作用，優雅地分離了兩個目標。

為什麼用 DCT 解泊松方程#

泊松方程是十九世紀數學物理最老練的問題，數值解法俯拾皆是。ePlace 的工程選擇是離散餘弦變換（DCT）：在矩形域、Neumann 邊界條件下，泊松方程以 DCT 為特徵函數基底，可以「一次正向變換、逐點除以特徵值、一次逆向變換」直接求出譜解。二維 DCT 的複雜度是 \(O(n \log n)\) ，而且有高度優化的 FFTW／FFT 實作，GPU 上更能並行。相比之下，GORDIAN 的釘扎迭代每輪都要組裝並預分解一個新的稀疏線性系統，而 ePlace 的密度項完全不改變線長部分的稀疏結構——每次迭代只需重算密度場（ \(O(n)\) 次高斯核疊加）與一次 DCT。這個複雜度結構使 ePlace 在百萬 cell 設計上每輪迭代只要數秒，成為第一個真正 scale 的開源分析式擺放。

非線性線長：weighted-average 的光滑化#

另一個同等重要的技術是線長函數本身。HPWL 不可微，二次線長又不準。ePlace 採用了光滑的 weighted-average 線長（源自 Nakhate 等 2000 年代的工作，又稱 WA 模型）：對一條 net，把每個 pin 的座標以其「指數權重」平均後加權求差：

\[ \widehat{x}_i = \frac{\sum_j x_j \exp(\alpha x_j)}{\sum_j \exp(\alpha x_j)}, \qquad \mathrm{WA}(e) \approx (\hat{x}_{\max} - \hat{x}_{\min}) \]

當控制參數 \(\alpha\) 隨迭代增大時，這個函數從平滑過渡到逼近真實 HPWL。這就是所謂 nonlinear HPWL：擺放演算法先在光滑鬆弛版上收斂到大致形狀，再逐步收緊近似，最後以真實 HPWL 評估。整個方法因此成為一個有明確目標函數、明確梯度、明確近似序列的連續優化過程——這正是 GORDIAN 缺少的理論完整性。

從論文到商業工具：RePlAce 與 Cadence#

ePlace 的學術影響迅速轉化為工程影響。2018 年，Cheng 與合作者以開源專案 RePlAce（曾進入 DAC 系統設計競賽）的形式發布了完整實作；同一時期，這批技術的核心人物相繼進入商業 EDA 公司。值得指出的是，Kahng 的長期合作網與 Cadence 的布局技術密切相關：ePlace 的思想被廣泛認為進入了新一代商業 place-and-route 工具的分析式引擎，Cadence 於 2010 年代後期收購了以實體設計自動化見長的團隊並持續強化其 Innovus 的擺放核心。同時，開源晶片設計運動（DARPA IDEA 計畫資助的 OpenROAD）把 RePlAce 的血統直接嵌入其 global placement 引擎，使「學術界發明、開源社群維護、商業工具吸收」成為近年 EDA 演算法流動的標準路徑。

為什麼 ePlace 能商業化而前代不能？技術上，它是第一個兼顧線長、密度、可擴展性三者且每項都有明確數學定義的方法；產業上，2010 年代先進製程（28nm 以降）的設計週期壓力使擺放從「一小時級」變成「分鐘級」需求，ePlace 的 DCT 快速迭代恰好命中這個績效指標；制度上，UCSD 團隊持續在 ISPD/ICCAD/DAC 發表可複現、開源的結果，配合大學科技轉移的慣常管道，讓演算法的知識產權路徑清楚，企業才敢投入整合。這是科技、經濟、制度三者咬合的教科書案例。

2021–2023 的 Google RL placement 論戰#

ePlace 的統治地位並非沒有挑戰。2021 年，Google 團隊（Mirhoseini 等，Nature 論文）宣稱以強化學習（RL）完成 TPU 的 macro 擺放，並稱達到或超過人類水準，引發廣泛關注。然而 2023 年，以 UCSD 的 Kahng、NVIDIA 的 Igor Markov 等人為代表的研究者發表了尖銳的反駁（「The ISPD 2023 Contest on Benchmarking of Commercial RL for CAD: Placement」相關討論與 Markov 等人的技術報告），指出該工作存在基準問題、與商業工具比較不當、以及把既有方法（如 simulated annealing 後處理）的貢獻混淆在內等疑點；Kahng 一貫的立場是：任何新方法必須在公開基準上與最先進的分析式＋退火混合流程公平對比，而 ePlace 系的分析式擺放至今仍是那個最難打敗的對手。這場論戰的細節我們在 9.3 節再深入展開，此處先記下一個史學上的觀察：每當有新典範宣稱取代基於物理與優化理論的舊典範，社群的第一反應都是檢驗其基準是否公平——這是 EDA 這門工程學科數十年累積出的自我修正機制。

ePlace 解決了標準 cell 與 macro 的連續擺放，但 ASIC 之外的另一個世界——FPGA——面對的是完全不同的約束結構：有限的邏輯塊、固定的開關盒、以及必須逐 site 對齊的離散格子。在那裡，統治三十年的不是分析式方法，而是模擬退火。下一節我們走進多倫多大學，看 VPR 如何成為 FPGA 擺放不敗的溫度計。