rhdl_fpga_planner/
layout.rs

1//! Steps 5 and 6: how the budget is split between the sides and, in the
2//! DSig paper, between foreground and background ([`apply_layout`],
3//! [`layout`], [`balance_mix`]); and the build config ([`build_config`]).
4
5use crate::*;
6
7/// How the budget is divided between the two sides, in percent (summing to
8/// at most 100).
9#[derive(Clone, Copy, Debug, PartialEq)]
10pub struct Powers {
11    /// Share of the budget for signing.
12    pub sign: f64,
13    /// Share of the budget for verification.
14    pub verify: f64,
15}
16
17/// The DSig paper's second split: the budget is **foreground** (the HBSS:
18/// DSig sign and DSig verify, divided by [`Powers`]) plus **background**
19/// (EdDSA: the Ed25519 sign and verify modules DSig relies on), and the
20/// background is divided between Ed25519 sign and verify. Each part sums
21/// to 100 %; `None` lets the planner choose ([`layout`]).
22#[derive(Clone, Copy, Debug, Default, PartialEq)]
23pub struct Background {
24    /// EdDSA's % of the budget (the foreground gets the rest).
25    pub share: Option<f64>,
26    /// Ed25519 sign's % of the EdDSA background (verify gets the rest).
27    pub sign: Option<f64>,
28}
29
30/// The background actually used: both values chosen or given.
31#[derive(Clone, Copy, Debug, Default, PartialEq)]
32pub struct BackgroundUsed {
33    /// EdDSA's % of the budget.
34    pub share: f64,
35    /// Ed25519 sign's % of the background.
36    pub sign: f64,
37    /// What the planner would choose for `share` ([`layout`]'s automatic
38    /// value): the EdDSA share the DSig chip actually needs.
39    pub needed_share: f64,
40    /// What it would choose for `sign` at `share`.
41    pub needed_sign: f64,
42}
43
44/// Half and half.
45impl Default for Powers {
46    fn default() -> Self {
47        Powers { sign: 50.0, verify: 50.0 }
48    }
49}
50
51/// The slots of `mode` that work for `side`.
52pub fn side_slots(mode: Mode, side: Side, slots: &[Slot]) -> Vec<usize> {
53    (0..slots.len())
54        .filter(|&k| {
55            let role = slots[k].component.role();
56            slots[k].component.fixed().is_none() && mode.admits(&*slots[k].component) && role.side() == Some(side)
57        })
58        .collect()
59}
60
61/// Set the module powers for `powers` (and, in the DSig paper, the
62/// background `bg`) and plan the chip. Slots outside the mode get 0.
63///
64/// - Ed25519 paper: the sign module gets `powers.sign` %, the verify module
65///   `powers.verify` %.
66/// - DSig paper: EdDSA gets `B` % of the budget and the HBSS foreground
67///   `100 − B`; the foreground is split by `powers`, the background by
68///   `S` (Ed25519 sign) and `100 − S` (Ed25519 verify).
69pub fn apply_powers(mode: Mode, budget: &Budget, cx: &Context, slots: &mut [Slot], powers: Powers) -> ChipPlan {
70    apply_layout(mode, budget, cx, slots, powers, Background::default()).0
71}
72
73/// [`apply_powers`] with the DSig paper's background `bg`; also returns the
74/// background used.
75pub fn apply_layout(
76    mode: Mode,
77    budget: &Budget,
78    cx: &Context,
79    slots: &mut [Slot],
80    powers: Powers,
81    bg: Background,
82) -> (ChipPlan, BackgroundUsed) {
83    let total = powers.sign + powers.verify;
84    let scale = if total > 0.0 { 100.0 / total } else { 0.0 };
85    let powers = Powers {
86        sign: powers.sign * scale,
87        verify: powers.verify * scale,
88    };
89    let used = if mode.paper() == Mode::Dsig {
90        layout_in(mode, budget, cx, slots, powers, bg)
91    } else {
92        BackgroundUsed::default()
93    };
94    set_powers(mode, slots, powers, used.share, used.sign);
95    let plan = plan_chip(mode, budget, cx, slots);
96    // Auto-sized lines remember the size they settled on.
97    for (slot, share) in slots.iter_mut().zip(&plan.guaranteed) {
98        if mode.admits(&*slot.component) && slot.component.size_for(0.0, cx).is_some() {
99            slot.component.resize(*share);
100        }
101    }
102    (plan, used)
103}
104
105/// Module powers from the three splits (the background is ignored in the
106/// Ed25519 paper).
107pub(crate) fn set_powers(mode: Mode, slots: &mut [Slot], powers: Powers, share: f64, sign: f64) {
108    let fg = 100.0 - share;
109    for s in slots.iter_mut() {
110        let role = s.component.role();
111        s.power = match (mode.admits(&*s.component), mode.paper(), role) {
112            (false, _, _) => 0.0,
113            (_, Mode::Ed25519, Role::Ed25519Sign) => powers.sign,
114            (_, Mode::Ed25519, Role::Ed25519Verify) => powers.verify,
115            (_, Mode::Dsig, Role::DsigSign) => fg * powers.sign / 100.0,
116            (_, Mode::Dsig, Role::DsigVerify) => fg * powers.verify / 100.0,
117            (_, Mode::Dsig, Role::Ed25519Sign) => share * sign / 100.0,
118            (_, Mode::Dsig, Role::Ed25519Verify) => share * (100.0 - sign) / 100.0,
119            _ => s.power,
120        };
121    }
122}
123
124/// Quick score of a DSig layout: every module planned in its guaranteed
125/// share (no lending), delivered rates, then `min(sign, verify / mix)`
126/// with ties to the larger total.
127pub(crate) fn quick_score(mode: Mode, budget: &Budget, cx: &Context, slots: &mut [Slot], powers: Powers, share: f64, sign: f64) -> f64 {
128    set_powers(mode, slots, powers, share, sign);
129    let shares = shares_with(budget, slots, &allowances_in(mode, slots));
130    let parts: Vec<(Share, Option<Plan>)> = slots
131        .iter()
132        .zip(&shares)
133        .map(|(slot, sh)| {
134            let on = mode.admits(&*slot.component) && (slot.component.fixed().is_some() || slot.power > 0.0);
135            (*sh, if on { plan_slot(slot, sh, cx) } else { None })
136        })
137        .collect();
138    let d = deliver(mode, cx, slots, &parts);
139    score(d.sign.rate, d.verify.rate, cx.mix)
140}
141
142/// `min(sign, verify / mix)`, ties to the larger total (`mix = 0`: signing).
143pub(crate) fn score(sign: f64, verify: f64, mix: f64) -> f64 {
144    if mix <= 0.0 {
145        sign
146    } else {
147        sign.min(verify / mix) + 1e-3 * (sign + verify / mix)
148    }
149}
150
151/// The best value of `f` over `grid`, refined in `fine` steps around it.
152pub(crate) fn search(grid: &[f64], fine: f64, lo: f64, hi: f64, mut f: impl FnMut(f64) -> f64) -> f64 {
153    let mut best = (f64::MIN, grid[0]);
154    for &x in grid {
155        let v = f(x);
156        if v > best.0 {
157            best = (v, x);
158        }
159    }
160    let center = best.1;
161    for k in [-3.0, -2.0, -1.0, 1.0, 2.0, 3.0] {
162        let x = (center + fine * k).clamp(lo, hi);
163        let v = f(x);
164        if v > best.0 {
165            best = (v, x);
166        }
167    }
168    best.1
169}
170
171/// The DSig paper's background: the given values, or the planner's.
172///
173/// *Automatic:* the EdDSA share and its sign/verify split that deliver the
174/// most for the mix with every module in its guaranteed share. Too little
175/// EdDSA starves the certificates or the cache misses; too much takes area
176/// from the HBSS. The best share is how much EdDSA DSig actually needs at
177/// this budget, best case and batch size, and is shown as "needed".
178pub fn layout(budget: &Budget, cx: &Context, slots: &mut [Slot], powers: Powers, bg: Background) -> BackgroundUsed {
179    layout_in(Mode::Dsig, budget, cx, slots, powers, bg)
180}
181
182/// [`layout`] for a mode that follows the DSig paper (`Mode::UbftDsig`
183/// too).
184pub fn layout_in(mode: Mode, budget: &Budget, cx: &Context, slots: &mut [Slot], powers: Powers, bg: Background) -> BackgroundUsed {
185    // This service contains both certificate cores. Searching an external
186    // EdDSA allocation would reserve area for hardware absent from the replica.
187    // Ignore even a manual background carried over from the generic DSig mode.
188    if mode == Mode::UbftDsig {
189        return BackgroundUsed::default();
190    }
191    let saved: Vec<f64> = slots.iter().map(|s| s.power).collect();
192    let sign_grid: Vec<f64> = (0..=20).map(|k| 5.0 * k as f64).collect();
193    let best_sign = |slots: &mut [Slot], share: f64| {
194        search(&sign_grid, 1.0, 0.0, 100.0, |sg| {
195            quick_score(mode, budget, cx, slots, powers, share, sg)
196        })
197    };
198    let share_grid = [
199        0.5, 1.0, 1.5, 2.0, 3.0, 4.0, 5.0, 6.0, 8.0, 10.0, 12.0, 15.0, 20.0, 25.0, 30.0, 40.0, 50.0, 70.0,
200    ];
201    let rough = search(&share_grid, 0.5, 0.0, 100.0, |sh| {
202        let sg = best_sign(slots, sh);
203        quick_score(mode, budget, cx, slots, powers, sh, sg)
204    });
205    // Refine with the full planner (lending included): modules can borrow
206    // what others leave, so the chip often needs less EdDSA than the quick
207    // score says, and a slice of HBSS can hinge on a few %. Every 0.5 % up
208    // to a little above the rough value; the smallest best one wins.
209    let mut needed_share = rough;
210    let mut best = f64::MIN;
211    let mut sh = 0.5;
212    while sh <= (rough + 2.0).min(100.0) {
213        let sg = best_sign(slots, sh);
214        set_powers(mode, slots, powers, sh, sg);
215        let d = plan_chip(mode, budget, cx, slots).delivered;
216        let v = score(d.sign.rate, d.verify.rate, cx.mix);
217        if v > best * (1.0 + 1e-9) {
218            best = v;
219            needed_share = sh;
220        }
221        sh += 0.5;
222    }
223    let share = bg.share.unwrap_or(needed_share).clamp(0.0, 100.0);
224    let needed_sign = best_sign(slots, share);
225    let sign = bg.sign.unwrap_or(needed_sign).clamp(0.0, 100.0);
226    for (s, p) in slots.iter_mut().zip(saved) {
227        s.power = p;
228    }
229    BackgroundUsed {
230        share,
231        sign,
232        needed_share,
233        needed_sign,
234    }
235}
236
237/// The sign/verify split (summing to 100 %) that maximizes
238/// `min(sign, verify / mix)`: what the B key does. With `mix = 0` only
239/// signing counts. Returns the chosen powers; the slots are left at them.
240///
241/// The search runs the sign power in 4 % steps, then refines around the
242/// best in 1 % and 0.5 % steps.
243pub fn balance_mix(mode: Mode, budget: &Budget, cx: &Context, slots: &mut [Slot]) -> Powers {
244    balance_mix_with(mode, budget, cx, slots, Background::default())
245}
246
247/// [`balance_mix`] with the DSig paper's background `bg` (the powers then
248/// split the HBSS foreground).
249pub fn balance_mix_with(mode: Mode, budget: &Budget, cx: &Context, slots: &mut [Slot], bg: Background) -> Powers {
250    // min(sign, verify / mix); ties (often 0 when the budget cannot hold
251    // both sides) go to the split that delivers more in total.
252    let score = |slots: &mut [Slot], sign: f64| {
253        let p = apply_layout(
254            mode,
255            budget,
256            cx,
257            slots,
258            Powers {
259                sign,
260                verify: 100.0 - sign,
261            },
262            bg,
263        )
264        .0;
265        score(p.delivered.sign.rate, p.delivered.verify.rate, cx.mix)
266    };
267    let mut best = (f64::MIN, 50.0);
268    let try_at = |slots: &mut [Slot], sign: f64, best: &mut (f64, f64)| {
269        let sign = sign.clamp(0.0, 100.0);
270        let s = score(slots, sign);
271        if s > best.0 {
272            *best = (s, sign);
273        }
274    };
275    for step in 0..=25 {
276        try_at(slots, 4.0 * step as f64, &mut best);
277    }
278    for (width, step) in [(3, 1.0), (1, 0.5)] {
279        let center = best.1;
280        for k in -width..=width {
281            if k != 0 {
282                try_at(slots, center + step * k as f64, &mut best);
283            }
284        }
285    }
286    let powers = Powers {
287        sign: best.1,
288        verify: 100.0 - best.1,
289    };
290    apply_layout(mode, budget, cx, slots, powers, bg);
291    powers
292}
293
294/// Every slot's build flags as TOML text, one table per component.
295pub fn build_config(mode: Mode, budget: &Budget, cx: &Context, slots: &[Slot]) -> String {
296    let plan = plan_chip(mode, budget, cx, slots);
297    let d = &plan.delivered;
298    let mut out = format!(
299        "# Written by the chip planner. mode = {:?}; LUT {} %, DSP {} %, BRAM {} %, URAM {} %; mix {}; best case {} %\n\
300         # delivered: {:.3e} {}/s ({}), {:.3e} {}/s ({})\n",
301        mode,
302        budget.lut_percent,
303        budget.dsp_percent,
304        budget.bram_percent,
305        budget.uram_percent,
306        cx.mix,
307        cx.best_case,
308        d.sign.rate,
309        mode.op(Side::Sign),
310        d.sign.bottleneck,
311        d.verify.rate,
312        mode.op(Side::Verify),
313        d.verify.bottleneck
314    );
315    if mode.is_ubft() {
316        use crate::build_apply::{Scheme, UbftBuild};
317        let scheme = if mode == Mode::UbftDsig { Scheme::Dsig } else { Scheme::Ed25519 };
318        let mut selected = UbftBuild {
319            scheme,
320            nodes: 8,
321            window: 3,
322            verify_machines: 1,
323            dsig_slices: 2,
324            dsig_message_bytes: 64,
325            dsig_allow_profile1_ubft: false,
326        };
327        let mut has_replica = false;
328        let mut has_sign = false;
329        let mut has_verify = false;
330        let mut complete = true;
331        let mut shared_dsig_flags = std::collections::BTreeMap::new();
332        for (slot, (_, part)) in slots.iter().zip(&plan.parts) {
333            if !mode.admits(slot.component.as_ref()) {
334                continue;
335            }
336            let role = slot.component.role();
337            let relevant = role == Role::Other
338                || match scheme {
339                    Scheme::Ed25519 => matches!(role, Role::Ed25519Sign | Role::Ed25519Verify),
340                    Scheme::Dsig => matches!(role, Role::DsigSign | Role::DsigVerify),
341                };
342            if !relevant {
343                continue;
344            }
345            let Some(part) = part else {
346                complete = false;
347                continue;
348            };
349            has_sign |= matches!(slot.component.role(), Role::Ed25519Sign | Role::DsigSign);
350            has_verify |= matches!(slot.component.role(), Role::Ed25519Verify | Role::DsigVerify);
351            let flags = slot.component.build_flags(part);
352            if scheme == Scheme::Dsig && matches!(role, Role::DsigSign | Role::DsigVerify) {
353                for required in ["dsig.DSIG_MESSAGE_BYTES", "dsig.allow_profile1_ubft"] {
354                    if !flags.iter().any(|(key, _)| key == required) {
355                        complete = false;
356                    }
357                }
358            }
359            for (key, value) in flags {
360                // A shared UI knob must describe one backend. Never let the
361                // last component silently override a conflicting signer.
362                if matches!(
363                    key.as_str(),
364                    "dsig.DSIG_MESSAGE_BYTES" | "dsig.allow_profile1_ubft" | "dsig.DSIG_SLICES"
365                ) {
366                    if let Some(prior) = shared_dsig_flags.insert(key.clone(), value.clone()) {
367                        if prior != value {
368                            complete = false;
369                        }
370                    }
371                }
372                match key.as_str() {
373                    "RHDL_UBFT_NODES" => {
374                        selected.nodes = value.parse().unwrap_or(0);
375                        has_replica = true;
376                    }
377                    "RHDL_UBFT_WINDOW" => selected.window = value.parse().unwrap_or(0),
378                    "RHDL_UBFT_VERIFY_MACHINES" => selected.verify_machines = value.parse().unwrap_or(0),
379                    "dsig.DSIG_SLICES" => selected.dsig_slices = value.parse().unwrap_or(0),
380                    "dsig.DSIG_MESSAGE_BYTES" => selected.dsig_message_bytes = value.parse().unwrap_or(0),
381                    "dsig.allow_profile1_ubft" => match value.parse::<bool>() {
382                        Ok(allowed) => selected.dsig_allow_profile1_ubft = allowed,
383                        Err(_) => complete = false,
384                    },
385                    "buildable" if value != "true" => complete = false,
386                    _ => {}
387                }
388            }
389        }
390        if scheme == Scheme::Dsig
391            && (!shared_dsig_flags.contains_key("dsig.DSIG_MESSAGE_BYTES") || !shared_dsig_flags.contains_key("dsig.allow_profile1_ubft"))
392        {
393            complete = false;
394        }
395        out.push_str("# Only [rhdl_build] is applied; component tables below describe the model.\n");
396        out.push_str(&selected.toml(complete && has_replica && has_sign && has_verify));
397    }
398    for (slot, (_, p)) in slots.iter().zip(&plan.parts) {
399        let Some(p) = p else { continue };
400        let flags = slot.component.build_flags(p);
401        if flags.is_empty() {
402            continue;
403        }
404        out.push_str(&format!("\n[\"{}\"]\n", slot.component.name()));
405        for (k, v) in flags {
406            out.push_str(&format!("{k} = {v}\n"));
407        }
408    }
409    out
410}
rhdl_fpga_planner/layout.rs

rhdl_fpga_planner/
layout.rs
