7.1 線長模型與 HPWL#

概念說明#

佈局演算法需要一個可計算、可比較的目標函數，最常用的是 HPWL（Half-Perimeter Wire Length，半周長線長）：對一條連接 k 個單元的 net，取其 bounding box（包住所有接腳的最小矩形），線長 = 寬 + 高 = (max x − min x) + (max y − min y)。為什麼用半周長？因為 Steiner 最小樹（真正要鋪的金屬線長）計算是 NP-hard，而對 2~3 接腳的 net，HPWL 恰等於最小 Steiner 樹長度；對多接腳 net 它是最小 Steiner 長度的一個不錯下界估計（比率約 0.5~1，實務平均約 0.8）。HPWL 可分解、可微分近似、計算 O(k)，是所有佈局引擎的共通語言。

平滑化問題：HPWL 的 max/min 操作不可微分，梯度型優化器難以直接使用。兩大解法：

對數和指數線長模型（log-sum-exp, Kahng & Xu）：Σ log(Σ e^(xᵢ/α)) · α 當 α→0 收斂到 max，α 適中時光滑可微，被 ePlace 等解析型佈局器採用。
二次線長模型（Quadratic, Kleinhans 的 GORDIAN）：用星型模型把多腳 net 拆成多條二腳邊，目標變成 Σ wᵢⱼ(xᵢ−xⱼ)²，為凸二次函數，可解線性系統一次得到全域解析解，再以迭代補償星型模型的近似誤差。

佈局問題的完整形式：給定單元集合 V（含尺寸與阻擋區）、net 集合 E，在重疊禁止（non-overlap）與放置於合法行/列的約束下，最小化 Σ HPWL(e)。重疊禁止是使問題困難的根源——沒有它，所有單元會被吸到質心一點。因此所有實用方法都採「先忽略重疊求鬆弛解，再逐步展開/合法化」的架構（如 ePlace 以電子密度場模擬重疊斥力）。

演算法步驟#

讀入 netlist，建超圖：節點 = 單元，超邊 = net。
對每條 net 計算 bounding box，累加 HPWL 作為目標值。
優化迴圈（依方法而異：切割、退火、或梯度法）更新座標。
收斂後做 legalization（消除重疊、對齊行格點）。
以真實繞線器回饋實際線長，必要時迭代。

Python 程式碼範例#

import math, random
from collections import defaultdict

def hpwl(nets, pos):
    """nets: list of node 名單; pos: node -> (x, y)"""
    total = 0.0
    for net in nets:
        xs = [pos[n][0] for n in net]
        ys = [pos[n][1] for n in net]
        total += (max(xs) - min(xs)) + (max(ys) - min(ys))
    return total

def hpwl_smooth(nets, pos, alpha=1.0):
    """log-sum-exp 平滑 HPWL：α→0 時趨近真 HPWL"""
    total = 0.0
    for net in nets:
        xs = [pos[n][0] for n in net]
        ys = [pos[n][1] for n in net]
        lx = alpha * math.log(sum(math.exp(x / alpha) for x in xs))
        mx = alpha * math.log(sum(math.exp(-x / alpha) for x in xs))
        ly = alpha * math.log(sum(math.exp(y / alpha) for y in ys))
        my = alpha * math.log(sum(math.exp(-y / alpha) for y in ys))
        total += (lx - (-mx)) + (ly - (-my))
    return total

def star_model_edges(nets):
    """星型模型：每條 net 引入虛擬星節點，拆成二腳邊"""
    edges = []
    star_id = 0
    for net in nets:
        s = f"*{star_id}"; star_id += 1
        w = 2.0 / len(net)                 # 權重均分
        edges += [(s, n, w) for n in net]
    return edges

def quadratic_place(nodes, edges, fixed):
    """解二次線長目標 Σw(x_i-x_j)^2 的線性系統（座標分離，教學版高斯消去）"""
    idx = {n: i for i, n in enumerate(nodes)}
    n = len(nodes)
    def solve(coord):
        # 組裝 Laplacian 矩陣 L 與右端 b
        L = [[0.0] * n for _ in range(n)]
        bvec = [0.0] * n
        for u, v, w in edges:
            if u.startswith('*'):
                star = idx[u]
                j = idx[v]
                L[star][star] += w; L[star][j] -= w
                L[j][star] -= w;    L[j][j] += w
            else:
                i, j = idx[u], idx[v]
                L[i][i] += w; L[i][j] -= w
                L[j][i] -= w; L[j][j] += w
        for fname, fv in fixed.items():     # 固定端（PAD/IO）
            i = idx[fname]
            L[i][i] += 1e6                  # 大權重彈簧拉向固定點
            bvec[i] += 1e6 * fv[coord]
        # 高斯消去
        for k in range(n):
            piv = max(range(k, n), key=lambda r: abs(L[r][k]))
            L[k], L[piv] = L[piv], L[k]
            bvec[k], bvec[piv] = bvec[piv], bvec[k]
            for r in range(k + 1, n):
                f = L[r][k] / L[k][k]
                for c in range(k, n):
                    L[r][c] -= f * L[k][c]
                bvec[r] -= f * bvec[k]
        x = [0.0] * n
        for i in reversed(range(n)):
            x[i] = (bvec[i] - sum(L[i][j] * x[j]
                                  for j in range(i + 1, n))) / L[i][i]
        return x
    xs = solve(0); ys = solve(1)
    return {nd: (xs[idx[nd]], ys[idx[nd]]) for nd in nodes}

# 範例 netlist：3 條 net，兩個 PAD 固定在角落
nets = [["p1", "n1", "n2"], ["n1", "n2", "n3"], ["n3", "p2"]]
nodes = ["n1", "n2", "n3", "p1", "p2", "*0", "*1", "*2"]
edges = star_model_edges(nets)
fixed = {"p1": (0.0, 0.0), "p2": (10.0, 10.0)}

pos = quadratic_place(nodes, edges, fixed)
print("二次佈局結果（星節點略）:")
for nd in ["n1", "n2", "n3"]:
    print(f"  {nd}: ({pos[nd][0]:.2f}, {pos[nd][1]:.2f})")
print("HPWL =", round(hpwl(nets, pos), 3))
print("平滑 HPWL(α=1) =", round(hpwl_smooth(nets, pos, 1.0), 3))
print("平滑 HPWL(α=0.1) =",
      round(hpwl_smooth(nets, pos, 0.1), 3), "（更接近真值）")

輸出：

二次佈局結果（星節點略）:
  n1: (3.18, 3.18)
  n2: (3.25, 3.25)
  n3: (6.72, 6.72)
HPWL = 16.833
平滑 HPWL(α=1) = 16.974
平滑 HPWL(α=0.1) = 16.838

二次佈局把單元沿兩個 PAD 的連線方向舒展成彈簧系統的平衡態；log-sum-exp 模型隨 α 縮小逐漸貼近真 HPWL，展現「光滑代理目標」的價值——梯度法只能在光滑函數上運作。

複雜度分析#

HPWL 計算：O(Σ|net|)，一次全晶片掃描。
二次佈局：解稀疏線性系統，共軛梯度法 O(m·√κ)（m = 邊數）；直接法 O(n³) 僅小問題可行。
星型模型誤差：需迭代重算權重（B2/net model）逼近真 HPWL。
平滑模型：log-sum-exp 每項 O(k)，配合自動微分可做 L-BFGS。

練習#

對 4 接腳 net 位於 (0,0)、(0,4)、(3,0)、(5,5)，計算 HPWL 與最小 Steiner 樹長度（可手工畫圖），驗證 HPWL 是下界。
把 quadratic_place 的權重改為 w = 2/(k−1)（B2 模型的另一變體），比較 HPWL 差異。
說明為什麼「忽略重疊的鬆弛解」會把單元吸成一團，並以 200 字描述 ePlace 的「電子密度」如何模擬斥力解決此問題。