rhdl_fpga_planner/

lending.rs

//! Steps 2, 3 and 3b of a plan: best builds, lending and the remainder
//! ([`plan_chip`]).

use crate::*;

/// The planned chip.
#[derive(Clone, Debug, PartialEq)]
pub struct ChipPlan {
    /// Share and plan of each slot, in order (`None`: off or nothing fits).
    /// The share is what the module was finally planned in: its guaranteed
    /// share plus anything it borrowed ([`plan_chip`]).
    pub parts: Vec<(Share, Option<Plan>)>,
    /// Each slot's guaranteed share ([`shares`]).
    pub guaranteed: Vec<Share>,
    /// Everything together.
    pub total: Cost,
    /// Delivered rates.
    pub delivered: Delivered,
}

/// `slot`'s best build in `share`, remembered across calls.
///
/// The balancing searches plan the same module in the same share many
/// times; the key is everything a plan depends on (the component's name
/// and knob values, the share and the workload), so a knob change simply
/// misses the cache.
pub fn plan_slot(slot: &Slot, share: &Share, cx: &Context) -> Option<Plan> {
    use std::{cell::RefCell, collections::HashMap};
    thread_local! {
        static CACHE: RefCell<HashMap<String, Option<Plan>>> = RefCell::new(HashMap::new());
    }
    let c = &slot.component;
    let knobs: Vec<f64> = c.knobs().iter().map(|k| k.value).collect();
    let key = format!("{}|{knobs:?}|{share:?}|{}|{}", c.name(), cx.mhz, cx.best_case);
    if let Some(hit) = CACHE.with(|m| m.borrow().get(&key).cloned()) {
        return hit;
    }
    let plan = c.plan(share, cx);
    CACHE.with(|m| {
        let mut m = m.borrow_mut();
        if m.len() > 200_000 {
            m.clear();
        }
        m.insert(key, plan.clone());
    });
    plan
}

/// The resources of the budget no build in `parts` uses. A fixed line that
/// builds less than its allowance (the SHA-512 line's pipelines come in
/// steps) gives the difference back here.
pub(crate) fn free_pool(budget: &Budget, parts: &[(Share, Option<Plan>)]) -> Share {
    let mut free = budget.chip();
    for (_, plan) in parts {
        if let Some(p) = plan {
            free = Share {
                lut: free.lut.saturating_sub(p.cost.lut),
                dsp: free.dsp.saturating_sub(p.cost.dsp),
                bram36: free.bram36.saturating_sub(p.cost.bram36),
                uram: free.uram.saturating_sub(p.cost.uram),
            };
        }
    }
    free
}

/// How much better `new` is than `old`: the relative gains of the two
/// sides, summed (a side going from zero to something counts as 1).
pub(crate) fn gain(old: &Delivered, new: &Delivered) -> f64 {
    Side::BOTH
        .iter()
        .map(|&s| {
            let (a, b) = (old.side(s).rate, new.side(s).rate);
            if a <= 0.0 { if b > 0.0 { 1.0 } else { 0.0 } } else { (b - a) / a }
        })
        .sum()
}

/// Plan every slot of `mode` and the delivered rates.
///
/// 1. Every module is planned in its guaranteed share ([`shares`]): its
///    power % of each resource.
/// 2. **Lending.** A module rarely uses its share evenly (DSig signing uses
///    almost no DSPs; an Ed25519 verifier may run out of URAM long before
///    its LUTs). What the modules leave unused is counted in real units
///    (LUTs, DSPs, BRAM36, URAM, not percentages), and each module is
///    re-planned in its own build's resources plus what is free. The re-plan
///    that raises the delivered rates the most is kept, and the round
///    repeats until no module gains. First each side lends only within
///    itself (its modules share what the side's guarantee leaves); then
///    whatever is still free, which that side could not use, goes to
///    either side. So a side never loses resources it could have used, and
///    nothing sits idle that the other side could turn into rate.
///
/// **Floors.** A module whose side delivers nothing because its share is
/// smaller than its smallest build gets that build first
/// (`floor_starved`), when that raises the weaker side.
///
/// **Auto-sized lines.** A line whose [`size_for`](Component::size_for)
/// answers (the SHA-512 line on "auto") gets the allowance of its smallest
/// build that supplies what the chip wants ([`Delivered::sha_wanted`]), and
/// the chip is planned again with the engines in what that leaves. A smaller
/// line gives the engines LUTs, which raises what they want, so this repeats
/// (at most four times) until the size settles; of the plans tried, the one
/// the line does not limit, delivering the most, wins.
pub fn plan_chip(mode: Mode, budget: &Budget, cx: &Context, slots: &[Slot]) -> ChipPlan {
    let mut allow = allowances_in(mode, slots);
    let auto: Vec<usize> = (0..slots.len())
        .filter(|&k| mode.admits(&*slots[k].component) && slots[k].component.size_for(0.0, cx).is_some())
        .collect();
    let mut plan = plan_with(mode, budget, cx, slots, &allow);
    floor_starved(mode, budget, cx, slots, &mut allow, &mut plan);
    if auto.is_empty() {
        return plan;
    }
    let rank = |p: &ChipPlan| (!p.delivered.sha_bound, p.delivered.sign.rate.min(p.delivered.verify.rate), p.delivered.sign.rate + p.delivered.verify.rate);
    let mut best = plan.clone();
    for _ in 0..4 {
        // Each auto line supplies its part of what the chip wants.
        let want = plan.delivered.sha_wanted / auto.len() as f64;
        let mut changed = false;
        for &k in &auto {
            let a = slots[k].component.size_for(want, cx);
            if a != allow[k] {
                allow[k] = a;
                changed = true;
            }
        }
        if !changed {
            break;
        }
        plan = plan_with(mode, budget, cx, slots, &allow);
        if rank(&plan).partial_cmp(&rank(&best)) == Some(std::cmp::Ordering::Greater) {
            best = plan.clone();
        }
    }
    best
}

/// **A floor for a starved side.** A side whose guaranteed share is
/// smaller than its smallest build delivers nothing, and lending then hands
/// its unused share to the other side (at 50 % LUTs, DSig verify took 176k
/// while no DSig signer fit in its own ~60k). For each such side this
/// sets aside the smallest build of every starved module on it at once
/// (DSig sign and its certificate signer together), as fixed allowances
/// out of the budget, and plans the rest of the chip in what is left. The floor is
/// kept only if the weaker side then delivers more (and, tied, the sum),
/// the same rank the auto-sized line uses. Modules with manual limits are
/// left as the user capped them.
pub(crate) fn floor_starved(mode: Mode, budget: &Budget, cx: &Context, slots: &[Slot], allow: &mut [Option<Share>], plan: &mut ChipPlan) {
    let rank = |p: &ChipPlan| (p.delivered.sign.rate.min(p.delivered.verify.rate), p.delivered.sign.rate + p.delivered.verify.rate);
    let starved = |k: usize, plan: &ChipPlan, allow: &[Option<Share>]| {
        let slot = &slots[k];
        mode.admits(&*slot.component)
            && allow[k].is_none()
            && slot.power > 0.0
            && slot.limits.iter().all(Option::is_none)
            && plan.parts[k].1.is_none()
            && slot.component.role().side().is_some_and(|side| plan.delivered.side(side).rate <= 0.0)
    };
    // Floor every starved module of one side in a single trial. Why: a side
    // can need two modules (DSig sign and the Ed25519 signer that certifies
    // it), and flooring one at a time never helps, because the side still
    // delivers nothing until both have a build.
    for side in [Side::Sign, Side::Verify] {
        let group: Vec<usize> = (0..slots.len())
            .filter(|&k| starved(k, plan, allow) && slots[k].component.role().side() == Some(side))
            .collect();
        if group.is_empty() {
            continue;
        }
        let mut trial_allow = allow.to_vec();
        let mut ok = true;
        for &k in &group {
            match smallest_build(&slots[k], &budget.rest_with(&trial_allow), cx) {
                Some(floor) => trial_allow[k] = Some(floor),
                None => ok = false,
            }
        }
        if !ok {
            continue;
        }
        let trial = plan_with(mode, budget, cx, slots, &trial_allow);
        if rank(&trial) > rank(plan) {
            allow.copy_from_slice(&trial_allow);
            *plan = trial;
        }
    }
}

/// The cost of `slot`'s build in the smallest uniform fraction of `rest`
/// that still plans one (bisected to 1/4096), or `None` if even all of
/// `rest` plans nothing.
pub(crate) fn smallest_build(slot: &Slot, rest: &Share, cx: &Context) -> Option<Share> {
    let at = |t: f64| Share {
        lut: (rest.lut as f64 * t) as u32,
        dsp: (rest.dsp as f64 * t) as u32,
        bram36: (rest.bram36 as f64 * t) as u32,
        uram: (rest.uram as f64 * t) as u32,
    };
    plan_slot(slot, rest, cx)?;
    let (mut lo, mut hi) = (0.0, 1.0);
    for _ in 0..12 {
        let mid = (lo + hi) / 2.0;
        if plan_slot(slot, &at(mid), cx).is_some() { hi = mid } else { lo = mid }
    }
    plan_slot(slot, &at(hi), cx).map(|p| p.cost)
}

/// [`plan_chip`] with the fixed allowances given per slot.
pub(crate) fn plan_with(mode: Mode, budget: &Budget, cx: &Context, slots: &[Slot], allow: &[Option<Share>]) -> ChipPlan {
    let guaranteed = shares_with(budget, slots, allow);
    let on: Vec<bool> =
        slots.iter().map(|s| mode.admits(&*s.component) && (s.component.fixed().is_some() || s.power > 0.0)).collect();
    let mut parts: Vec<(Share, Option<Plan>)> = slots
        .iter()
        .zip(&guaranteed)
        .zip(&on)
        .map(|((slot, share), &on)| (*share, if on { plan_slot(slot, share, cx) } else { None }))
        .collect();
    let mut delivered = deliver(mode, cx, slots, &parts);
    // What `side`'s modules have left of their guaranteed shares.
    let side_free = |side: Side, parts: &[(Share, Option<Plan>)]| {
        let mut left = Share::default();
        for k in 0..slots.len() {
            if !on[k] || slots[k].component.fixed().is_some() || slots[k].component.role().side() != Some(side) {
                continue;
            }
            let g = guaranteed[k];
            left = left.add(g, 1);
        }
        for k in 0..slots.len() {
            if !on[k] || slots[k].component.fixed().is_some() || slots[k].component.role().side() != Some(side) {
                continue;
            }
            if let Some(p) = &parts[k].1 {
                left = Share {
                    lut: left.lut.saturating_sub(p.cost.lut),
                    dsp: left.dsp.saturating_sub(p.cost.dsp),
                    bram36: left.bram36.saturating_sub(p.cost.bram36),
                    uram: left.uram.saturating_sub(p.cost.uram),
                };
            }
        }
        left
    };
    // Lending rounds; each commits one module's larger build. Phase 0: each
    // side only lends within itself, so it first uses its own share. Phase
    // 1: what is still free (a side could not use it) goes to anyone.
    for phase in 0..2 {
    for _ in 0..8 {
        let global = free_pool(budget, &parts);
        if global == Share::default() {
            break;
        }
        let mut best: Option<(f64, usize, Share, Plan, Delivered)> = None;
        for k in 0..slots.len() {
            // A fixed line (the SHA-512 line) has no side; it borrows in
            // phase 1, from what neither side could use.
            if !on[k] || (phase == 0 && slots[k].component.fixed().is_some()) {
                continue;
            }
            let free = match (phase, slots[k].component.role().side()) {
                (0, Some(side)) => {
                    let f = side_free(side, &parts);
                    Share { lut: f.lut.min(global.lut), dsp: f.dsp.min(global.dsp), bram36: f.bram36.min(global.bram36), uram: f.uram.min(global.uram) }
                }
                _ => global,
            };
            if free == Share::default() {
                continue;
            }
            // Its current build's resources plus everything free. A module
            // with no build starts from nothing: its unused share is already
            // in the free pool (counting it twice once let a plan exceed the
            // budget).
            let base = parts[k].1.as_ref().map_or(Share::default(), |p| p.cost);
            let mut wider = Share {
                lut: base.lut + free.lut,
                dsp: base.dsp + free.dsp,
                bram36: base.bram36 + free.bram36,
                uram: base.uram + free.uram,
            };
            // A manual limit is a hard cap.
            for (i, r) in Resource::ALL.into_iter().enumerate() {
                if slots[k].limits[i].is_some() {
                    wider = r.with(wider, r.of(&guaranteed[k]));
                }
            }
            if wider == base {
                continue;
            }
            let Some(p) = plan_slot(&slots[k], &wider, cx) else { continue };
            if parts[k].1.as_ref().is_some_and(|q| p.rate <= q.rate * (1.0 + 1e-9)) {
                continue;
            }
            let mut trial = parts.clone();
            trial[k] = (wider, Some(p.clone()));
            let d = deliver(mode, cx, slots, &trial);
            let g = gain(&delivered, &d);
            if g > 1e-6 && best.as_ref().is_none_or(|b| g > b.0) {
                best = Some((g, k, wider, p, d));
            }
        }
        let Some((g, k, mut wider, mut p, mut d)) = best else { break };
        // Borrow only what the gain needs: the smallest slice of the free
        // pool (1/16, 1/8, 1/4, 1/2 of it) that gains as much. A helper that
        // needs one more machine should not take every spare LUT.
        let base = parts[k].1.as_ref().map_or(Share::default(), |q| q.cost);
        let room = Share { lut: wider.lut - base.lut, dsp: wider.dsp - base.dsp, bram36: wider.bram36 - base.bram36, uram: wider.uram - base.uram };
        for div in [16u32, 8, 4, 2] {
            let small = Share {
                lut: base.lut + room.lut / div,
                dsp: base.dsp + room.dsp / div,
                bram36: base.bram36 + room.bram36 / div,
                uram: base.uram + room.uram / div,
            };
            let Some(q) = plan_slot(&slots[k], &small, cx) else { continue };
            let mut trial = parts.clone();
            trial[k] = (small, Some(q.clone()));
            let e = deliver(mode, cx, slots, &trial);
            if gain(&delivered, &e) >= 0.999 * g {
                (wider, p, d) = (small, q, e);
                break;
            }
        }
        parts[k] = (wider, Some(p));
        delivered = d;
    }
    }
    fill_remainder(mode, budget, cx, slots, &on, &guaranteed, &mut parts, &mut delivered);
    let total = parts.iter().filter_map(|(_, p)| p.as_ref()).fold(Cost::default(), |a, p| a.add(p.cost, 1));
    ChipPlan { parts, guaranteed, total, delivered }
}

/// `share + extra`, with `slot`'s manual limits as hard caps.
pub(crate) fn widen(slot: &Slot, guaranteed: &Share, share: Share, extra: Share) -> Share {
    let mut wider = share.add(extra, 1);
    for (i, r) in Resource::ALL.into_iter().enumerate() {
        if slot.limits[i].is_some() {
            wider = r.with(wider, r.of(guaranteed));
        }
    }
    wider
}

/// Neither side delivers less in `new` than in `old`.
pub(crate) fn no_side_drops(old: &Delivered, new: &Delivered) -> bool {
    Side::BOTH.iter().all(|&s| new.side(s).rate >= old.side(s).rate * (1.0 - 1e-9))
}

/// 3. **The remainder.** Lending hands out only what raises the delivered
/// rates. Whatever is still free after it could not raise them (the
/// bottleneck is elsewhere, or a build step is too coarse), but it can still
/// make modules faster: a background Ed25519 module with DSig's unused DSPs
/// has headroom for bursts and for a worse best case. So it is not left
/// idle:
///
/// - **Pro rata.** Each module of the paper, the SHA-512 line included, is
///   offered its pro-rata slice of each free resource (in proportion to its
///   guaranteed share of that resource) on top of its build, and keeps a
///   larger build if its capacity rises.
/// - **Greedy.** If no pro-rata slice buys anything (one more core or
///   slice costs more than the slice), modules in descending guaranteed
///   LUTs may take the whole pool. The SHA-512 line grows this way, up to
///   its largest build, when the engines cannot use the LUTs.
///
/// A step is kept only if no side delivers less (through the SHA-512 line,
/// one side's growth could take blocks from the other). Rounds repeat until
/// nothing grows, at most 6.
#[allow(clippy::too_many_arguments)]
pub(crate) fn fill_remainder(
    mode: Mode,
    budget: &Budget,
    cx: &Context,
    slots: &[Slot],
    on: &[bool],
    guaranteed: &[Share],
    parts: &mut [(Share, Option<Plan>)],
    delivered: &mut Delivered,
) {
    let mut order: Vec<usize> =
        (0..slots.len()).filter(|&k| on[k] && (slots[k].component.fixed().is_some() || slots[k].power > 0.0)).collect();
    order.sort_by(|&a, &b| guaranteed[b].lut.cmp(&guaranteed[a].lut));
    // Each resource's guaranteed total over these modules (the pro-rata
    // denominators).
    let mut total = Share::default();
    for &k in &order {
        total = total.add(guaranteed[k], 1);
    }
    let part = |free: u32, mine: u32, all: u32| if all == 0 { 0 } else { (free as f64 * mine as f64 / all as f64) as u32 };
    // Try `k` in `share`; keep it if its capacity rises and no side drops.
    let try_grow = |k: usize, share: Share, parts: &mut [(Share, Option<Plan>)], delivered: &mut Delivered| -> bool {
        let Some(p) = plan_slot(&slots[k], &share, cx) else { return false };
        if parts[k].1.as_ref().is_some_and(|q| p.rate <= q.rate * (1.0 + 1e-9)) {
            return false;
        }
        let old = std::mem::replace(&mut parts[k], (share, Some(p)));
        let d = deliver(mode, cx, slots, parts);
        if no_side_drops(delivered, &d) {
            *delivered = d;
            true
        } else {
            parts[k] = old;
            false
        }
    };
    for _ in 0..6 {
        let free = free_pool(budget, parts);
        if free == Share::default() {
            return;
        }
        let mut grew = false;
        for &k in &order {
            let g = guaranteed[k];
            let slice = Share {
                lut: part(free.lut, g.lut, total.lut),
                dsp: part(free.dsp, g.dsp, total.dsp),
                bram36: part(free.bram36, g.bram36, total.bram36),
                uram: part(free.uram, g.uram, total.uram),
            };
            let base = parts[k].1.as_ref().map_or(Share::default(), |p| p.cost);
            let wider = widen(&slots[k], &guaranteed[k], base, slice);
            if wider != base {
                grew |= try_grow(k, wider, parts, delivered);
            }
        }
        if !grew {
            for &k in &order {
                let free = free_pool(budget, parts);
                let base = parts[k].1.as_ref().map_or(Share::default(), |p| p.cost);
                let wider = widen(&slots[k], &guaranteed[k], base, free);
                if wider != base && try_grow(k, wider, parts, delivered) {
                    grew = true;
                    break;
                }
            }
        }
        if !grew {
            return;
        }
    }
}