/home/noah/src/trueno/src/simulation/scheduler.rs

Source
//! Heijunka Scheduler (Leveled Testing)
//!
//! Implements Toyota Production System's Heijunka principle:
//! level the workload to reduce waste and variability.

use crate::Backend;
use std::collections::VecDeque;
use std::marker::PhantomData;

/// Backend-specific tolerance configuration
///
/// Implements Poka-Yoke (mistake-proofing) by providing compile-time
/// guarantees for correct tolerance values per backend type.
#[derive(Debug, Clone, Copy, PartialEq)]
pub struct BackendTolerance {
    /// Scalar vs SIMD tolerance (should be exact: 0.0)
    pub scalar_vs_simd: f32,
    /// SIMD vs GPU tolerance (IEEE 754: 1e-5)
    pub simd_vs_gpu: f32,
    /// GPU vs GPU tolerance (same precision: 1e-6)
    pub gpu_vs_gpu: f32,
}

impl Default for BackendTolerance {
    fn default() -> Self {
        Self {
            scalar_vs_simd: 0.0,
            simd_vs_gpu: 1e-5,
            gpu_vs_gpu: 1e-6,
        }
    }
}

impl BackendTolerance {
    /// Strict tolerance for exact comparisons
    #[must_use]
    pub const fn strict() -> Self {
        Self {
            scalar_vs_simd: 0.0,
            simd_vs_gpu: 0.0,
            gpu_vs_gpu: 0.0,
        }
    }

    /// Relaxed tolerance for approximate comparisons
    #[must_use]
    pub const fn relaxed() -> Self {
        Self {
            scalar_vs_simd: 1e-6,
            simd_vs_gpu: 1e-4,
            gpu_vs_gpu: 1e-5,
        }
    }

    /// Get tolerance for comparing two backends
    #[must_use]
    pub fn for_backends(&self, a: Backend, b: Backend) -> f32 {
        match (a, b) {
            (Backend::Scalar, Backend::Scalar) => 0.0,
            (Backend::Scalar, Backend::SSE2 | Backend::AVX | Backend::AVX2 | Backend::AVX512)
            | (Backend::SSE2 | Backend::AVX | Backend::AVX2 | Backend::AVX512, Backend::Scalar) => {
                self.scalar_vs_simd
            }
            (Backend::GPU, Backend::GPU) => self.gpu_vs_gpu,
            (Backend::GPU, _) | (_, Backend::GPU) => self.simd_vs_gpu,
            _ => self.scalar_vs_simd, // SIMD vs SIMD
        }
    }
}

/// Poka-Yoke: Type-safe backend selection
///
/// Provides compile-time and runtime guarantees for correct backend selection
/// based on input size and operation type.
#[derive(Debug, Clone)]
pub struct BackendSelector {
    /// Minimum size for GPU offload (default: 100,000)
    gpu_threshold: usize,
    /// Minimum size for parallel execution (default: 1,000)
    parallel_threshold: usize,
}

impl Default for BackendSelector {
    fn default() -> Self {
        Self {
            gpu_threshold: 100_000,
            parallel_threshold: 1_000,
        }
    }
}

impl BackendSelector {
    /// Create a new backend selector with custom thresholds
    #[must_use]
    pub const fn new(gpu_threshold: usize, parallel_threshold: usize) -> Self {
        Self {
            gpu_threshold,
            parallel_threshold,
        }
    }

    /// Get the GPU threshold
    #[must_use]
    pub const fn gpu_threshold(&self) -> usize {
        self.gpu_threshold
    }

    /// Get the parallel threshold
    #[must_use]
    pub const fn parallel_threshold(&self) -> usize {
        self.parallel_threshold
    }

    /// Select backend based on input size
    ///
    /// # Decision Logic (TRUENO-SPEC-012)
    ///
    /// - N < 1,000: Pure SIMD (no parallelization overhead)
    /// - 1,000 <= N < 100,000: SIMD + Parallel (Rayon)
    /// - N >= 100,000: GPU (if available), else SIMD + Parallel
    #[must_use]
    pub fn select_for_size(&self, size: usize, gpu_available: bool) -> BackendCategory {
        if size < self.parallel_threshold {
            BackendCategory::SimdOnly
        } else if size < self.gpu_threshold {
            BackendCategory::SimdParallel
        } else if gpu_available {
            BackendCategory::Gpu
        } else {
            BackendCategory::SimdParallel // Graceful fallback
        }
    }

    /// Check if size is at GPU threshold boundary (for testing)
    #[must_use]
    pub fn is_at_gpu_boundary(&self, size: usize) -> bool {
        size == self.gpu_threshold || size == self.gpu_threshold - 1
    }

    /// Check if size is at parallel threshold boundary (for testing)
    #[must_use]
    pub fn is_at_parallel_boundary(&self, size: usize) -> bool {
        size == self.parallel_threshold || size == self.parallel_threshold - 1
    }
}

/// Backend category for selection result
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum BackendCategory {
    /// Pure SIMD (N < 1,000)
    SimdOnly,
    /// SIMD with parallel execution (1,000 <= N < 100,000)
    SimdParallel,
    /// GPU compute (N >= 100,000)
    Gpu,
}

/// Simulation test configuration
#[derive(Debug, Clone)]
pub struct SimulationTest {
    /// Backend to test
    pub backend: Backend,
    /// Input size
    pub input_size: usize,
    /// Test cycle number
    pub cycle: u32,
    /// Seed for deterministic RNG
    pub seed: u64,
}

/// Heijunka: Balanced test distribution across backends and sizes
///
/// Implements Toyota Production System's Heijunka principle:
/// level the workload to reduce waste and variability.
#[derive(Debug)]
pub struct HeijunkaScheduler {
    /// Test queue balanced across backends
    queue: VecDeque<SimulationTest>,
    /// Backends to cycle through
    backends: Vec<Backend>,
}

impl HeijunkaScheduler {
    /// Create a leveled test schedule
    #[must_use]
    pub fn new(
        backends: Vec<Backend>,
        input_sizes: Vec<usize>,
        cycles_per_backend: u32,
        master_seed: u64,
    ) -> Self {
        let mut queue = VecDeque::new();

        // Interleave tests across backends (leveling)
        for size in &input_sizes {
            for backend in &backends {
                for cycle in 0..cycles_per_backend {
                    let seed = compute_seed(*backend, *size, cycle, master_seed);
                    queue.push_back(SimulationTest {
                        backend: *backend,
                        input_size: *size,
                        cycle,
                        seed,
                    });
                }
            }
        }

        Self {
            queue,
            backends: backends.clone(),
        }
    }

    /// Get the next test from the queue
    pub fn next_test(&mut self) -> Option<SimulationTest> {
        self.queue.pop_front()
    }

    /// Get remaining test count
    #[must_use]
    pub fn remaining(&self) -> usize {
        self.queue.len()
    }

    /// Get backends being tested
    #[must_use]
    pub fn backends(&self) -> &[Backend] {
        &self.backends
    }

    /// Check if schedule is empty
    #[must_use]
    pub fn is_empty(&self) -> bool {
        self.queue.is_empty()
    }
}

/// Compute deterministic seed for a test configuration
pub(crate) fn compute_seed(backend: Backend, size: usize, cycle: u32, master_seed: u64) -> u64 {
    let backend_bits = backend as u64;
    let size_bits = size as u64;
    let cycle_bits = u64::from(cycle);

    master_seed
        .wrapping_add(backend_bits.wrapping_mul(0x9E37_79B9_7F4A_7C15))
        .wrapping_add(size_bits.wrapping_mul(0x6A09_E667_BB67_AE85))
        .wrapping_add(cycle_bits.wrapping_mul(0x3C6E_F372_FE94_F82B))
}

/// Simulation test configuration builder
#[derive(Debug, Clone)]
pub struct SimTestConfigBuilder<S> {
    seed: u64,
    tolerance: BackendTolerance,
    backends: Vec<Backend>,
    input_sizes: Vec<usize>,
    cycles: u32,
    _state: PhantomData<S>,
}

/// Builder state: seed not set
pub struct NeedsSeed;
/// Builder state: ready to build
pub struct Ready;

impl Default for SimTestConfigBuilder<NeedsSeed> {
    fn default() -> Self {
        Self::new()
    }
}

impl SimTestConfigBuilder<NeedsSeed> {
    /// Create a new config builder
    #[must_use]
    pub fn new() -> Self {
        Self {
            seed: 0,
            tolerance: BackendTolerance::default(),
            backends: vec![Backend::Scalar, Backend::AVX2],
            input_sizes: vec![100, 1_000, 10_000, 100_000],
            cycles: 10,
            _state: PhantomData,
        }
    }

    /// Set the master seed (required)
    #[must_use]
    pub fn seed(self, seed: u64) -> SimTestConfigBuilder<Ready> {
        SimTestConfigBuilder {
            seed,
            tolerance: self.tolerance,
            backends: self.backends,
            input_sizes: self.input_sizes,
            cycles: self.cycles,
            _state: PhantomData,
        }
    }
}

impl SimTestConfigBuilder<Ready> {
    /// Set tolerance configuration
    #[must_use]
    pub fn tolerance(mut self, tolerance: BackendTolerance) -> Self {
        self.tolerance = tolerance;
        self
    }

    /// Set backends to test
    #[must_use]
    pub fn backends(mut self, backends: Vec<Backend>) -> Self {
        self.backends = backends;
        self
    }

    /// Set input sizes to test
    #[must_use]
    pub fn input_sizes(mut self, sizes: Vec<usize>) -> Self {
        self.input_sizes = sizes;
        self
    }

    /// Set number of test cycles
    #[must_use]
    pub fn cycles(mut self, cycles: u32) -> Self {
        self.cycles = cycles;
        self
    }

    /// Build the configuration
    #[must_use]
    pub fn build(self) -> SimTestConfig {
        SimTestConfig {
            seed: self.seed,
            tolerance: self.tolerance,
            backends: self.backends,
            input_sizes: self.input_sizes,
            cycles: self.cycles,
        }
    }
}

/// Simulation test configuration
#[derive(Debug, Clone)]
pub struct SimTestConfig {
    /// Master seed for deterministic RNG
    pub seed: u64,
    /// Backend tolerance configuration
    pub tolerance: BackendTolerance,
    /// Backends to test
    pub backends: Vec<Backend>,
    /// Input sizes to test
    pub input_sizes: Vec<usize>,
    /// Number of test cycles
    pub cycles: u32,
}

impl SimTestConfig {
    /// Create a config builder
    #[must_use]
    pub fn builder() -> SimTestConfigBuilder<NeedsSeed> {
        SimTestConfigBuilder::new()
    }

    /// Create a Heijunka scheduler from this config
    #[must_use]
    pub fn create_scheduler(&self) -> HeijunkaScheduler {
        HeijunkaScheduler::new(
            self.backends.clone(),
            self.input_sizes.clone(),
            self.cycles,
            self.seed,
        )
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_backend_selector_default_thresholds() {
        // Falsifiable claim A-005, A-006
        let selector = BackendSelector::default();

        assert_eq!(selector.gpu_threshold(), 100_000);
        assert_eq!(selector.parallel_threshold(), 1_000);
    }

    #[test]
    fn test_backend_selector_simd_only() {
        // N < 1,000 should use SIMD only
        let selector = BackendSelector::default();

        assert_eq!(
            selector.select_for_size(100, false),
            BackendCategory::SimdOnly
        );
        assert_eq!(
            selector.select_for_size(999, false),
            BackendCategory::SimdOnly
        );
        assert_eq!(
            selector.select_for_size(999, true),
            BackendCategory::SimdOnly
        );
    }

    #[test]
    fn test_backend_selector_simd_parallel() {
        // 1,000 <= N < 100,000 should use SIMD + Parallel
        let selector = BackendSelector::default();

        assert_eq!(
            selector.select_for_size(1_000, false),
            BackendCategory::SimdParallel
        );
        assert_eq!(
            selector.select_for_size(50_000, false),
            BackendCategory::SimdParallel
        );
        assert_eq!(
            selector.select_for_size(99_999, false),
            BackendCategory::SimdParallel
        );
    }

    #[test]
    fn test_backend_selector_gpu() {
        // N >= 100,000 should use GPU (if available)
        let selector = BackendSelector::default();

        assert_eq!(
            selector.select_for_size(100_000, true),
            BackendCategory::Gpu
        );
        assert_eq!(
            selector.select_for_size(1_000_000, true),
            BackendCategory::Gpu
        );
    }

    #[test]
    fn test_backend_selector_gpu_fallback() {
        // N >= 100,000 without GPU should fallback to SIMD + Parallel
        let selector = BackendSelector::default();

        assert_eq!(
            selector.select_for_size(100_000, false),
            BackendCategory::SimdParallel
        );
    }

    #[test]
    fn test_backend_selector_boundary() {
        // Falsifiable claim A-005
        let selector = BackendSelector::default();

        // At GPU threshold boundary
        assert!(selector.is_at_gpu_boundary(100_000));
        assert!(selector.is_at_gpu_boundary(99_999));
        assert!(!selector.is_at_gpu_boundary(99_998));

        // At parallel threshold boundary
        assert!(selector.is_at_parallel_boundary(1_000));
        assert!(selector.is_at_parallel_boundary(999));
        assert!(!selector.is_at_parallel_boundary(998));
    }

    #[test]
    fn test_backend_tolerance_default() {
        let tolerance = BackendTolerance::default();

        assert_eq!(tolerance.scalar_vs_simd, 0.0);
        assert!((tolerance.simd_vs_gpu - 1e-5).abs() < 1e-10);
        assert!((tolerance.gpu_vs_gpu - 1e-6).abs() < 1e-10);
    }

    #[test]
    fn test_backend_tolerance_strict() {
        let tolerance = BackendTolerance::strict();

        assert_eq!(tolerance.scalar_vs_simd, 0.0);
        assert_eq!(tolerance.simd_vs_gpu, 0.0);
        assert_eq!(tolerance.gpu_vs_gpu, 0.0);
    }

    #[test]
    fn test_backend_tolerance_for_backends() {
        // Falsifiable claim A-002, A-003, A-004
        let tolerance = BackendTolerance::default();

        // Scalar vs Scalar
        assert_eq!(
            tolerance.for_backends(Backend::Scalar, Backend::Scalar),
            0.0
        );

        // Scalar vs SIMD (should be exact)
        assert_eq!(tolerance.for_backends(Backend::Scalar, Backend::AVX2), 0.0);

        // GPU vs GPU
        assert_eq!(
            tolerance.for_backends(Backend::GPU, Backend::GPU),
            tolerance.gpu_vs_gpu
        );

        // SIMD vs GPU
        assert_eq!(
            tolerance.for_backends(Backend::AVX2, Backend::GPU),
            tolerance.simd_vs_gpu
        );
    }

    #[test]
    fn test_heijunka_schedule_creation() {
        let backends = vec![Backend::Scalar, Backend::AVX2];
        let sizes = vec![100, 1000];
        let cycles = 2;

        let scheduler = HeijunkaScheduler::new(backends.clone(), sizes, cycles, 42);

        // Should have backends.len() * sizes.len() * cycles tests
        // 2 backends * 2 sizes * 2 cycles = 8 tests
        assert_eq!(scheduler.remaining(), 8);
    }

    #[test]
    fn test_heijunka_deterministic_seeds() {
        // Falsifiable claim B-017
        let backends = vec![Backend::Scalar, Backend::AVX2];
        let sizes = vec![100, 1000];
        let cycles = 2;

        let mut scheduler1 = HeijunkaScheduler::new(backends.clone(), sizes.clone(), cycles, 42);
        let mut scheduler2 = HeijunkaScheduler::new(backends, sizes, cycles, 42);

        // Seeds should be identical for same configuration
        while let (Some(t1), Some(t2)) = (scheduler1.next_test(), scheduler2.next_test()) {
            assert_eq!(t1.seed, t2.seed, "Seeds must be deterministic");
        }
    }

    #[test]
    fn test_heijunka_consumes_all_tests() {
        let backends = vec![Backend::Scalar];
        let sizes = vec![100];
        let cycles = 5;

        let mut scheduler = HeijunkaScheduler::new(backends, sizes, cycles, 42);

        let mut count = 0;
        while scheduler.next_test().is_some() {
            count += 1;
        }

        assert_eq!(count, 5);
        assert!(scheduler.is_empty());
    }

    #[test]
    fn test_heijunka_different_master_seeds() {
        // Falsifiable claim B-018
        let backends = vec![Backend::Scalar];
        let sizes = vec![100];
        let cycles = 1;

        let mut scheduler1 = HeijunkaScheduler::new(backends.clone(), sizes.clone(), cycles, 42);
        let mut scheduler2 = HeijunkaScheduler::new(backends, sizes, cycles, 43);

        let t1 = scheduler1.next_test().unwrap();
        let t2 = scheduler2.next_test().unwrap();

        assert_ne!(
            t1.seed, t2.seed,
            "Different master seeds must produce different test seeds"
        );
    }

    #[test]
    fn test_sim_test_config_builder() {
        let config = SimTestConfig::builder()
            .seed(42)
            .tolerance(BackendTolerance::strict())
            .backends(vec![Backend::Scalar, Backend::AVX2, Backend::GPU])
            .input_sizes(vec![100, 1000, 10000])
            .cycles(5)
            .build();

        assert_eq!(config.seed, 42);
        assert_eq!(config.backends.len(), 3);
        assert_eq!(config.input_sizes.len(), 3);
        assert_eq!(config.cycles, 5);
    }

    #[test]
    fn test_sim_test_config_creates_scheduler() {
        let config = SimTestConfig::builder()
            .seed(42)
            .backends(vec![Backend::Scalar, Backend::AVX2])
            .input_sizes(vec![100, 1000])
            .cycles(3)
            .build();

        let scheduler = config.create_scheduler();

        // 2 backends * 2 sizes * 3 cycles = 12 tests
        assert_eq!(scheduler.remaining(), 12);
    }

    #[test]
    fn test_backend_category_debug() {
        let category = BackendCategory::Gpu;
        let debug = format!("{category:?}");
        assert!(debug.contains("Gpu"));
    }
}

#[cfg(test)]
mod proptests {
    use super::*;
    use proptest::prelude::*;

    proptest! {
        /// Falsifiable claim A-009: Backend selection is deterministic
        #[test]
        fn prop_backend_selection_deterministic(size in 0usize..1_000_000) {
            let selector = BackendSelector::default();

            let result1 = selector.select_for_size(size, true);
            let result2 = selector.select_for_size(size, true);

            prop_assert_eq!(result1, result2);
        }

        /// Falsifiable claim: compute_seed is deterministic
        #[test]
        fn prop_compute_seed_deterministic(
            backend_idx in 0u8..8,
            size in 0usize..1_000_000,
            cycle in 0u32..100,
            master_seed in any::<u64>()
        ) {
            let backend = match backend_idx {
                0 => Backend::Scalar,
                1 => Backend::SSE2,
                2 => Backend::AVX,
                3 => Backend::AVX2,
                4 => Backend::AVX512,
                5 => Backend::NEON,
                6 => Backend::WasmSIMD,
                _ => Backend::GPU,
            };

            let seed1 = compute_seed(backend, size, cycle, master_seed);
            let seed2 = compute_seed(backend, size, cycle, master_seed);

            prop_assert_eq!(seed1, seed2);
        }
    }
}

Coverage Report

Created: 2026-01-25 15:05

Line	Count	Source
1		//! Heijunka Scheduler (Leveled Testing)
2		//!
3		//! Implements Toyota Production System's Heijunka principle:
4		//! level the workload to reduce waste and variability.
5
6		use crate::Backend;
7		use std::collections::VecDeque;
8		use 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)]
15		pub 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
24		impl Default for BackendTolerance {
25	0	fn default() -> Self {
26	0	Self {
27	0	scalar_vs_simd: 0.0,
28	0	simd_vs_gpu: 1e-5,
29	0	gpu_vs_gpu: 1e-6,
30	0	}
31	0	}
32		}
33
34		impl BackendTolerance {
35		/// Strict tolerance for exact comparisons
36		#[must_use]
37	0	pub const fn strict() -> Self {
38	0	Self {
39	0	scalar_vs_simd: 0.0,
40	0	simd_vs_gpu: 0.0,
41	0	gpu_vs_gpu: 0.0,
42	0	}
43	0	}
44
45		/// Relaxed tolerance for approximate comparisons
46		#[must_use]
47	0	pub const fn relaxed() -> Self {
48	0	Self {
49	0	scalar_vs_simd: 1e-6,
50	0	simd_vs_gpu: 1e-4,
51	0	gpu_vs_gpu: 1e-5,
52	0	}
53	0	}
54
55		/// Get tolerance for comparing two backends
56		#[must_use]
57	0	pub fn for_backends(&self, a: Backend, b: Backend) -> f32 {
58	0	match (a, b) {
59	0	(Backend::Scalar, Backend::Scalar) => 0.0,
60		(Backend::Scalar, Backend::SSE2 \| Backend::AVX \| Backend::AVX2 \| Backend::AVX512)
61		\| (Backend::SSE2 \| Backend::AVX \| Backend::AVX2 \| Backend::AVX512, Backend::Scalar) => {
62	0	self.scalar_vs_simd
63		}
64	0	(Backend::GPU, Backend::GPU) => self.gpu_vs_gpu,
65	0	(Backend::GPU, _) \| (_, Backend::GPU) => self.simd_vs_gpu,
66	0	_ => self.scalar_vs_simd, // SIMD vs SIMD
67		}
68	0	}
69		}
70
71		/// Poka-Yoke: Type-safe backend selection
72		///
73		/// Provides compile-time and runtime guarantees for correct backend selection
74		/// based on input size and operation type.
75		#[derive(Debug, Clone)]
76		pub struct BackendSelector {
77		/// Minimum size for GPU offload (default: 100,000)
78		gpu_threshold: usize,
79		/// Minimum size for parallel execution (default: 1,000)
80		parallel_threshold: usize,
81		}
82
83		impl Default for BackendSelector {
84	0	fn default() -> Self {
85	0	Self {
86	0	gpu_threshold: 100_000,
87	0	parallel_threshold: 1_000,
88	0	}
89	0	}
90		}
91
92		impl BackendSelector {
93		/// Create a new backend selector with custom thresholds
94		#[must_use]
95	0	pub const fn new(gpu_threshold: usize, parallel_threshold: usize) -> Self {
96	0	Self {
97	0	gpu_threshold,
98	0	parallel_threshold,
99	0	}
100	0	}
101
102		/// Get the GPU threshold
103		#[must_use]
104	0	pub const fn gpu_threshold(&self) -> usize {
105	0	self.gpu_threshold
106	0	}
107
108		/// Get the parallel threshold
109		#[must_use]
110	0	pub const fn parallel_threshold(&self) -> usize {
111	0	self.parallel_threshold
112	0	}
113
114		/// Select backend based on input size
115		///
116		/// # Decision Logic (TRUENO-SPEC-012)
117		///
118		/// - N < 1,000: Pure SIMD (no parallelization overhead)
119		/// - 1,000 <= N < 100,000: SIMD + Parallel (Rayon)
120		/// - N >= 100,000: GPU (if available), else SIMD + Parallel
121		#[must_use]
122	0	pub fn select_for_size(&self, size: usize, gpu_available: bool) -> BackendCategory {
123	0	if size < self.parallel_threshold {
124	0	BackendCategory::SimdOnly
125	0	} else if size < self.gpu_threshold {
126	0	BackendCategory::SimdParallel
127	0	} else if gpu_available {
128	0	BackendCategory::Gpu
129		} else {
130	0	BackendCategory::SimdParallel // Graceful fallback
131		}
132	0	}
133
134		/// Check if size is at GPU threshold boundary (for testing)
135		#[must_use]
136	0	pub fn is_at_gpu_boundary(&self, size: usize) -> bool {
137	0	size == self.gpu_threshold \|\| size == self.gpu_threshold - 1
138	0	}
139
140		/// Check if size is at parallel threshold boundary (for testing)
141		#[must_use]
142	0	pub fn is_at_parallel_boundary(&self, size: usize) -> bool {
143	0	size == self.parallel_threshold \|\| size == self.parallel_threshold - 1
144	0	}
145		}
146
147		/// Backend category for selection result
148		#[derive(Debug, Clone, Copy, PartialEq, Eq)]
149		pub enum BackendCategory {
150		/// Pure SIMD (N < 1,000)
151		SimdOnly,
152		/// SIMD with parallel execution (1,000 <= N < 100,000)
153		SimdParallel,
154		/// GPU compute (N >= 100,000)
155		Gpu,
156		}
157
158		/// Simulation test configuration
159		#[derive(Debug, Clone)]
160		pub struct SimulationTest {
161		/// Backend to test
162		pub backend: Backend,
163		/// Input size
164		pub input_size: usize,
165		/// Test cycle number
166		pub cycle: u32,
167		/// Seed for deterministic RNG
168		pub seed: u64,
169		}
170
171		/// Heijunka: Balanced test distribution across backends and sizes
172		///
173		/// Implements Toyota Production System's Heijunka principle:
174		/// level the workload to reduce waste and variability.
175		#[derive(Debug)]
176		pub struct HeijunkaScheduler {
177		/// Test queue balanced across backends
178		queue: VecDeque<SimulationTest>,
179		/// Backends to cycle through
180		backends: Vec<Backend>,
181		}
182
183		impl HeijunkaScheduler {
184		/// Create a leveled test schedule
185		#[must_use]
186	0	pub fn new(
187	0	backends: Vec<Backend>,
188	0	input_sizes: Vec<usize>,
189	0	cycles_per_backend: u32,
190	0	master_seed: u64,
191	0	) -> Self {
192	0	let mut queue = VecDeque::new();
193
194		// Interleave tests across backends (leveling)
195	0	for size in &input_sizes {
196	0	for backend in &backends {
197	0	for cycle in 0..cycles_per_backend {
198	0	let seed = compute_seed(backend, size, cycle, master_seed);
199	0	queue.push_back(SimulationTest {
200	0	backend: *backend,
201	0	input_size: *size,
202	0	cycle,
203	0	seed,
204	0	});
205	0	}
206		}
207		}
208
209	0	Self {
210	0	queue,
211	0	backends: backends.clone(),
212	0	}
213	0	}
214
215		/// Get the next test from the queue
216	0	pub fn next_test(&mut self) -> Option<SimulationTest> {
217	0	self.queue.pop_front()
218	0	}
219
220		/// Get remaining test count
221		#[must_use]
222	0	pub fn remaining(&self) -> usize {
223	0	self.queue.len()
224	0	}
225
226		/// Get backends being tested
227		#[must_use]
228	0	pub fn backends(&self) -> &[Backend] {
229	0	&self.backends
230	0	}
231
232		/// Check if schedule is empty
233		#[must_use]
234	0	pub fn is_empty(&self) -> bool {
235	0	self.queue.is_empty()
236	0	}
237		}
238
239		/// Compute deterministic seed for a test configuration
240	0	pub(crate) fn compute_seed(backend: Backend, size: usize, cycle: u32, master_seed: u64) -> u64 {
241	0	let backend_bits = backend as u64;
242	0	let size_bits = size as u64;
243	0	let cycle_bits = u64::from(cycle);
244
245	0	master_seed
246	0	.wrapping_add(backend_bits.wrapping_mul(0x9E37_79B9_7F4A_7C15))
247	0	.wrapping_add(size_bits.wrapping_mul(0x6A09_E667_BB67_AE85))
248	0	.wrapping_add(cycle_bits.wrapping_mul(0x3C6E_F372_FE94_F82B))
249	0	}
250
251		/// Simulation test configuration builder
252		#[derive(Debug, Clone)]
253		pub struct SimTestConfigBuilder<S> {
254		seed: u64,
255		tolerance: BackendTolerance,
256		backends: Vec<Backend>,
257		input_sizes: Vec<usize>,
258		cycles: u32,
259		_state: PhantomData<S>,
260		}
261
262		/// Builder state: seed not set
263		pub struct NeedsSeed;
264		/// Builder state: ready to build
265		pub struct Ready;
266
267		impl Default for SimTestConfigBuilder<NeedsSeed> {
268	0	fn default() -> Self {
269	0	Self::new()
270	0	}
271		}
272
273		impl SimTestConfigBuilder<NeedsSeed> {
274		/// Create a new config builder
275		#[must_use]
276	0	pub fn new() -> Self {
277	0	Self {
278	0	seed: 0,
279	0	tolerance: BackendTolerance::default(),
280	0	backends: vec![Backend::Scalar, Backend::AVX2],
281	0	input_sizes: vec![100, 1_000, 10_000, 100_000],
282	0	cycles: 10,
283	0	_state: PhantomData,
284	0	}
285	0	}
286
287		/// Set the master seed (required)
288		#[must_use]
289	0	pub fn seed(self, seed: u64) -> SimTestConfigBuilder<Ready> {
290	0	SimTestConfigBuilder {
291	0	seed,
292	0	tolerance: self.tolerance,
293	0	backends: self.backends,
294	0	input_sizes: self.input_sizes,
295	0	cycles: self.cycles,
296	0	_state: PhantomData,
297	0	}
298	0	}
299		}
300
301		impl SimTestConfigBuilder<Ready> {
302		/// Set tolerance configuration
303		#[must_use]
304	0	pub fn tolerance(mut self, tolerance: BackendTolerance) -> Self {
305	0	self.tolerance = tolerance;
306	0	self
307	0	}
308
309		/// Set backends to test
310		#[must_use]
311	0	pub fn backends(mut self, backends: Vec<Backend>) -> Self {
312	0	self.backends = backends;
313	0	self
314	0	}
315
316		/// Set input sizes to test
317		#[must_use]
318	0	pub fn input_sizes(mut self, sizes: Vec<usize>) -> Self {
319	0	self.input_sizes = sizes;
320	0	self
321	0	}
322
323		/// Set number of test cycles
324		#[must_use]
325	0	pub fn cycles(mut self, cycles: u32) -> Self {
326	0	self.cycles = cycles;
327	0	self
328	0	}
329
330		/// Build the configuration
331		#[must_use]
332	0	pub fn build(self) -> SimTestConfig {
333	0	SimTestConfig {
334	0	seed: self.seed,
335	0	tolerance: self.tolerance,
336	0	backends: self.backends,
337	0	input_sizes: self.input_sizes,
338	0	cycles: self.cycles,
339	0	}
340	0	}
341		}
342
343		/// Simulation test configuration
344		#[derive(Debug, Clone)]
345		pub struct SimTestConfig {
346		/// Master seed for deterministic RNG
347		pub seed: u64,
348		/// Backend tolerance configuration
349		pub tolerance: BackendTolerance,
350		/// Backends to test
351		pub backends: Vec<Backend>,
352		/// Input sizes to test
353		pub input_sizes: Vec<usize>,
354		/// Number of test cycles
355		pub cycles: u32,
356		}
357
358		impl SimTestConfig {
359		/// Create a config builder
360		#[must_use]
361	0	pub fn builder() -> SimTestConfigBuilder<NeedsSeed> {
362	0	SimTestConfigBuilder::new()
363	0	}
364
365		/// Create a Heijunka scheduler from this config
366		#[must_use]
367	0	pub fn create_scheduler(&self) -> HeijunkaScheduler {
368	0	HeijunkaScheduler::new(
369	0	self.backends.clone(),
370	0	self.input_sizes.clone(),
371	0	self.cycles,
372	0	self.seed,
373		)
374	0	}
375		}
376
377		#[cfg(test)]
378		mod tests {
379		use super::*;
380
381		#[test]
382		fn test_backend_selector_default_thresholds() {
383		// Falsifiable claim A-005, A-006
384		let selector = BackendSelector::default();
385
386		assert_eq!(selector.gpu_threshold(), 100_000);
387		assert_eq!(selector.parallel_threshold(), 1_000);
388		}
389
390		#[test]
391		fn test_backend_selector_simd_only() {
392		// N < 1,000 should use SIMD only
393		let selector = BackendSelector::default();
394
395		assert_eq!(
396		selector.select_for_size(100, false),
397		BackendCategory::SimdOnly
398		);
399		assert_eq!(
400		selector.select_for_size(999, false),
401		BackendCategory::SimdOnly
402		);
403		assert_eq!(
404		selector.select_for_size(999, true),
405		BackendCategory::SimdOnly
406		);
407		}
408
409		#[test]
410		fn test_backend_selector_simd_parallel() {
411		// 1,000 <= N < 100,000 should use SIMD + Parallel
412		let selector = BackendSelector::default();
413
414		assert_eq!(
415		selector.select_for_size(1_000, false),
416		BackendCategory::SimdParallel
417		);
418		assert_eq!(
419		selector.select_for_size(50_000, false),
420		BackendCategory::SimdParallel
421		);
422		assert_eq!(
423		selector.select_for_size(99_999, false),
424		BackendCategory::SimdParallel
425		);
426		}
427
428		#[test]
429		fn test_backend_selector_gpu() {
430		// N >= 100,000 should use GPU (if available)
431		let selector = BackendSelector::default();
432
433		assert_eq!(
434		selector.select_for_size(100_000, true),
435		BackendCategory::Gpu
436		);
437		assert_eq!(
438		selector.select_for_size(1_000_000, true),
439		BackendCategory::Gpu
440		);
441		}
442
443		#[test]
444		fn test_backend_selector_gpu_fallback() {
445		// N >= 100,000 without GPU should fallback to SIMD + Parallel
446		let selector = BackendSelector::default();
447
448		assert_eq!(
449		selector.select_for_size(100_000, false),
450		BackendCategory::SimdParallel
451		);
452		}
453
454		#[test]
455		fn test_backend_selector_boundary() {
456		// Falsifiable claim A-005
457		let selector = BackendSelector::default();
458
459		// At GPU threshold boundary
460		assert!(selector.is_at_gpu_boundary(100_000));
461		assert!(selector.is_at_gpu_boundary(99_999));
462		assert!(!selector.is_at_gpu_boundary(99_998));
463
464		// At parallel threshold boundary
465		assert!(selector.is_at_parallel_boundary(1_000));
466		assert!(selector.is_at_parallel_boundary(999));
467		assert!(!selector.is_at_parallel_boundary(998));
468		}
469
470		#[test]
471		fn test_backend_tolerance_default() {
472		let tolerance = BackendTolerance::default();
473
474		assert_eq!(tolerance.scalar_vs_simd, 0.0);
475		assert!((tolerance.simd_vs_gpu - 1e-5).abs() < 1e-10);
476		assert!((tolerance.gpu_vs_gpu - 1e-6).abs() < 1e-10);
477		}
478
479		#[test]
480		fn test_backend_tolerance_strict() {
481		let tolerance = BackendTolerance::strict();
482
483		assert_eq!(tolerance.scalar_vs_simd, 0.0);
484		assert_eq!(tolerance.simd_vs_gpu, 0.0);
485		assert_eq!(tolerance.gpu_vs_gpu, 0.0);
486		}
487
488		#[test]
489		fn test_backend_tolerance_for_backends() {
490		// Falsifiable claim A-002, A-003, A-004
491		let tolerance = BackendTolerance::default();
492
493		// Scalar vs Scalar
494		assert_eq!(
495		tolerance.for_backends(Backend::Scalar, Backend::Scalar),
496		0.0
497		);
498
499		// Scalar vs SIMD (should be exact)
500		assert_eq!(tolerance.for_backends(Backend::Scalar, Backend::AVX2), 0.0);
501
502		// GPU vs GPU
503		assert_eq!(
504		tolerance.for_backends(Backend::GPU, Backend::GPU),
505		tolerance.gpu_vs_gpu
506		);
507
508		// SIMD vs GPU
509		assert_eq!(
510		tolerance.for_backends(Backend::AVX2, Backend::GPU),
511		tolerance.simd_vs_gpu
512		);
513		}
514
515		#[test]
516		fn test_heijunka_schedule_creation() {
517		let backends = vec![Backend::Scalar, Backend::AVX2];
518		let sizes = vec![100, 1000];
519		let cycles = 2;
520
521		let scheduler = HeijunkaScheduler::new(backends.clone(), sizes, cycles, 42);
522
523		// Should have backends.len() * sizes.len() * cycles tests
524		// 2 backends * 2 sizes * 2 cycles = 8 tests
525		assert_eq!(scheduler.remaining(), 8);
526		}
527
528		#[test]
529		fn test_heijunka_deterministic_seeds() {
530		// Falsifiable claim B-017
531		let backends = vec![Backend::Scalar, Backend::AVX2];
532		let sizes = vec![100, 1000];
533		let cycles = 2;
534
535		let mut scheduler1 = HeijunkaScheduler::new(backends.clone(), sizes.clone(), cycles, 42);
536		let mut scheduler2 = HeijunkaScheduler::new(backends, sizes, cycles, 42);
537
538		// Seeds should be identical for same configuration
539		while let (Some(t1), Some(t2)) = (scheduler1.next_test(), scheduler2.next_test()) {
540		assert_eq!(t1.seed, t2.seed, "Seeds must be deterministic");
541		}
542		}
543
544		#[test]
545		fn test_heijunka_consumes_all_tests() {
546		let backends = vec![Backend::Scalar];
547		let sizes = vec![100];
548		let cycles = 5;
549
550		let mut scheduler = HeijunkaScheduler::new(backends, sizes, cycles, 42);
551
552		let mut count = 0;
553		while scheduler.next_test().is_some() {
554		count += 1;
555		}
556
557		assert_eq!(count, 5);
558		assert!(scheduler.is_empty());
559		}
560
561		#[test]
562		fn test_heijunka_different_master_seeds() {
563		// Falsifiable claim B-018
564		let backends = vec![Backend::Scalar];
565		let sizes = vec![100];
566		let cycles = 1;
567
568		let mut scheduler1 = HeijunkaScheduler::new(backends.clone(), sizes.clone(), cycles, 42);
569		let mut scheduler2 = HeijunkaScheduler::new(backends, sizes, cycles, 43);
570
571		let t1 = scheduler1.next_test().unwrap();
572		let t2 = scheduler2.next_test().unwrap();
573
574		assert_ne!(
575		t1.seed, t2.seed,
576		"Different master seeds must produce different test seeds"
577		);
578		}
579
580		#[test]
581		fn test_sim_test_config_builder() {
582		let config = SimTestConfig::builder()
583		.seed(42)
584		.tolerance(BackendTolerance::strict())
585		.backends(vec![Backend::Scalar, Backend::AVX2, Backend::GPU])
586		.input_sizes(vec![100, 1000, 10000])
587		.cycles(5)
588		.build();
589
590		assert_eq!(config.seed, 42);
591		assert_eq!(config.backends.len(), 3);
592		assert_eq!(config.input_sizes.len(), 3);
593		assert_eq!(config.cycles, 5);
594		}
595
596		#[test]
597		fn test_sim_test_config_creates_scheduler() {
598		let config = SimTestConfig::builder()
599		.seed(42)
600		.backends(vec![Backend::Scalar, Backend::AVX2])
601		.input_sizes(vec![100, 1000])
602		.cycles(3)
603		.build();
604
605		let scheduler = config.create_scheduler();
606
607		// 2 backends * 2 sizes * 3 cycles = 12 tests
608		assert_eq!(scheduler.remaining(), 12);
609		}
610
611		#[test]
612		fn test_backend_category_debug() {
613		let category = BackendCategory::Gpu;
614		let debug = format!("{category:?}");
615		assert!(debug.contains("Gpu"));
616		}
617		}
618
619		#[cfg(test)]
620		mod proptests {
621		use super::*;
622		use proptest::prelude::*;
623
624		proptest! {
625		/// Falsifiable claim A-009: Backend selection is deterministic
626		#[test]
627		fn prop_backend_selection_deterministic(size in 0usize..1_000_000) {
628		let selector = BackendSelector::default();
629
630		let result1 = selector.select_for_size(size, true);
631		let result2 = selector.select_for_size(size, true);
632
633		prop_assert_eq!(result1, result2);
634		}
635
636		/// Falsifiable claim: compute_seed is deterministic
637		#[test]
638		fn prop_compute_seed_deterministic(
639		backend_idx in 0u8..8,
640		size in 0usize..1_000_000,
641		cycle in 0u32..100,
642		master_seed in any::<u64>()
643		) {
644		let backend = match backend_idx {
645		0 => Backend::Scalar,
646		1 => Backend::SSE2,
647		2 => Backend::AVX,
648		3 => Backend::AVX2,
649		4 => Backend::AVX512,
650		5 => Backend::NEON,
651		6 => Backend::WasmSIMD,
652		_ => Backend::GPU,
653		};
654
655		let seed1 = compute_seed(backend, size, cycle, master_seed);
656		let seed2 = compute_seed(backend, size, cycle, master_seed);
657
658		prop_assert_eq!(seed1, seed2);
659		}
660		}
661		}