5.2 佈局與繞線：退火與 PathFinder#

pub fn default_path() -> Option<String> {
    if let Ok(p) = std::env::var("VERYL_EDA_CHIPDB") { return Some(p); }
    let home = std::env::var("HOME").unwrap_or_default();
    let cands = [
        "/opt/homebrew/share/icebox/chipdb-5k.txt".to_string(),
        "/usr/local/share/icebox/chipdb-5k.txt".to_string(),
        "/usr/share/icebox/chipdb-5k.txt".to_string(),
        "/Users/Shared/ccc/oss-cad-suite/share/icebox/chipdb-5k.txt".to_string(),
        format!("{}/oss-cad-suite/share/icebox/chipdb-5k.txt", home),
    ];
    cands.into_iter().find(|p| std::path::Path::new(p).exists())
}

fn bitpos(s: &str) -> R<BitPos> {
    let s = s.strip_prefix('B').ok_or_else(|| format!("bad bit '{}'", s))?;
    let (r, c) = s.split_once('[').ok_or_else(|| format!("bad bit '{}'", s))?;
    let c = c.trim_end_matches(']');
    Ok((r.parse()..., c.parse()...))
}

let pat = p[0].bytes().enumerate().fold(0u32, |a, (i, b)| a | (((b == b'1') as u32) << i));

fn wanted(name: &str) -> bool {
    name.starts_with("lutff_") || name.starts_with("io_") || name.starts_with("glb_netwk_")
        || name == "fabout" || name.starts_with("carry_in") || name.starts_with("ram/")
}

pub struct Pip { pub x: u8, pub y: u8, pub src: u32, pub dst: u32,
                 pub group: u32,  // Chip::groups 的索引
                 pub pat: u32 }   // 該 group 的位元值，位 i = group[i]

pub struct Chip {
    pub w: i32, pub h: i32,
    pub tiles: Vec<((i32,i32), String)>,
    pub tile_type: HashMap<(i32,i32), String>,
    pub dims: HashMap<String, (usize, usize)>,
    pub tile_bits: HashMap<String, HashMap<String, Vec<BitPos>>>,
    pub by_name: HashMap<(i32,i32,String), u32>,
    pub net_box: Vec<(i16,i16,i16,i16)>,
    pub net_label: Vec<(i32,i32,String)>,
    pub kind: Vec<Kind>,
    pub pips: Vec<Pip>,
    pub groups: Vec<Vec<BitPos>>,
    pub fanout: Vec<Vec<u32>>,
    pub pins: HashMap<String, (i32,i32,u8)>,
    ...
}

let hpwl = |n: usize, slot: &Vec<usize>, ram_site: &Vec<usize>| -> f64 {
    let (mut x0, mut y0, mut x1, mut y1) = (i32::MAX, i32::MAX, i32::MIN, i32::MIN);
    for pn in &net_pins[n] {
        let (x, y) = pos(pn, slot, ram_site);
        x0 = x0.min(x); y0 = y0.min(y); x1 = x1.max(x); y1 = y1.max(y);
    }
    if x0 == i32::MAX { 0.0 } else { ((x1 - x0) + (y1 - y0)) as f64 * net_w[n] }
};

// 200 次隨機移動的代價差的標準差，乘 2，下限 1.0
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) * 2.0

let moves_per_t = ((movable.len() + p.rams.len()) as f64).powf(1.33) as usize * 4 + 100;

if delta <= 0.0 || rng.unit() < (-delta / temp).exp() { accept } else { undo }

temp *= if rate > 0.96 { 0.5 } else if rate > 0.8 { 0.9 } else if rate > 0.15 { 0.95 } else { 0.8 };
rlim = (rlim * (1.0 - 0.44 + rate)).clamp(1.0, ncols.max(H) as f64);

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

// 選一個隨機 LC，選一個半徑內的隨機目的地，選目的地 tile 裡 8 個 LC 中的一個
let r = rlim.max(1.0) as i32;
let nci = (ci + rng.below((2*r+1) as usize) as i32 - r).clamp(0, ncols-1);
let ny  = (ay + rng.below((2*r+1) as usize) as i32 - r).clamp(1, H);
let sb  = nci as usize * PER_COL + (ny as usize - 1) * 8 + rng.below(8);

let col_order: Vec<usize> = (0..cols.len())
    .map(|i| if i % 2 == 0 { mid + i/2 } else { mid - 1 - i/2 })
    .filter(|c| *c < cols.len()).collect();

sites.sort_by_key(|&(x,y)| ((y - H/2).abs(), x, y));

pub struct RNet {
    pub name: String,
    pub src: u32,
    pub sinks: Vec<u32>,
    /// 要使用的全域網路：(fabout wire, global wire, 直接從 global 到的 sinks)
    pub global: Option<(u32, u32, Vec<u32>)>,
    pub crit: f32,     // 時序緊要度 0..1
}

for iter in 0..200 {
    for &ni in &order {              // 依 sink 數遞減排序
        // ...
        if iter > 0 && !nodes_of[ni].iter().any(|w| occ[*w as usize] > 1) { continue; }  // 只重繪衝突的網路
        // A* 搜尋
    }
    let over: Vec<usize> = (0..n).filter(|w| occ[w] > 1).collect();
    iters.push(over.len());
    if over.is_empty() { return Ok((routes, iters)); }
    for w in over { hist[w] += 0.5 * (occ[w] - 1) as f32; }
    pres *= 1.8;
}

let over = occ[v as usize] as f32;
let cong = (1.0 + hist[v as usize]) * (1.0 + pres * over);

let mut heap = BinaryHeap::new();
for &t in &tree_order {
    dist[t as usize] = 0.0; prev[t as usize] = u32::MAX; seen[t as usize] = gen;
    heap.push(Item(tdist(t, tx, ty) * 0.3, t));
}
while let Some(Item(_, u)) = heap.pop() {
    if u == sink { found = true; break; }
    let fan = chip.fanout[u as usize].iter().map(|p| (*p, chip.pips[*p as usize].dst))
        .chain(extra_fanout.get(&u).into_iter().flatten().copied());
    for (p, v) in fan {
        let o = owner[v as usize];
        if o >= 0 && o != ni as i32 { continue; }     // 被保留的 wire
        let over = occ[v as usize] as f32;
        let cong = (1.0 + hist[v as usize]) * (1.0 + pres * over);
        let c = if crit > 0.0 {
            let d = super::sta::hop_delay(chip.kind[u as usize], chip.kind[v as usize]) as f32 / 0.6;
            crit * d + (1.0 - crit) * cong
        } else { cong };
        let nd = du + c;
        if seen[v as usize] != gen || nd < dist[v as usize] { ... }
    }
}

// tdist(v, target) × 0.3：目標點到 wire 邊界框的曼哈頓距離

// 網路先被繞到一個 fabout wire，然後用一個偽 pip 代表硬接的
// fabout → glb_netwk_g 連接，全域網路的 sinks 直接由全域 wire 連出
let pip_dst = |p: u32| -> u32 {
    if p >= u32::MAX - extra_pips.len() as u32 { extra_pips[(u32::MAX - p) as usize].1 }
    else { chip.pips[p as usize].dst }
};

// sink 依到 source 的距離排序（近的先），每個用 A* 從目前的樹接上，
// 然後把回溯路徑嫁接進樹

const CLK_Q: f64 = 1.391;                              // clk -> Q
const LUT: [f64; 4]   = [1.285, 1.232, 1.205, 0.874]; // in_k -> out
const SETUP: [f64; 4] = [1.232, 1.060, 0.980, 0.728]; // in_k -> setup
const CARRY_IN1: f64 = 0.675;   // in_1 -> carry
const CARRY_IN2: f64 = 0.609;   // in_2 -> carry
const CARRY_CIN: f64 = 0.278;   // carry-in -> carry-out
const RAM_CLK_Q: f64 = 1.179;   // RCLK -> RDATA
const IO_IN: f64 = 1.105;       // PRE_IO -> DIN0
const IO_OUT: f64 = 0.187;      // 輸出墊

pub fn ram_setup(pin: &str) -> f64 {
    if pin.starts_with("RADDR") { 0.384 } else if pin.starts_with("WADDR") { 0.424 }
    else if pin.starts_with("WDATA") { 0.305 } else if pin.starts_with("MASK") { 0.517 }
    else if pin == "WE" { 0.252 } else if pin == "RE" { 0.185 } else { 0.503 }
}

pub fn hop_delay(src: Kind, dst: Kind) -> f64 {
    let from_lc = src == Kind::LutOut;
    match dst {
        Kind::LutIn     => 0.662,
        Kind::Local     => 1.099,
        Kind::Ctrl      => 0.636,
        Kind::Glb2Local => 0.583,
        Kind::Glb       => 0.278,
        Kind::Sp4H => if from_lc { 0.649 } else { 0.543 },
        Kind::Sp4V => if from_lc { 0.649 } else { 0.596 },
        Kind::Sp12H=> if from_lc { 1.232 } else { 1.231 },
        Kind::Sp12V=> if from_lc { 1.232 } else { 1.072 },
        Kind::Carry => 0.556,
        Kind::Fabout => 0.0,
        Kind::Io     => 0.0,
        Kind::LutOut | Kind::Other => 0.5,
    }
}

// 沿著路徑往回走，產生 Vec<Step>，每個 Step 有
// what（人類可讀的說明）、delay、at（累積時間）

// 後向最長路徑：tail_out[l] = 從 l 的輸出到端點的最長延遲
let net_crit: Vec<f32> = nets.iter().enumerate().map(|(ni, net)| {
    if net.global.is_some() { return 0.0; }
    let src = src_arr(ni, &out_arr);
    let mut worst = 0.0f64;
    for &s in &net.sinks {
        let d = sink_route.get(&s).map(|x| x.1).unwrap_or(0.0);
        let after = match sink_ep(s) { ... };
        worst = worst.max(src + d + after);
    }
    (worst / period).min(1.0) as f32
}).collect();