ruda_runtime/runtime/tune/stack/
policy.rs

1//! Shared policy and workload vocabulary. This file also builds in the standalone host harness.
2use std::{fmt, string::{String, ToString}, time::Duration, vec::Vec};
3
4/// Selection policy for adapters participating in the shared controller.
5#[derive(Debug, Clone, Copy, PartialEq, Eq)]
6pub enum Mode {
7    /// Reuse valid choices, otherwise validate and time eligible candidates.
8    Explore,
9    /// Reuse choices without fresh timing search; misses use the reference.
10    /// Cold disk hits still require validation in the current process.
11    CacheOnly,
12    /// Use the declared reference without this controller's cache or trials.
13    /// This does not restore the legacy LocalTuner route.
14    Disabled
15}
16/// Retention order for this controller's bounded process-memory cache.
17#[derive(Debug, Clone, Copy, PartialEq, Eq)]
18pub enum MemoryEviction {
19    /// Evict the oldest inserted key; the existing default.
20    Fifo,
21    /// Promote successful memory lookups and replace the least recently used key.
22    Lru,
23}
24/// Completed-work timing requested from the trial adapter.
25#[derive(Debug, Clone, Copy, PartialEq, Eq)]
26pub enum Timing {
27    /// Use device profiling facilities and wait for the measured work to finish.
28    Device,
29    /// Include candidate-internal allocation, layout conversion, submission and waiting.
30    EndToEnd
31}
32/// Whether the adapter can establish numerical agreement for this trial.
33#[derive(Debug, Clone, Copy, PartialEq, Eq)]
34pub enum Validation {
35    /// The reference/candidate comparison completed and met the tolerance.
36    Passed,
37    /// No validator supports this output or its readback size.
38    /// A numerical mismatch is an error, not this outcome.
39    Unsupported
40}
41
42/// Absolute/relative comparison limits and bounded host readback size.
43#[derive(Debug, Clone, Copy, PartialEq)]
44pub struct Tolerance {
45    /// Nonnegative finite absolute error limit; default `1e-4`.
46    pub absolute: f64,
47    /// Nonnegative finite relative error limit; default `1e-3`.
48    pub relative: f64,
49    /// Maximum combined reference/candidate readback bytes, not a GPU allocator quota.
50    pub max_bytes: u64,
51}
52impl Default for Tolerance {
53    fn default() -> Self { Self { absolute: 1e-4, relative: 1e-3, max_bytes: 64 << 20 } }
54}
55
56/// Immutable limits shared by operator, graph and application selection.
57/// Defaults are selection rules, not measured performance guarantees.
58#[derive(Debug, Clone)]
59pub struct StackPolicy {
60    /// Explore, cache-only or reference-only operation; defaults to Explore.
61    pub mode: Mode,
62    /// Completed timing scope; defaults to EndToEnd.
63    pub timing: Timing,
64    /// Require numerical validation before promoting a choice; defaults to true.
65    pub require_validation: bool,
66    /// Numerical limits and combined reference/candidate readback quota.
67    pub tolerance: Tolerance,
68    /// Positive warmup count in `1..=100`; default 2.
69    pub warmups: usize,
70    /// Odd sample count. Each non-reference sample is paired with a fresh reference measurement.
71    pub samples: usize,
72    /// Positive candidate trial limit up to 4096; default 32.
73    pub max_candidates: usize,
74    /// A soft deadline checked BETWEEN completed trials; running kernels are never interrupted.
75    pub budget: Duration,
76    /// Required reciprocal median timing ratio for promotion; finite and at least 1.
77    /// Default 1.05 is a threshold, not an observed speedup.
78    pub min_speedup: f64,
79    /// Maximum median absolute deviation of paired ratios divided by their median.
80    pub max_relative_mad: f64,
81    /// Optional candidate scratch-byte ceiling. Unknown estimates do not fit
82    /// an enabled limit, including for the declared reference. Default None.
83    pub workspace_limit: Option<u64>,
84    /// Maximum retained keys in `1..=65536`; default 1024.
85    pub capacity: usize,
86    /// Maximum simultaneous trials in `1..=256`; default 1, also per-device serialized.
87    pub max_parallel_tunes: usize,
88    /// Nonzero cache lifetime; default seven days. Future-dated entries expire.
89    pub ttl: Duration,
90    /// Odd nonzero regression window in `3..=101`; default 7.
91    pub regression_pairs: usize,
92    /// Median selected/reference threshold above 1; default 1.15.
93    pub regression_ratio: f64,
94}
95impl Default for StackPolicy {
96    fn default() -> Self {
97        Self {
98            mode: Mode::Explore, timing: Timing::EndToEnd, require_validation: true,
99            tolerance: Tolerance::default(), warmups: 2, samples: 7,
100            max_candidates: 32, budget: Duration::from_secs(30), min_speedup: 1.05,
101            max_relative_mad: 0.15, workspace_limit: None, capacity: 1024,
102            max_parallel_tunes: 1, ttl: Duration::from_secs(7 * 24 * 3600),
103            regression_pairs: 7, regression_ratio: 1.15,
104        }
105    }
106}
107impl StackPolicy {
108    /// Reject invalid counts, bounds, nonfinite numerical limits or zero durations.
109    /// Returns `FailureKind::InvalidInput` without starting a trial or touching disk.
110    pub fn validate(&self) -> Result<(), TuneFailure> {
111        if self.warmups == 0 || self.warmups > 100 || self.samples < 3
112            || self.samples > 101 || self.samples % 2 == 0
113            || self.max_candidates == 0 || self.max_candidates > 4096
114            || self.budget.is_zero() || self.capacity == 0 || self.capacity > 65536
115            || self.max_parallel_tunes == 0 || self.max_parallel_tunes > 256
116            || self.ttl.is_zero() || self.regression_pairs < 3 || self.regression_pairs > 101
117            || self.regression_pairs % 2 == 0
118            || !self.min_speedup.is_finite() || self.min_speedup < 1.0
119            || !self.max_relative_mad.is_finite() || self.max_relative_mad < 0.0
120            || !self.regression_ratio.is_finite() || self.regression_ratio <= 1.0
121            || !self.tolerance.absolute.is_finite() || self.tolerance.absolute < 0.0
122            || !self.tolerance.relative.is_finite() || self.tolerance.relative < 0.0
123            || self.tolerance.max_bytes == 0 {
124            return Err(TuneFailure::invalid("invalid stack autotune policy"));
125        }
126        Ok(())
127    }
128    /// Mode is intentionally excluded: an offline Explore cache is usable by CacheOnly.
129    pub fn accuracy_key(&self) -> String {
130        std::format!("timing={:?};checked={};atol={:016x};rtol={:016x};workspace={:?};min_speedup={:016x};mad={:016x}",
131            self.timing, self.require_validation, self.tolerance.absolute.to_bits(),
132            self.tolerance.relative.to_bits(), self.workspace_limit,
133            self.min_speedup.to_bits(), self.max_relative_mad.to_bits())
134    }
135}
136
137/// Workload level included in cache identity and dependency tracking.
138#[derive(Debug, Clone, Copy, PartialEq, Eq)]
139#[repr(u8)]
140pub enum Scope {
141    /// One complete operator, including its internal setup costs.
142    Operator = 0,
143    /// A fused graph with all externally visible outputs.
144    Graph = 1,
145    /// A complete application plan, such as greedy generation.
146    Pipeline = 2
147}
148
149/// Exact operation/environment signature; shapes are not bucketed or guessed.
150#[derive(Debug, Clone)]
151pub struct Problem {
152    /// Operator, graph or pipeline level.
153    pub scope: Scope,
154    /// Stable library/graph/model operation identity and semantic revision.
155    pub operation: String,
156    /// Backend + physical device + driver/runtime + compiler/build + capabilities.
157    pub environment: String,
158    /// Exact dtype, shape, strides, precision and operation parameters; no lossy bucketing.
159    pub workload: String,
160    /// Caller supplied load/topology/batching/power regime, not inferred from device id.
161    pub execution_context: String,
162    /// False when a reliable driver/build identity cannot be established.
163    pub persistent: bool,
164}
165#[derive(Clone, Copy)]
166pub(super) struct ProblemView<'a> {
167    pub(super) scope: Scope,
168    pub(super) operation: &'a str,
169    pub(super) environment: &'a str,
170    pub(super) workload: &'a str,
171    pub(super) execution_context: &'a str,
172    pub(super) persistent: bool,
173}
174impl<'a> From<&'a Problem> for ProblemView<'a> {
175    fn from(problem: &'a Problem) -> Self {
176        Self { scope: problem.scope, operation: &problem.operation, environment: &problem.environment,
177            workload: &problem.workload, execution_context: &problem.execution_context, persistent: problem.persistent }
178    }
179}
180/// Stable candidate identity and its declared eligibility/scratch requirement.
181#[derive(Debug, Clone)]
182pub struct Candidate {
183    /// Stable algorithm/configuration name, not an index from an old binary.
184    pub name: String,
185    /// Semantic/configuration revision invalidating old choices; default `"1"`.
186    pub revision: String,
187    /// Known temporary workspace bytes, or None when no reliable estimate exists.
188    pub workspace_bytes: Option<u64>,
189    /// Whether the existing operator eligibility rules admit this candidate.
190    pub eligible: bool,
191}
192impl Candidate {
193    /// Create an eligible revision-1 candidate without a workspace estimate.
194    pub fn new(name: impl Into<String>) -> Self {
195        let name = name.into();
196        let view = CandidateView::new(&name);
197        let revision = view.revision.into();
198        let workspace_bytes = view.workspace_bytes;
199        let eligible = view.eligible;
200        Self { name, revision, workspace_bytes, eligible }
201    }
202    /// Check eligibility and the optional workspace ceiling, without executing code.
203    pub fn fits(&self, policy: &StackPolicy) -> bool {
204        self.view().fits(policy)
205    }
206}
207
208#[derive(Clone, Copy)]
209pub(super) struct CandidateView<'a> {
210    pub(super) name: &'a String,
211    pub(super) revision: &'a str,
212    pub(super) workspace_bytes: Option<u64>,
213    pub(super) eligible: bool,
214}
215
216impl<'a> CandidateView<'a> {
217    pub(super) fn new(name: &'a String) -> Self {
218        Self { name, revision: "1", workspace_bytes: None, eligible: true }
219    }
220
221    pub(super) fn fits(&self, policy: &StackPolicy) -> bool {
222        self.eligible && match policy.workspace_limit {
223            Some(limit) => self.workspace_bytes.is_some_and(|n| n <= limit),
224            None => true,
225        }
226    }
227}
228
229pub(super) trait CandidateSource {
230    fn view(&self) -> CandidateView<'_>;
231}
232
233impl CandidateSource for Candidate {
234    fn view(&self) -> CandidateView<'_> {
235        CandidateView { name: &self.name, revision: &self.revision,
236            workspace_bytes: self.workspace_bytes, eligible: self.eligible }
237    }
238}
239
240impl CandidateSource for CandidateView<'_> {
241    fn view(&self) -> CandidateView<'_> { *self }
242}
243
244/// Failure classification used to distinguish rejected trials from device faults.
245#[derive(Debug, Clone, Copy, PartialEq, Eq)]
246pub enum FailureKind {
247    /// Invalid policy, workload or trial metadata.
248    InvalidInput,
249    /// A candidate/reference failed correctness or a safely completed execution.
250    Rejected,
251    /// Validation/timing is unavailable; only the declared reference may be used unchecked.
252    Unavailable,
253    /// Device work could not be confirmed complete; faults the tuning lane.
254    Device,
255    /// This environment's lane was previously faulted and rejects further selection.
256    Quarantined,
257}
258/// Structured selection failure; Display combines the kind and explanatory message.
259#[derive(Debug, Clone)]
260pub struct TuneFailure {
261    /// Failure category controlling adapter error handling.
262    pub kind: FailureKind,
263    /// Human-readable failure reason.
264    pub message: String
265}
266impl TuneFailure {
267    /// Report an invalid caller-supplied policy or signature.
268    pub fn invalid(message: impl Into<String>) -> Self { Self { kind: FailureKind::InvalidInput, message: message.into() } }
269    /// Report incorrect output or a trial rejected after confirmed completion.
270    pub fn rejected(message: impl Into<String>) -> Self { Self { kind: FailureKind::Rejected, message: message.into() } }
271    /// Report a device completion failure, not an ordinary unsupported candidate.
272    pub fn device(message: impl Into<String>) -> Self { Self { kind: FailureKind::Device, message: message.into() } }
273}
274impl fmt::Display for TuneFailure {
275    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { write!(f, "{:?}: {}", self.kind, self.message) }
276}
277impl std::error::Error for TuneFailure {}
278
279/// Canonical, length-delimited encoding prevents concatenation aliases such as (ab,c)/(a,bc).
280pub fn fields(parts: &[&str]) -> String {
281    let mut out = String::new();
282    for part in parts { append_field(&mut out, part); }
283    out
284}
285
286fn append_field(out: &mut String, part: &str) {
287    use std::fmt::Write;
288    let _ = write!(out, "{}:", part.len());
289    out.push_str(part);
290}
291
292struct ByteCounter(usize);
293impl fmt::Write for ByteCounter {
294    fn write_str(&mut self, text: &str) -> fmt::Result { self.0 += text.len(); Ok(()) }
295}
296
297fn append_candidate(out: &mut String, candidate: CandidateView<'_>) {
298    use std::fmt::Write;
299    let mut tag_length = ByteCounter(0);
300    let _ = write!(tag_length, "{:?}/{}", candidate.workspace_bytes, candidate.eligible);
301    let length = [candidate.name.len(), candidate.revision.len(), tag_length.0].into_iter().map(|length| {
302        length + 1 + length.checked_ilog10().map_or(1, |digits| digits as usize + 1)
303    }).sum::<usize>();
304    let _ = write!(out, "{length}:");
305    append_field(out, candidate.name);
306    append_field(out, candidate.revision);
307    let _ = write!(out, "{}:{:?}/{}", tag_length.0, candidate.workspace_bytes, candidate.eligible);
308}
309/// Encode the full workload, ordered candidate manifest, reference and numerical policy.
310/// This returns identity text, not a cryptographic hash or proof of correctness.
311pub fn cache_key(problem: &Problem, candidates: &[Candidate], reference: usize, policy: &StackPolicy) -> String {
312    cache_key_candidates(problem.into(), candidates, reference, policy)
313}
314
315pub(super) fn cache_key_candidates<C: CandidateSource>(problem: ProblemView<'_>, candidates: &[C], reference: usize, policy: &StackPolicy) -> String {
316    let mut manifest = String::new();
317    for c in candidates {
318        append_candidate(&mut manifest, c.view());
319    }
320    fields(&["ruda-stack-autotune-v1", &std::format!("{:?}", problem.scope), problem.operation, problem.environment, problem.workload,
321        problem.execution_context, &reference.to_string(), &manifest,
322        &policy.accuracy_key()])
323}
324/// Sort positive finite ratios in place and return their median.
325/// Empty, zero, negative or nonfinite input returns None.
326pub fn median(values: &mut [f64]) -> Option<f64> {
327    if values.is_empty() || values.iter().any(|v| !v.is_finite() || *v <= 0.0) { return None; }
328    values.sort_by(f64::total_cmp);
329    let m = values.len() / 2;
330    Some(if values.len() % 2 == 0 { values[m - 1] / 2.0 + values[m] / 2.0 } else { values[m] })
331}
332/// Return `(median_selected_over_reference, relative_mad)` for completed pairs.
333/// Requires at least `policy.samples` nonzero pairs and acceptable relative MAD;
334/// an unavailable/noisy score returns None, not a statistically proven speedup.
335pub fn paired_score(pairs: &[(Duration, Duration)], policy: &StackPolicy) -> Option<(f64, f64)> {
336    if pairs.len() < policy.samples || pairs.iter().any(|(a,b)| a.is_zero() || b.is_zero()) { return None; }
337    let mut ratios: Vec<_> = pairs.iter().map(|(a,b)| b.as_secs_f64()/a.as_secs_f64()).collect();
338    let center = median(&mut ratios)?;
339    let mut deviations: Vec<_> = ratios.iter().map(|r| (r-center).abs()).collect();
340    // Unlike timing ratios, zero deviations are valid and desirable.
341    deviations.sort_by(f64::total_cmp);
342    let mad = deviations[deviations.len()/2] / center;
343    if !mad.is_finite() || mad > policy.max_relative_mad { None } else { Some((center, mad)) }
344}
ruda_runtime/runtime/tune/stack/policy.rs

ruda_runtime/runtime/tune/stack/
policy.rs
