rhdl_fpga_planner/

decisions.rs

//! # How the planner decides: from your knobs to a build
//!
//! This chapter follows one question from the moment you press a key in
//! the TUI to the `build-config.toml` that W writes:
//!
//! > *With this many LUTs, DSPs, BRAM and URAM, which modules do we build,
//! > how big is each one, and how fast does the chip sign and verify?*
//!
//! Read it once top to bottom and you will know which function to open
//! for any number the screen shows. Every heuristic is named with the
//! reason it exists and the problem it solved, because each one was added
//! after a real number on the screen looked wrong.
//!
//! ```text
//!  you: budget %, powers, background, limits, knobs
//!        │
//!        ▼
//!  1. shares        powers → guaranteed LUT/DSP/BRAM/URAM per module   shares()
//!        │
//!        ▼
//!  2. best builds   each module searches its own build space           Component::plan
//!        │
//!        ▼
//!  3. lending       unused resources → modules that can use them       plan_chip()
//!        │
//!        ▼
//!  4. delivery      capacity ÷ need per side, SHA-512 supply           deliver()
//!        │
//!        ▼
//!  5. balancing     B key: sign/verify split; DSig background          balance_mix(), layout()
//!        │
//!        ▼
//!  6. build flags   W key: each module's compile-time settings         build_config()
//! ```
//!
//! # Chapter 1: A budget becomes shares
//!
//! The budget is four numbers: LUTs (`LUT %` of 485k), DSPs (`DSP %` of
//! 4,520), BRAM (`BRAM %` of the 1,776 BRAM36 in the U280 shell's dynamic
//! region) and URAM (`URAM %` of 960). See [`Budget`](crate::Budget).
//!
//! *Why 1,776 and not the device's 2,016:* DSig's build v4 failed
//! placement asking for 4,033 BRAM18 in a region that has 3,552. The rest
//! belongs to the shell. A plan that counts the whole device promises RAM
//! we cannot have.
//!
//! The SHA-512 line is in the budget. Its allowance (65k LUTs and 20 DSPs
//! by default) comes off the top, and the modules with powers divide the
//! rest ([`Budget::rest`](crate::Budget::rest)). 485k and 4,520 are the old
//! 420k and 4,500 plus that default, so the default chip gives the engines
//! what it always did; but now a bigger line costs the engines LUTs, and a
//! smaller one gives them LUTs. *Why it changed:* with the line outside
//! the budget, shrinking it bought nothing, and the line's own unused LUTs
//! (65k holds one 43.2k pipeline) could not be lent.
//!
//! The TUI shows this as the **LUT split** row, in % of the LUT budget:
//!
//! ```text
//!  Ed25519 paper:  SHA x %  |  Ed25519 (100 - x) %
//!  DSig paper:     SHA x %  |  DSig (100 - x)(100 - B)/100 %  |  Ed25519 (100 - x)·B/100 %
//! ```
//!
//! **The line sizes itself (auto, the default).** The SHA-512 line should
//! never be what limits the chip, and it should not hold LUTs it does not
//! need. So [`plan_chip`](crate::plan_chip) asks it, through
//! [`Component::size_for`](crate::Component::size_for), for the smallest
//! build that hashes what the engines want
//! ([`Delivered::sha_wanted`](crate::Delivered::sha_wanted), the blocks per
//! second at the rates they deliver before any SHA limit), plans the engines
//! in what that leaves, and repeats (a smaller line frees LUTs, the engines
//! grow and want more) at most four times. The plan the line does not limit,
//! delivering the most, wins, and
//! [`apply_layout`](crate::apply_layout) tells the line the size it settled
//! on ([`Component::resize`](crate::Component::resize)), so the next plan
//! starts there. The Ed25519 paper at 100 % wants about 25M blocks per
//! second, an eighth of a block per clock: a ~13.6k-LUT line instead of 65k.
//!
//! **By hand.** Left/Right on the row sets the line's LUT allowance (and its
//! "size" knob to manual) in 0.5 % steps of the budget, from 0 up to 432k
//! (ten full pipelines). A bigger line takes its LUTs from the engines; the
//! "size" knob returns it to auto. B, the EdDSA background below, is a % of
//! what the line leaves.
//!
//! **Every split sums to 100 %.** You never set a module's share directly.
//! You set splits, and [`apply_layout`](crate::apply_layout) turns them
//! into module powers:
//!
//! ```text
//!  Ed25519 paper:  sign s %  +  verify (100 - s) %
//!
//!  DSig paper:     HBSS foreground (100 - B) %  +  EdDSA background B %
//!                  foreground = DSig sign s % + DSig verify (100 - s) %
//!                  background = Ed25519 sign e % + Ed25519 verify (100 - e) %
//!
//!  e.g. B = 8.5, s = 44, e = 75:
//!    DSig sign 40.3 %, DSig verify 51.2 %, Ed25519 sign 6.4 %, Ed25519 verify 2.1 %
//! ```
//!
//! A module's **guaranteed share** is its power % of each resource
//! ([`shares`](crate::shares)). With power 40.3 % at the default budget that
//! is 169.1k LUT, 1,811 DSP, 715 BRAM36 and 386 URAM.
//!
//! **Manual limits** ([`Slot::limits`](crate::Slot::limits)) override this
//! per resource. "DSig sign URAM 10 %" gives DSig sign exactly 96 URAM, and
//! the other modules split the remaining URAM by their powers. A limit is
//! a hard cap: lending (Chapter 3) never gives that module more of that
//! resource. Leave limits on auto unless you are testing a specific
//! partition; auto plans better.
//!
//! # Chapter 2: Each module finds its best build
//!
//! Each module is a [`Component`](crate::Component). Given a share, it
//! returns the fastest build that fits, or `None`. The planner knows
//! nothing about Ed25519 or DSig; all the architecture choices below live
//! in the modules' own crates. That is deliberate: the people who build a
//! module know its costs.
//!
//! ## Ed25519 sign (`rhdl_ed25519_scalable_core::planner::Ed25519Sign`)
//!
//! A signing core is a profile `fb/sha/sc/cp`:
//! - `fb`: fixed-base field machines, 14,615 LUT and 225 DSP each (routed).
//! - `sha`: SHA-512 rings; 0 on the shared SHA-512 line.
//! - `sc`: scalar rings.
//! - `cp`: one batch-compress machine (1), or none (0).
//!
//! The search (`frontier::plan_sign_shaped`) tries every profile up to 40
//! machines, with both multipliers (225 DSP, and the lean 150-DSP
//! Karatsuba that costs +4,440 LUT and saves 75 DSP, routed), and keeps the
//! fastest that fits. A tie goes
//! to fewer LUTs. Three refinements shape what you see:
//!
//! 1. **The cycle model picks the bottleneck.** Cycles per signature is
//!    the slowest stage (`config::Profile::cycles_per_sign`):
//!    - machines: `392 bundles / fb / 0.97`;
//!    - SHA: `243 / sha / 0.886`;
//!    - scalar: `64 / sc / 0.9`;
//!    - admission: 2;
//!    - compress credits: `(392·32 + 423·64 + 8000) / 2048 = 23.25`.
//!
//!    That last stage caps one core at **8.82M signatures/s** however many
//!    machines it has.
//! 2. **Cores.** Because of that cap, a module may be 1 to
//!    `MAX_CORES` (4) identical cores, each planned in `1/n` of the share.
//!    Before this, the signing rate stopped growing near 8.8M whatever the
//!    budget.
//! 3. **Memory placement.** Every block starts in its preferred memory
//!    layout (machine banks in URAM). If the share's URAM runs out, a
//!    greedy placer (`frontier::place`) moves one block at a time to
//!    whichever layout shrinks the overflow most:
//!    - the block-RAM layout of a machine;
//!    - a controller, key table or key loader with its URAM converted at
//!      8 BRAM36 per URAM;
//!    - and when BRAM runs out too, machine banks in LUT RAM (+22,830 LUT,
//!      routed).
//!
//!    That is how spare LUTs still buy machines when RAM is short. The
//!    plan detail says where memory went ("some URAM moved to BRAM",
//!    "some banks in LUT RAM").
//!
//! Your shape knobs restrict the search; they never add builds it would
//! not consider:
//! - **block ratio manual**: only profiles whose `fb : sha : sc` follows
//!   your weights (rounded, at least 1).
//! - **batch compress on/off**: only `cp = 1` or `cp = 0` builds. Off
//!   means each machine inverts and encodes its own point: the 657-bundle
//!   program, a model. The measured small signer counts as off.
//!
//! The **small signer** (`Ed25519SignCoreSmall`, routed, 29,055 LUT,
//! 248 DSP, 40 BRAM36, 32 URAM, 895 cycles = 229k signatures/s) is a separate
//! candidate. It wins any share too small for a full core, which is
//! exactly DSig's certificate signer.
//!
//! ## Ed25519 verify (`Ed25519Verify`)
//!
//! The same structure: a profile `machines/sha/sc/cp` (`cp` 0–2), verify
//! modes with different program lengths (known-key 775 bundles, strict
//! ~3,050, batch ~1,300, the last two models), cores, shape knobs and
//! memory placement. Known-key adds a key loader and a 24-URAM key table
//! per machine, which is why the verifier is the first to run out of URAM.
//!
//! ## DSig sign (`rhdl_dsig_scalable_core::planner::Dsig`)
//!
//! DSig scales in **slices**, 1 to 16. The largest count that fits wins
//! (`Dsig::plan`).
//! - One slice: 127.5k LUT (3 chain lanes of 23.9k Haraka plus a 16.4k
//!   BLAKE3 factory lane plus the rest) and 72 URAM.
//! - Rate: `slices × 205 MHz / 68` = 3.01M signatures/s per slice.
//! - Built: 2, 4 and 8 slices; 2 is measured on the card at 6.02M/s.
//!   Every other count is a model with the same per-slice cost.
//!
//! The knobs change the slice's cost, and only through cost do they change
//! the rate. A cheaper chain hash (BLAKE3 lanes, 16.4k) or S-boxes in RAM
//! fit more slices in the same LUTs; the key period (68 cycles) stays the
//! same. This is why changing the hash at the default budget may show the
//! same rate: the saving is real but not yet a whole slice.
//!
//! "Ed25519 certs" decides who signs the batch roots:
//! - **The chip's Ed25519 sign module** (default): DSig's cost has no
//!   Ed25519 core.
//! - **Inside DSig**, as built: +25.4k LUT, a 29.3M/s certificate ceiling,
//!   and the plan [covers](crate::Plan::covers) Ed25519 signing, so the
//!   chip's Ed25519 sign module is not needed.
//!
//! The HBSS knob offers HORS. It plans nothing and says so
//! ([`Component::unavailable`](crate::Component::unavailable)) until
//! someone writes its cost model.
//!
//! ## DSig verify (`DsigVerify`, a model)
//!
//! Identical verify units, as many as the LUTs and BRAM allow. One unit is
//! 3 chain lanes, a BLAKE3 lane and ~20k of glue: 108k LUT with Haraka. It
//! takes 35 cycles per verification (105 chain steps over 3 lanes), so
//! 5.86M/s per unit.
//!
//! ## SHA-512 line (`rhdl_sha512_pipelined::planner::Sha512`)
//!
//! One core, because the clients' arbiter drives a single in-order core:
//! a full pipeline (62,252 LUT, 1 block per clock) or a folded ring of
//! 2–40 stages (`rhdl_sha512_pipelined::folded`, 3,509 to 40,047 LUT,
//! `S / 80` blocks per clock); LUTs routed out of context at 4.878 ns, not
//! in-chip. `fastest(luts)` fills a manual LUT cap; on **auto** (the
//! default), `smallest(units)` gives the cheapest core that hashes what the
//! chip wants (below).
//!
//! # Chapter 3: Lending: real units, not percentages
//!
//! Percentages hand every module the same fraction of *every* resource,
//! and modules are lopsided:
//! - DSig signing uses no DSPs.
//! - An Ed25519 verifier exhausts URAM long before LUTs.
//! - A 40.3 % share holds 1 DSig slice (148k of its 169k LUT), and the
//!   last 21k does nothing.
//!
//! The first planner wasted all of that, and the TUI used about half the
//! LUTs you gave it.
//!
//! [`plan_chip`](crate::plan_chip) fixes it in rounds. After every module
//! plans in its guaranteed share:
//! 1. Count what is unused, per resource, in real units.
//! 2. Re-plan each module in its own build's cost plus that free pool.
//! 3. Commit the re-plan that raises the delivered rates most (relative
//!    gains of both sides, summed), and repeat until nobody gains.
//!
//! Two rules keep it fair:
//! - **Own side first.** Phase 0 lends only within a side (DSig sign and
//!   the Ed25519 signer share the sign side's leftovers). Phase 1 opens
//!   whatever is still free, which that side could not use, to either side.
//!   Without this, the verify side once took the LUTs the sign side needed
//!   for its next slice, and 200 % / 200 % delivered less than 200 % / 100 %.
//! - **Borrow only what the gain needs.** The committed module takes the
//!   smallest slice of the free pool (1/16, 1/8, 1/4, 1/2 or all) that
//!   gains as much. Without this, the Ed25519 verifier in the DSig paper
//!   took 123k spare LUTs (6 machines, 1.54M/s) to deliver 45.8k/s.
//!
//! The card line "uses resources other modules left free" marks a
//! borrower; its gauges show the share it ended up with.
//!
//! ## The remainder: nothing idle that a module could use
//!
//! Lending only commits what raises the *delivered* rates. That leaves
//! resources idle whenever the bottleneck is elsewhere: in the DSig paper
//! the DSig signer uses almost no DSPs, but the Ed25519 modules behind it
//! are not the bottleneck, so lending never gave them those DSPs. Two
//! slices' worth of LUTs short of a third slice also sat idle.
//!
//! So after lending, a third pass (`fill_remainder`, inside
//! [`plan_chip`](crate::plan_chip)) hands out whatever is still free:
//! 1. **Pro rata.** Every module of the paper, the SHA-512 line included,
//!    is offered its slice of each free resource, in proportion to its
//!    guaranteed share of that resource, on top of its build. It keeps a
//!    larger build if its capacity rises.
//! 2. **Greedy.** If no pro-rata slice buys anything (the next core or
//!    slice costs more than a slice), modules in descending guaranteed LUTs
//!    may take the whole pool; the first that grows keeps what it uses.
//! 3. Repeat (at most 6 rounds) until nothing grows.
//!
//! **The SHA-512 line takes part.** Its allowance is what it is
//! guaranteed, not a ceiling: it borrows in lending's phase 1 when it is
//! the bottleneck (a line shrunk to 2k grows back out of LUTs the engines
//! leave), and it grows in the remainder pass up to its largest build, 2
//! blocks per clock (two full pipelines, 86.4k LUT). In the Ed25519 paper
//! at LUT 150 % / DSP 100 % the engines are DSP-bound, so the line takes
//! the idle LUTs and goes from 1 to 2 blocks per clock.
//!
//! A step is kept only if neither side delivers less (one side's growth
//! can take SHA-512 blocks from the other). The delivered rates rarely
//! change in this pass; what changes is **capacity**, the headroom each
//! module has above what the chip delivers, which the cards show as
//! "capacity". *Why not lend it in the first place:* lending's rule,
//! borrow only what raises the delivered rates, is what keeps a helper from
//! taking the LUTs the bottleneck needs. The remainder pass runs after the
//! bottleneck has taken everything it can use, so it cannot starve it.
//!
//! # Chapter 4: What the chip delivers
//!
//! Capacities are not results: on each side the slowest link sets the
//! pace ([`deliver`](crate::deliver)). Each paper says how many operations
//! of each role one delivered operation needs
//! ([`Mode::need`](crate::Mode::need)):
//!
//! ```text
//!  DSig sign side:    DSig sign × 1,  Ed25519 sign × 1/K          (K = 128)
//!  DSig verify side:  DSig verify × 1, Ed25519 verify × (1 - h),  h = b·(K-1)/K
//! ```
//!
//! A side delivers `min over its roles (capacity / need)`. Then the SHA-512
//! line: if both sides together want more blocks than it supplies, both
//! slow down in proportion and the screen marks it "limits the chip".
//! Latency is the slowest module of the side plus one line pass per block.
//!
//! # Chapter 5: Balancing: what "100 %" means
//!
//! **The B key** ([`balance_mix`](crate::balance_mix)) searches the
//! sign/verify split for the most `min(sign, verify / mix)`: 4 % steps,
//! then 1 % and 0.5 % around the best. Ties go to the larger total. This
//! is how a budget too small for both sides still shows something instead
//! of zeros everywhere.
//!
//! **The DSig background on auto** ([`layout`](crate::layout)) asks how
//! much EdDSA DSig really needs:
//! 1. A quick search over the background `B` and its sign share `e`, with
//!    every module in its guaranteed share.
//! 2. A refinement over `B` in 0.5 % steps with the full planner,
//!    lending included, because a borrowed slice can make a much smaller
//!    background enough. Without this step the quick score reserved 20 %
//!    and cost the foreground a whole slice.
//!
//! The smallest best `B` is shown as **needed** (8.5 % at the defaults).
//!
//! # Chapter 6: The build config
//!
//! W calls [`build_config`](crate::build_config): one TOML table per module
//! with that module's
//! [`build_flags`](crate::Component::build_flags), plus a header with the
//! budget and the delivered rates.
//!
//! | Module | Keys | Meaning |
//! |---|---|---|
//! | Ed25519 sign | `ED25519_SCALABLE_PROFILE = "fb,sha,sc,cp"`, `cores`, `SH`, `memory`, `multiplier`, `uram_machines`, `lut_machines`, `buildable`, `not_buildable` | the profile `build.rs` reads; `1,1,1,0` is the small signer; `SH = 1` on the shared line; `SPECIALIZED` or `AS_BUILT` memory; `DSP225` or `LEAN150`; how many machines keep their banks in UltraRAM and how many in LUT RAM (the rest in block RAM), which the export reads as `ED25519_URAM_MACHINES` / `ED25519_LUT_MACHINES` |
//! | Ed25519 verify | `verify_profile`, `cores`, `verify_mode`, `SH`, `memory`, `multiplier`, `uram_machines`, `lut_machines`, `buildable`, `not_buildable` | the same, for `KnownKeyVerifyCore` (`machines,sha,sc,1`: it always has one compress stage) |
//! | DSig sign | `dsig.DSIG_SLICES = N`, `dsig.DSIG_CHAIN = "haraka"\|"blake3"\|"sha512"`, `dsig.DSIG_SBOX_PLACEMENT`, `dsig.DSIG_TABLE_MASK` (the T-table rounds "auto" chose, e.g. `0x1f8` for 6), `dsig.certificates`, `buildable`, `not_buildable` | build variables the DSig crate's `build.rs` reads (any other value fails the build, so host and kernel cannot silently disagree); `buildable = false` marks a model configuration with no build behind it, and `not_buildable` lists why (as for Ed25519) |
//! | SHA-512 line | `sha512.full_pipelines`, `sha512.folded_pipelines` | the pipelines that fill the cap |
//!
//! *Why placement and the multiplier are in the file:* the first L200
//! verifier plan (27,0,2,1) was exported with every machine in its
//! preferred layout, and Vivado stopped before placement asking for 2,646
//! BRAM36 on a device with 2,016 (job 023, 2026-10-18). A plan the file
//! cannot reproduce is a plan nobody can build. Since then every Ed25519
//! plan on screen is exported exactly as planned, and
//! `measure/export_build.py` turns the table into the export's
//! environment.
//!
//! # Chapter 7: Why a rate stays flat
//!
//! Builds come in whole blocks:
//! - an Ed25519 machine is ~14.6k LUT and 225 DSP;
//! - a DSig slice is ~128k LUT;
//! - a DSig verify unit is ~108k LUT.
//!
//! Between steps nothing changes, and that is physical, not a bug. Every
//! card shows **next: +N LUT -> rate**, the distance to the next faster
//! build ([`tui::next_step`](crate::tui::next_step)), and its limiting
//! resource. If "next" is far, look at the limit: often DSP or URAM, not
//! LUT, is the wall.
//!
//! Two walls are common:
//!
//! - **DSPs in the Ed25519 paper.** Every Ed25519 machine needs its DSP
//!   multiplier, so at DSP 100 % the chip is DSP-bound: LUT 150 % and 200 %
//!   both deliver 4.57M signatures / 4.50M verifications (fix9 costs,
//!   `measure/configs/predictions.tsv`), with 4,4xx of 4,520 DSPs used and
//!   LUTs idle that no module can turn into a machine. Raise DSP and the
//!   LUTs fill: 200 % / 200 % uses 956k of 970k LUTs for 6.09M / 6.61M.
//!   (A LUT-only multiplier would turn those LUTs into machines; open
//!   problem.)
//! - **Slices in the DSig paper.** A slice is ~95k–125k LUT with T-tables.
//!   At 100 % (485k, 65k of it the SHA line) the chip holds 2 slices and 3
//!   verify units: 6.03M / 17.57M, all but 2k LUTs used. A third slice would
//!   need a verify unit back, and 9.04M / 5.86M balances worse. At 150 % it
//!   is 4 slices (12.06M), at 200 % 6 slices (18.09M). The sixth slice
//!   needs DSig's "table RAM" knob on "block RAM, then URAM (model)" (the
//!   default), which moves T-tables that block RAM cannot hold into spare
//!   URAM; on "block RAM (built)" 200 % holds 5 slices (15.07M).
//!
//! In the DSig paper the Ed25519 modules get almost every DSP (DSig uses
//! none), but they cannot build more machines without LUTs, which the
//! slices hold; their capacity stays a little above what DSig needs.
//!
//! # Chapter 8: Working on it
//!
//! | You want to… | Change | Then check |
//! |---|---|---|
//! | correct a block's cost | the module's cost table (`frontier::slimmed_costs`, DSig `config.rs`) | `chip` test `rates_scale_with_luts_and_dsps` |
//! | add a knob | the component's `knobs`/`set_knob`, and its search | the module's own tests; the knob appears in the TUI by itself |
//! | share a knob across modules | `Knob::shared()` with the same name in each | `dsig_scheme_knobs_reach_both_modules` |
//! | add a module | a [`Component`](crate::Component) and a slot in `rhdl_signatures::paper::slots`, behind its crate's feature | `this_builds_papers_balance_and_render` |
//! | change how resources move | `plan_chip` (lending), `shares` (limits), `layout` (background) | planner tests `unused_resources_are_lent_in_real_units`, `manual_limits_are_exact_caps` |
//!
//! Three things bite newcomers:
//! - **The plan cache** ([`plan_slot`](crate::plan_slot)) keys on the
//!   component's name and knob values. A component whose plan depends on
//!   state that is not a knob must put it in a knob, or stale plans
//!   appear.
//! - **Speed.** Balancing calls the planner thousands of times. Run the
//!   chip tests with `--profile sim` (optimized); the debug build can
//!   exceed the 20-minute bound of `tools/bounded.sh`.
//! - **One tuner, two builds.** `cargo tuner` (the root crate
//!   `rhdl_signatures`) has both papers; `cargo tuner-ed25519` is the same
//!   binary built without the `dsig` feature, so it shows the Ed25519 paper
//!   only. A paper is offered only when its modules are in the slot list
//!   ([`App::has_paper`](crate::tui::App::has_paper)).
//!
//! # Open problems
//!
//! 1. A `cp = 0` known-key verifier (machines encode their own points)
//!    would save the 16.6k-LUT compress machine at small sizes. It is not
//!    built, so the search offers known-key verifiers only with `cp = 1`.
//! 2. Measure the 8 BRAM per URAM conversion of controllers and key tables.
//!    (URAM, block-RAM and LUT-RAM machine banks are routed at 205 MHz:
//!    fix9 jobs 007zy–007zzb.)
//! 3. Model HORS (a cost model for the HBSS knob's second choice).
//! 4. Replace the DSig per-slice estimate with build v5's measured slice
//!    (DSig expects ~75–80k LUT, which moves every step in Chapter 7).
//! 5. Lending is greedy. It is checked by the scaling tests, not proven
//!    optimal; an exact search over the few modules is possible if it
//!    ever matters.
//!
//! # Where to go next
//!
//! - The chip guide (the root crate `rhdl_signatures`) for the papers, the features and the team.
//! - [`crate::tui`], the Tuner guide: the screen, one plan start to finish,
//!   every cost constant and the measured accuracy.
//! - The Ed25519 crate's `frontier` and `planner` modules for its search.
//! - DSig's `planner` module for slices, the HBSS and the verifier model.