trueno/simulation/scheduler/
mod.rs

1//! Heijunka Scheduler (Leveled Testing)
2//!
3//! Implements Toyota Production System's Heijunka principle:
4//! level the workload to reduce waste and variability.
5
6use crate::Backend;
7use std::collections::VecDeque;
8use std::marker::PhantomData;
9
10/// Backend-specific tolerance configuration
11///
12/// Implements Poka-Yoke (mistake-proofing) by providing compile-time
13/// guarantees for correct tolerance values per backend type.
14#[derive(Debug, Clone, Copy, PartialEq)]
15pub struct BackendTolerance {
16    /// Scalar vs SIMD tolerance (should be exact: 0.0)
17    pub scalar_vs_simd: f32,
18    /// SIMD vs GPU tolerance (IEEE 754: 1e-5)
19    pub simd_vs_gpu: f32,
20    /// GPU vs GPU tolerance (same precision: 1e-6)
21    pub gpu_vs_gpu: f32,
22}
23
24impl Default for BackendTolerance {
25    fn default() -> Self {
26        Self { scalar_vs_simd: 0.0, simd_vs_gpu: 1e-5, gpu_vs_gpu: 1e-6 }
27    }
28}
29
30impl BackendTolerance {
31    /// Strict tolerance for exact comparisons
32    #[must_use]
33    pub const fn strict() -> Self {
34        Self { scalar_vs_simd: 0.0, simd_vs_gpu: 0.0, gpu_vs_gpu: 0.0 }
35    }
36
37    /// Relaxed tolerance for approximate comparisons
38    #[must_use]
39    pub const fn relaxed() -> Self {
40        Self { scalar_vs_simd: 1e-6, simd_vs_gpu: 1e-4, gpu_vs_gpu: 1e-5 }
41    }
42
43    /// Get tolerance for comparing two backends
44    #[must_use]
45    pub fn for_backends(&self, a: Backend, b: Backend) -> f32 {
46        match (a, b) {
47            (Backend::Scalar, Backend::Scalar) => 0.0,
48            (
49                Backend::Scalar,
50                Backend::SSE2
51                | Backend::AVX
52                | Backend::AVX2
53                | Backend::AVX512
54                | Backend::NEON
55                | Backend::WasmSIMD
56                | Backend::Auto,
57            )
58            | (
59                Backend::SSE2
60                | Backend::AVX
61                | Backend::AVX2
62                | Backend::AVX512
63                | Backend::NEON
64                | Backend::WasmSIMD
65                | Backend::Auto,
66                Backend::Scalar,
67            ) => self.scalar_vs_simd,
68            (Backend::GPU, Backend::GPU) => self.gpu_vs_gpu,
69            (
70                Backend::GPU,
71                Backend::Scalar
72                | Backend::SSE2
73                | Backend::AVX
74                | Backend::AVX2
75                | Backend::AVX512
76                | Backend::NEON
77                | Backend::WasmSIMD
78                | Backend::Auto,
79            )
80            | (
81                Backend::Scalar
82                | Backend::SSE2
83                | Backend::AVX
84                | Backend::AVX2
85                | Backend::AVX512
86                | Backend::NEON
87                | Backend::WasmSIMD
88                | Backend::Auto,
89                Backend::GPU,
90            ) => self.simd_vs_gpu,
91            // SIMD vs SIMD (all remaining non-Scalar, non-GPU combinations)
92            (
93                Backend::SSE2
94                | Backend::AVX
95                | Backend::AVX2
96                | Backend::AVX512
97                | Backend::NEON
98                | Backend::WasmSIMD
99                | Backend::Auto,
100                Backend::SSE2
101                | Backend::AVX
102                | Backend::AVX2
103                | Backend::AVX512
104                | Backend::NEON
105                | Backend::WasmSIMD
106                | Backend::Auto,
107            ) => self.scalar_vs_simd,
108        }
109    }
110}
111
112/// Poka-Yoke: Type-safe backend selection
113///
114/// Provides compile-time and runtime guarantees for correct backend selection
115/// based on input size and operation type.
116#[derive(Debug, Clone)]
117pub struct BackendSelector {
118    /// Minimum size for GPU offload (default: 100,000)
119    gpu_threshold: usize,
120    /// Minimum size for parallel execution (default: 1,000)
121    parallel_threshold: usize,
122}
123
124impl Default for BackendSelector {
125    fn default() -> Self {
126        Self { gpu_threshold: 100_000, parallel_threshold: 1_000 }
127    }
128}
129
130impl BackendSelector {
131    /// Create a new backend selector with custom thresholds
132    #[must_use]
133    pub const fn new(gpu_threshold: usize, parallel_threshold: usize) -> Self {
134        Self { gpu_threshold, parallel_threshold }
135    }
136
137    /// Get the GPU threshold
138    #[must_use]
139    pub const fn gpu_threshold(&self) -> usize {
140        self.gpu_threshold
141    }
142
143    /// Get the parallel threshold
144    #[must_use]
145    pub const fn parallel_threshold(&self) -> usize {
146        self.parallel_threshold
147    }
148
149    /// Select backend based on input size
150    ///
151    /// # Decision Logic (TRUENO-SPEC-012)
152    ///
153    /// - N < 1,000: Pure SIMD (no parallelization overhead)
154    /// - 1,000 <= N < 100,000: SIMD + Parallel (Rayon)
155    /// - N >= 100,000: GPU (if available), else SIMD + Parallel
156    #[must_use]
157    pub fn select_for_size(&self, size: usize, gpu_available: bool) -> BackendCategory {
158        if size < self.parallel_threshold {
159            BackendCategory::SimdOnly
160        } else if size < self.gpu_threshold {
161            BackendCategory::SimdParallel
162        } else if gpu_available {
163            BackendCategory::Gpu
164        } else {
165            BackendCategory::SimdParallel // Graceful fallback
166        }
167    }
168
169    /// Check if size is at GPU threshold boundary (for testing)
170    #[must_use]
171    pub fn is_at_gpu_boundary(&self, size: usize) -> bool {
172        size == self.gpu_threshold || size == self.gpu_threshold - 1
173    }
174
175    /// Check if size is at parallel threshold boundary (for testing)
176    #[must_use]
177    pub fn is_at_parallel_boundary(&self, size: usize) -> bool {
178        size == self.parallel_threshold || size == self.parallel_threshold - 1
179    }
180}
181
182/// Backend category for selection result
183#[derive(Debug, Clone, Copy, PartialEq, Eq)]
184pub enum BackendCategory {
185    /// Pure SIMD (N < 1,000)
186    SimdOnly,
187    /// SIMD with parallel execution (1,000 <= N < 100,000)
188    SimdParallel,
189    /// GPU compute (N >= 100,000)
190    Gpu,
191}
192
193/// Simulation test configuration
194#[derive(Debug, Clone)]
195pub struct SimulationTest {
196    /// Backend to test
197    pub backend: Backend,
198    /// Input size
199    pub input_size: usize,
200    /// Test cycle number
201    pub cycle: u32,
202    /// Seed for deterministic RNG
203    pub seed: u64,
204}
205
206/// Heijunka: Balanced test distribution across backends and sizes
207///
208/// Implements Toyota Production System's Heijunka principle:
209/// level the workload to reduce waste and variability.
210#[derive(Debug)]
211pub struct HeijunkaScheduler {
212    /// Test queue balanced across backends
213    queue: VecDeque<SimulationTest>,
214    /// Backends to cycle through
215    backends: Vec<Backend>,
216}
217
218impl HeijunkaScheduler {
219    /// Create a leveled test schedule
220    #[must_use]
221    pub fn new(
222        backends: Vec<Backend>,
223        input_sizes: Vec<usize>,
224        cycles_per_backend: u32,
225        master_seed: u64,
226    ) -> Self {
227        let mut queue = VecDeque::new();
228
229        // Interleave tests across backends (leveling)
230        for size in &input_sizes {
231            for backend in &backends {
232                for cycle in 0..cycles_per_backend {
233                    let seed = compute_seed(*backend, *size, cycle, master_seed);
234                    queue.push_back(SimulationTest {
235                        backend: *backend,
236                        input_size: *size,
237                        cycle,
238                        seed,
239                    });
240                }
241            }
242        }
243
244        Self { queue, backends: backends.clone() }
245    }
246
247    /// Get the next test from the queue
248    pub fn next_test(&mut self) -> Option<SimulationTest> {
249        self.queue.pop_front()
250    }
251
252    /// Get remaining test count
253    #[must_use]
254    pub fn remaining(&self) -> usize {
255        self.queue.len()
256    }
257
258    /// Get backends being tested
259    #[must_use]
260    pub fn backends(&self) -> &[Backend] {
261        &self.backends
262    }
263
264    /// Check if schedule is empty
265    #[must_use]
266    pub fn is_empty(&self) -> bool {
267        self.queue.is_empty()
268    }
269}
270
271/// Compute deterministic seed for a test configuration
272pub(crate) fn compute_seed(backend: Backend, size: usize, cycle: u32, master_seed: u64) -> u64 {
273    let backend_bits = backend as u64;
274    let size_bits = size as u64;
275    let cycle_bits = u64::from(cycle);
276
277    master_seed
278        .wrapping_add(backend_bits.wrapping_mul(0x9E37_79B9_7F4A_7C15))
279        .wrapping_add(size_bits.wrapping_mul(0x6A09_E667_BB67_AE85))
280        .wrapping_add(cycle_bits.wrapping_mul(0x3C6E_F372_FE94_F82B))
281}
282
283/// Simulation test configuration builder
284#[derive(Debug, Clone)]
285pub struct SimTestConfigBuilder<S> {
286    seed: u64,
287    tolerance: BackendTolerance,
288    backends: Vec<Backend>,
289    input_sizes: Vec<usize>,
290    cycles: u32,
291    _state: PhantomData<S>,
292}
293
294/// Builder state: seed not set
295pub struct NeedsSeed;
296/// Builder state: ready to build
297pub struct Ready;
298
299impl Default for SimTestConfigBuilder<NeedsSeed> {
300    fn default() -> Self {
301        Self::new()
302    }
303}
304
305impl SimTestConfigBuilder<NeedsSeed> {
306    /// Create a new config builder
307    #[must_use]
308    pub fn new() -> Self {
309        Self {
310            seed: 0,
311            tolerance: BackendTolerance::default(),
312            backends: vec![Backend::Scalar, Backend::AVX2],
313            input_sizes: vec![100, 1_000, 10_000, 100_000],
314            cycles: 10,
315            _state: PhantomData,
316        }
317    }
318
319    /// Set the master seed (required)
320    #[must_use]
321    pub fn seed(self, seed: u64) -> SimTestConfigBuilder<Ready> {
322        SimTestConfigBuilder {
323            seed,
324            tolerance: self.tolerance,
325            backends: self.backends,
326            input_sizes: self.input_sizes,
327            cycles: self.cycles,
328            _state: PhantomData,
329        }
330    }
331}
332
333impl SimTestConfigBuilder<Ready> {
334    /// Set tolerance configuration
335    #[must_use]
336    pub fn tolerance(mut self, tolerance: BackendTolerance) -> Self {
337        self.tolerance = tolerance;
338        self
339    }
340
341    /// Set backends to test
342    #[must_use]
343    pub fn backends(mut self, backends: Vec<Backend>) -> Self {
344        self.backends = backends;
345        self
346    }
347
348    /// Set input sizes to test
349    #[must_use]
350    pub fn input_sizes(mut self, sizes: Vec<usize>) -> Self {
351        self.input_sizes = sizes;
352        self
353    }
354
355    /// Set number of test cycles
356    #[must_use]
357    pub fn cycles(mut self, cycles: u32) -> Self {
358        self.cycles = cycles;
359        self
360    }
361
362    /// Build the configuration
363    #[must_use]
364    pub fn build(self) -> SimTestConfig {
365        SimTestConfig {
366            seed: self.seed,
367            tolerance: self.tolerance,
368            backends: self.backends,
369            input_sizes: self.input_sizes,
370            cycles: self.cycles,
371        }
372    }
373}
374
375/// Simulation test configuration
376#[derive(Debug, Clone)]
377pub struct SimTestConfig {
378    /// Master seed for deterministic RNG
379    pub seed: u64,
380    /// Backend tolerance configuration
381    pub tolerance: BackendTolerance,
382    /// Backends to test
383    pub backends: Vec<Backend>,
384    /// Input sizes to test
385    pub input_sizes: Vec<usize>,
386    /// Number of test cycles
387    pub cycles: u32,
388}
389
390impl SimTestConfig {
391    /// Create a config builder
392    #[must_use]
393    pub fn builder() -> SimTestConfigBuilder<NeedsSeed> {
394        SimTestConfigBuilder::new()
395    }
396
397    /// Create a Heijunka scheduler from this config
398    #[must_use]
399    pub fn create_scheduler(&self) -> HeijunkaScheduler {
400        HeijunkaScheduler::new(
401            self.backends.clone(),
402            self.input_sizes.clone(),
403            self.cycles,
404            self.seed,
405        )
406    }
407}
408
409#[cfg(test)]
410mod tests;
411
412#[cfg(test)]
413mod proptests;
trueno/simulation/scheduler/mod.rs

trueno/simulation/scheduler/
mod.rs
