flynnel 0.6.0

K-aware NUMA-aware work-stealing scheduler with extended-Flynn-taxonomy dispatch (MIMD / SIMC / MIMC / MISD / SIMT / MIMT): a rayon-shaped pool reshaped around per-call execution-class plans with first-class CPU+GPU hybrid (join_hybrid, hybrid_pipeline) and per-call dispatch profiles.
Documentation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
//! Unified user-facing dispatch API across the Flynn taxonomy.
//!
//! The user describes their workload declaratively and the
//! framework picks the right Flynn-axis entry point - SISD
//! (inline) vs MIMD (work-steal) vs SIMC (cooperative fan-out) vs
//! MISD (variant race) - based on a single
//! [`crate::sched::workload_shape::WorkloadShape`] hint.
//!
//! ## The Flynn-axis dispatch table
//!
//! | WorkloadShape             | Flynn axis | Underlying primitive                                   | Dispatch method                     |
//! |---------------------------|------------|--------------------------------------------------------|-------------------------------------|
//! | `Streaming`               | SISD       | inline execution (`op()`)                              | [`AdaptiveDispatcher::execute_streaming`]      |
//! | `ProducerFast { burst }`  | SIMC       | [`crate::sched::cooperative_join_n_flat`]              | [`AdaptiveDispatcher::execute_cooperative`]    |
//! | `WorkSteal { n, batch }`  | MIMD       | [`crate::sched::par_iter::for_each_chunk`]             | [`AdaptiveDispatcher::execute_for_each`]       |
//! | `Cooperative { n_cores }` | SIMC/MIMC  | [`crate::sched::cooperative::cooperative_join_n_flat_mailbox`] | [`AdaptiveDispatcher::execute_cooperative_mailbox`] |
//!
//! MISD variant racing has no `execute_*` shortcut here: call
//! [`crate::sched::race::race_variants`] directly (three typed
//! closures, each polling a
//! [`crate::sched::race::CancelToken`]).
//!
//! The K_gating axis (PerSlot vs CounterOnly) swaps at runtime via
//! [`AdaptiveDispatcher::migrate_k_gating`]; measured on Zen+ R7
//! 2700 the per-push AtomicU32 Acquire load adds 0.02 ns over
//! direct dispatch (noise floor).
//!
//! ```
//! use flynnel::sched::dispatch::AdaptiveDispatcher;
//! use flynnel::sched::workload_shape::WorkloadShape;
//!
//! let closures: Vec<Box<dyn FnOnce() -> u32 + Send>> =
//!     (0..8u32).map(|i| Box::new(move || i) as _).collect();
//! let results = AdaptiveDispatcher::new()
//!     .with_shape(WorkloadShape::ProducerFast { burst: 64 })
//!     .execute_cooperative(closures);
//! assert_eq!(results, (0..8u32).collect::<Vec<_>>());
//! ```
//!
//! No deque, K-axis, or Flynn-axis name appears in user code; the
//! user describes the workload and the framework dispatches.

#![allow(clippy::missing_errors_doc)]

use crate::backend::{Backend, BackendRef};
use crate::dispatch_profile::DispatchProfile;
use crate::foundation::Variant;
use crate::sched::JobPlan;
use crate::sched::adaptive_backend::{
    active_backend_id, migrate_backend, resolve_active_backend,
};
use crate::sched::adaptive_profile::{
    WorkloadClass, active_dispatch_profile, migrate_dispatch_profile,
    migrate_workload_class,
};
use crate::sched::k_gating::KGating;
use crate::sched::workload_shape::WorkloadShape;

/// User-facing adaptive dispatcher. Carries the WorkloadShape hint
/// and routes the dispatch through the matching Flynn-axis
/// primitive.
pub struct AdaptiveDispatcher {
    shape: WorkloadShape,
    variant: Variant,
    k_outer: u8,
    use_smt: bool,
    /// Optional per-call WorkloadClass override; takes precedence
    /// over the global active DispatchProfile when set.
    explicit_class: Option<WorkloadClass>,
}

impl Default for AdaptiveDispatcher {
    fn default() -> Self {
        Self::new()
    }
}

impl AdaptiveDispatcher {
    /// Fresh dispatcher with default settings: `WorkSteal` shape
    /// (MIMD baseline), faithful variant, k_outer=4, no SMT,
    /// no explicit workload-class (consults global active
    /// DispatchProfile).
    pub fn new() -> Self {
        Self {
            shape: WorkloadShape::WorkSteal {
                n_consumers: num_cpus(),
                batch_size: 256,
            },
            variant: Variant::Faithful,
            k_outer: 4,
            use_smt: false,
            explicit_class: None,
        }
    }

    /// Builder: install a declarative workload-shape hint. The
    /// shape selects which Flynn-axis primitive the framework
    /// routes to and the low-level K-axis knobs (K_gating,
    /// mailbox routing, oversubscription) via
    /// [`WorkloadShape::hints`].
    #[inline]
    pub fn with_shape(mut self, shape: WorkloadShape) -> Self {
        self.shape = shape;
        self
    }

    /// Builder: select the [`Variant`] (correctness tier).
    #[inline]
    pub fn with_variant(mut self, variant: Variant) -> Self {
        self.variant = variant;
        self
    }

    /// Builder: set the [`crate::sched::JobPlan::k_outer`] hint
    /// (log2 of operand size in limbs).
    #[inline]
    pub fn with_k_outer(mut self, k_outer: u8) -> Self {
        self.k_outer = k_outer;
        self
    }

    /// Builder: opt in to SMT-sibling participation. The
    /// dispatched plan's `use_smt=true` raises the arena's SMT
    /// request counter; siblings join the work-stealing loop for
    /// the duration of the dispatch.
    #[inline]
    pub fn with_smt(mut self) -> Self {
        self.use_smt = true;
        self
    }

    /// Build the underlying `JobPlan` from the dispatcher's
    /// settings. Maps the shape hint through
    /// [`JobPlan::with_workload_shape`] and the workload-class
    /// hint (explicit or global) through [`JobPlan::set_profile`]
    /// derived knobs.
    fn build_plan(&self, batch_size: u32) -> JobPlan {
        // Pick the effective DispatchProfile: explicit per-call
        // class wins; otherwise read the global active tag.
        let profile = match self.explicit_class {
            Some(c) => c.to_dispatch_profile(),
            None => active_dispatch_profile(),
        };
        // Build a profile-derived base plan so use_smt +
        // oversubscription_log2 + estimated_per_item_ns are set
        // according to the active class. The explicit flag mirrors
        // whether the caller supplied a workload class: a
        // with_workload_class dispatcher is pinned; one consulting
        // the global default stays overridable by per-site learning.
        let mut plan = JobPlan::set_profile_with(
            self.k_outer,
            batch_size,
            profile,
            self.explicit_class.is_some(),
        )
        .with_variant(self.variant)
        .with_workload_shape(self.shape);
        if self.use_smt {
            plan = plan.with_smt();
        }
        plan
    }

    /// SIMC dispatch: run a list of closures cooperatively across
    /// workers (fan-out + per-closure result). Maps to
    /// [`crate::sched::cooperative_join_n_flat`] which uses
    /// `push_burst` + flush to unlock the K_inner=3 amortization
    /// (3 jobs per cache-line transfer).
    ///
    /// Returns results in caller order regardless of execution
    /// thread.
    pub fn execute_cooperative<R>(
        self,
        closures: Vec<Box<dyn FnOnce() -> R + Send>>,
    ) -> Vec<R>
    where
        R: Send + 'static,
    {
        let plan = self.build_plan(closures.len() as u32);
        crate::sched::cooperative_join_n_flat(&plan, closures)
    }

    /// SIMC/MIMC dispatch with mailbox routing: variant of
    /// `execute_cooperative` that hands each closure directly to
    /// a specific worker's mailbox (URD-style owner-directed
    /// distribution). Use when N >= n_workers and closures are
    /// uniform-cost. Internally gated to demote to deque mode
    /// when N < n_workers.
    pub fn execute_cooperative_mailbox<R>(
        self,
        closures: Vec<Box<dyn FnOnce() -> R + Send>>,
    ) -> Vec<R>
    where
        R: Send + 'static,
    {
        let plan = self
            .build_plan(closures.len() as u32)
            .with_mailbox_routing(true);
        crate::sched::cooperative::cooperative_join_n_flat_mailbox(&plan, closures)
    }

    /// MIMD dispatch: run an in-place op over `items` via
    /// recursive work-stealing bisection through
    /// [`crate::sched::par_iter::for_each_chunk`]. Callers who
    /// need finer control over the leaf floor (heavy per-element
    /// work like matmul, spmv, LU update) should build a `JobPlan`
    /// with an explicit `estimated_per_item_ns` hint and call
    /// [`crate::sched::par_iter::for_each_chunk_indexed_min_leaf`]
    /// directly.
    #[track_caller]
    pub fn execute_for_each<T, F>(self, items: &mut [T], op: F)
    where
        T: Send,
        F: Fn(&mut [T]) + Sync + Send,
    {
        let plan = self.build_plan(items.len() as u32);
        crate::sched::par_iter::for_each_chunk(&plan, items, op);
    }

    /// SISD dispatch: run a single closure inline on the caller's
    /// thread. No scheduler involvement; useful as the
    /// degenerate-case fall-through.
    pub fn execute_streaming<R, F>(self, op: F) -> R
    where
        F: FnOnce() -> R + Send,
        R: Send,
    {
        op()
    }

    /// Backend-adaptive indexed parallel-for: invokes `work(i)` for
    /// `i` in `0..count`, routed through the global active
    /// backend's `DispatchBackend::dispatch_parallel_for` impl.
    ///
    /// When the active backend is CPU, this routes through the
    /// work-stealing arena (same as the per-slice
    /// [`Self::execute_for_each`] path). When active is CUDA /
    /// ROCm / Metal / TPU, this dispatches via the GPU/TPU
    /// runtime if a registered backend is available; falls back
    /// to CPU gracefully when the active backend is not
    /// registered.
    ///
    /// Returns `(fell_back_to_cpu, ())` so the caller can
    /// observe the routing decision for telemetry.
    pub fn execute_indexed<F>(self, count: u32, work: F) -> bool
    where
        F: Fn(u32) + Send + Sync,
    {
        let (backend, fell_back) = resolve_active_backend();
        backend.dispatch_parallel_for(count, &work);
        fell_back
    }

    /// Migrate the active K_gating across all workers in the
    /// global LocalArena. Each worker's per-tier AdaptiveWorker
    /// flips its active tag with a single Release-store; new
    /// pushes route to the new backing immediately.
    ///
    /// Use this when the application observes a workload shift
    /// (e.g., the burst-vs-single profile crosses a threshold)
    /// and wants to switch the per-op deque primitive without
    /// respawning the worker pool. Migration cost: one
    /// Release-store per worker per tier (~30 atomic stores on
    /// a 16-worker arena with 4 tiers); per-op cost on new
    /// pushes is unchanged from the existing AtomicU32-tag
    /// dispatch.
    pub fn migrate_k_gating(&self, gating: KGating) {
        let arena = crate::sched::arena::global_local_arena();
        arena.migrate_all_workers_k_gating(gating);
    }

    /// Migrate the active global [`DispatchProfile`]. One AtomicU8
    /// Release-store; subsequent dispatches that consult the
    /// active profile (via [`active_dispatch_profile`]) see the
    /// new value. Per-op cost on the deque hot path is unchanged
    /// because the profile is only read at plan-construction time.
    #[inline]
    pub fn migrate_dispatch_profile(&self, profile: DispatchProfile) {
        migrate_dispatch_profile(profile);
    }

    /// High-level workload-class migration. Maps the class to a
    /// [`DispatchProfile`] then calls
    /// [`Self::migrate_dispatch_profile`].
    ///
    /// Use this when the application observes a workload shift
    /// (Light -> Compute, Compute -> Heavy, Heavy -> Memory) and
    /// wants the scheduler's default plan to retune SMT
    /// activation + oversubscription + cost estimate without
    /// touching the per-call API.
    #[inline]
    pub fn migrate_workload_class(&self, class: WorkloadClass) {
        migrate_workload_class(class);
    }

    /// Read the active global [`DispatchProfile`].
    #[inline]
    pub fn active_dispatch_profile(&self) -> DispatchProfile {
        active_dispatch_profile()
    }

    /// Migrate the global active backend (CPU / CUDA / TPU / etc.)
    /// via one AtomicU32 Release-store. Subsequent dispatches
    /// route through the new backend's `DispatchBackend`
    /// implementation; if the requested backend is not registered,
    /// dispatches gracefully fall back to CPU (the always-
    /// auto-registered default).
    ///
    /// Per-op cost on the deque hot path: zero. Per-dispatch cost:
    /// one Acquire-load on the active-backend tag + one registry
    /// lookup (HashMap probe) at execute-entry. Migration cost:
    /// one Release-store (~1 ns).
    #[inline]
    pub fn migrate_backend(&self, backend: Backend) {
        migrate_backend(backend);
    }

    /// Read the active global backend id.
    #[inline]
    pub fn active_backend_id(&self) -> Backend {
        active_backend_id()
    }

    /// Resolve the active backend to a concrete `BackendRef`.
    /// Returns `(backend, fell_back_to_cpu)`; the second tuple
    /// element is true when the requested active backend was not
    /// registered and CPU was used as fallback. Useful for
    /// observability and telemetry around backend migration
    /// readiness.
    #[inline]
    pub fn resolve_active_backend(&self) -> (BackendRef, bool) {
        resolve_active_backend()
    }

    /// Builder: install a declarative WorkloadClass hint. Sets the
    /// underlying DispatchProfile on the JobPlan that this
    /// dispatcher constructs. The plan-level profile takes
    /// precedence over the global active profile for this
    /// dispatch only; subsequent dispatchers without the explicit
    /// class still read the global active tag.
    #[inline]
    pub fn with_workload_class(mut self, class: WorkloadClass) -> Self {
        // Stash the explicit class in the variant tag's high bits
        // via a sibling field. The implementation keeps the field
        // strictly as a hint, applied in build_plan when present.
        self.explicit_class = Some(class);
        self
    }
}

fn num_cpus() -> u32 {
    std::thread::available_parallelism()
        .map(|n| n.get() as u32)
        .unwrap_or(4)
}

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

    #[test]
    fn default_dispatcher_constructs() {
        let d = AdaptiveDispatcher::new();
        assert_eq!(d.k_outer, 4);
        assert!(!d.use_smt);
        assert_eq!(d.variant, Variant::Faithful);
    }

    #[test]
    fn builder_chains() {
        let d = AdaptiveDispatcher::new()
            .with_shape(WorkloadShape::ProducerFast { burst: 32 })
            .with_variant(Variant::Fast)
            .with_k_outer(8)
            .with_smt();
        assert_eq!(d.k_outer, 8);
        assert!(d.use_smt);
        assert_eq!(d.variant, Variant::Fast);
        assert!(matches!(d.shape, WorkloadShape::ProducerFast { burst: 32 }));
    }

    #[test]
    fn execute_streaming_runs_inline() {
        let d = AdaptiveDispatcher::new()
            .with_shape(WorkloadShape::Streaming);
        let r = d.execute_streaming(|| 42u32);
        assert_eq!(r, 42);
    }

    #[test]
    fn execute_cooperative_round_trips_caller_order() {
        let d = AdaptiveDispatcher::new()
            .with_shape(WorkloadShape::ProducerFast { burst: 8 });
        let closures: Vec<Box<dyn FnOnce() -> u32 + Send>> =
            (0..8u32).map(|i| Box::new(move || i) as _).collect();
        let results = d.execute_cooperative(closures);
        assert_eq!(results, (0..8u32).collect::<Vec<_>>());
    }

    #[test]
    fn execute_for_each_in_place_updates_items() {
        let d = AdaptiveDispatcher::new()
            .with_shape(WorkloadShape::WorkSteal { n_consumers: 4, batch_size: 64 });
        let mut items: Vec<u32> = (0..256).collect();
        d.execute_for_each(&mut items, |slice| {
            for x in slice.iter_mut() {
                *x = x.wrapping_mul(2);
            }
        });
        for (i, x) in items.iter().enumerate() {
            assert_eq!(*x, (i as u32).wrapping_mul(2));
        }
    }
}