metrale_circuit/
runs.rs

1// SPDX-License-Identifier: MIT OR Apache-2.0
2
3//! 2026-09-30: The row table of a batched MTP verify (`Mode::VerifyBatch`) and the per-run
4//! launches a `repeat = "per_run"` rule selects. A batched verify checks `n` sequences
5//! together, sequence `i` with `k_i` rows, seq-major. The GatedDeltaNet layers launch once per
6//! run: a maximal group of adjacent sequences with equal `k`. Model-engine
7//! `batched_conv_gdn_route` forms the runs, and so does [`RowTable::from_seqs`]. Each run is
8//! contiguous when its sequences' state slots are consecutive, which the batched kernels need.
9//! A table is carried when the verify runs the carried-state GDN kernels (`gdn_carry_begin`),
10//! which it does whenever the WY tables are staged.
11//!
12//! Owner: metrale-circuit.
13//! Invariants:
14//! - A row table has at least one run; every run has `k >= 1` and `n >= 1`; adjacent runs differ
15//!   in `k` (runs are maximal).
16//! - A per-run rule applies to a table only when every run matches one of its selectors; the
17//!   first matching selector, in file order, gives the run's launches.
18
19use std::fmt;
20
21use crate::rules::KernelId;
22
23/// 2026-09-30: One run of a batched verify.
24#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
25pub struct VerifyRun {
26    /// 2026-09-30: Rows per sequence.
27    pub k: u64,
28    /// 2026-09-30: Sequences.
29    pub n: u64,
30    /// 2026-09-30: The sequences' state slots are consecutive in batch order.
31    pub contiguous: bool,
32}
33
34/// 2026-09-30: The runs of a batched verify, in batch order.
35#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
36pub struct RowTable {
37    /// 2026-09-30: The runs.
38    pub runs: Vec<VerifyRun>,
39    /// 2026-09-30: The verify runs the carried-state GDN kernels.
40    pub carried: bool,
41}
42
43/// 2026-09-30: Why a row table was refused.
44#[derive(Debug, Clone, PartialEq, Eq, thiserror::Error)]
45pub enum RowTableError {
46    /// 2026-09-30: No sequences.
47    #[error("a row table needs at least one sequence")]
48    Empty,
49    /// 2026-09-30: A sequence with no rows, or a run with no sequences.
50    #[error("row table: {0}")]
51    Shape(String),
52    /// 2026-09-30: Text that is not `<k>x<n>[!]` runs.
53    #[error("row table `{0}`: runs are `<k>x<n>`, `!` marking a fragmented run")]
54    Parse(String),
55}
56
57impl RowTable {
58    /// 2026-09-30: The table of sequences with `ks` rows each, in batch order; `contiguous` says
59    /// for a run (first sequence, sequences) whether its slots are consecutive.
60    pub fn from_seqs(
61        ks: &[u64],
62        carried: bool,
63        contiguous: impl Fn(usize, usize) -> bool,
64    ) -> Result<Self, RowTableError> {
65        if ks.is_empty() {
66            return Err(RowTableError::Empty);
67        }
68        if ks.contains(&0) {
69            return Err(RowTableError::Shape("a sequence with no rows".into()));
70        }
71        let mut runs = Vec::new();
72        let mut g0 = 0;
73        while g0 < ks.len() {
74            let g1 = (g0..ks.len())
75                .find(|&i| ks[i] != ks[g0])
76                .unwrap_or(ks.len());
77            runs.push(VerifyRun {
78                k: ks[g0],
79                n: (g1 - g0) as u64,
80                contiguous: g1 - g0 > 1 && contiguous(g0, g1 - g0),
81            });
82            g0 = g1;
83        }
84        Ok(RowTable { runs, carried })
85    }
86
87    /// 2026-09-30: Parse [`RowTable::text`].
88    pub fn parse(s: &str) -> Result<Self, RowTableError> {
89        let bad = || RowTableError::Parse(s.to_string());
90        let mut runs = Vec::new();
91        let body = s.strip_prefix(UNCARRIED);
92        let carried = body.is_none();
93        for tok in body.unwrap_or(s).split_whitespace() {
94            let (body, contiguous) = match tok.strip_suffix('!') {
95                Some(b) => (b, false),
96                None => (tok, true),
97            };
98            let (k, n) = body.split_once('x').ok_or_else(bad)?;
99            let (k, n) = (k.parse().map_err(|_| bad())?, n.parse().map_err(|_| bad())?);
100            runs.push(VerifyRun { k, n, contiguous });
101        }
102        let t = RowTable { runs, carried };
103        t.check()?;
104        Ok(t)
105    }
106
107    fn check(&self) -> Result<(), RowTableError> {
108        if self.runs.is_empty() {
109            return Err(RowTableError::Empty);
110        }
111        if self.runs.iter().any(|r| r.k == 0 || r.n == 0) {
112            return Err(RowTableError::Shape(
113                "a run with no rows or no sequences".into(),
114            ));
115        }
116        // 2026-09-30: The batched arm needs two sequences (`multi_run_arm` declines one).
117        if self.runs.iter().any(|r| r.n == 1 && r.contiguous) {
118            return Err(RowTableError::Shape(format!(
119                "`{self}`: a run of one sequence is never batched; mark it `!`"
120            )));
121        }
122        if self.runs.windows(2).any(|w| w[0].k == w[1].k) {
123            return Err(RowTableError::Shape(format!(
124                "`{self}`: adjacent runs of equal k are one run"
125            )));
126        }
127        Ok(())
128    }
129
130    /// 2026-09-30: Rows, `Σ k·n`.
131    pub fn rows(&self) -> u64 {
132        self.runs.iter().map(|r| r.k * r.n).sum()
133    }
134
135    /// 2026-09-30: Sequences, `Σ n`.
136    pub fn seqs(&self) -> u64 {
137        self.runs.iter().map(|r| r.n).sum()
138    }
139
140    /// 2026-09-30: `<k>x<n>` per run, space-separated, `!` after a fragmented run, the whole
141    /// prefixed `uncarried: ` when the verify does not carry.
142    pub fn text(&self) -> String {
143        self.to_string()
144    }
145}
146
147impl fmt::Display for RowTable {
148    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
149        let parts: Vec<String> = self
150            .runs
151            .iter()
152            .map(|r| format!("{}x{}{}", r.k, r.n, if r.contiguous { "" } else { "!" }))
153            .collect();
154        if !self.carried {
155            f.write_str(UNCARRIED)?;
156        }
157        f.write_str(&parts.join(" "))
158    }
159}
160
161/// 2026-09-30: The text prefix of a table that does not carry.
162const UNCARRIED: &str = "uncarried: ";
163
164/// 2026-09-30: How often a per-run launch (or copy) happens within its run.
165#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
166pub enum Times {
167    /// 2026-09-30: Once for the run.
168    Once,
169    /// 2026-09-30: Once per sequence.
170    PerSeq,
171    /// 2026-09-30: Once per row (`k·n`).
172    PerRow,
173    /// 2026-09-30: Once per row of each sequence but its last (`(k - 1)·n`).
174    PerSeqRowButLast,
175}
176
177impl Times {
178    /// 2026-09-30: The count in `run`.
179    pub fn count(self, run: VerifyRun) -> u64 {
180        match self {
181            Times::Once => 1,
182            Times::PerSeq => run.n,
183            Times::PerRow => run.k * run.n,
184            Times::PerSeqRowButLast => run.k.saturating_sub(1) * run.n,
185        }
186    }
187
188    /// 2026-09-30: The spelling in FUSIONS.toml.
189    pub fn name(self) -> &'static str {
190        match self {
191            Times::Once => "once",
192            Times::PerSeq => "per_seq",
193            Times::PerRow => "per_row",
194            Times::PerSeqRowButLast => "per_seq_row_but_last",
195        }
196    }
197
198    /// 2026-09-30: Parse [`Times::name`].
199    pub fn parse(s: &str) -> Option<Self> {
200        [
201            Times::Once,
202            Times::PerSeq,
203            Times::PerRow,
204            Times::PerSeqRowButLast,
205        ]
206        .into_iter()
207        .find(|t| t.name() == s)
208    }
209}
210
211/// 2026-09-30: One `[[rule.run]]` selector: the runs it serves and what it launches for one.
212#[derive(Debug, Clone, PartialEq, Eq)]
213pub struct RunSelect {
214    /// 2026-09-30: Inclusive `k` range.
215    pub k: (u64, u64),
216    /// 2026-09-30: Inclusive sequence-count range.
217    pub n: (u64, u64),
218    /// 2026-09-30: The contiguity it serves; `None` for either.
219    pub contiguous: Option<bool>,
220    /// 2026-09-30: Whether the verify carries; `None` for either.
221    pub carried: Option<bool>,
222    /// 2026-09-30: Kernel launches, in the order the emitter makes them.
223    pub launches: Vec<(KernelId, Times)>,
224    /// 2026-09-30: Copy-engine transfers besides them, and how often.
225    pub copies: Option<Times>,
226}
227
228impl RunSelect {
229    /// 2026-09-30: Whether this selector serves `run` of a verify that carries or not.
230    pub fn serves(&self, run: VerifyRun, carried: bool) -> bool {
231        (self.k.0..=self.k.1).contains(&run.k)
232            && (self.n.0..=self.n.1).contains(&run.n)
233            && self.contiguous.is_none_or(|c| c == run.contiguous)
234            && self.carried.is_none_or(|c| c == carried)
235    }
236}
237
238/// 2026-09-30: The launches one run of a per-run group makes.
239#[derive(Debug, Clone, PartialEq, Eq)]
240pub struct RunLaunches {
241    /// 2026-09-30: The run.
242    pub run: VerifyRun,
243    /// 2026-09-30: Its launches, in order.
244    pub launches: Vec<(KernelId, Times)>,
245    /// 2026-09-30: Its copies.
246    pub copies: Option<Times>,
247}
248
249impl RunLaunches {
250    /// 2026-09-30: Kernel launches this run makes.
251    pub fn launch_count(&self) -> u64 {
252        self.launches.iter().map(|(_, t)| t.count(self.run)).sum()
253    }
254
255    /// 2026-09-30: Copies this run makes.
256    pub fn copy_count(&self) -> u64 {
257        self.copies.map_or(0, |t| t.count(self.run))
258    }
259}
260
261/// 2026-09-30: Each run of `table` resolved against `selects`: the first selector that serves
262/// it; `None` when some run has none.
263pub fn resolve_runs(table: &RowTable, selects: &[RunSelect]) -> Option<Vec<RunLaunches>> {
264    table
265        .runs
266        .iter()
267        .map(|&run| {
268            selects
269                .iter()
270                .find(|s| s.serves(run, table.carried))
271                .map(|s| RunLaunches {
272                    run,
273                    launches: s.launches.clone(),
274                    copies: s.copies,
275                })
276        })
277        .collect()
278}
279
280#[cfg(test)]
281#[path = "runs_tests.rs"]
282mod runs_tests;
metrale_circuit/runs.rs

metrale_circuit/
runs.rs
