Expand description
Wavefront (levelized) scheduling — grouping independent nodes into concurrently-launchable waves.
A computation DAG can be partitioned into wavefronts (a.k.a. topological
levels): the set of nodes whose longest-path distance from any source is
k forms wavefront k. All nodes within a wavefront are mutually
independent and may, in principle, be launched concurrently (on separate
streams); wavefront k+1 cannot begin until wavefront k completes.
This is the natural CPU-side model for “how much parallelism does this graph expose, and in what order should waves of work be issued?” — the information a stream partitioner or a multi-stream launcher consumes.
Schedule::levelize computes the wavefront decomposition, the critical
path (cost-weighted longest path) and a simple concurrency model (the
makespan under unbounded streams vs. a bounded stream count).
This module is distinct from crate::analysis::topo, which annotates
per node (ASAP/ALAP/slack). Here the output is per wave: explicit
groups of independent nodes, which is what a launcher iterates over.
Structs§
- Schedule
- A wavefront schedule: the full level decomposition of a
ComputeGraphplus derived concurrency metrics. - Wavefront
- One wavefront: a set of mutually-independent nodes at the same topological level, all of which may be launched concurrently.