rhdl_ed25519_scalable_core/frontier/

pareto.rs

//! The sign / verify frontier on the whole device ([`frontier`]): every build
//! that fits, keeping the non-dominated pairs.

use super::*;

/// How a module's blocks are proportioned, set from the TUI.
#[derive(Clone, Copy, Debug, PartialEq)]
pub struct Shape {
    /// `None`: the planner picks the best mix. `Some([machines, sha, sc])`:
    /// field machines : SHA-512 rings : scalar rings are kept in this ratio
    /// (rounded, at least one each), and only the size is searched. The SHA
    /// weight is ignored on the shared SHA-512 line (no rings).
    pub ratio: Option<[f64; 3]>,
    /// Batch compression (one compress machine inverting and encoding 32
    /// points at a time).
    pub compress: Compress,
}

/// Whether a module uses a batch-compress machine.
#[derive(Clone, Copy, Debug, PartialEq, Eq, Default)]
pub enum Compress {
    /// Both kinds of build are tried.
    #[default]
    Auto,
    /// Only builds with a compress machine.
    On,
    /// Only builds without one: each field machine inverts and encodes its
    /// own point (a longer program: [`crate::config::FUSED_BUNDLES`] for
    /// signing, the same extra bundles for verification).
    Off,
}

impl Compress {
    /// Whether builds with (`true`) or without a compress machine are tried.
    pub fn allows(self, with: bool) -> bool {
        match self {
            Compress::Auto => true,
            Compress::On => with,
            Compress::Off => !with,
        }
    }
}

impl Default for Shape {
    /// The planner chooses everything.
    fn default() -> Self {
        Shape { ratio: None, compress: Compress::Auto }
    }
}

impl Shape {
    /// Whether `(machines, sha, sc)` keeps the ratio (`sha` is not checked
    /// when `shared_sha`).
    pub(super) fn keeps(&self, machines: u32, sha: u32, sc: u32, shared_sha: bool) -> bool {
        let Some([m, h, r]) = self.ratio else { return true };
        let want = |w: f64| ((machines as f64 * w / m.max(1e-9)).round() as u32).max(1);
        sc == want(r) && (shared_sha || sha == want(h))
    }
}

/// Extra field-machine bundles per verification without a compress
/// machine: the per-point inversion and encoding, as in signing
/// (`FUSED_BUNDLES - FB_BUNDLES`).
pub const VERIFY_FUSED_EXTRA: u32 = crate::config::FUSED_BUNDLES - FB_BUNDLES;

/// One point: a sign build, a verify build, their rates and total cost.
#[derive(Clone, Copy, Debug)]
pub struct Point {
    /// Signing build (`None`: no signer).
    pub sign: Option<Profile>,
    /// Verify build (`None`: no verifier).
    pub verify: Option<VerifyProfile>,
    /// Signatures per second.
    pub signs_per_sec: f64,
    /// Verifications per second.
    pub verifies_per_sec: f64,
    /// Total resources.
    pub cost: Cost,
}

/// Every non-fused signing build that fits the device on its own, with its
/// rate (signatures/s) and cost, thinned by [`pareto_by`].
pub(super) fn sign_options(c: &Costs, d: &Device) -> Vec<(Profile, f64, Cost)> {
    let mut out = Vec::new();
    // Search ranges: up to 24 fixed-base machines, 16 SHA rings, 5 scalar
    // rings. Fused profiles are not considered.
    for fb in 1..=24 {
        for sha in 1..=16 {
            for sc in 1..=5 {
                let p = Profile { fb, sha, sc, fused: false };
                let cost = sign_cost_within(&p, c, &d.share(), 0);
                if !cost.fits(d) {
                    continue;
                }
                // Clock (Hz) divided by modeled cycles per signature.
                let rate = d.mhz * 1e6 / p.cycles_per_sign().0;
                out.push((p, rate, cost));
            }
        }
    }
    pareto_by(out, |x| (x.1, x.2))
}

/// Every verify build in `mode` that fits the device on its own, with its
/// rate (verifications/s) and cost, thinned by [`pareto_by`].
pub(super) fn verify_options(mode: VerifyMode, c: &Costs, d: &Device) -> Vec<(VerifyProfile, f64, Cost)> {
    let mut out = Vec::new();
    // Search ranges: up to 40 machines, 12 SHA rings, 3 scalar rings; always
    // one compress machine.
    for machines in 1..=40 {
        for sha in 1..=12 {
            for sc in 1..=3 {
                let v = VerifyProfile { machines, sha, sc, cp: 1 };
                let cost = verify_cost_within(&v, mode, c, &d.share(), 0);
                if !cost.fits(d) {
                    continue;
                }
                out.push((v, d.mhz * 1e6 / v.cycles(mode), cost));
            }
        }
    }
    pareto_by(out, |x| (x.1, x.2))
}

/// Keep, for each rate, only builds that no cheaper build beats. "Cheaper"
/// means fewer LUTs only; DSP, BRAM and URAM do not take part in the order.
/// `key` returns `(rate, cost)` of an item.
pub(super) fn pareto_by<T: Copy>(mut items: Vec<T>, key: impl Fn(&T) -> (f64, Cost)) -> Vec<T> {
    // Ascending LUT, so each kept item is the cheapest one reaching its rate.
    items.sort_by(|a, b| key(a).1.lut.cmp(&key(b).1.lut));
    // Highest rate kept so far.
    let mut best = -1.0;
    let mut out = Vec::new();
    for item in items {
        let (rate, _) = key(&item);
        // Keep only items that are faster than every cheaper item by more
        // than 1 operation/s (the margin ignores floating-point ties).
        if rate > best + 1.0 {
            best = rate;
            out.push(item);
        }
    }
    out
}

/// The frontier for one verification mode: for each signing rate, the best
/// verification rate that still fits, keeping only non-dominated points.
/// Includes sign-only and verify-only points. Sorted by descending signing
/// rate.
pub fn frontier(mode: VerifyMode, c: &Costs, d: &Device) -> Vec<Point> {
    let signs = sign_options(c, d);
    let verifies = verify_options(mode, c, d);
    let mut points = Vec::new();
    // Verify only and sign only.
    for (v, rate, cost) in &verifies {
        points.push(Point { sign: None, verify: Some(*v), signs_per_sec: 0.0, verifies_per_sec: *rate, cost: *cost });
    }
    for (p, s_rate, s_cost) in &signs {
        points.push(Point { sign: Some(*p), verify: None, signs_per_sec: *s_rate, verifies_per_sec: 0.0, cost: *s_cost });
        // Every pair of a sign build and a verify build whose combined cost
        // fits the device.
        for (v, v_rate, v_cost) in &verifies {
            let total = Cost::default().add(*s_cost, 1).add(*v_cost, 1);
            if total.fits(d) {
                points.push(Point {
                    sign: Some(*p),
                    verify: Some(*v),
                    signs_per_sec: *s_rate,
                    verifies_per_sec: *v_rate,
                    cost: total,
                });
            }
        }
    }
    // Non-dominated set, ordered by signing rate.
    // Walking from the fastest signer down, a point is kept only if its
    // verification rate beats every faster-signing point by more than 1/s.
    points.sort_by(|a, b| b.signs_per_sec.partial_cmp(&a.signs_per_sec).unwrap());
    let mut front: Vec<Point> = Vec::new();
    let mut best_verify = -1.0;
    for p in points {
        if p.verifies_per_sec > best_verify + 1.0 {
            best_verify = p.verifies_per_sec;
            front.push(p);
        }
    }
    front
}

/// Best verification rate at or above a signing rate: the frontier point
/// with the highest verifications/s among those with at least `min_signs`
/// signatures/s. `None` if no point reaches `min_signs`.
pub fn best_verify_at(front: &[Point], min_signs: f64) -> Option<Point> {
    front
        .iter()
        .filter(|p| p.signs_per_sec >= min_signs)
        .max_by(|a, b| a.verifies_per_sec.partial_cmp(&b.verifies_per_sec).unwrap())
        .copied()
}