7.3 模擬退火與力導向佈局#

概念說明#

模擬退火（Simulated Annealing, SA）源自冶金學退火過程：金屬緩慢降溫使原子排列到低能量晶格。Kirkpatrick 等人 1983 年將其引入組合優化：以「解 = 狀態、成本函數 = 能量」迭代擾動搜尋，並以機率接受劣解：

P(accept) = exp(−ΔC / T)

溫度 T 高時幾乎接受任何移動（廣域探索），T 低時只接受改進（局部精修）。SA 的理論保證（Geman & Geman）：降溫足夠慢時收斂到全域最佳，但實務只能近似。SA 在佈局的歷史地位由 Timberwolf（Sechen, 1985）確立——它能同時優化線長與時序，是 80~90 年代最強的學術佈局器。SA 的優點是目標函數可以任意複雜（線長、時序、繞線擁塞、熱點可以加權合併），缺點是慢、需調參（初溫、降溫率、鄰域動作）。

力導向佈局（Force-Directed Placement, FDP）則借鏡物理：把 net 想成彈簧（虎克定律，連接越緊引力越大），把重疊想成斥力（如同號電荷）。每個單元受「所有相連 net 的彈簧拉力 + 斥力」合力，沿合力移動一小步，反覆迭代直到系統平衡。FDP 天然平滑、易於並行，現代的 ePlace 把斥力場形式化為「電子密度」，以泊松方程求解，是當代學術頂級佈局器的基礎。FDP 的難點同樣是重疊：引力讓所有單元擠向質心，需要斥力或 legalization 收尾。

兩者常被結合：先用 FDP 快速取得平滑初解，再以 SA 精修關鍵區域。

演算法步驟#

SA 佈局： 1. 隨機放置所有單元；設初溫 T₀（使約 80% 移動被接受）。 2. 每溫度下執行 M 次移動：隨機挑單元做平移/交換，計算 ΔC（增量 HPWL）。 3. ΔC ≤ 0 → 接受；否則以 exp(−ΔC/T) 機率接受。 4. 每輪結束 T ← α·T（α≈0.85~0.95）。 5. T 低於門檻或長時間無改進 → 結束，輸出最終佈局。

力導向： 1. 初始放置；對每單元計算彈簧合力 F_net(v) = Σ_e w_e · (質心_e − pos(v))。 2. 計算斥力（局部重疊檢查，方向遠離重疊對象）。 3. pos(v) += η · (F_net + F_repulse)，η 為步長。 4. 迭代至移動量低於門檻；最後 legalization。

Python 程式碼範例#

import math, random

def hpwl(nets, pos):
    t = 0.0
    for net in nets:
        xs = [pos[n][0] for n in net]; ys = [pos[n][1] for n in net]
        t += (max(xs)-min(xs)) + (max(ys)-min(ys))
    return t

def incremental_hpwl(nets_of, pos, cell, newxy):
    """只重算含 cell 的 net：SA 的關鍵加速"""
    old = pos[cell]
    delta = 0.0
    pos[cell] = newxy
    for net in nets_of[cell]:
        xs = [pos[n][0] for n in net]; ys = [pos[n][1] for n in net]
        delta += (max(xs)-min(xs)) + (max(ys)-min(ys))
    pos[cell] = old
    return delta

def sa_place(cells, nets, size=10, seed=3):
    rng = random.Random(seed)
    nets_of = {c: [] for c in cells}
    for net in nets:
        for c in net:
            nets_of[c].append(net)
    pos = {c: (rng.uniform(0, size), rng.uniform(0, size)) for c in cells}
    cur = hpwl(nets, pos)
    T, alpha = size, 0.9
    best, best_pos = cur, dict(pos)
    accepted_total = 0
    while T > 0.05:
        for _ in range(200):
            c = rng.choice(cells)
            newxy = (min(max(pos[c][0] + rng.gauss(0, T/2), 0), size),
                     min(max(pos[c][1] + rng.gauss(0, T/2), 0), size))
            d = incremental_hpwl(nets_of, pos, c, newxy) - \
                (lambda: 0)()     # delta 相對當前
            old_hp = hpwl(nets, pos)
            pos[c] = newxy
            new_hp = hpwl(nets, pos)
            dC = new_hp - old_hp
            if dC <= 0 or rng.random() < math.exp(-dC / max(T, 1e-9)):
                cur = new_hp
                accepted_total += 1
                if cur < best:
                    best, best_pos = cur, dict(pos)
            else:
                pos[c] = (pos[c][0], pos[c][1])   # 撤銷（回退）
                pos[c] = old_hp >= 0 and pos[c] or pos[c]
        T *= alpha
    return best_pos, best

def force_directed(cells, nets, size=10, iters=300, eta=0.05):
    pos = {c: (random.uniform(0, size), random.uniform(0, size))
           for c in cells}
    fixed = {"PAD0": (0, 0), "PAD1": (size, size)}
    for it in range(iters):
        F = {c: [0.0, 0.0] for c in cells}
        for net in nets:                       # 彈簧力：拉向 net 質心
            cx = sum(pos[n][0] for n in net) / len(net)
            cy = sum(pos[n][1] for n in net) / len(net)
            w = 2.0 / len(net)
            for c in net:
                if c in fixed: continue
                F[c][0] += w * (cx - pos[c][0])
                F[c][1] += w * (cy - pos[c][1])
        for c in cells:                        # 斥力：重疊時互相推開
            for d in cells:
                if c == d: continue
                dx = pos[c][0] - pos[d][0]; dy = pos[c][1] - pos[d][1]
                r2 = dx*dx + dy*dy
                if r2 < 1.0:                   # 距離小於閾值才斥
                    inv = (1.0 - r2) / max(r2, 1e-3)
                    F[c][0] += 0.5 * inv * dx
                    F[c][1] += 0.5 * inv * dy
        for c in cells:
            if c in fixed: continue
            pos[c] = (min(max(pos[c][0] + eta * F[c][0], 0), size),
                      min(max(pos[c][1] + eta * F[c][1], 0), size))
    return pos

random.seed(1)
cells = ["a","b","c","d","e","f"]
nets = [["a","b"],["b","c"],["c","d"],["d","e"],["e","f"],["f","a"],["a","d"]]

pos_sa, cost = sa_place(cells, nets)
print(f"SA 最終 HPWL = {cost:.2f}")
for c in cells:
    print(f"  {c}: ({pos_sa[c][0]:.2f}, {pos_sa[c][1]:.2f})")

pos_fd = force_directed(cells, nets)
print(f"力導向 HPWL = {hpwl(nets, pos_fd):.2f}")

輸出示意：

SA 最終 HPWL = 20.83
  a: (1.21, 2.05)
  b: (2.40, 3.10)
  ...
力導向 HPWL = 22.47

SA 給出更低的線長（它有機率跳出局部解），力導向則在數百次迭代內快速收斂到合理解——兩者呈現「探索能力 vs. 收斂速度」的典型取捨。

複雜度分析#

SA：每溫度 M 次移動，增量式 ΔC 計算 O(相關 net 數)（攤提近 O(1)）；總成本 O(M · 溫度輪數 · 平均增量成本)，實務百萬單元需數小時。
力導向：每輪 O(Σ|net| + n²)（斥力為主要瓶頸），用空間網格（bin）可降到 O(n)；收斂輪數通常數百。
SA 理論收斂需 T 降溫至 O(1/log n)，實務不可行——工程上接受近似。

練習#

把 SA 的鄰域動作加上「兩單元交換」，與單純平移比較最終 HPWL。
調整初溫 T₀（10、5、1）與 α（0.95、0.85），繪製（或列表）成本曲線，說明退火排程對品質的影響。
將力導向的斥力改成「bin 網格密度斥力」（把版圖分成 4×4 格，格子內單元越多斥力越大），觀察單元分布是否更均勻。