5.1 二次線長最小化：Quadratic Placement 的譜方法起源#
在布局自動化（placement）的漫長歷史中，二次線長最小化（quadratic wirelength minimization）是最早被系統化、數學化的一支。它不但孕育了後來的 force-directed 方法，也間接催生了今日商業工具中的分析式布局（analytic placement）。要理解這條主線，我們得先回到問題本身：擺放到底在擺什麼？
擺放問題的定義與半周長線長#
給定一個 netlist，其中包含一組 cell（邏輯閘、暫存器）與一組 net（連接這些 cell 的網線），擺放問題就是把每個 cell \(i\) 指派到晶片平面上的座標 \((x_i, y_i)\) ，在滿足面積、可繞性等限制下，最佳化某個成本函數。最常用的成本函數是總線長估計，其中最主流的是半周長線長（Half-Perimeter Wire Length, HPWL）：
對於一條 net \(e\) ，其 HPWL 定義為該 net 所有 pin 在 \(x\) 方向的分布範圍加上 \(y\) 方向的分布範圍：
HPWL 之所以成為產業標準，是因為它近似於 Steiner 樹線長（對 pin 數在 3 以下的 net，它就是精確的 rectilinear Steiner 樹線長），而且計算是 \(O(|e|)\) 的線性掃描，極為便宜。整體目標就是：
這個問題是組合性質很強的非凸問題——max/min 運算使其不可微，加上站位（site）對齊等離散限制，使其本質上接近二次指派問題（quadratic assignment problem），已被證明是 NP-hard。既然精確解不可得，1970 年代以降的研究者便開始尋找「好解且算得快」的近似框架，其中最成功的一條路，就是把 max/min 換成平方，把整個問題變成一個光滑的凸二次規劃。
從 HPWL 到二次目標函數#
二次擺放（quadratic placement）的核心想法是：對每一條 net，不再用半周長，而是用該 net 上所有 pin 座標的平方和（或以兩兩 pin 的平方距離）來估計線長：
其中 \((i,j)\) 是經過 net 拆解（star model 或 clique model）得到的 pin 對， \(w_{ij}\) 是權重。例如 clique model 把一條 \(k\) -pin net 拆成 \(\binom{k}{2}\) 條邊，並以 \(w_{ij} = 2/(k \cdot (k-1))\) 之類的係數校正，使二次模型在統計意義上貼近原 HPWL。
這個替換為什麼合理？直覺來自物理：把每條 net 想成一條線性彈簧，彈簧常數 \(w_{ij}\) ，彈簧能量恰好是 \(\frac{1}{2}w_{ij}\|p_i - p_j\|^2\) 。最小化總彈簧能量，等價於讓所有連接的 cell 互相靠攏。Hooke 定律給出的回復力 \(F_{ij} = w_{ij}(p_j - p_i)\) 是線性的，這使得整個系統的力平衡條件——也就是目標函數的梯度為零——變成一組線性方程。這是 quadratic placement 最大的美德：它是唯一能把擺放問題直接化約為解線性系統的主流方法。
線性系統 \(Ax=b\) 與正定性#
把目標函數對座標向量微分。設 \(x\) 為所有 cell 的 \(x\) 座標堆疊成的向量，則
矩陣 \(A\) 是 netlist 的（加權）Laplacian 矩陣：對角元 \(A_{ii} = \sum_j w_{ij}\) 是 cell \(i\) 連接的總彈簧常數，非對角元 \(A_{ij} = -w_{ij}\) 。右端項 \(b\) 來自固定座標的 cell（如 I/O pad）：若有 pad 固定在座標 \(p_k\) ，它對相連 cell 貢獻 \(w_{ik} p_k\) 到 \(b\) 。 \(y\) 方向同理，且由於目標函數在 \(x\) 、 \(y\) 可分離，兩個方向各解一個線性系統，共用同一個矩陣 \(A\) 。
這裡有一個微妙但關鍵的點：純 Laplacian 系統是半正定（positive semi-definite）而非正定的——如果整個電路沒有任何固定點，把所有 cell 平移任意距離成本不變， \(A\) 有一個零特徵值（對應常向量 \(\mathbf{1}\) ），解不唯一。標準的處理方式有三種：固定至少一個 cell（pad 就是天然的固定點）、加上質心約束 \(\sum x_i = \sum y_i = 0\) 並以 Lagrange 乘子擴充系統、或是加上微弱的「拉向質心」正則項。只要處理得當， \(A\) 成為對稱正定矩陣，而對稱正定系統是數值線性代數最擅長的對象：共軛梯度法（conjugate gradient）保證收斂，且因為 netlist 的稀疏性（每個 cell 只與少數鄰居相連），矩陣向量乘法非常便宜，甚至可以用 incompleate Cholesky 或 multigrid 之類的預條件加速。
解出 \(Ax=b\) ，就得到一組使二次線長最小的連續座標。問題是：這組解通常嚴重重疊——所有被強連接的 cell 會被彈簧拉到幾乎同一點。因此純粹的二次方法只是「分析階段」，後面還需要拆散（spreading）與合法化（legalization）。這個「求解—散開—再求解」的迭代結構，正是 5.2 的 GORDIAN 與 5.3 的 ePlace 一脈相承的主軸。
Hall 1970 與譜方法的起源#
二次擺放的數學根源，比 VLSI 還要早。英國劍橋大學的 Kenneth M. Hall 在 1970 年發表了論文 An r-Dimensional Quadratic Placement Algorithm（Management Science），研究的對象還是電路板元件布局。Hall 做了兩件影響深遠的事。
第一，他明確寫下了上述二次目標函數，並指出最小值由線性系統給出——這就是後世所稱的 Hall 定理。
第二，他考慮了「完全沒有固定點」的情形，此時線性系統退化（trivial 解：全部疊在質心）。Hall 的觀察是：此時應該求助於系統的特徵結構。對無約束的二次形式 \(\sum w_{ij}\|p_i-p_j\|^2\) ，若把座標限制在單位球上（即 \(\|p\|=1\) 這種尺度約束），最小化問題的解就是 netlist Laplacian 的最小非零特徵值所對應的特徵向量。具體而言，將 cell 的座標取為 Laplacian 的第二小特徵向量（又稱 Fiedler 向量，以 Miroslav Fiedler 1973 年關於圖連通性與代數連通性 \(\lambda_2\) 的研究得名）作為一維座標，取第三小、第四小特徵向量作為第二、三維座標，就得到一個把圖「攤開」在低維空間中的擺置——連接緊密的節點彼此靠近，整體結構按圖的譜（spectrum）自然展開。
這就是譜方法（spectral method）：用圖的特徵向量當作座標。譜方法在 1980–90 年代被廣泛用於電路劃分（partitioning，配合 Kernighan–Lin/Fiduccia–Mattheyses 的比例改進）與一維/二維擺放，著名實作包括 Frankle 與 Karp（1986 年 IBM）把特徵向量迭代用於 cell placement，以及 1990 年代 Alpert 與 Yao 的 partitioning-based spectral placement。譜方法的優雅之處在於它「一次給出全域形狀」：不需要迭代散開，特徵向量天然把整個電路攤平。代價則是：求解特徵向量（尤其大型矩陣的多個特徵向量）比解一個線性系統貴；而且譜座標無法輕易融入固定 pad、密度等約束。因此在 VLSI 尺度上，譜方法逐漸讓位給「解線性系統＋迭代散開」的 GORDIAN 路線，但它的思想——把電路當成一個有內在振動模態的彈簧系統——深深嵌入了所有後續的分析式方法。有趣的是，譜方法在 2010 年代以 graph embedding、node2vec 的形式在機器學習圈復活，可見好的數學不會過時。
為何是二次模型：物理直覺與工程折衷#
讀者可能會問：為什麼偏偏選平方？除了「可微、凸、線性系統」這三個技術理由之外，還有一層物理直覺。Hooke 彈簧的能量是位移的二次函數，而彈簧網的最小能量組態正是結構力學中桁架（truss）的平衡問題——這是工程師兩百年來已經完全理解的系統。把電路看成一個彈簧桁架，等於把一個離散組合優化問題映射到一個有成熟數值方法的連續力學問題上。二次模型也有一個統計上的合理性：在隨機擺放下，平方線長與實際 HPWL 之間存在可校正的系統關係，線性回歸式的權重補償（如 1980 年代 Quinn、Cheng 等人的工作）能把二次解的品質拉得相當接近真實目標。
當然，二次模型有明顯缺點：它對長 net 的懲罰過重（平方放大遠距），導致二次解過度壓縮；它完全不管密度，解出來的 cell 互相重疊。這些缺點正是後續三十多年研究的動力——5.2 用「分區迭代」解決散開問題，5.3 用「密度懲罰函數」把它變成全域收斂的完整方法。理解了二次擺放這塊基石，這些後續發展就不再是零散的技巧，而是同一個數學骨架上的修補。
下一節我們走進 1980 年代的慕尼黑工業大學，看 GORDIAN 系統如何把這個彈簧模型變成一個會呼吸、會自我散開的迭代機器。