跳轉到

5.3 模擬退火佈局#

原始碼：veryl-eda/src/asic/place.rs（342 行）。輸入：映射後網路 + 目標 利用率；輸出：RowPlacement（每 cell 的 (row, site)、IO pin 位置、退火 history）。

5.3.1 問題與座標系#

標準單元佈局（standard-cell placement）要求：所有 cell 落在等高的列 （row）上，彼此不重疊，並最小化某種估計成本。vlib 的幾何（lib.rs）：

pub const ROW_H: f64 = 4.0;   // 列高 µm
pub const SITE_W: f64 = 0.5;  // site 寬 µm

每列是一排 site；cell 寬度以 site 計（NAND2 3 site、DFF 14 site，見 lib::LIB）。巨集（SRAM，多列高）位置固定（fixed），先以 shelf packing 從左下角排好，die 不夠大就長大：

// veryl-eda/src/asic/place.rs（節錄）
// macros: shelf packing from the bottom left (grow the die until they fit)
loop {
    mpos.clear();
    let (mut x, mut y, mut shelf) = (0u32, 0u32, 0u32);
    for c in (0..n).filter(|c| fixed[*c]) {
        if x + widths[c] > sites { x = 0; y += shelf; shelf = 0; }
        if y + heights[c] > rows || x + widths[c] > sites { ok = false; break; }
        mpos.push((c, y, x)); x += widths[c]; shelf = shelf.max(heights[c]);
    }
    if ok { break; }
    rows += 1; sites += sites / 20 + 1;
}

die 大小由利用率反推：

\[ \text{need} = \frac{\text{cell 總 site 數}}{util} + 1.1 \times \text{macro 面積},\qquad side = \sqrt{\text{need} \times \text{site\_w} \times \text{row\_h}} \]

IO pin 均勻分布在 die 邊（輸入左/上、輸出右/下，around()），並吸附到 繞線網格（site 欄 × 軌道列）上，被佔的節點沿邊讓位。

5.3.2 模擬退火理論#

佈局是組合最佳化問題（把 \(n\) 顆 cell 放進 \(\text{rows} \times \text{sites}\) 的格子、不重疊），搜尋空間天文數字且處處局部極小。模擬退火（simulated annealing, Kirkpatrick et al. 1983）用統計力學的退火類比跳脫局部極小：

  • 每步在鄰域中隨機產生新解，成本變化 \(\Delta\) ；
  • Metropolis 準則： \(\Delta \le 0\) 必收； \(\Delta > 0\) 以機率
\[ P = e^{-\Delta / T} \]

接受（ \(T\) 是「溫度」）； - \(T\) 逐輪下降，高溫時幾乎什麼都收（自由探索），低溫時只接受變好 （收斂成局部下降）。

本專案的實作，接受判準一行：

// veryl-eda/src/asic/place.rs
if delta <= 0.0 || rng.unit() < (-delta / temp).exp() { ... accept ... }

溫度排程#

初始溫度不是拍腦袋，而是從 200 顆隨機 cell 的 net 成本統計出標準差：

let mut temp = {
    let mut d = vec![];
    for _ in 0..200 {
        let c = rng.below(n); if fixed[c] { continue; }
        d.push(cell_nets[c].iter().map(|k| ncost[*k]).sum::<f64>());
    }
    let m = d.iter().sum::<f64>() / d.len() as f64;
    (d.iter().map(|x| (x - m) * (x - m)).sum::<f64>() / d.len() as f64).sqrt().max(1.0)
};

這是 Kirkpatrick 原文的自適應初始溫度想法： \(T_0\) 應與「單步成本擾動的 尺度」同量級，使初期接受率落在舒適區。之後每輪依實測接受率調溫：

temp *= if rate > 0.96 { 0.5 } else if rate > 0.8 { 0.9 }
        else if rate > 0.15 { 0.95 } else { 0.8 };

解讀：接受率太高（>96%）→ 降溫太快一半（還在亂晃，省時間）；80–96% → 穩定 下降；15–80% → 溫和降溫（黃金工作區）；<15% → 凍住了，反而回升 20% 給它 一次機會。這比幾何排程（ \(T \leftarrow \alpha T\) ）更能對不同大小的設計自洽。

終止條件也是尺度化的：

if temp < 0.005 * cost.max(1.0) / pnets.len() as f64 { break; }

即：單步溫度小於「每 net 平均成本的 0.5%」時，擾動已無意義，停。

鄰域：move 與 swap，且永遠合法#

let a = rng.below(n);
let rr = rlim.max(1.0) as i64;
let r2 = (ra as i64 + rng.below((2*rr+1) as usize) as i64 - rr).clamp(0, rows as i64 - 1) as u32;
let xr = (rr * 8).max(4);
let x2 = (xa as i64 + rng.below((2*xr+1) as usize) as i64 - xr).clamp(0, (sites - wa) as i64) as u32;
// target: free space, or a single cell we can swap with
let b = occ[r2 as usize][x2 as usize];
if free_run(&occ, r2, x2, wa, &[a as i32]) { plan.push((a, r2, x2)); }
else if b >= 0 && ... && free_run(&occ, rb, xb, wa, &ig) && free_run(&occ, ra, xa, wb, &ig) && !clash {
    plan.push((a, rb, xb)); plan.push((b, ra, xa));   // swap
}

只有兩種鄰域動作：move（cell 挪進一段 free_run 空位）與 swap （兩顆 cell 互換，且互換後雙方都得放得下）。每次移動一步就合法 （不重疊、不越界）——這是讓退火可以直接做的關鍵設計；若允許非法中間態， 就要每步做「合法化修復」，成本高且成本函式不連續。

rlim（range limit）控制 move 的距離：高溫時大範圍搬動，低溫時只做 小抖動，且同樣依接受率自適應：

rlim = (rlim * (1.0 - 0.44 + rate)).clamp(1.0, rows.max(sites / 8) as f64);

若從既有佈局精修（start: Some(...)，timing-driven pass 用），則 temp *= 0.02; rlim = 2.0——低溫短步，只做局部整理。

5.3.3 成本：HPWL + 密度懲罰#

線長用半周長線長（Half-Perimeter Wire Length）估計：

\[ \text{HPWL}(net) = (x_{\max} - x_{\min}) + (y_{\max} - y_{\min}) \]

這是 Steiner 樹長度的下界，計算只要掃一遍端點，且對移動單一端點的 增量更新極廉價——退火每步要做幾萬次，這是唯一現實的選擇：

let hpwl = |k: usize, pos: &Vec<(u32, u32)>| -> f64 {
    let (mut x0, mut y0, mut x1, mut y1) = (f64::MAX, f64::MAX, f64::MIN, f64::MIN);
    for &c in &pnets[k].cells { ... x0 = x0.min(x); ... }
    for &p in &pnets[k].pins { ... }
    ((x1 - x0) + (y1 - y0)) * weights.get(&pnets[k].bit).copied().unwrap_or(1.0)
};

weights 來自 mod.rs 的 timing_weights()（時序驅動 pass）：

crit.iter().map(|(b, c)| (*b, 1.0 + 6.0 * (*c as f64).powi(8)
                            / (fanout.get(b).copied().unwrap_or(1).max(1) as f64).sqrt())).collect()

只加重近臨界（criticality 接近 1）的 net，並以 \(\sqrt{\text{fanout}}\) 折減—— 為什麼折減？ 一條高扇出又高權重的 net 會把散布全 die 的端點全拉近， 擠爆它周圍的佈局；criticality⁸ 的陡峭次方則保證只有真正臨界的 net 才被拉。

純線長最佳化有個著名病理：cell 全擠到 pin 附近，其餘 die 空著、局部繞線 密度爆炸。所以成本加上密度 bin 懲罰：

let (bw, bh) = (32u32, 4u32);                       // 16 × 16 µm 的 bin
let target = (util + 0.15).min(0.9);
let pen = |used: f64, cap: f64| lambda * (used - target * cap).max(0.0);

懲罰是單側線性（超過 target × 容量 才罰），每 bin 的 bin_used 在 move/swap 時增量維護——拒絕時逆序回退：

for &(b, dw) in &bins { delta += pen(bin_used[b] + dw, bin_cap[b]) - pen(bin_used[b], bin_cap[b]); bin_used[b] += dw; }
...
} else {
    for &(b, dw) in bins.iter().rev() { bin_used[b] -= dw; }   // undo
    ...還原 occ/pos...
}

5.3.4 增量評估：退火能跑起來的唯一理由#

naïve 做法每步重算全部 net 的 HPWL： \(O(N)\) 。本實作只重算被動到的 net：

touched.clear();
for (c, _, _) in &plan { for &k in &cell_nets[*c] { if stamp[k] != gen { stamp[k] = gen; touched.push(k); } } }
let newc: Vec<f64> = touched.iter().map(|&k| { let v = hpwl(k, &pos); delta += v - ncost[k]; v }).collect();

stamp/gen 是去重蓋章法（同一 net 一個 plan 只算一次）。cell 平均接 2–4 條 net，所以每步成本是常數級，總複雜度 \(O(\text{rounds} \times \text{moves}) = O(n)\) 量級——瀏覽器裡跑幾千顆 cell 可行的原因。

時鐘/非同步 reset 網路不參與線長退火：

pub fn special_nets(nl: &Netlist) -> HashSet<Bit> { ... "CK" | "RN" | "SN" ... CLKBUF ... }
let pnets: Vec<PNet> = nets(nl, &pins).into_iter().filter(|p| !special.contains(&p.bit)).collect();

為什麼？ 時鐘樹的形狀由 CTS 之後才決定（5.6），而且時鐘網路是星狀 （一源多載），HPWL 會誤導退火把所有 FF 拉成一團——那既不可能（FF 屬於 各自邏輯簇）也不需要（CTS 會建平衡樹）。

5.3.5 時序驅動 pass 與 keep-the-better#

mod.rs 的 physical() 在第一次（純線長）佈局 + STA 之後，用臨界度加權 再退火（可能從原佈局精修，或小設計整個重來），並只在「可繞且更快」時 採用：

let p2 = place::place(&mapped, seed, util, &weights, start.as_deref());
let r2 = route::route(&mapped, &p2);
let t2 = sta::analyze(&mapped, &p2, &r2, extra_hold);
if r2.overflow == 0 && t2.fmax > timing.fmax { placement = p2; routing = r2; timing = t2; }

RowPlacement.history 記錄每輪的 (temp, cost, accept, pos)（上限 40 個 frame），供網頁端畫退火過程曲線——退火過程本身就是教學素材。

5.3.6 與 SKY130 重試的銜接#

佈局層不管詳細繞線，但 die 夠不夠鬆由它定：flow_with 在詳細繞線有 conflict/opens 時以 util = r.9 * 0.85 重跑 physical()，等於回到本章 重新退火一個更大的 die（見 5.1.2）。另一個方向：physical() 開頭的 route probe（route_with(..., 8)）若 overflow 大或 demand 高，也會直接 util *= 0.8 重退火。佈局品質不只有線長一個面向，繞得通是前提。

5.3.7 虛擬碼總覽#

place(nl, seed, util, weights, start):
    # 1. 幾何準備
    die 大小 ← cell 總 site / util（巨集 +10% 餘量）
    巨集 shelf packing（放不下就長大 die）
    IO pin 均勻分布到四邊 → 吸附繞線網格（佔用讓位）
    # 2. 初始解
    標準 cell 按拓撲序蛇形鋪排（每列配額 ∝ 空位數，奇數列反向）
    放不下的 spill cell 找第一段空位
    if start: 清空標準 cell，按 start 座標重放（精修模式）
    # 3. 成本狀態
    ncost[k] ← 每條 net 的 weighted HPWL
    bin_used/bin_cap ← 32×4 site 的密度 bin
    cost ← Σ ncost + Σ pen(bin)
    T ← 200 顆 cell net 成本的標準差；rlim ← 大範圍
    # 4. 退火
    for round in 0..400:
        for move in 0..max(12n, 2000):
            隨機 cell a，範圍 rlim 內選 (r2, x2)
            plan ← move（有空位）或 swap（雙方可放、同列不重疊）
            套用 plan；增量算 Δ（touched nets + bins）
            if Δ≤0 or rand < e^(−Δ/T): 接受（更新 ncost/cost）
            else: 還原 occ/pos/bins
        rate ← accepted/moves
        T ← 依 rate 四段調整；rlim ← (1 − 0.44 + rate)·rlim
        if T < 0.005·cost/nets: break
    return RowPlacement（pos、pins、history、max_density…）

對照 Rust 原始碼讀，每一段都有對應的行：初始鋪排在 place.rs:170-220、 初始溫度在 :258-264、主迴圈在 :274-334。虛擬碼省略的只有 start.is_some() 時的 temp *= 0.02; rlim = 2.0 精修模式，以及 history 壓縮到 40 個 frame 的收尾。

5.3.8 已知的簡化與它們的後果#

誠實列出本實作相對工業工具的簡化，以及為何在教育語境下可接受：

  • HPWL 而非 Steiner/RSMT：退火階段的線長估計系統性偏低約 10–30%（Steiner 樹有分支節點）；但這是單調偏差，退火只在乎相對 好壞，真正的線長由全域繞線與詳細繞線量測。
  • 無巨集方向旋轉：SRAM 只能 N/FS（列翻轉），不能 90° 轉——教學 設計的巨集少且大，shelf packing 的位置已由面積主導。
  • spill cell 的落點不管線長（:204 的 let _ = spill）：初始解 允許幾顆 cell 隨便落位，退火會立刻把它們搬走；省掉的是「初始解 就完美」的不必要工程。
  • 密度 bin 是懲罰而非硬約束：max_density 可能超過 target （RowPlacement.max_density 記錄實測值）；若超出太多，繞線 probe 會發現並放大 die 重來——硬約束的成本被轉嫁給 5.1 的重試迴圈。

這些簡化共享一個哲學：佈局的最佳化目標不必精確，只要單調； 精確性由下游（繞線、STA）量測，錯了由重試迴圈糾正。

本章重點#

  • 佈局 = 列/site 上的合法化組合問題；move/swap 兩種鄰域動作每步保持合法， 讓退火不需要修復步驟。
  • Metropolis 準則 \(P = e^{-\Delta/T}\) ； \(T_0\) 由 net 成本統計自適應，排程依 實測接受率四段調整（含 <15% 時回升），rlim 同步縮放搜尋範圍。
  • 成本 = Σ weighted HPWL + 密度 bin 線性懲罰；HPWL 是 Steiner 長度下界且 可增量更新（stamp 去重），是退火速度的根基。
  • 時鐘/set-reset 網路排除在退火外，交給 CTS；時序驅動 pass 用 criticality⁸/√fanout 權重，且只在「可繞且更快」時採納。
  • 利用率由 mod.rs 的重試迴圈（probe 失敗 ×0.8、詳細繞線失敗 ×0.85）反覆 餵回退火——佈局與繞線是同一個資源分配問題的兩面。