rhdl_ed25519_scalable_core/frontier/
placement.rs

1//! Packing blocks into a share: each block's memory layouts, tried in order,
2//! and how many machines of each layout fit.
3
4use super::*;
5
6/// Some instances of one block and the memory layouts it can be built in,
7/// most preferred first.
8pub(super) struct Block {
9    /// Instances.
10    count: u32,
11    /// Cost of one instance in each layout.
12    layouts: Vec<Cost>,
13}
14
15/// How far `c` is over `limit`: the summed relative overshoot of every
16/// resource (0 when it fits).
17pub(super) fn overflow(c: &Cost, limit: &Share) -> f64 {
18    let over = |used: u32, cap: u32| if used > cap { (used - cap) as f64 / cap.max(1) as f64 } else { 0.0 };
19    over(c.lut, limit.lut) + over(c.dsp, limit.dsp) + over(c.bram36, limit.bram36) + over(c.uram, limit.uram)
20}
21
22/// The cost of `blocks` with each instance's memory layout chosen to fit
23/// `limit`: every instance starts in its preferred layout; while the total
24/// does not fit, one instance moves to whichever other layout shrinks the
25/// overflow most (UltraRAM to block RAM when URAM runs out, banks to LUT
26/// RAM when block RAM runs out too). Returns the total, which does not fit
27/// `limit` if no placement does.
28///
29/// *Why greedy:* each move relieves the resource that is over without
30/// pushing another one over, so it finds a fit when one exists for these
31/// cost tables (layouts differ in one or two resources), in at most one
32/// move per instance and layout.
33pub(super) fn place(blocks: &[Block], limit: &Share) -> Cost {
34    place_counts(blocks, limit).0
35}
36
37/// [`place`], also returning how many instances of each block ended up in
38/// each of its layouts.
39pub(super) fn place_counts(blocks: &[Block], limit: &Share) -> (Cost, Vec<Vec<u32>>) {
40    // Instances of each block in each layout.
41    let mut counts: Vec<Vec<u32>> = blocks.iter().map(|b| {
42        let mut c = vec![0; b.layouts.len()];
43        c[0] = b.count;
44        c
45    }).collect();
46    let mut total = blocks.iter().fold(Cost::default(), |t, b| t.add(b.layouts[0], b.count));
47    if fits(&total, limit) {
48        return (total, counts);
49    }
50    // Quick reject: even the cheapest layout of every block, resource by
51    // resource, is over.
52    let floor = |f: fn(&Cost) -> u32| blocks.iter().map(|b| b.count * b.layouts.iter().map(f).min().unwrap_or(0)).sum::<u32>();
53    if floor(|c| c.lut) > limit.lut || floor(|c| c.dsp) > limit.dsp || floor(|c| c.bram36) > limit.bram36 || floor(|c| c.uram) > limit.uram {
54        return (total, counts);
55    }
56    let sub = |t: Cost, c: Cost| Cost { lut: t.lut - c.lut, dsp: t.dsp - c.dsp, bram36: t.bram36 - c.bram36, uram: t.uram - c.uram };
57    loop {
58        let now = overflow(&total, limit);
59        if now == 0.0 {
60            return (total, counts);
61        }
62        // The single move that leaves the least overflow.
63        let mut best: Option<(f64, usize, usize, usize)> = None;
64        for (i, b) in blocks.iter().enumerate() {
65            for from in 0..b.layouts.len() {
66                if counts[i][from] == 0 {
67                    continue;
68                }
69                for to in 0..b.layouts.len() {
70                    if to == from {
71                        continue;
72                    }
73                    let t = sub(total, b.layouts[from]).add(b.layouts[to], 1);
74                    let o = overflow(&t, limit);
75                    if o < now - 1e-12 && best.is_none_or(|x| o < x.0) {
76                        best = Some((o, i, from, to));
77                    }
78                }
79            }
80        }
81        let Some((_, i, from, to)) = best else { return (total, counts) };
82        counts[i][from] -= 1;
83        counts[i][to] += 1;
84        total = sub(total, blocks[i].layouts[from]).add(blocks[i].layouts[to], 1);
85    }
86}
87
88/// The layouts a block may use: its own cost, then (specialized table
89/// only) the block-RAM layout, banks in LUT RAM, and everything in block
90/// RAM.
91pub(super) fn options(c: &Costs, own: Cost, bram: impl Fn(&BramLayout) -> Cost, machine: bool) -> Vec<Cost> {
92    // Only layouts the RTL can build: a core's replicated machines are
93    // built per instance in UltraRAM or in the block-RAM fallback
94    // (`machine::machine_with_placement`, `ED25519_URAM_MACHINES`); every
95    // other block in its one layout. Machines: UltraRAM, LUT-RAM banks or
96    // block-RAM banks (`MachineMemory::{SPECIALIZED, LUT_BANKS,
97    // BRAM_BANKS}`), in that order. Moving other memories to block RAM is
98    // not built, so it is not offered.
99    match (c.bram_layout, machine) {
100        (Some(alt), true) => vec![own, lut_banks(own), bram(&alt)],
101        _ => vec![own],
102    }
103}
104
105/// Layouts of a block with no block-RAM variant of its own (controllers):
106/// its one built layout.
107pub(super) fn plain(_c: &Costs, own: Cost) -> Vec<Cost> {
108    vec![own]
109}
110
111/// The signing build's cost with the memory layouts placed to fit `limit`
112/// (see `place`); `extra_lut` (the shared-SHA client port) is part of
113/// the build and counted in the fit.
114pub fn sign_cost_within(p: &Profile, c: &Costs, limit: &Share, extra_lut: u32) -> Cost {
115    place(&sign_blocks(p, c, extra_lut), limit)
116}
117
118/// The blocks of a signing build; the fixed-base machines are index 4.
119pub(super) fn sign_blocks(p: &Profile, c: &Costs, extra_lut: u32) -> Vec<Block> {
120    vec![
121        Block { count: 1, layouts: vec![Cost { lut: extra_lut, ..Cost::default() }] },
122        Block { count: p.sha, layouts: vec![c.sha_ring] },
123        Block { count: p.sc, layouts: vec![c.scalar_ring] },
124        Block { count: 1, layouts: plain(c, if p.fused { c.sign_controller_fused } else { c.sign_controller }) },
125        Block { count: p.fb, layouts: options(c, c.fb_machine, |a| a.fb_machine, true) },
126        Block { count: u32::from(!p.fused), layouts: options(c, c.cp_machine, |a| a.cp_machine, false) },
127    ]
128}
129
130/// Where a signing build's fixed-base machines go within `limit`: how many
131/// in UltraRAM, LUT-RAM banks and block-RAM banks.
132pub fn sign_placement(p: &Profile, c: &Costs, limit: &Share, extra_lut: u32) -> [u32; 3] {
133    let (_, counts) = place_counts(&sign_blocks(p, c, extra_lut), limit);
134    machine_counts(&counts[4], p.fb)
135}
136
137/// Where a verify build's verify machines go within `limit` (as
138/// [`sign_placement`]).
139pub fn verify_placement(v: &VerifyProfile, mode: VerifyMode, c: &Costs, limit: &Share, extra_lut: u32) -> [u32; 3] {
140    let (_, counts) = place_counts(&verify_blocks(v, mode, c, extra_lut), limit);
141    machine_counts(&counts[5], v.machines)
142}
143
144/// A signing build's cost with its fixed-base machines in exactly the
145/// layouts `machines` = `[uram, lut, bram]` (`ED25519_URAM_MACHINES`,
146/// `ED25519_LUT_MACHINES`), for comparing a built design with the table.
147pub fn sign_cost_placed(p: &Profile, c: &Costs, extra_lut: u32, machines: [u32; 3]) -> Cost {
148    placed(&sign_blocks(p, c, extra_lut), 4, machines)
149}
150
151/// A verify build's cost with its verify machines in exactly the layouts
152/// `machines` (as [`sign_cost_placed`]).
153pub fn verify_cost_placed(v: &VerifyProfile, mode: VerifyMode, c: &Costs, extra_lut: u32, machines: [u32; 3]) -> Cost {
154    placed(&verify_blocks(v, mode, c, extra_lut), 5, machines)
155}
156
157/// The cost of `blocks` with block `at` split over its layouts as
158/// `machines` and every other block in its preferred layout.
159pub(super) fn placed(blocks: &[Block], at: usize, machines: [u32; 3]) -> Cost {
160    blocks.iter().enumerate().fold(Cost::default(), |t, (i, b)| {
161        if i == at && b.layouts.len() == 3 {
162            (0..3).fold(t, |t, k| t.add(b.layouts[k], machines[k]))
163        } else {
164            t.add(b.layouts[0], b.count)
165        }
166    })
167}
168
169/// A machine block's layout counts as `[uram, lut, bram]` (a cost table
170/// without a fallback has the first only).
171pub(super) fn machine_counts(c: &[u32], n: u32) -> [u32; 3] {
172    match c {
173        [u, l, b] => [*u, *l, *b],
174        _ => [n, 0, 0],
175    }
176}
177
178/// A verify build's cost with the memory layouts placed to fit `limit`.
179pub fn verify_cost_within(v: &VerifyProfile, mode: VerifyMode, c: &Costs, limit: &Share, extra_lut: u32) -> Cost {
180    place(&verify_blocks(v, mode, c, extra_lut), limit)
181}
182
183/// The blocks of a verify build; the verify machines are index 5.
184pub(super) fn verify_blocks(v: &VerifyProfile, mode: VerifyMode, c: &Costs, extra_lut: u32) -> Vec<Block> {
185    let machine = options(
186        c,
187        mode.machine(c),
188        |a| match mode {
189            VerifyMode::Strict | VerifyMode::Batch => a.verify_machine_strict,
190            VerifyMode::KnownKey => a.verify_machine_known_key,
191        },
192        true,
193    );
194    vec![
195        Block { count: 1, layouts: vec![Cost { lut: extra_lut, ..Cost::default() }] },
196        Block { count: v.sha, layouts: vec![c.sha_ring] },
197        Block { count: v.sc, layouts: vec![c.verify_scalar_ring] },
198        Block { count: 1, layouts: plain(c, c.verify_controller) },
199        Block { count: u32::from(mode == VerifyMode::KnownKey), layouts: options(c, c.key_loader, |a| a.key_loader, false) },
200        Block { count: v.machines, layouts: machine },
201        Block { count: v.cp, layouts: options(c, c.cp_machine, |a| a.cp_machine, false) },
202    ]
203}
rhdl_ed25519_scalable_core/frontier/placement.rs

rhdl_ed25519_scalable_core/frontier/
placement.rs
