跳轉到

5.2 GORDIAN 與 Force-Directed：把電路當彈簧網#

上一節我們看到，二次擺放把 cell 用彈簧相連、解一個線性系統 \(Ax=b\) ，就能得到線長極小的連續座標。但這個解有個致命傷：它把電路壓成一團重疊的點。整個 1980 年代，「如何讓彈簧網的解攤開成合法布局」是分析式擺放的核心難題，而德國慕尼黑工業大學（Technische Universität München, TUM）的 GORDIAN 系統，給出了影響後世十年的答案。

早期的工作：QS 與 Goto 的力學直覺#

在 GORDIAN 之前，把力學類比引入擺放已有前例。Goto（1976，東京大學／日立）提出了把 cell 之間的連接視為吸引力的「force-directed」雛形：每條 net 對其 pin 施加拉力，使相連 cell 趨近；再以力的逐次平衡（每次把一個 cell 移到其合力為零的位置）推進解。同時期的 Quinn 與 Breuer（1979）等人也研究了以二次線長為基礎的迭代鬆弛。這些方法的共同特徵是「逐 cell 鬆弛」：一次優化一個 cell 的座標，反覆掃描直到系統平衡。它們實現簡單、直觀，但收斂慢，而且缺乏對密度的全局觀——所有 cell 仍然會互相擠壓。

真正把這個框架提升到 VLSI 工業可用水準的，是 TUM 的系統性工作。Jürgen Kleinhaus、Jens Stangl 與 Kurt Antreich 在 1980 年代末發表了 GORDIAN 的第一版（Kleinhaus, Stangl, Antreich, "GORDIAN: VLSI Placement by Quadratic Programming", ICCAD 1990）；隨後 Pedro Sigl、Konrad Doll 與 Frank Johannes 在 1991 年 ICCAD 上發表了把分區與分析式擺放結合的擴充版（Sigl, Doll, Johannes, "Solving Generalized Assignment Problems by Quadratic Programming" 一系工作，一般通稱 GORDIAN-L）。這批工作出自 Antreich 領導的 TUM 積體電路設計自動化研究組，是德國學派在 EDA 數值方法上的代表性成果。

GORDIAN：解線性系統、再分區散開#

GORDIAN 的流程可以用一個迴圈概括：

repeat
  1. 解二次擺放:  A x = b,  A y = b   (以當前的區域固定區為邊界條件)
  2. 依當前 cell 密度, 將平面劃分為數百到數千個小區域 (bin)
  3. 對每個 bin, 若其 cell 密度過高, 則將該 bin 內的 cell
     「凍結」在它們的質心 (視為新的固定點)
until 所有 bin 的密度近似均勻

關鍵在第三步：GORDIAN 不試圖顯式地「推開」重疊的 cell，而是把過度擁擠區域的 cell 直接釘死在當前位置，把它們當成新的邊界條件，再重解線性系統。被釘死的 cell 對剩餘的 cell 產生排斥性的「佔位效應」——後續的彈簧網必須繞開這些已佔據的區域，擁擠自然向外擴散。這在數學上等價於用邊界條件逼近一個含密度約束的變分問題，每輪迭代都是一次廉價的稀疏線性系統求解，配合好的預條件子可以在幾十輪內收斂到密度大致均勻的布局。GORDIAN 也引入了 bin 級的整數規劃式指派（把 cell 分給 bin 的子問題近似為線性指派），使其散開過程更受控。

Force-Directed placement：顯式的力#

與 GORDIAN 的「隱式散開」相對，force-directed placement 選擇顯式建模力。這個框架的完整敘述如下：

每對相連 cell \((i,j)\) 之間存在吸引力 \(F^{\text{att}}_{ij} = w_{ij}(p_j - p_i)\) ，這正是二次目標函數的負梯度。除此之外，為了防止坍縮，必須加入排斥力。最經典的設計是 Eisenmann 與 Johannes（1998，TUM 的後續工作）所總結的：對每個 cell 附加一個「偽排斥力」，其大小正比於該 cell 偏離其目標密度的程度，方向由周圍密度場的梯度決定：

\[ F^{\text{rep}}_i = -\gamma\, \nabla \, D(p_i) \]

其中 \(D(p)\) 是以 cell 疊加而成的密度函數， \(\gamma\) 是控制散開速度的係數。整個系統按下列 pseudo code 迭代：

初始化座標 p (例如質心)
while not converged:
    計算吸引力 F_att = A p - b          # 二次目標的負梯度
    計算排斥力 F_rep = -γ ∇D(p)        # 密度場梯度
    總力 F = F_att + F_rep
    解 A p' = b - F_rep 的線性系統      # 在當前排斥力下的平衡位置
    增大 γ (逐步加強散開)
return p

這在數學上是一個梯度流：吸引力項想最小化線長，排斥力項想最小化密度不均，兩者的權衡由 \(\gamma\) 的排程控制——初期線長主導，晚期密度主導。這個「密度函數＋其梯度作為力」的思想，正是 5.3 節 ePlace 的直系祖先，只是 ePlace 把密度函數從粗糙的直方圖升級為可微的高斯混合，並把「力的來源」從經驗法則換成了嚴格的靜電學類比。

與 5.1 的數學關係：同一個 Laplacian 的三種讀法#

把這條主線放回 5.1 的框架，可以看得很清楚。Hall 的譜方法讀的是 \(A\) 的特徵結構（整體模態）；GORDIAN 讀的是 \(Ax=b\) 的解（強迫振動的平衡態），再用釘扎近似密度約束；force-directed 方法則直接對目標函數做梯度迭代，並把密度項顯式寫進梯度。三者共享同一個加權 Laplacian 矩陣，差別只在於如何處理「線長與密度的矛盾」。這個矛盾在數學上是必然的：純線長最優解永遠坍縮，純密度最優解永遠是均勻網格，真實的擺放必須在兩者之間找 Pareto 前沿。GORDIAN 時代的方法只能以啟發式的方式逼近這個前沿；要到 ePlace 把密度項做成光滑可微的懲罰函數，這個逼近才成為有收斂理論支撐的連續優化問題。

值得一提的是 GORDIAN-L 的另一項貢獻：它證明了分析式方法可以與 net splitting 權重校正（如 Sigl 提出的使二次模型貼合 HPWL 的權重法）配合，讓「二次解的品質」可以量化地與 HPWL 目標掛鉤。這讓學界與業界開始認真比較分析式方法與模擬退火（當時另一主流，見 5.4）的優劣，也埋下了 1990 年代後期學術界系統性評測擺放演算法（如 ISPD benchmark）的種子。

德國學派的工作在當時受限於商業工具由美國主導的格局，GORDIAN 本身並未直接商品化，但它的學生們把這套方法帶進了全球的 EDA 產業與學術界：Sigl 與 Johannes 的門生遍及 Cadence、Mentor 與各大學；「解線性系統＋密度散開」成為所有後續分析式擺放（APlace、Kraftwerk、ePlace）的骨架。科技面上，這批工作回應的是 1980 年代末 ASIC 與標準單元（standard cell）流程的興起——數十萬個同尺寸 cell 的擺放，模擬退火已經太慢，產業需要「一次解一個大線性系統」的規模化方案；經濟面上，標準單元設計的商業利益讓「更快的擺放＝更短的設計週期」成為直接賣點。這是典型的制度驅動：新設計範式（標準單元）創造了新問題規模，新問題規模逼出了新數值方法。

下一節，我們看加州大學聖地牙哥分校的 Andrew Kahng 團隊如何在 2012 年把「密度函數」升級為「電荷」，讓分析式擺放一舉跨越商業化的門檻。