Skip to main content

strided_basic/
cost.rs

1//! Serial cost classes and the parallel gate of the strided kernels.
2//!
3//! A kernel does not own a minimum length. It states how long its region takes
4//! on one thread (elements times the serial throughput of its class) and asks
5//! the placement token whether that pays: a region runs in parallel when the
6//! serial time is at least [`threadteam::PAYS`] times the dispatch cost of every
7//! section it opens (`Exec::pays`). The cost of a section belongs to the token
8//! and the thread that calls, not to this crate; the design record is
9//! `threadteam`'s `docs/design/thresholds.md`.
10//!
11//! # The class table
12//!
13//! This table is the only place the throughputs live (the `Copy` row is owned by
14//! `strided-perm`, which sits below this crate). Every kernel of the workspace is
15//! one of four classes, and the rate of a class depends on the *host class*
16//! (`strided_perm::HostClass`, keyed by the kernel dispatch the machine takes,
17//! detected once at first use; the enum is `threadteam::HostClass` re-exported by
18//! `strided-perm`). Serial, `f64`, in nanoseconds per element:
19//!
20//! | [`KernelClass`] | `x86_64-avx512` | `aarch64-apple` | `generic` (every other class) | kernels |
21//! | --- | --- | --- | --- | --- |
22//! | `Copy` | 0.171 | 0.090 | 0.090 | copies, fills, permutations, gathers, static indexing, transposes |
23//! | `Map` | 0.173 | 0.100 | 0.100 | element-wise map, zip, add_acc, mul_acc, axpy_acc, fma_acc, in-place update, fused arithmetic chains |
24//! | `Transcendental` | 5.60 | 1.38 | 1.38 | `exp`, `ln`, `tanh`, other libm-like functions (fused chains that contain one, softmax) |
25//! | `Reduce` | 0.104 | 0.081 | 0.081 | sum, dot, reduce, zip-reduce, axis reductions, norms, scans and arg-reductions |
26//!
27//! * `aarch64-apple`: one Apple M5 Max core, memory resident (thresholds.md
28//!   section 3.2).
29//! * `x86_64-avx512`: an AMD Ryzen AI 9 HX 470 at 2.0 GHz (boost off), from the
30//!   `seq` column of the strided probes (`copy`, `map`, `exp`, `sum`) in
31//!   `faer-benchmark` `data/probes/20261026-awake-team-linux/tables-confirm-exec3.md`
32//!   (width 8 table): the median over the L2-resident sizes 16384, 32768 and
33//!   65536 elements of `seq us * 1000 / elements`. Copy 2.80, 4.29, 13.17 us give
34//!   0.171, 0.131, 0.201; map 2.84, 5.21, 15.39 us give 0.173, 0.159, 0.235; exp
35//!   91.77, 180, 419 us give 5.60, 5.49, 6.39; sum 1.71, 3.55, 6.65 us give 0.104,
36//!   0.108, 0.102.
37//! * `generic` (`x86_64-avx2`, `x86_64-scalar`, `aarch64`, `generic`: no
38//!   measurement): the fastest known value of each row, the minimum over the
39//!   measured classes. It is the conservative choice: a rate that is too small
40//!   keeps work serial.
41//!
42//! The rates of a class and the dispatch costs of the same class in `threadteam`
43//! come from the same machine in the same clock state: boost on or off moves both
44//! by about 1.66x and leaves their ratio stable within a few percent
45//! (`raw-exec3-boost`, `tables-*-exec3-boost.md`).
46//!
47//! A reduction counts the source elements it reads (outputs times reduced
48//! elements). A kernel with a cost not in the table is classified by the nearest
49//! row, never given a constant of its own.
50//!
51//! A [`CopyPlan`](crate::CopyPlan) prices itself above the `Copy` row by the runs
52//! its walk takes: `Copy` row + one cache line per run
53//! (`copy_ns_per_element_for_plan`, which carries the measurement of both
54//! regimes; strided-rs#364). A run is a contiguous stretch of the walk on both
55//! sides, so a transposing plan walks one element per run and pays a line per
56//! element: a hit inside the class's L2, one DRAM line past it. The footprint and
57//! the run structure are both known in `CopyPlan::compile`, so the plan carries
58//! them and nothing is probed at run time, and the rate reaches every scheduling
59//! decision the replay makes: the width of the replay that is not tiled
60//! (`for_len_at_rate`) and both the fork gate and every node of the recursive
61//! splitter of the tiled replay of strided-rs#422 (`is_parallel_at_rate`). A
62//! contiguous run keeps the row at every size:
63//! a streamed unit-stride copy measures the row's rate past L2 as well, which is
64//! why the row itself is not raised. Every other kernel still prices itself at
65//! the row.
66//!
67//! # Sections
68//!
69//! `sections` is the number of dispatches the entry performs, counted truthfully:
70//!
71//! * A *flat* entry (`Exec::for_ranges`: the copy and fill helpers, the
72//!   permutation engine, the axis-chunked kernels) publishes the region once:
73//!   1 section at the chosen width.
74//! * A *tree* entry (the recursive halving of `parallel_map_reduce` and of the
75//!   dimension splitter) forks twice per level and the children fork again on
76//!   half of the budget, so the critical path holds `ceil(log2 width)` sections.
77//!   The splitter gates every node on its own fork (1 section at width 2) because
78//!   each child decides again for the work it has left.
79
80use core::num::NonZeroUsize;
81use core::time::Duration;
82use strided_perm::{copy_ns_per_element_of, HostClass};
83use threadteam::Exec;
84
85/// Working set, in bytes, past which a copy pays L3/DRAM traffic instead of the
86/// L2-resident rate: the L2 size of both hosts behind the `x86_64-avx512` `Copy`
87/// row (1 MiB per core on the Zen 5 host of the worklog of `strided-rs#364` and
88/// on the Xeon Platinum 9242 of `strided-rs#363`).
89const COPY_L2_BYTES: usize = 1 << 20;
90
91/// Serial throughput of a copy whose working set is past the class's L2 cache and
92/// whose runs are one element long, in nanoseconds per element: the sum of the
93/// `Copy` row and one DRAM line per element, 3.0 on the `x86_64-avx512` class
94/// (the derivation is below).
95const COPY_BEYOND_L2_NS_PER_RUN: f64 = 3.0;
96
97/// Extra nanoseconds per run of the walk while the working set fits the class's
98/// L2 cache: one further cache line touched per run, on the line-hitting side.
99///
100/// Derived from the three in-L2 transposing rows of strided-rs#363's table (Intel
101/// Xeon Platinum 9242, serial and warm, `f64`, one-element runs) minus the 0.171
102/// row: `n` = 64 measures 0.65-0.68 (0.48-0.51 over the row), 128 measures 0.78
103/// (0.61 over) and 256 measures 0.90-0.94 (0.73-0.77 over). The median is 0.609
104/// and is rounded to 0.61, which puts every one of those rows within 1.25x: 64
105/// prices at 0.781 against 0.65-0.68 (1.20x), 128 at 0.781 against the measured
106/// 0.78, and 256 at 0.781 against 0.90-0.94 (1.20x).
107const COPY_NS_PER_RUN_RESIDENT: f64 = 0.61;
108
109/// Serial throughput of a copy in nanoseconds per element on `host` for a plan
110/// whose source and destination span `bytes` bytes together and whose walk covers
111/// `run_len` elements per run: `Copy` row + [`COPY_NS_PER_RUN_RESIDENT`] (or one
112/// DRAM line, past [`COPY_L2_BYTES`]) per run, i.e. the `segments * per_segment +
113/// elements * per_element` cost of strided-rs#364 divided by `elements`, since
114/// `segments = elements / run_len`.
115///
116/// A run is a contiguous stretch of the walk on both sides; a transposing plan
117/// walks one element per run, so it pays a cache line per element. Inside the
118/// class's L2 that line is a hit ([`COPY_NS_PER_RUN_RESIDENT`]); past it the plan
119/// touches a new line per element: it reads a line to take one `f64` out of it and
120/// writes a line to put it down, so the cost is the L3/DRAM traffic of the plan and
121/// the line is [`COPY_BEYOND_L2_NS_PER_RUN`] minus the row.
122///
123/// Past [`COPY_L2_BYTES`] this is a calibration of the *tiled* transposing path;
124/// the replay that is not tiled is not calibrated row by row. A transposing
125/// `n x n` `f64` copy measures 2.33-2.45 ns per element at `n` = 512 and 1024 on
126/// the Zen 5 host of
127/// `docs/worklogs/2026-11-09-issue-364-copy-plan-footprint.md`, and 2.91-3.24 on
128/// the Xeon Platinum 9242 (`n` = 512 and 1024, quoted from the table of #364), so
129/// the beyond-L2 rate is 3.0: 3.0 / 2.33 = 1.29, 3.0 / 3.24 = 0.93, i.e. within
130/// 1.3x of every one of those medians, and 9.7 / 3.0 = 3.2 below the 7.2-9.7 the
131/// same host measured before strided-rs#422 tiled its transposed path.
132///
133/// A *contiguous* copy is not priced here: it streams 0.176-0.177 ns per element
134/// at 2 and 16 MiB on that host, which is the row within 4%, so a plan that is one
135/// unit-stride run keeps the row at every footprint (the caller does not ask this
136/// function for such a plan). Every class without a beyond-L2 measurement keeps the
137/// row at every size: only `x86_64-avx512` has the second rate.
138///
139/// A traversal whose runs are shorter than a cache line may be worse than 3.0: a
140/// rank-1 run at stride 256 (one element per 2 KiB) measured 9.6-12.7 ns per element
141/// under a co-tenant process. A contended sample cannot establish the uncontended
142/// value, so this is recorded as an observation and this rate is not claimed to
143/// under- or over-price that extreme.
144pub(crate) fn copy_ns_per_element_for_plan(host: HostClass, bytes: usize, run_len: usize) -> f64 {
145    let row = copy_ns_per_element_of(host);
146    if !matches!(host, HostClass::X86_64Avx512) {
147        return row;
148    }
149    let per_run = if bytes > COPY_L2_BYTES {
150        COPY_BEYOND_L2_NS_PER_RUN - row
151    } else {
152        COPY_NS_PER_RUN_RESIDENT
153    };
154    row + per_run / run_len.max(1) as f64
155}
156
157/// Serial cost class of a kernel; see the module documentation of `strided-basic/src/cost.rs` for the
158/// table.
159///
160/// # Examples
161///
162/// ```
163/// use strided_basic::execution::KernelClass;
164///
165/// assert!(KernelClass::Transcendental.ns_per_element() > KernelClass::Map.ns_per_element());
166/// // 1e6 elements at the rate of this host's class.
167/// let ns = KernelClass::Map.ns_per_element() * 1e6;
168/// assert_eq!(KernelClass::Map.estimate(1_000_000).as_nanos() as f64, ns.round());
169/// ```
170#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
171pub enum KernelClass {
172    /// Copies, fills, permutations and index gathers.
173    ///
174    /// A `CopyPlan` prices itself above this row by one cache line per run of its
175    /// walk, and past the class's L2 cache by one DRAM line per run
176    /// (`strided-basic/src/cost.rs`'s `copy_ns_per_element_for_plan`,
177    /// strided-rs#364).
178    Copy,
179    /// Element-wise arithmetic and fused arithmetic chains.
180    Map,
181    /// `exp`-like functions.
182    Transcendental,
183    /// Reductions and line kernels that read each source element once.
184    Reduce,
185}
186
187impl KernelClass {
188    /// Serial throughput of the class in nanoseconds per element on this host
189    /// ([`ns_per_element_of`](Self::ns_per_element_of) of `HostClass::detect()`).
190    pub fn ns_per_element(self) -> f64 {
191        self.ns_per_element_of(HostClass::detect())
192    }
193
194    /// Serial throughput of the class in nanoseconds per element on a host class
195    /// (the table in the module documentation).
196    pub const fn ns_per_element_of(self, host: HostClass) -> f64 {
197        match host {
198            HostClass::X86_64Avx512 => match self {
199                KernelClass::Copy => copy_ns_per_element_of(host),
200                KernelClass::Map => 0.173,
201                KernelClass::Transcendental => 5.60,
202                KernelClass::Reduce => 0.104,
203            },
204            HostClass::Aarch64Apple => match self {
205                KernelClass::Copy => copy_ns_per_element_of(host),
206                KernelClass::Map => 0.100,
207                KernelClass::Transcendental => 1.38,
208                KernelClass::Reduce => 0.081,
209            },
210            HostClass::X86_64Avx2
211            | HostClass::X86_64Scalar
212            | HostClass::Aarch64
213            | HostClass::Generic => match self {
214                KernelClass::Copy => copy_ns_per_element_of(HostClass::Generic),
215                KernelClass::Map => 0.100,
216                KernelClass::Transcendental => 1.38,
217                KernelClass::Reduce => 0.081,
218            },
219        }
220    }
221
222    /// Serial time of `elements` elements of this class.
223    pub fn estimate(self, elements: usize) -> Duration {
224        Duration::from_secs_f64(elements as f64 * self.ns_per_element() * 1e-9)
225    }
226}
227
228const ONE: NonZeroUsize = NonZeroUsize::MIN;
229
230/// Width of a flat entry (one section) that `exec` should use for `elements`
231/// elements of `class`: the width in `1..=budget` that minimises the section
232/// cost plus the share of the work, `1` when no width pays.
233///
234/// # Examples
235///
236/// ```
237/// use strided_basic::execution::{parallel_width, KernelClass};
238/// use strided_basic::Exec;
239///
240/// assert_eq!(parallel_width(&Exec::serial(), KernelClass::Copy, usize::MAX >> 8).get(), 1);
241/// ```
242pub fn parallel_width(exec: &Exec<'_>, class: KernelClass, elements: usize) -> NonZeroUsize {
243    if exec.is_serial() {
244        return ONE;
245    }
246    exec.width_for(class.estimate(elements), 1)
247}
248
249/// Width of a tree entry (`parallel_map_reduce`): the width in `1..=budget`
250/// that minimises `ceil(log2 k) * D(k) + estimate / k` among the widths at which
251/// `ceil(log2 k)` sections pay, `1` when none does.
252///
253/// # Examples
254///
255/// ```
256/// use strided_basic::execution::{tree_width, KernelClass};
257/// use strided_basic::Exec;
258///
259/// assert_eq!(tree_width(&Exec::serial(), KernelClass::Reduce, usize::MAX >> 8).get(), 1);
260/// ```
261pub fn tree_width(exec: &Exec<'_>, class: KernelClass, elements: usize) -> NonZeroUsize {
262    if exec.is_serial() {
263        return ONE;
264    }
265    let estimate = class.estimate(elements);
266    let mut best = (ONE, estimate);
267    for k in 2..=exec.budget().get() {
268        let width = NonZeroUsize::new(k).unwrap_or(ONE);
269        let sections = k.next_power_of_two().trailing_zeros();
270        if !exec.pays(estimate, sections, width) {
271            continue;
272        }
273        let time = estimate / u32::try_from(k).unwrap_or(u32::MAX)
274            + exec.dispatch_cost(width).saturating_mul(sections);
275        if time < best.1 {
276            best = (width, time);
277        }
278    }
279    best.0
280}
281
282/// Narrows `exec` to the width a flat entry over `len` elements of `class` justifies.
283pub(crate) fn for_len<'a>(exec: Exec<'a>, class: KernelClass, len: usize) -> Exec<'a> {
284    for_len_at_rate(exec, len, class.ns_per_element())
285}
286
287/// Narrows `exec` to the width a flat entry over `len` elements costing
288/// `ns_per_element` each justifies.
289///
290/// [`for_len`] is this function at the rate of a class. A `CopyPlan` passes a rate
291/// of its own: one whose traversal is not a single contiguous run pays a cache
292/// line per run on top of the row
293/// (`copy_ns_per_element_for_plan`, strided-rs#364).
294pub(crate) fn for_len_at_rate<'a>(exec: Exec<'a>, len: usize, ns_per_element: f64) -> Exec<'a> {
295    if exec.is_serial() {
296        return exec;
297    }
298    let estimate = Duration::from_secs_f64(len as f64 * ns_per_element * 1e-9);
299    let width = exec.width_for(estimate, 1);
300    exec.limit(width)
301}
302
303/// Narrows `exec` to the width a tree entry over `len` elements of `class` justifies.
304pub(crate) fn for_len_tree<'a>(exec: Exec<'a>, class: KernelClass, len: usize) -> Exec<'a> {
305    let width = tree_width(&exec, class, len);
306    exec.limit(width)
307}
308
309/// Whether one fork of `exec` over `len` elements of `class` pays: the gate of a
310/// node of the dimension splitter and of the entries that call it.
311pub(crate) fn is_parallel(class: KernelClass, len: usize, exec: &Exec<'_>) -> bool {
312    is_parallel_at_rate(len, class.ns_per_element(), exec)
313}
314
315/// Whether one fork of `exec` over `len` elements costing `ns_per_element` each
316/// pays: the gate of a node of the dimension splitter, at the rate its caller
317/// prices the work at.
318///
319/// [`is_parallel`] is this function at the rate of a class. A `CopyPlan` passes its
320/// own rate, so the tiled splitter of strided-rs#422 opens the same fork the plan's
321/// width rule asks for (`copy_ns_per_element_for_plan`, strided-rs#364).
322pub(crate) fn is_parallel_at_rate(len: usize, ns_per_element: f64, exec: &Exec<'_>) -> bool {
323    if exec.is_serial() {
324        return false;
325    }
326    let two = NonZeroUsize::new(2).unwrap_or(ONE);
327    let estimate = Duration::from_secs_f64(len as f64 * ns_per_element * 1e-9);
328    exec.pays(estimate, 1, two.min(exec.budget()))
329}
330
331#[cfg(test)]
332mod tests;