rhdl_sha512_pipelined/
planner.rs

1//! The shared SHA-512 line as a component of the chip planner/TUI.
2//!
3//! The line supplies `"sha512 blocks"` to every client on it (Ed25519 sign
4//! and verify). DSig's chain lanes do not use it; they carry their own
5//! hashers. Its allowance comes out of the chip budget before the signature
6//! engines share the rest (the SHA part of the LUT split).
7//!
8//! # What a line is made of
9//!
10//! **One core.** The clients' arbiter (`rhdl_ed25519_scalable_core::
11//! sha_client`) feeds a single in-order core, so a line is one of:
12//!
13//! | Core | Blocks/clock | LUT (routed) |
14//! |---|---|---|
15//! | [`Sha512Pipeline`](crate::Sha512Pipeline), 80 stages | 1 | [`FULL_LUT`] = 62,252 |
16//! | [`Sha512Folded40`](crate::folded::Sha512Folded40) | ½ | 40,047 |
17//! | `Sha512Folded20`, `16`, `10`, `8`, `5`, `4` | `S / 80` | 20,880, 16,887, 11,295, 9,431, 6,778, 5,851 |
18//! | [`Sha512Folded2`](crate::folded::Sha512Folded2) | 1/40 | 3,509 |
19//!
20//! ([`ROUTED_LUT`].) The smallest line hashes 5.1M blocks per second,
21//! enough for about 1.7M Ed25519 signatures. [`fastest`] picks the core
22//! that hashes the most in a LUT budget; [`smallest`] the cheapest core
23//! that hashes a given rate (a full pipeline when nothing is enough).
24//!
25//! # How big: auto or by hand
26//!
27//! | Knob | Range | Default |
28//! |---|---|---|
29//! | LUT cap | 0 – 432,000 ([`SHA_LINE_MAX_LUT`]) | 65,000 (manual: a full pipeline, 1 block/clock) |
30//! | DSP cap | 0 – 20 | 20 |
31//! | size | auto / manual | **auto** |
32//!
33//! - **Auto** (the default): *the line never limits the chip.* The planner
34//!   asks the line for the smallest build that hashes what the engines want
35//!   ([`Component::size_for`]), gives the engines what that leaves, and
36//!   repeats until the size settles (`rhdl_fpga_planner::plan_chip`). The
37//!   LUT cap then shows the size it settled on.
38//! - **Manual**: the LUT cap is the line's guaranteed allowance (moving it,
39//!   or the TUI's LUT split row, switches to manual). The planner can still
40//!   lend the line LUTs nobody else uses, and it grows past the cap up to
41//!   [`LARGEST_LINE_LUT`] (one full pipeline). A cap of 0 means no line.
42//!
43//! The LUT costs are **routed out of context** (Vivado 2023.2, 4.878 ns =
44//! 205 MHz, every core with positive slack, +0.59 to +1.17 ns;
45//! 2026-10-16/17), not in-chip: a placed chip can differ. The rates are
46//! the cores' design rates (`S / 80`, one block per clock for the
47//! pipeline), checked in native simulation. The earlier Yosys estimates
48//! (87,178 for the pipeline, `folded::folded_lut`) were 20-40 % high.
49
50use rhdl_fpga_planner::{BuildFlags, Component, Context, Cost, Flow, Knob, Plan, Role, SHA512_BLOCKS, Share};
51
52pub use crate::folded::folded_lut;
53use crate::folded::FOLDS;
54
55/// The default LUT allowance of a manual line.
56pub const SHA_LINE_LUT: u32 = 65_000;
57/// Largest LUT allowance the knob takes (about five full pipelines). A
58/// bigger allowance takes LUTs from the engines (the LUT split).
59pub const SHA_LINE_MAX_LUT: u32 = 432_000;
60/// Default and largest DSP allowance of the line.
61pub const SHA_LINE_DSP: u32 = 20;
62/// LUTs of one full pipeline, routed out of context at 4.878 ns (WNS
63/// +0.638 ns). Yosys estimated 87,178.
64pub const FULL_LUT: u32 = 62_252;
65/// Routed out-of-context LUTs of each folded core, `(stages, LUT)`, at
66/// 4.878 ns (Vivado 2023.2, 2026-10-16/17; WNS +0.59 to +1.17 ns).
67pub const ROUTED_LUT: [(u32, u32); 8] =
68    [(2, 3_509), (4, 5_851), (5, 6_778), (8, 9_431), (10, 11_295), (16, 16_887), (20, 20_880), (40, 40_047)];
69/// The largest line: one full pipeline, 1 block per clock (the arbiter
70/// drives one core).
71pub const LARGEST_LINE_LUT: u32 = FULL_LUT;
72/// Latency of every core in cycles (the folded cores match the pipeline's).
73pub const LINE_LATENCY: f64 = crate::LATENCY as f64;
74
75/// The kinds of core a line can hold: (ring stages, LUTs). Stages are also
76/// the rate in 1/80 blocks per clock; 80 is the full pipeline.
77#[must_use]
78pub fn cores() -> Vec<(u32, u32)> {
79    let routed = |s: u32| ROUTED_LUT.iter().find(|(t, _)| *t == s).map_or_else(|| folded_lut(s), |(_, l)| *l);
80    let mut c: Vec<(u32, u32)> = FOLDS.iter().map(|&s| (s, routed(s))).collect();
81    c.push((80, FULL_LUT));
82    c
83}
84
85/// A line: how many cores of each kind ([`cores`] order).
86#[derive(Clone, Debug, PartialEq, Eq, Default)]
87pub struct Line {
88    /// Count per core kind.
89    pub counts: Vec<u32>,
90}
91
92impl Line {
93    /// Its rate in 1/80 blocks per clock.
94    #[must_use]
95    pub fn units(&self) -> u32 {
96        cores().iter().zip(&self.counts).map(|((s, _), n)| s * n).sum()
97    }
98    /// Its LUTs.
99    #[must_use]
100    pub fn lut(&self) -> u32 {
101        cores().iter().zip(&self.counts).map(|((_, l), n)| l * n).sum()
102    }
103    /// Blocks per clock.
104    #[must_use]
105    pub fn per_clock(&self) -> f64 {
106        f64::from(self.units()) / 80.0
107    }
108    /// "1 full + 2 fold10", biggest first.
109    #[must_use]
110    pub fn describe(&self) -> String {
111        let parts: Vec<String> = cores()
112            .iter()
113            .zip(&self.counts)
114            .rev()
115            .filter(|(_, n)| **n > 0)
116            .map(|((s, _), n)| if *s == 80 { format!("{n} full") } else { format!("{n} fold{s}") })
117            .collect();
118        if parts.is_empty() { "none".into() } else { parts.join(" + ") }
119    }
120}
121
122/// The one-core line that hashes the most within `luts` (ties: fewer
123/// LUTs); no line when not even the smallest core fits.
124#[must_use]
125pub fn fastest(luts: u32) -> Line {
126    let kinds = cores();
127    let mut line = Line { counts: vec![0; kinds.len()] };
128    let best = kinds.iter().enumerate().filter(|(_, (_, l))| *l <= luts).max_by_key(|(_, (s, l))| (*s, std::cmp::Reverse(*l)));
129    if let Some((k, _)) = best {
130        line.counts[k] = 1;
131    }
132    line
133}
134
135/// The cheapest one-core line that hashes at least `units` / 80 blocks per
136/// clock; above one block per clock, a full pipeline (the line then
137/// limits the chip).
138#[must_use]
139pub fn smallest(units: u32) -> Line {
140    let kinds = cores();
141    let mut line = Line { counts: vec![0; kinds.len()] };
142    let pick = kinds.iter().enumerate().filter(|(_, (s, _))| *s >= units).min_by_key(|(_, (_, l))| *l);
143    let k = pick.map_or(kinds.len() - 1, |(k, _)| k);
144    line.counts[k] = 1;
145    line
146}
147
148/// The shared SHA-512 line.
149#[derive(Clone, Debug)]
150pub struct Sha512 {
151    /// LUT allowance (manual), or the size the planner settled on (auto).
152    pub lut_cap: u32,
153    /// DSP allowance.
154    pub dsp_cap: u32,
155    /// Sized by the planner to what the chip wants (the default).
156    pub auto: bool,
157}
158
159impl Default for Sha512 {
160    fn default() -> Self {
161        Self {
162            lut_cap: SHA_LINE_LUT,
163            dsp_cap: SHA_LINE_DSP,
164            auto: true,
165        }
166    }
167}
168
169/// Choices of the "size" knob.
170const SIZE: [&str; 2] = ["auto (never limits)", "manual (LUT cap)"];
171
172impl Component for Sha512 {
173    fn name(&self) -> String {
174        "SHA-512 line".into()
175    }
176
177    fn role(&self) -> Role {
178        Role::Sha512
179    }
180
181    fn knobs(&self) -> Vec<Knob> {
182        vec![
183            Knob::range("LUT cap", f64::from(self.lut_cap), 0.0, f64::from(SHA_LINE_MAX_LUT), 1_000.0),
184            Knob::range("DSP cap", f64::from(self.dsp_cap), 0.0, f64::from(SHA_LINE_DSP), 1.0),
185            Knob::choice("size", usize::from(!self.auto), &SIZE),
186        ]
187    }
188
189    fn set_knob(&mut self, index: usize, value: f64) {
190        match index {
191            // Setting the LUTs by hand makes the size manual.
192            0 => {
193                self.lut_cap = (value.max(0.0) as u32).min(SHA_LINE_MAX_LUT);
194                self.auto = false;
195            }
196            1 => self.dsp_cap = (value.max(0.0) as u32).min(SHA_LINE_DSP),
197            _ => self.auto = value < 0.5,
198        }
199    }
200
201    fn plan(&self, share: &Share, cx: &Context) -> Option<Plan> {
202        // The allowance is the guaranteed share; a larger share (LUTs the
203        // planner lends because nobody else can use them) grows the line,
204        // up to its largest build. A manual allowance of 0 means no line.
205        if !self.auto && self.lut_cap == 0 {
206            return None;
207        }
208        let line = fastest(share.lut.min(LARGEST_LINE_LUT.max(self.lut_cap)));
209        if line.units() == 0 {
210            return None;
211        }
212        let per_clock = line.per_clock();
213        let rate = per_clock * cx.mhz * 1e6;
214        let size = if self.auto { "auto" } else { "manual" };
215        Some(Plan {
216            cost: Cost { lut: line.lut(), dsp: 0, bram36: 0, uram: 0 },
217            rate,
218            unit: "blocks",
219            limit: if !self.auto && share.lut > self.lut_cap {
220                format!("grew past its {}k allowance", self.lut_cap / 1_000)
221            } else {
222                format!("{size}, {}k", share.lut / 1_000)
223            },
224            detail: format!("{} = {per_clock:.4} blocks/clk ({size}; LUTs routed out of context, 4.878 ns)", line.describe()),
225            demands: Vec::new(),
226            supplies: vec![Flow { service: SHA512_BLOCKS, per_second: rate }],
227            // Routed out of context (see the module docs), not in-chip.
228            measured: true,
229            latency_cycles: LINE_LATENCY,
230            // Every stage holds a block at full rate; a pipeline holds 82.
231            in_flight: f64::from(line.units()) * LINE_LATENCY / 80.0,
232            batch: None,
233            covers: Vec::new(),
234        })
235    }
236
237    fn fixed(&self) -> Option<Share> {
238        Some(Share { lut: self.lut_cap, dsp: self.dsp_cap, bram36: 0, uram: 0 })
239    }
240
241    fn size_for(&self, per_second: f64, cx: &Context) -> Option<Share> {
242        if !self.auto {
243            return None;
244        }
245        // Blocks per clock, in 1/80 steps, rounded up; nothing wanted
246        // means no line.
247        let units = (per_second / (cx.mhz * 1e6) * 80.0 - 1e-9).ceil().max(0.0) as u32;
248        let lut = if units == 0 { 0 } else { smallest(units).lut() };
249        Some(Share { lut, dsp: 0, bram36: 0, uram: 0 })
250    }
251
252    fn resize(&mut self, allowance: Share) {
253        if self.auto {
254            self.lut_cap = allowance.lut;
255        }
256    }
257
258    fn build_flags(&self, plan: &Plan) -> BuildFlags {
259        let line = fastest(plan.cost.lut);
260        let mut flags: BuildFlags = vec![("sha512.cores".into(), format!("\"{}\"", line.describe()))];
261        for ((s, _), n) in cores().iter().zip(&line.counts) {
262            if *n > 0 {
263                let key = if *s == 80 { "sha512.full_pipelines".to_string() } else { format!("sha512.fold{s}") };
264                flags.push((key, n.to_string()));
265            }
266        }
267        flags
268    }
269}
270
271#[cfg(test)]
272mod tests {
273    use super::*;
274
275    #[test]
276    fn the_default_manual_line_is_above_half_a_block_per_clock() {
277        let sha = Sha512 { auto: false, ..Sha512::default() };
278        let plan = sha.plan(&sha.fixed().unwrap(), &Context::default()).unwrap();
279        assert!(plan.rate >= 0.5 * 205e6, "{}", plan.detail);
280    }
281
282    #[test]
283    fn shrinking_the_line_never_raises_its_rate() {
284        let cx = Context::default();
285        let mut last = f64::INFINITY;
286        for lut in (0..=SHA_LINE_LUT).rev().step_by(1_000) {
287            let sha = Sha512 { lut_cap: lut, auto: false, ..Sha512::default() };
288            let rate = sha.plan(&sha.fixed().unwrap(), &cx).map_or(0.0, |p| p.rate);
289            assert!(rate <= last);
290            last = rate;
291        }
292    }
293
294    /// A line is one core: the cheapest that covers the rate (a full
295    /// pipeline above one block per clock), and the fastest that fits a
296    /// budget, never over it.
297    #[test]
298    fn lines_are_one_core() {
299        for units in 1..=100 {
300            let line = smallest(units);
301            assert_eq!(line.counts.iter().sum::<u32>(), 1, "{units}: {}", line.describe());
302            if units <= 80 {
303                assert!(line.units() >= units, "{units}: {}", line.describe());
304                for (s, l) in cores() {
305                    assert!(s < units || l >= line.lut(), "{units}: fold{s} is cheaper than {}", line.describe());
306                }
307            } else {
308                assert_eq!(line.units(), 80);
309            }
310        }
311        for lut in (0..=150_000).step_by(2_500) {
312            let line = fastest(lut);
313            assert!(line.lut() <= lut, "{lut}: {}", line.describe());
314            assert!(line.counts.iter().sum::<u32>() <= 1);
315        }
316        assert_eq!(fastest(3_000).units(), 0);
317        assert_eq!(fastest(LARGEST_LINE_LUT).units(), 80);
318    }
319
320    /// Auto: the size covers exactly what is asked, in 1/80 steps, and
321    /// nothing asked means no line; manual lines do not size themselves.
322    #[test]
323    fn auto_sizes_to_demand() {
324        let cx = Context::default();
325        let sha = Sha512::default();
326        // 25M blocks/s is 0.122 block/clock: 10 units (1/8).
327        let a = sha.size_for(25e6, &cx).unwrap();
328        let plan = sha.plan(&a, &cx).unwrap();
329        assert!(plan.rate >= 25e6 && plan.rate < 25e6 + 205e6 / 8.0, "{}", plan.detail);
330        assert!(a.lut < 20_000, "{a:?}");
331        assert_eq!(sha.size_for(0.0, &cx).unwrap().lut, 0);
332        assert!(Sha512 { auto: false, ..sha }.size_for(25e6, &cx).is_none());
333    }
334}
rhdl_sha512_pipelined/planner.rs

rhdl_sha512_pipelined/
planner.rs
