5.4 全域繞線#

// veryl-eda/src/asic/route.rs
/// tracks per gcell edge and direction: two layers × 10 tracks
pub const CAP: u16 = 12;

// gcells: one row高、TRACKS 列寬
let (gw, gh) = (super::detail::TRACKS as f64 * tech.site_w, tech.row_h);
// tracks per gcell edge and direction (80 % of what the layers hold): vlib CAP;
// SKY130 horizontal met1 (6 free of 8) + met3 (4), vertical met2 (8) + met4 (4)
let (cap_h, cap_v) = if tech.is_vlib() { (CAP, CAP) } else { (6u16, 8u16) };
let gx = ((pl.w / gw).ceil() as u32).max(1);
let gy = pl.rows.max(1);

// Prim order of each net's terminals: (terminal, its tree parent)
let md = |a: u32, b: u32| (a % gx).abs_diff(b % gx) + (a / gx).abs_diff(b / gx);
let prim: Vec<Vec<(u32, u32)>> = terms.iter().map(|(_, t, _)| {
    ...
    let mut done = vec![false; k];
    let mut best: Vec<(u32, usize)> = (0..k).map(|i| (md(t[0], t[i]), 0)).collect();
    done[0] = true;
    for _ in 1..k {
        let (j, _) = (0..k).filter(|&i| !done[i]).map(|i| (i, best[i].0)).min_by_key(|x| x.1).unwrap();
        done[j] = true;
        out.push((t[j], t[best[j].1]));
        for i in 0..k { if !done[i] { let d = md(t[j], t[i]); if d < best[i].0 { best[i] = (d, j); } } }
    }
    out
}).collect();

let pts: Vec<(u32, u32)> = if dims[c].1 > 1 {
    nl.cells[c].conns.iter().enumerate().filter(|(_, x)| x.1 == p.bit).map(|(k, _)| {
        let (x, y) = super::detail::pin_point(nl, pl, c, k);
        ((x / super::detail::TRACKS).min(gx - 1), (y / super::detail::TRACKS).min(gy - 1))
    }).collect()
} else { vec![gcell_of_cell(c)] };

while let Some(Item(_, u)) = heap.pop() {
    if in_tree[u as usize] == mark { goal = u; break; }
    ...
    for v in nb {
        let (h, e) = edge(u, v);
        let (us, hi) = if h { (use_h[e], hist_h[e]) } else { (use_v[e], hist_v[e]) };
        let over = (us + 1).saturating_sub(if h { cap_h } else { cap_v }) as f32;
        let nd = du + (1.0 + hi) * (1.0 + pres * over);
        ...
    }
}

for it in 0..max_iters {
    for &ni in &order {
        ...
        if it > 0 {
            // 只重繞目前有觸到超載邊的 net（省時）
            let over = trees[ni].iter().any(|&(a, b)| { ... use > cap ... });
            if !over { continue; }
        }
        // rip-up：先把這條 net 從所有邊的計數中拿掉
        for &(a, b) in &trees[ni] { let (h, e) = edge(a, b); if h { use_h[e] -= 1 } else { use_v[e] -= 1 } }
        trees[ni].clear();
        ... Prim 順序逐終端 A* ...
        // 重新計入
        for &(a, b) in &trees[ni] { let (h, e) = edge(a, b); if h { use_h[e] += 1 } else { use_v[e] += 1 } }
    }
    let mut over = 0u32;
    for e in 0..ne {
        if use_h[e] > cap_h { over += (use_h[e] - cap_h) as u32; hist_h[e] += 0.5; }
        if use_v[e] > cap_v { over += (use_v[e] - cap_v) as u32; hist_v[e] += 0.5; }
    }
    iters.push(over);
    if over == 0 { break; }
    pres *= 1.6;
}

/// horizontal wires on M2/M4, vertical wires on M3/M5
/// horizontal edge h(x,y) between (x,y)-(x+1,y); vertical v(x,y) between (x,y)-(x,y+1)

let turns = dirs.values().filter(|d| d.0 && d.1).count() as u32;
let v = turns + npins;   // 轉彎 via + 每個 cell pin 一顆 M1 via

pub struct Routing {
    ...
    pub iters: Vec<u32>,    // 每輪結束的總 overflow（收斂曲線）
    pub wirelength: f64,
    pub vias: u32,
    pub overflow: u32,      // 最後一輪的 overflow；0 = 成功
    pub demand: f64,        // 邊的平均使用率 / (cap_h + cap_v)
}

global_route(nl, placement, max_iters):
    建 gcell 網格（gx × gy），每邊容量 cap_h / cap_v
    收集每 net 的終端 gcell（巨集用 pin_point、IO pin 用邊上 gcell）
    每 net 算 Prim（MST）加入順序
    net 依端點數升序排（小 net 先定案）
    for it in 0..max_iters:
        for net in 排序後的 nets:
            if it > 0 and net 沒踩到超載邊: continue     # 只重繞受害者
            rip-up：從 use_h/use_v 扣掉自己的所有邊
            in_tree ← {起點}
            for (src, parent) in prim_order:
                A*：cost(e) = (1+hist[e])·(1+pres·max(0, use−cap))
                    goal = 任何 in_tree 節點（早停）
                把路徑併入樹、計入 use
        over ← Σ 邊的 max(0, use − cap)
        iters.push(over)
        if over == 0: break
        超載邊 hist += 0.5；pres ×= 1.6
    輸出：每 net 的 gcell 段、線長、via（轉彎 + pin 數）