Function partition_for_cycle_cap

crates/kernel/src/shard.rs:1845–1990

Size a partition to a per-shard **cycle** (guest-STEP) budget by **bin-packing to the cap**, not by balancing into a fixed shard count. `max_cycles` is the ceiling on a single shard's in-circuit Zisk guest steps — the leaf prover's trace size, which is what sets peak prover RAM. Get it from a host-RAM budget with [`cycle_cap_for_ram`] (the measured prover model `peak_RAM_GiB ≈ 50 + 33 × steps_bil

(
  profile: &BlockProfile,
  max_cycles: u64,
  epsilon: f64,
)

    fmt_duration(est.wall_secs),
    est.parallelism,
    fmt_duration(est.seq_secs),
  )
}

/// A partition sized to a per-shard Zisk **cycle** budget (rather than a fixed
/// shard count). See [`partition_for_cycle_cap`].
pub struct BudgetPlan {
  /// Chosen shard count.
  pub num_shards: usize,
  /// Shard assignment per block id (as [`Hypergraph::partition`] returns).
  pub shard_of: Vec<u32>,
  /// The bisection tree for the chosen partition, for tree-aligned aggregation.
  pub tree: AggNode,
  /// Per-shard predicted-STEPS cap: `max_cycles − SHARD_COST_FLOOR` (the block
  /// step-costs that may sum into one shard before the floor pushes it over
  /// `max_cycles`).
  pub step_cap: u64,
  /// Heaviest shard's **full** predicted guest STEPS — `SHARD_COST_FLOOR +
  /// Σ block_step_cost + COST_PER_INGRESS_BYTE × cross_ingress_bytes`. The
  /// packer keeps this `≤ max_cycles` (cross-ingress included), so it is the
  /// tightest single number to compare against the cap / RAM budget.
  pub max_shard_steps: u64,
  /// Largest single (atomic) block's [`block_step_cost`] — the hard floor on
  /// `max_shard_steps` that no shard count can beat.
  pub largest_block_steps: u64,
  /// True when the largest atomic block alone exceeds the cap: the budget is
  /// infeasible by sharding (split that mutual block upstream, or raise the cap
  /// / use a bigger box).
  pub infeasible_atomic_floor: bool,
}

/// Size a partition to a per-shard **cycle** (guest-STEP) budget by **bin-packing
/// to the cap**, not by balancing into a fixed shard count.
///
/// `max_cycles` is the ceiling on a single shard's in-circuit Zisk guest steps
/// — the leaf prover's trace size, which is what sets peak prover RAM. Get it
/// from a host-RAM budget with [`cycle_cap_for_ram`] (the measured prover model
/// `peak_RAM_GiB ≈ 50 + 33 × steps_billions`).
///
/// **Why packing, not balancing.** A shard's predicted STEPS is
/// `SHARD_COST_FLOOR + Σ block_step_cost + COST_PER_INGRESS_BYTE ×
/// cross_ingress_bytes` (member reduction + own ingress, plus the foreign
/// dependencies it re-ingresses). The goal is the *fewest* shards that each stay
/// under the cap — not uniform shards. Balancing into `N = ⌈total/cap⌉` and
/// growing `N` whenever imbalance pushed the heaviest shard over the cap (the
/// old approach) *over-sharded*: it spread work evenly, so every shard sat
/// partially full and a single un-equalizable block forced extra shards. Packing
/// instead fills each shard as close to the cap as the dependency structure
/// allows and only opens a new shard when the next block won't fit — giving
/// `⌈total/cap⌉` shards plus a small packing remainder, each maximally
/// performant. Lumpy (a near-full shard beside a partial one) is fine.
///
/// **How dependency overlap is packed.** We first cut a *fine* min-cut partition
/// ([`PACK_PIECES_PER_CAP`] pieces per cap) purely to obtain a **cut-coherent
/// order**: a DFS of the bisection tree visits each tightly-coupled subtree
/// before moving on, so dependency-overlapping blocks are contiguous. Greedy
/// next-fit along that order therefore packs overlapping blocks into the same
/// shard — keeping their shared dependencies in-shard so they are not re-paid as