use std::cell::RefCell;
use vyre::MemoryOrdering;
use vyre::ir::{BufferAccess, BufferDecl, DataType, Expr, Node, Program};
use vyre_driver::{DispatchConfig, Resource, VyreBackend};
use vyre_driver::grid_sync::contains_grid_sync;
use vyre_primitives::fixpoint::persistent_fixpoint::{
PERSISTENT_FIXPOINT_WORKGROUP_SIZE, persistent_fixpoint, persistent_fixpoint_grid,
};
use vyre_primitives::wire::{pack_u32_slice_into, unpack_u32_slice_into};
use crate::{ExatokError, trap_program};
pub const OP_ID: &str = "exatok::gpu_loop::persistent_merge";
pub const OP_ID_SINGLE_PASS: &str = "exatok::gpu_loop::merge_pass";
pub const NAME_STATE_CURRENT: &str = "wt_loop_current";
pub const NAME_STATE_NEXT: &str = "wt_loop_next";
pub const NAME_CHANGED: &str = "wt_loop_changed";
pub const NAME_PASSES: &str = "wt_loop_passes";
pub const NAME_SEGMENT_CHANGED: &str = "wt_loop_segment_changed";
pub const NAME_SEGMENT_PASSES: &str = "wt_loop_segment_passes";
pub const BINDING_STATE_CURRENT: u32 = 0;
pub const BINDING_STATE_NEXT: u32 = 1;
pub const BINDING_CHANGED: u32 = 2;
pub const BINDING_PASSES: u32 = 3;
pub const BINDING_SEGMENT_CHANGED: u32 = 4;
pub const BINDING_SEGMENT_PASSES: u32 = 5;
pub const FIRST_CALLER_BINDING: u32 = 6;
const HARNESS_BUFFERS: usize = 6;
const HARNESS_SEED_IS_READ: [bool; HARNESS_BUFFERS] = [
true, false, true, true, false, true, ];
pub const SLOT_LIVE_LEN: u32 = 0;
pub const SLOT_FIRST_TOKEN: u32 = 1;
pub const DEAD_SLOT: u32 = u32::MAX;
pub const LOOP_WORKGROUP_WIDTH: u32 = PERSISTENT_FIXPOINT_WORKGROUP_SIZE[0];
#[must_use]
pub const fn merge_pass_bound(longest: u32) -> u32 {
if longest < 1 { 1 } else { longest }
}
#[must_use]
pub fn longest_segment<S: AsRef<[u32]>>(pretokens: &[S]) -> u32 {
let mut longest = 0usize;
for pretoken in pretokens {
let len = pretoken.as_ref().len();
if len > longest {
longest = len;
}
}
longest as u32
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub struct LoopShape {
segments: u32,
segment_capacity: u32,
max_passes: u32,
}
impl LoopShape {
#[must_use]
pub const fn new(segments: u32, segment_capacity: u32, max_passes: u32) -> Self {
Self {
segments,
segment_capacity,
max_passes,
}
}
#[must_use]
pub const fn segments(self) -> u32 {
self.segments
}
#[must_use]
pub const fn segment_capacity(self) -> u32 {
self.segment_capacity
}
#[must_use]
pub const fn max_passes(self) -> u32 {
self.max_passes
}
#[must_use]
pub const fn stride(self) -> u32 {
self.segment_capacity + 1
}
#[must_use]
pub const fn segments_per_group(self) -> u32 {
let per = LOOP_WORKGROUP_WIDTH / self.stride();
if per == 0 { 1 } else { per }
}
#[must_use]
pub const fn groups(self) -> u32 {
let per = self.segments_per_group();
(self.segments + per - 1) / per
}
#[must_use]
pub const fn words_per_group(self) -> u32 {
let used = self.segments_per_group() * self.stride();
used.div_ceil(LOOP_WORKGROUP_WIDTH) * LOOP_WORKGROUP_WIDTH
}
#[must_use]
pub const fn state_words(self) -> u32 {
self.groups() * self.words_per_group()
}
#[must_use]
pub const fn segment_base(self, segment: u32) -> u32 {
let per = self.segments_per_group();
(segment / per) * self.words_per_group() + (segment % per) * self.stride()
}
#[must_use]
pub const fn with_max_passes(self, max_passes: u32) -> Self {
Self { max_passes, ..self }
}
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct LoopBatch {
shape: LoopShape,
state: Vec<u32>,
}
impl LoopBatch {
#[must_use]
pub fn new<S: AsRef<[u32]>>(pretokens: &[S], max_passes: u32) -> Self {
let mut batch = Self {
shape: LoopShape::new(0, 1, max_passes),
state: Vec::new(),
};
batch.reseed(pretokens, max_passes);
batch
}
pub(crate) fn reseed<S: AsRef<[u32]>>(&mut self, pretokens: &[S], max_passes: u32) {
let segment_capacity = longest_segment(pretokens).max(1);
self.shape = LoopShape::new(pretokens.len() as u32, segment_capacity, max_passes);
self.state.clear();
self.state.resize(self.shape.state_words() as usize, DEAD_SLOT);
for (index, pretoken) in pretokens.iter().enumerate() {
let tokens = pretoken.as_ref();
let base = self.shape.segment_base(index as u32) as usize;
self.state[base + SLOT_LIVE_LEN as usize] = tokens.len() as u32;
let first = base + SLOT_FIRST_TOKEN as usize;
self.state[first..first + tokens.len()].copy_from_slice(tokens);
}
}
#[must_use]
pub fn with_sound_bound<S: AsRef<[u32]>>(pretokens: &[S]) -> Self {
Self::new(pretokens, merge_pass_bound(longest_segment(pretokens)))
}
#[must_use]
pub const fn shape(&self) -> LoopShape {
self.shape
}
#[must_use]
pub fn state(&self) -> &[u32] {
&self.state
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub enum Termination {
Converged,
CapReached,
}
impl Termination {
#[must_use]
pub const fn is_converged(self) -> bool {
matches!(self, Self::Converged)
}
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct LoopOutcome {
shape: LoopShape,
state: Vec<u32>,
passes: u32,
segment_passes: Vec<u32>,
segment_changed: Vec<u32>,
termination: Termination,
}
impl LoopOutcome {
#[must_use]
pub fn from_parts(
shape: LoopShape,
state: Vec<u32>,
passes: u32,
segment_passes: Vec<u32>,
segment_changed: Vec<u32>,
termination: Termination,
) -> Self {
Self {
shape,
state,
passes,
segment_passes,
segment_changed,
termination,
}
}
#[must_use]
pub fn state(&self) -> &[u32] {
&self.state
}
#[must_use]
pub const fn shape(&self) -> LoopShape {
self.shape
}
#[must_use]
pub fn live_len(&self, segment: u32) -> u32 {
let base = self.shape.segment_base(segment) as usize;
self.state
.get(base + SLOT_LIVE_LEN as usize)
.copied()
.unwrap_or(0)
.min(self.shape.segment_capacity())
}
#[must_use]
pub fn tokens(&self, segment: u32) -> &[u32] {
let base = self.shape.segment_base(segment) as usize;
let start = base + SLOT_FIRST_TOKEN as usize;
let end = start + self.live_len(segment) as usize;
self.state.get(start..end).unwrap_or(&[])
}
pub fn converged_tokens(&self, segment: u32) -> Result<&[u32], ExatokError> {
if self.termination.is_converged() || self.segment_changed(segment) == 0 {
return Ok(self.tokens(segment));
}
Err(ExatokError::Divergence {
byte_offset: segment as usize,
host: None,
device: self.tokens(segment).first().copied().map(crate::TokenId),
fix: format!(
"segment {segment} was still merging after {} pass(es) of a {} pass budget, so \
its {} live token(s) are a partial merge. Every merge drops one token, so \
merge_pass_bound(longest pretoken) always suffices: a cap hit at that bound is \
a pass-body bug, not a budget to raise. This dispatch used {} workgroup(s) over \
{} segment(s); ONE workgroup rules out every cross-group cause, so a failure \
here is intra-workgroup. Both defects that produced this exact message were \
intra-workgroup ordering bugs that needed no concurrency and no second \
dispatch: a missing barrier on `persistent_fixpoint`'s loop back edge, and a \
`_vyre_grid_barrier` counter left unzeroed between grid-sync launches of one \
module. Check the pass body and the primitive's barriers before suspecting \
anything above them.",
self.passes,
self.shape.max_passes(),
self.live_len(segment),
self.shape.groups(),
self.shape.segments()
),
})
}
pub fn converged_segments(&self) -> Option<impl Iterator<Item = &[u32]> + '_> {
if !self.termination.is_converged() {
return None;
}
let stride = self.shape.stride() as usize;
let used = self.shape.segments_per_group() as usize * stride;
let capacity = self.shape.segment_capacity();
let segments = self.shape.segments() as usize;
Some(
self.state
.chunks_exact(self.shape.words_per_group() as usize)
.flat_map(move |group| group[..used].chunks_exact(stride))
.take(segments)
.map(move |segment| {
let live = segment[SLOT_LIVE_LEN as usize].min(capacity) as usize;
&segment[SLOT_FIRST_TOKEN as usize..SLOT_FIRST_TOKEN as usize + live]
}),
)
}
#[must_use]
pub const fn passes(&self) -> u32 {
self.passes
}
#[must_use]
pub fn segment_passes(&self, segment: u32) -> u32 {
self.segment_passes
.get(segment as usize)
.copied()
.unwrap_or(0)
}
#[must_use]
pub fn segment_changed(&self, segment: u32) -> u32 {
self.segment_changed
.get(segment as usize)
.copied()
.unwrap_or(0)
}
#[must_use]
pub fn unconverged_segments(&self) -> Vec<u32> {
self.segment_changed
.iter()
.enumerate()
.filter(|(_, changed)| **changed != 0)
.map(|(index, _)| index as u32)
.collect()
}
#[must_use]
pub const fn termination(&self) -> Termination {
self.termination
}
}
impl Drop for LoopOutcome {
fn drop(&mut self) {
let _ = STAGING_POOL.try_with(|pool| {
let pool = &mut *pool.borrow_mut();
park(&mut pool.current, std::mem::take(&mut self.state));
park(
&mut pool.segment_passes,
std::mem::take(&mut self.segment_passes),
);
park(
&mut pool.segment_changed,
std::mem::take(&mut self.segment_changed),
);
});
}
}
#[must_use]
pub fn device_loop_program(
shape: LoopShape,
pass_body: Vec<Node>,
caller_buffers: Vec<BufferDecl>,
) -> Program {
build_loop_program(
OP_ID,
shape,
shape.max_passes(),
pass_body,
caller_buffers,
StateReadback::Discarded,
)
}
#[must_use]
pub fn single_pass_program(
shape: LoopShape,
pass_body: Vec<Node>,
caller_buffers: Vec<BufferDecl>,
) -> Program {
build_loop_program(
OP_ID_SINGLE_PASS,
shape,
1,
pass_body,
caller_buffers,
StateReadback::Discarded,
)
}
#[must_use]
pub fn single_pass_program_returning_state(
shape: LoopShape,
pass_body: Vec<Node>,
caller_buffers: Vec<BufferDecl>,
) -> Program {
build_loop_program(
OP_ID_SINGLE_PASS,
shape,
1,
pass_body,
caller_buffers,
StateReadback::Full,
)
}
pub fn run_device_loop(
backend: &dyn VyreBackend,
program: &Program,
batch: &LoopBatch,
caller_inputs: &[Vec<u8>],
) -> Result<LoopOutcome, ExatokError> {
let borrowed: Vec<&[u8]> = caller_inputs.iter().map(Vec::as_slice).collect();
run_device_loop_borrowed(backend, program, batch, &host_inputs(&borrowed))
}
pub(crate) fn run_device_loop_borrowed(
backend: &dyn VyreBackend,
program: &Program,
batch: &LoopBatch,
caller_inputs: &[CallerInput<'_>],
) -> Result<LoopOutcome, ExatokError> {
let mut window = PassWindow::seed(batch);
dispatch_window(backend, program, batch.shape(), &mut window, caller_inputs)?;
Ok(window.into_outcome(batch.shape()))
}
pub fn run_host_driven_loop(
backend: &dyn VyreBackend,
one_pass: &Program,
batch: &LoopBatch,
caller_inputs: &[Vec<u8>],
) -> Result<LoopOutcome, ExatokError> {
let shape = batch.shape();
let borrowed: Vec<&[u8]> = caller_inputs.iter().map(Vec::as_slice).collect();
let inputs = host_inputs(&borrowed);
let mut window = PassWindow::seed(batch);
for _ in 0..shape.max_passes() {
dispatch_window(backend, one_pass, shape, &mut window, &inputs)?;
if !window.any_segment_moved() {
break;
}
}
Ok(window.into_outcome(shape))
}
struct PassWindow {
staging: Staging,
passes: u32,
}
#[derive(Debug, Default)]
struct Staging {
current: Vec<u32>,
segment_passes: Vec<u32>,
segment_changed: Vec<u32>,
changed: Vec<u32>,
current_bytes: Vec<u8>,
passes_bytes: Vec<u8>,
segment_changed_bytes: Vec<u8>,
segment_passes_bytes: Vec<u8>,
next_filler: Vec<u8>,
changed_filler: Vec<u8>,
}
thread_local! {
static STAGING_POOL: RefCell<Staging> = RefCell::new(Staging::default());
}
const MAX_PARKED_CAPACITY: usize = 64 << 20;
fn take_staging() -> Staging {
STAGING_POOL
.try_with(|pool| std::mem::take(&mut *pool.borrow_mut()))
.unwrap_or_default()
}
fn park<T>(slot: &mut Vec<T>, buffer: Vec<T>) {
if buffer.capacity() > slot.capacity() && buffer.capacity() <= MAX_PARKED_CAPACITY {
*slot = buffer;
}
}
fn park_staging(staging: Staging) {
let _ = STAGING_POOL.try_with(|pool| {
let pool = &mut *pool.borrow_mut();
park(&mut pool.current, staging.current);
park(&mut pool.segment_passes, staging.segment_passes);
park(&mut pool.segment_changed, staging.segment_changed);
park(&mut pool.changed, staging.changed);
park(&mut pool.current_bytes, staging.current_bytes);
park(&mut pool.passes_bytes, staging.passes_bytes);
park(&mut pool.segment_changed_bytes, staging.segment_changed_bytes);
park(&mut pool.segment_passes_bytes, staging.segment_passes_bytes);
park(&mut pool.next_filler, staging.next_filler);
park(&mut pool.changed_filler, staging.changed_filler);
});
}
impl PassWindow {
fn seed(batch: &LoopBatch) -> Self {
let shape = batch.shape();
let segments = shape.segments() as usize;
let mut staging = take_staging();
staging.current.clear();
staging.current.extend_from_slice(batch.state());
pack_u32_slice_into(batch.state(), &mut staging.current_bytes);
staging.segment_passes.clear();
staging.segment_passes.resize(segments, 0);
staging.segment_changed.clear();
staging.segment_changed.resize(segments, 0);
staging.changed.clear();
Self { staging, passes: 0 }
}
fn size_changed_filler(&mut self, words: u32) {
let bytes = words as usize * 4;
if self.staging.changed_filler.len() != bytes {
self.staging.changed_filler = vec![0; bytes];
}
}
fn any_segment_moved(&self) -> bool {
self.staging
.segment_changed
.iter()
.any(|changed| *changed != 0)
}
fn into_outcome(mut self, shape: LoopShape) -> LoopOutcome {
normalize_padding(shape, &mut self.staging.current);
let converged = !self.any_segment_moved();
let mut staging = self.staging;
let outcome = LoopOutcome {
shape,
state: std::mem::take(&mut staging.current),
passes: self.passes,
segment_passes: std::mem::take(&mut staging.segment_passes),
segment_changed: std::mem::take(&mut staging.segment_changed),
termination: if converged {
Termination::Converged
} else {
Termination::CapReached
},
};
park_staging(staging);
outcome
}
}
fn normalize_padding(shape: LoopShape, state: &mut [u32]) {
let owned = shape.segments_per_group() * shape.stride();
let width = shape.words_per_group() as usize;
for (index, word) in state.iter_mut().enumerate() {
let offset = index % width;
let group = index / width;
let segment = group as u32 * shape.segments_per_group() + offset as u32 / shape.stride();
if offset as u32 >= owned || segment >= shape.segments() {
*word = DEAD_SLOT;
}
}
}
fn cooperative_gate(
fits: bool,
allows_split: bool,
blocks: u32,
limit: impl FnOnce() -> u32,
) -> Result<(), ExatokError> {
if fits || allows_split {
return Ok(());
}
let limit = limit();
if limit == 0 {
return Err(ExatokError::Backend(format!(
"gpu_loop needs {blocks} co-resident block(s) to grid-synchronize this batch, \
but this backend admits no cooperative launch of this program at any grid \
size and refuses a host kernel split. \
Fix: run a single-group batch, which needs no grid synchronization at all"
)));
}
Err(ExatokError::Backend(format!(
"gpu_loop needs {blocks} co-resident block(s) to grid-synchronize this batch, \
but this device admits at most {limit}. \
Fix: dispatch fewer pretokens per batch so the grid fits in {limit} block(s). \
Lowering the group count instead would leave segments without lanes"
)))
}
fn probe_block_limit(ceiling: u32, mut fits_at: impl FnMut(u32) -> Option<bool>) -> u32 {
let mut low = 0;
let mut high = ceiling;
while high - low > 1 {
let mid = low + (high - low) / 2;
match fits_at(mid) {
Some(true) => low = mid,
Some(false) => high = mid,
None => return low,
}
}
low
}
fn check_cooperative_residency(
backend: &dyn VyreBackend,
program: &Program,
inputs: &[&[u8]],
config: &DispatchConfig,
blocks: u32,
) -> Result<(), ExatokError> {
let fits = backend
.cooperative_grid_sync_fits(program, inputs, config)
.map_err(|error| {
ExatokError::Backend(format!(
"gpu_loop could not compute the cooperative launch geometry: {error}. \
Fix: rebuild the backend and retry, because the geometry predicate answering \
at all is a driver-level property no batch shape can repair"
))
})?;
cooperative_gate(fits, backend.allows_host_grid_sync_split(), blocks, || {
probe_block_limit(blocks, |candidate| {
let mut probe = config.clone();
probe.grid_override = Some([candidate, 1, 1]);
backend
.cooperative_grid_sync_fits(program, inputs, &probe)
.ok()
})
})
}
fn changed_words(program: &Program) -> u32 {
program
.buffers()
.iter()
.find(|buffer| buffer.name.as_ref() == NAME_CHANGED)
.map_or(1, |buffer| buffer.count.max(1))
}
fn launch_geometry(program: &Program, shape: LoopShape) -> (DispatchConfig, u32) {
let mut config = DispatchConfig::default();
config.dispatch_elements = Some(shape.state_words());
let workgroup = program.workgroup_size();
let lanes_per_group = workgroup[0].max(1) * workgroup[1].max(1) * workgroup[2].max(1);
let groups = shape.state_words().div_ceil(lanes_per_group);
config.grid_override = Some([groups.max(1), 1, 1]);
config.workgroup_override = Some(workgroup);
config.label = Some(OP_ID.to_owned());
(config, groups.max(1))
}
fn probe_inputs(program: &Program) -> Vec<Vec<u8>> {
program
.buffers()
.iter()
.map(|buffer| vec![0u8; buffer.count.max(1) as usize * 4])
.collect()
}
#[must_use]
pub fn cooperative_block_ceiling(
backend: &dyn VyreBackend,
program: &Program,
shape: LoopShape,
) -> u32 {
if !contains_grid_sync(program) {
return 0;
}
let inputs = probe_inputs(program);
let borrowed: Vec<&[u8]> = inputs.iter().map(Vec::as_slice).collect();
let (config, _) = launch_geometry(program, shape);
let fits_at = |blocks: u32| {
let mut probe = config.clone();
probe.grid_override = Some([blocks, 1, 1]);
backend
.cooperative_grid_sync_fits(program, &borrowed, &probe)
.ok()
};
if fits_at(1) != Some(true) {
return 0;
}
let mut ceiling = 2;
while fits_at(ceiling) == Some(true) {
match ceiling.checked_mul(2) {
Some(doubled) => ceiling = doubled,
None => return u32::MAX,
}
}
probe_block_limit(ceiling, fits_at)
}
#[derive(Clone, Copy)]
pub(crate) enum CallerInput<'a> {
Host(&'a [u8]),
Resident {
resource: &'a Resource,
bytes: &'a [u8],
},
}
impl<'a> CallerInput<'a> {
const fn bytes(&self) -> &'a [u8] {
match self {
Self::Host(bytes) | Self::Resident { bytes, .. } => bytes,
}
}
const fn resident(&self) -> Option<&'a Resource> {
match self {
Self::Host(_) => None,
Self::Resident { resource, .. } => Some(resource),
}
}
}
fn host_inputs<'a>(caller_inputs: &[&'a [u8]]) -> Vec<CallerInput<'a>> {
caller_inputs
.iter()
.map(|bytes| CallerInput::Host(bytes))
.collect()
}
enum ResidentBinding<'a> {
Staged(&'a [u8]),
Overwritten(usize),
}
impl ResidentBinding<'_> {
const fn len(&self) -> usize {
match self {
Self::Staged(bytes) => bytes.len(),
Self::Overwritten(len) => *len,
}
}
}
fn dispatch_resident(
backend: &dyn VyreBackend,
program: &Program,
bindings: &[ResidentBinding<'_>],
resident: &[Option<&Resource>],
config: &DispatchConfig,
) -> Result<Vec<Vec<u8>>, ExatokError> {
debug_assert_eq!(
bindings.len(),
resident.len(),
"every binding must say whether it is already resident"
);
let mut owned: Vec<Resource> = Vec::with_capacity(bindings.len());
let mut resources: Vec<Resource> = Vec::with_capacity(bindings.len());
let mut staging = Ok(());
for (binding, already) in bindings.iter().zip(resident) {
if let Some(resource) = already {
resources.push((*resource).clone());
continue;
}
if binding.len() == 0 {
staging = Err(ExatokError::Backend(
"gpu_loop resident dispatch cannot bind a zero-length buffer. \
Fix: every harness buffer must carry at least one word"
.to_string(),
));
break;
}
match backend.allocate_resident(binding.len()) {
Ok(resource) => {
if let ResidentBinding::Staged(bytes) = binding {
if let Err(error) = backend.upload_resident(&resource, bytes) {
owned.push(resource);
staging = Err(ExatokError::Backend(format!(
"gpu_loop resident upload failed: {error}. \
Fix: drop the session and bind a fresh one, since a buffer the \
backend just allocated refusing its upload marks the device \
context as suspect"
)));
break;
}
}
owned.push(resource.clone());
resources.push(resource);
}
Err(error) => {
staging = Err(ExatokError::Backend(format!(
"gpu_loop resident allocation of {} byte(s) failed: {error}. \
Fix: free device memory and retry, or encode without a resident session \
so buffers are bound from host memory per call",
binding.len()
)));
break;
}
}
}
let dispatched = staging.and_then(|()| {
backend
.dispatch_resident_timed(program, &resources, config)
.map(|timed| timed.outputs)
.map_err(|error| {
ExatokError::Backend(format!(
"gpu_loop resident dispatch failed: {error}. \
Fix: re-run the encode; if it repeats, re-create the backend to rule \
out a stale device context before suspecting the program"
))
})
});
for resource in owned {
backend.free_resident(resource).map_err(|error| {
ExatokError::Backend(format!("gpu_loop resident free failed: {error}"))
})?;
}
dispatched
}
fn dispatch_window(
backend: &dyn VyreBackend,
program: &Program,
shape: LoopShape,
window: &mut PassWindow,
caller_inputs: &[CallerInput<'_>],
) -> Result<(), ExatokError> {
let words = window.staging.current.len();
let segments = window.staging.segment_passes.len();
let changed = changed_words(program);
window.size_changed_filler(changed);
let use_resident = caller_inputs
.iter()
.any(|input| input.resident().is_some());
pack_u32_slice_into(
&window.staging.current,
&mut window.staging.current_bytes,
);
pack_u32_slice_into(&[window.passes], &mut window.staging.passes_bytes);
pack_u32_slice_into(
&window.staging.segment_changed,
&mut window.staging.segment_changed_bytes,
);
pack_u32_slice_into(
&window.staging.segment_passes,
&mut window.staging.segment_passes_bytes,
);
if !use_resident && window.staging.next_filler.len() != words * 4 {
window.staging.next_filler = vec![0xFF; words * 4];
}
let next_binding: &[u8] = if use_resident {
&window.staging.current_bytes
} else {
&window.staging.next_filler
};
let harness: [&[u8]; HARNESS_BUFFERS] = [
&window.staging.current_bytes,
next_binding,
&window.staging.changed_filler,
&window.staging.passes_bytes,
&window.staging.segment_changed_bytes,
&window.staging.segment_passes_bytes,
];
let mut inputs: Vec<&[u8]> = Vec::with_capacity(HARNESS_BUFFERS + caller_inputs.len());
inputs.extend_from_slice(&harness);
inputs.extend(caller_inputs.iter().map(CallerInput::bytes));
let mut resident: Vec<Option<&Resource>> = Vec::with_capacity(inputs.len());
resident.extend(std::iter::repeat_n(None, HARNESS_BUFFERS));
resident.extend(caller_inputs.iter().map(CallerInput::resident));
let mut seed_is_read: Vec<bool> = Vec::with_capacity(inputs.len());
seed_is_read.extend_from_slice(&HARNESS_SEED_IS_READ);
seed_is_read.extend(std::iter::repeat_n(true, caller_inputs.len()));
let (config, groups) = launch_geometry(program, shape);
if contains_grid_sync(program) {
check_cooperative_residency(backend, program, &inputs, &config, groups.max(1))?;
}
let outputs = if use_resident {
let bindings: Vec<ResidentBinding<'_>> = inputs
.iter()
.zip(&seed_is_read)
.map(|(bytes, seeded)| {
if *seeded {
ResidentBinding::Staged(bytes)
} else {
ResidentBinding::Overwritten(bytes.len())
}
})
.collect();
dispatch_resident(backend, program, &bindings, &resident, &config)?
} else {
backend
.dispatch_borrowed(program, &inputs, &config)
.map_err(|error| {
ExatokError::Backend(format!(
"gpu_loop dispatch failed: {error}. \
Fix: retry on a freshly created backend, because a launch with buffers \
bound per call fails for driver reasons the input cannot cause"
))
})?
};
if outputs.len() < HARNESS_BUFFERS {
return Err(ExatokError::Backend(format!(
"gpu_loop dispatch returned {} output buffer(s), needs {HARNESS_BUFFERS}. \
Fix: keep the six harness buffers declared ReadWrite so the backend returns them",
outputs.len()
)));
}
read_words(
&outputs[0],
words,
NAME_STATE_CURRENT,
&mut window.staging.current,
)?;
let declared_next_bytes = declared_readback_bytes(program, BINDING_STATE_NEXT, words);
if outputs[1].len() != declared_next_bytes {
return Err(ExatokError::Backend(format!(
"gpu_loop read {} byte(s) back from `{NAME_STATE_NEXT}`, which declares {} byte(s). \
Fix: honour BufferDecl::output_byte_range on this backend",
outputs[1].len(),
declared_next_bytes
)));
}
read_words(
&outputs[2],
changed as usize,
NAME_CHANGED,
&mut window.staging.changed,
)?;
window.passes = read_word(&outputs[3], NAME_PASSES)?;
read_words(
&outputs[4],
segments,
NAME_SEGMENT_CHANGED,
&mut window.staging.segment_changed,
)?;
read_words(
&outputs[5],
segments,
NAME_SEGMENT_PASSES,
&mut window.staging.segment_passes,
)?;
Ok(())
}
fn read_words(
bytes: &[u8],
count: usize,
label: &str,
out: &mut Vec<u32>,
) -> Result<(), ExatokError> {
unpack_u32_slice_into(bytes, count, label, out).map_err(ExatokError::Backend)
}
fn read_word(bytes: &[u8], label: &str) -> Result<u32, ExatokError> {
let mut word = Vec::new();
read_words(bytes, 1, label, &mut word)?;
word.first().copied().ok_or_else(|| {
ExatokError::Backend(format!(
"gpu_loop read no word from `{label}`. Fix: declare it with a one-word count"
))
})
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum StateReadback {
Discarded,
Full,
}
fn build_loop_program(
op_id: &str,
shape: LoopShape,
max_passes: u32,
pass_body: Vec<Node>,
caller_buffers: Vec<BufferDecl>,
state_readback: StateReadback,
) -> Program {
if let Some(message) = shape_rejection(shape, max_passes, &pass_body, &caller_buffers) {
return trap_program(op_id, NAME_STATE_CURRENT, DataType::U32, message);
}
let state_words = shape.state_words();
let mut body = Vec::with_capacity(pass_body.len() + 8);
body.extend(open_pass(shape));
body.extend(pass_body);
body.push(barrier());
body.extend(close_pass(shape));
let primitive = if shape.groups() > 1 {
persistent_fixpoint_grid(
body,
NAME_STATE_CURRENT,
NAME_STATE_NEXT,
NAME_CHANGED,
state_words,
max_passes,
)
} else {
persistent_fixpoint(
body,
NAME_STATE_CURRENT,
NAME_STATE_NEXT,
NAME_CHANGED,
state_words,
max_passes,
)
};
let program = vyre_libs::region::tag_program(op_id, primitive);
let segments = shape.segments();
let mut buffers = program.buffers().to_vec();
if state_readback == StateReadback::Discarded {
narrow_readback_to_nothing(&mut buffers, NAME_STATE_NEXT);
}
buffers.push(word_buffer(NAME_PASSES, BINDING_PASSES, 1));
buffers.push(word_buffer(
NAME_SEGMENT_CHANGED,
BINDING_SEGMENT_CHANGED,
segments,
));
buffers.push(word_buffer(
NAME_SEGMENT_PASSES,
BINDING_SEGMENT_PASSES,
segments,
));
buffers.extend(caller_buffers);
program.with_rewritten_buffers(buffers)
}
fn narrow_readback_to_nothing(buffers: &mut [BufferDecl], name: &str) {
for buffer in buffers.iter_mut() {
if buffer.name() == name {
*buffer = buffer.clone().with_output_byte_range(0..0);
}
}
}
fn declared_readback_bytes(program: &Program, binding: u32, words: usize) -> usize {
program
.buffers()
.iter()
.find(|buffer| buffer.binding == binding)
.and_then(BufferDecl::output_byte_range)
.map_or(words * 4, |range| range.len())
}
fn open_pass(shape: LoopShape) -> Vec<Node> {
vec![
Node::if_then(
Expr::eq(lane(), Expr::u32(0)),
vec![Node::let_bind(
"wt_tick",
Expr::atomic_add(NAME_PASSES, Expr::u32(0), Expr::u32(1)),
)],
),
Node::if_then(
lane_live(shape),
vec![Node::if_then(
Expr::eq(slot(shape), Expr::u32(0)),
vec![Node::store(NAME_SEGMENT_CHANGED, segment(shape), Expr::u32(0))],
)],
),
barrier(),
]
}
fn close_pass(shape: LoopShape) -> Vec<Node> {
vec![
Node::if_then(
lane_dead(shape),
vec![Node::store(NAME_STATE_NEXT, lane(), Expr::u32(DEAD_SLOT))],
),
Node::if_then(
lane_live(shape),
vec![
Node::let_bind("wt_cur", Expr::load(NAME_STATE_CURRENT, lane())),
Node::let_bind("wt_nxt", Expr::load(NAME_STATE_NEXT, lane())),
Node::if_then(
Expr::ne(Expr::var("wt_cur"), Expr::var("wt_nxt")),
vec![Node::let_bind(
"wt_mark",
Expr::atomic_or(NAME_SEGMENT_CHANGED, segment(shape), Expr::u32(1)),
)],
),
],
),
barrier(),
Node::if_then(
lane_live(shape),
vec![Node::if_then(
Expr::eq(slot(shape), Expr::u32(0)),
vec![Node::if_then(
Expr::ne(Expr::load(NAME_SEGMENT_CHANGED, segment(shape)), Expr::u32(0)),
vec![Node::let_bind(
"wt_seg_tick",
Expr::atomic_add(NAME_SEGMENT_PASSES, segment(shape), Expr::u32(1)),
)],
)],
)],
),
barrier(),
]
}
#[must_use]
pub fn segment_coordinates(shape: LoopShape) -> Vec<Node> {
vec![
Node::let_bind("seg", segment(shape)),
Node::let_bind("slot", slot(shape)),
Node::let_bind(
"base",
Expr::add(
Expr::mul(group_index(), Expr::u32(LOOP_WORKGROUP_WIDTH)),
Expr::mul(
Expr::div(group_offset(), Expr::u32(shape.stride())),
Expr::u32(shape.stride()),
),
),
),
Node::let_bind(
"len",
Expr::load(
NAME_STATE_CURRENT,
Expr::add(Expr::var("base"), Expr::u32(SLOT_LIVE_LEN)),
),
),
]
}
fn lane() -> Expr {
Expr::gid_x()
}
fn group_offset() -> Expr {
Expr::rem(lane(), Expr::u32(LOOP_WORKGROUP_WIDTH))
}
fn group_index() -> Expr {
Expr::div(lane(), Expr::u32(LOOP_WORKGROUP_WIDTH))
}
fn segment(shape: LoopShape) -> Expr {
Expr::add(
Expr::mul(group_index(), Expr::u32(shape.segments_per_group())),
Expr::div(group_offset(), Expr::u32(shape.stride())),
)
}
fn slot(shape: LoopShape) -> Expr {
Expr::rem(group_offset(), Expr::u32(shape.stride()))
}
fn lane_live(shape: LoopShape) -> Expr {
Expr::and(
Expr::lt(
group_offset(),
Expr::u32(shape.segments_per_group() * shape.stride()),
),
Expr::lt(segment(shape), Expr::u32(shape.segments())),
)
}
fn lane_dead(shape: LoopShape) -> Expr {
Expr::or(
Expr::ge(
group_offset(),
Expr::u32(shape.segments_per_group() * shape.stride()),
),
Expr::ge(segment(shape), Expr::u32(shape.segments())),
)
}
#[must_use]
pub fn lane_is_live(shape: LoopShape) -> Expr {
lane_live(shape)
}
fn barrier() -> Node {
Node::Barrier {
ordering: MemoryOrdering::SeqCst,
}
}
fn word_buffer(name: &str, binding: u32, count: u32) -> BufferDecl {
BufferDecl::storage(name, binding, BufferAccess::ReadWrite, DataType::U32).with_count(count)
}
fn shape_rejection(
shape: LoopShape,
max_passes: u32,
pass_body: &[Node],
caller_buffers: &[BufferDecl],
) -> Option<String> {
if shape.segments() == 0 {
return Some(
"segments is 0: an empty batch has no pretoken to converge. \
Fix: build the LoopShape from the pretokens in this dispatch"
.to_owned(),
);
}
if shape.segment_capacity() == 0 {
return Some(
"segment_capacity is 0: a segment with no token slots holds only its length word. \
Fix: size the capacity from the longest pretoken in the batch, which is at least 1"
.to_owned(),
);
}
let stride = shape.stride();
if stride > LOOP_WORKGROUP_WIDTH {
return Some(format!(
"segment_capacity {} needs a stride of {stride} words, past the \
{LOOP_WORKGROUP_WIDTH} one workgroup covers: a segment cannot straddle a workgroup \
boundary, because the pass body's barriers order writes only within a group. \
Fix: cap a single pretoken at {} tokens. The number of pretokens per dispatch is \
unbounded, only one pretoken's own length is limited",
shape.segment_capacity(),
LOOP_WORKGROUP_WIDTH - 1
));
}
if max_passes == 0 {
return Some(
"max_passes is 0: the loop would never run the pass body and would report the \
untouched seed as a converged tokenization. \
Fix: use merge_pass_bound(longest pretoken in the batch)"
.to_owned(),
);
}
if pass_body.is_empty() {
return Some(
"pass_body is empty: it would leave the next buffer untouched, so the loop would \
converge on whatever that scratch already held. \
Fix: emit a body that writes every slot of the next state, including the length \
word and the DEAD_SLOT tail"
.to_owned(),
);
}
caller_buffer_rejection(caller_buffers)
}
fn caller_buffer_rejection(caller_buffers: &[BufferDecl]) -> Option<String> {
const RESERVED: [&str; HARNESS_BUFFERS] = [
NAME_STATE_CURRENT,
NAME_STATE_NEXT,
NAME_CHANGED,
NAME_PASSES,
NAME_SEGMENT_CHANGED,
NAME_SEGMENT_PASSES,
];
let mut seen: Vec<u32> = Vec::with_capacity(caller_buffers.len());
for buffer in caller_buffers {
if buffer.binding() < FIRST_CALLER_BINDING {
return Some(format!(
"caller_buffers declares `{}` at binding {}, which the loop harness owns: it \
would alias the ping-pong or a convergence flag and read as a mysterious \
non-convergence. \
Fix: number pass-body buffers from {FIRST_CALLER_BINDING} upward",
buffer.name(),
buffer.binding()
));
}
if RESERVED.contains(&buffer.name()) {
return Some(format!(
"caller_buffers reuses the harness buffer name `{}`, which would shadow it in \
the IR name space even on a free binding. \
Fix: rename the pass-body buffer",
buffer.name()
));
}
if seen.contains(&buffer.binding()) {
return Some(format!(
"caller_buffers declares binding {} twice, so one of the two would be dropped at \
bind time and the pass body would read whichever bound last. \
Fix: give every pass-body buffer its own binding",
buffer.binding()
));
}
seen.push(buffer.binding());
}
None
}
#[cfg(test)]
mod tests {
use super::*;
use std::cell::Cell;
use vyre_primitives::wire::pack_u32_slice;
fn stub_body() -> Vec<Node> {
vec![Node::store(NAME_STATE_NEXT, Expr::u32(0), Expr::u32(0))]
}
fn top_level_barriers(nodes: &[Node]) -> usize {
nodes
.iter()
.filter(|node| matches!(node, Node::Barrier { .. }))
.count()
}
fn innermost_body(nodes: &[Node]) -> &[Node] {
for node in nodes {
match node {
Node::Region { body, .. } => return innermost_body(body),
Node::Block(inner) => return innermost_body(inner),
Node::Loop { body, .. } => return innermost_body(body),
_ => {}
}
}
nodes
}
#[test]
fn the_pass_body_barrier_is_still_emitted() {
let program = device_loop_program(LoopShape::new(2, 4, 4), stub_body(), Vec::new());
let body = innermost_body(program.entry());
assert_eq!(
top_level_barriers(body),
7,
"expected 7 top-level barriers in the fixpoint loop body. A count of 6 \
means the barrier between the pass body and the compare and copy step \
was removed, which is a real race on hardware that no other test in this \
crate detects. \
Fix: restore `body.push(barrier())` after `body.extend(pass_body)`. \
A count of 8 or more means the primitive changed its own barrier \
placement: re-derive the split before editing this number."
);
}
fn caller_buffer(name: &str, binding: u32) -> BufferDecl {
BufferDecl::storage(name, binding, BufferAccess::ReadOnly, DataType::U32).with_count(8)
}
fn trap_message(nodes: &[Node]) -> Option<String> {
for node in nodes {
let found = match node {
Node::Trap { tag, .. } => Some(tag.as_str().to_owned()),
Node::Region { body, .. } => trap_message(body),
Node::Block(inner) => trap_message(inner),
Node::If { then, otherwise, .. } => {
trap_message(then).or_else(|| trap_message(otherwise))
}
Node::Loop { body, .. } => trap_message(body),
_ => None,
};
if found.is_some() {
return found;
}
}
None
}
fn trap_for(shape: LoopShape) -> Option<String> {
trap_message(device_loop_program(shape, stub_body(), Vec::new()).entry())
}
#[test]
fn stride_reserves_one_slot_per_segment_for_the_live_length() {
let shape = LoopShape::new(3, 4, 4);
assert_eq!(shape.stride(), 5);
assert_eq!(shape.segments_per_group(), 51);
assert_eq!(shape.groups(), 1);
assert_eq!(shape.state_words(), LOOP_WORKGROUP_WIDTH);
assert_eq!(shape.segment_base(0), 0);
assert_eq!(shape.segment_base(1), 5);
assert_eq!(shape.segment_base(2), 10);
}
#[test]
fn no_segment_straddles_a_workgroup_boundary() {
for capacity in [1_u32, 2, 3, 4, 7, 15, 16, 31, 63, 127, 254] {
let shape = LoopShape::new(1000, capacity, 4);
let stride = shape.stride();
for segment in 0..shape.segments() {
let base = shape.segment_base(segment);
let last = base + stride - 1;
assert_eq!(
base / LOOP_WORKGROUP_WIDTH,
last / LOOP_WORKGROUP_WIDTH,
"capacity {capacity}: segment {segment} spans words {base}..={last}, \
which crosses a group boundary"
);
assert!(
last < shape.state_words(),
"capacity {capacity}: segment {segment} ends at {last}, past the {} allocated",
shape.state_words()
);
}
}
}
#[test]
fn distinct_segments_never_share_a_state_word() {
for capacity in [1_u32, 3, 4, 5, 16, 51, 127] {
let shape = LoopShape::new(500, capacity, 4);
let mut owner = vec![u32::MAX; shape.state_words() as usize];
for segment in 0..shape.segments() {
let base = shape.segment_base(segment) as usize;
for word in base..base + shape.stride() as usize {
assert_eq!(
owner[word],
u32::MAX,
"capacity {capacity}: word {word} claimed by both segment {} and {segment}",
owner[word]
);
owner[word] = segment;
}
}
}
}
#[test]
fn merge_pass_bound_is_the_longest_segment_length() {
assert_eq!(merge_pass_bound(0), 1);
assert_eq!(merge_pass_bound(1), 1);
assert_eq!(merge_pass_bound(2), 2);
assert_eq!(merge_pass_bound(16), 16);
assert_eq!(merge_pass_bound(506), 506);
let batch: Vec<Vec<u32>> = vec![vec![1, 2, 3], vec![4], vec![5, 6, 7, 8, 9]];
assert_eq!(longest_segment(&batch), 5);
assert_eq!(merge_pass_bound(longest_segment(&batch)), 5);
}
#[test]
fn longest_segment_of_an_empty_batch_is_zero() {
let empty: Vec<Vec<u32>> = Vec::new();
assert_eq!(longest_segment(&empty), 0);
}
fn segment_window(batch: &LoopBatch, segment: u32) -> &[u32] {
let shape = batch.shape();
let base = shape.segment_base(segment) as usize;
&batch.state()[base..base + shape.stride() as usize]
}
#[test]
fn state_words_never_under_allocates_any_segment_it_sizes() {
for capacity in 0u32..=300 {
for segments in 0u32..=9 {
let shape = LoopShape::new(segments, capacity, 1);
assert_eq!(
shape.words_per_group() % LOOP_WORKGROUP_WIDTH,
0,
"a group must stay a whole number of workgroup widths, else \
lane / width no longer names the group: capacity {capacity}"
);
for segment in 0..segments {
let end = shape.segment_base(segment) + shape.stride();
assert!(
end <= shape.state_words(),
"segment {segment} of {segments} at capacity {capacity} ends \
at word {end} but the batch only sizes {} words",
shape.state_words()
);
}
}
}
}
#[test]
fn no_two_segments_share_a_word_at_any_capacity() {
for capacity in 0u32..=64 {
let shape = LoopShape::new(9, capacity, 1);
let stride = shape.stride() as usize;
let mut owner = vec![u32::MAX; shape.state_words() as usize];
for segment in 0..shape.segments() {
let base = shape.segment_base(segment) as usize;
for word in &mut owner[base..base + stride] {
assert_eq!(
*word,
u32::MAX,
"capacity {capacity}: segment {segment} claims a word already \
owned by segment {word}"
);
*word = segment;
}
}
}
}
#[test]
fn batch_layout_pads_every_segment_to_a_uniform_stride() {
let batch = LoopBatch::new(&[vec![11, 22, 33], vec![44]], 3);
assert_eq!(batch.shape().segments(), 2);
assert_eq!(batch.shape().segment_capacity(), 3);
assert_eq!(batch.shape().max_passes(), 3);
assert_eq!(segment_window(&batch, 0), &[3, 11, 22, 33]);
assert_eq!(segment_window(&batch, 1), &[1, 44, DEAD_SLOT, DEAD_SLOT]);
assert_eq!(batch.state().len(), LOOP_WORKGROUP_WIDTH as usize);
}
#[test]
fn batch_layout_handles_empty_pretokens() {
let batch = LoopBatch::new(&[vec![7, 8], Vec::new()], 2);
assert_eq!(segment_window(&batch, 0), &[2, 7, 8]);
assert_eq!(segment_window(&batch, 1), &[0, DEAD_SLOT, DEAD_SLOT]);
let all_empty = LoopBatch::new(&[Vec::<u32>::new(), Vec::new()], 1);
assert_eq!(all_empty.shape().segment_capacity(), 1);
assert_eq!(all_empty.shape().stride(), 2);
assert_eq!(segment_window(&all_empty, 0), &[0, DEAD_SLOT]);
assert_eq!(segment_window(&all_empty, 1), &[0, DEAD_SLOT]);
}
#[test]
fn a_token_equal_to_the_dead_marker_stays_live() {
let batch = LoopBatch::new(&[vec![DEAD_SLOT, 5]], 2);
assert_eq!(segment_window(&batch, 0), &[2, DEAD_SLOT, 5]);
let outcome = LoopOutcome {
shape: batch.shape(),
state: batch.state().to_vec(),
passes: 1,
segment_passes: vec![0],
segment_changed: vec![0],
termination: Termination::Converged,
};
assert_eq!(outcome.tokens(0), &[DEAD_SLOT, 5]);
}
#[test]
fn sound_bound_comes_from_the_longest_pretoken() {
let batch = LoopBatch::with_sound_bound(&[vec![1], vec![1, 2, 3, 4]]);
assert_eq!(batch.shape().max_passes(), 4);
assert_eq!(batch.shape().segment_capacity(), 4);
}
#[test]
fn an_over_long_pretoken_traps_but_a_wide_batch_does_not() {
assert_eq!(trap_for(LoopShape::new(1, 255, 4)), None);
let message = trap_for(LoopShape::new(1, 256, 4)).unwrap_or_default();
assert!(
message.contains("257") && message.contains("256") && message.contains("Fix:"),
"trap must name the stride, the limit, and a fix, got: {message}"
);
assert!(
message.contains("255"),
"trap must name the per-pretoken token cap, got: {message}"
);
for (segments, capacity) in [(16_u32, 16_u32), (1000, 3), (100_000, 1), (60, 254)] {
assert_eq!(
trap_for(LoopShape::new(segments, capacity, 4)),
None,
"a batch of {segments} pretokens of capacity {capacity} must dispatch, \
because pretokens per dispatch is unbounded"
);
}
}
#[test]
fn degenerate_layouts_trap_with_distinct_messages() {
let no_segments = trap_for(LoopShape::new(0, 4, 4)).unwrap_or_default();
assert!(
no_segments.contains("segments is 0"),
"trap must name segments, got: {no_segments}"
);
let no_capacity = trap_for(LoopShape::new(2, 0, 4)).unwrap_or_default();
assert!(
no_capacity.contains("segment_capacity is 0"),
"trap must name segment_capacity, got: {no_capacity}"
);
}
#[test]
fn a_zero_pass_budget_traps() {
let message = trap_for(LoopShape::new(2, 4, 0)).unwrap_or_default();
assert!(
message.contains("max_passes is 0") && message.contains("merge_pass_bound"),
"trap must name max_passes and point at the sound bound, got: {message}"
);
}
#[test]
fn an_empty_pass_body_traps() {
let program = device_loop_program(LoopShape::new(2, 4, 4), Vec::new(), Vec::new());
let message = trap_message(program.entry()).unwrap_or_default();
assert!(
message.contains("pass_body is empty"),
"trap must name pass_body, got: {message}"
);
}
#[test]
fn a_caller_buffer_on_a_harness_binding_traps() {
let shape = LoopShape::new(2, 4, 4);
for binding in 0..FIRST_CALLER_BINDING {
let program =
device_loop_program(shape, stub_body(), vec![caller_buffer("ranks", binding)]);
let message = trap_message(program.entry()).unwrap_or_default();
assert!(
message.contains("caller_buffers") && message.contains(&binding.to_string()),
"binding {binding} must trap and be named, got: {message}"
);
}
let ok = device_loop_program(
shape,
stub_body(),
vec![caller_buffer("ranks", FIRST_CALLER_BINDING)],
);
assert_eq!(trap_message(ok.entry()), None);
}
#[test]
fn a_caller_buffer_reusing_a_harness_name_traps() {
for name in [
NAME_STATE_CURRENT,
NAME_STATE_NEXT,
NAME_CHANGED,
NAME_PASSES,
NAME_SEGMENT_CHANGED,
NAME_SEGMENT_PASSES,
] {
let program = device_loop_program(
LoopShape::new(2, 4, 4),
stub_body(),
vec![caller_buffer(name, FIRST_CALLER_BINDING)],
);
let message = trap_message(program.entry()).unwrap_or_default();
assert!(
message.contains(name),
"reusing `{name}` must trap and name it, got: {message}"
);
}
}
#[test]
fn duplicate_caller_bindings_trap() {
let program = device_loop_program(
LoopShape::new(2, 4, 4),
stub_body(),
vec![
caller_buffer("ranks", FIRST_CALLER_BINDING),
caller_buffer("ids", FIRST_CALLER_BINDING),
],
);
let message = trap_message(program.entry()).unwrap_or_default();
assert!(
message.contains("twice"),
"trap must report the duplicate binding, got: {message}"
);
}
#[test]
fn the_program_declares_the_harness_buffers_in_binding_order() {
let shape = LoopShape::new(3, 4, 4);
let program = device_loop_program(
shape,
stub_body(),
vec![caller_buffer("ranks", FIRST_CALLER_BINDING)],
);
let names: Vec<&str> = program.buffers().iter().map(BufferDecl::name).collect();
assert_eq!(
names,
vec![
NAME_STATE_CURRENT,
NAME_STATE_NEXT,
NAME_CHANGED,
NAME_PASSES,
NAME_SEGMENT_CHANGED,
NAME_SEGMENT_PASSES,
"ranks",
]
);
let bindings: Vec<u32> = program.buffers().iter().map(BufferDecl::binding).collect();
assert_eq!(bindings, vec![0, 1, 2, 3, 4, 5, 6]);
let counts: Vec<u32> = program.buffers().iter().map(BufferDecl::count).collect();
assert_eq!(
counts,
vec![
LOOP_WORKGROUP_WIDTH,
LOOP_WORKGROUP_WIDTH,
1,
1,
3,
3,
8
]
);
}
#[test]
fn live_len_is_clamped_to_the_segment_capacity() {
let outcome = LoopOutcome {
shape: LoopShape::new(2, 2, 2),
state: vec![99, 5, 6, 1, 7, DEAD_SLOT],
passes: 1,
segment_passes: vec![0, 0],
segment_changed: vec![0, 0],
termination: Termination::Converged,
};
assert_eq!(outcome.live_len(0), 2);
assert_eq!(outcome.tokens(0), &[5, 6]);
assert_eq!(outcome.tokens(1), &[7]);
}
#[test]
fn converged_tokens_refuses_only_the_segments_still_moving() {
let capped = LoopOutcome {
shape: LoopShape::new(2, 2, 2),
state: vec![2, 40, 41, 1, 42, DEAD_SLOT],
passes: 2,
segment_passes: vec![2, 1],
segment_changed: vec![1, 0],
termination: Termination::CapReached,
};
assert_eq!(capped.tokens(0), &[40, 41]);
assert!(capped.converged_tokens(0).is_err());
assert_eq!(capped.converged_tokens(1).ok(), Some(&[42][..]));
assert_eq!(capped.unconverged_segments(), vec![0]);
assert!(!capped.termination().is_converged());
let converged = LoopOutcome {
shape: capped.shape(),
state: capped.state().to_vec(),
passes: capped.passes(),
segment_passes: vec![2, 1],
segment_changed: vec![0, 0],
termination: Termination::Converged,
};
assert_eq!(converged.converged_tokens(0).ok(), Some(&[40, 41][..]));
assert!(converged.unconverged_segments().is_empty());
assert!(converged.termination().is_converged());
}
#[test]
fn the_refusal_names_the_segment_and_the_pass_count() {
let capped = LoopOutcome {
shape: LoopShape::new(2, 2, 3),
state: vec![2, 40, 41, 1, 42, DEAD_SLOT],
passes: 3,
segment_passes: vec![3, 1],
segment_changed: vec![0, 1],
termination: Termination::CapReached,
};
let message = capped
.converged_tokens(1)
.err()
.map(|error| error.to_string())
.unwrap_or_default();
assert!(
message.contains("segment 1") && message.contains("3 pass"),
"refusal must name the segment and the pass count, got: {message}"
);
}
fn region_chain(nodes: &[Node]) -> Vec<(String, Option<String>)> {
let mut chain = Vec::new();
let mut level = nodes;
loop {
let mut descend = None;
for node in level {
if let Node::Region {
generator,
source_region,
body,
} = node
{
chain.push((
generator.as_str().to_owned(),
source_region.as_ref().map(|parent| parent.name.clone()),
));
descend = Some(body.as_slice());
break;
}
}
match descend {
Some(inner) => level = inner,
None => return chain,
}
}
}
#[test]
fn the_region_chain_attributes_the_composed_primitive() {
let program = device_loop_program(LoopShape::new(2, 4, 4), stub_body(), Vec::new());
let chain = region_chain(program.entry());
assert_eq!(
chain.first().map(|entry| entry.0.as_str()),
Some(OP_ID),
"the outermost region must be this op, got: {chain:?}"
);
assert_eq!(
chain.get(1).map(|entry| entry.0.as_str()),
Some(vyre_primitives::fixpoint::persistent_fixpoint::OP_ID),
"the composed primitive must keep its own generator, got: {chain:?}"
);
assert_eq!(
chain.get(1).and_then(|entry| entry.1.as_deref()),
Some(OP_ID),
"the composed primitive must point back at this op, got: {chain:?}"
);
}
#[test]
fn the_single_pass_program_carries_its_own_op_id() {
let program = single_pass_program(LoopShape::new(2, 4, 4), stub_body(), Vec::new());
let chain = region_chain(program.entry());
assert_eq!(
chain.first().map(|entry| entry.0.as_str()),
Some(OP_ID_SINGLE_PASS)
);
assert_eq!(
chain.get(1).and_then(|entry| entry.1.as_deref()),
Some(OP_ID_SINGLE_PASS)
);
assert_ne!(OP_ID, OP_ID_SINGLE_PASS);
}
#[test]
fn op_ids_declare_the_tier_four_prefix() {
for op_id in [OP_ID, OP_ID_SINGLE_PASS] {
assert!(
op_id.starts_with("exatok::gpu_loop::"),
"`{op_id}` must be namespaced under this crate and module"
);
}
}
fn refusal(fits: bool, allows_split: bool, blocks: u32, limit: u32) -> String {
match cooperative_gate(fits, allows_split, blocks, || limit) {
Ok(()) => "<gate admitted the dispatch>".to_owned(),
Err(error) => format!("{error}"),
}
}
#[test]
fn the_gate_admits_exactly_the_launches_that_can_run() {
assert!(cooperative_gate(true, true, 4, || 0).is_ok());
assert!(cooperative_gate(true, false, 4, || 0).is_ok());
assert!(cooperative_gate(false, true, 4, || 0).is_ok());
assert!(cooperative_gate(false, false, 4, || 2).is_err());
}
#[test]
fn an_admitted_dispatch_never_pays_for_the_limit() {
for (fits, allows_split) in [(true, false), (false, true), (true, true)] {
let probes = Cell::new(0u32);
let result = cooperative_gate(fits, allows_split, 4, || {
probes.set(probes.get() + 1);
0
});
assert!(result.is_ok(), "fits={fits} allows_split={allows_split}");
assert_eq!(
probes.get(),
0,
"admitted dispatch probed for a limit it never reports"
);
}
}
#[test]
fn a_refusal_names_the_required_blocks_and_the_device_limit() {
let text = refusal(false, false, 9, 5);
assert!(text.contains("needs 9 co-resident block(s)"), "got: {text}");
assert!(text.contains("at most 5"), "got: {text}");
assert!(text.contains("Fix: "), "got: {text}");
}
#[test]
fn a_backend_with_no_cooperative_launch_says_so_instead_of_naming_zero() {
let text = refusal(false, false, 9, 0);
assert!(text.contains("no cooperative launch"), "got: {text}");
assert!(!text.contains("at most 0"), "got: {text}");
}
#[test]
fn the_probe_recovers_the_exact_largest_admitted_grid() {
for limit in 0u32..24 {
for ceiling in (limit + 1)..40 {
let found = probe_block_limit(ceiling, |candidate| Some(candidate <= limit));
assert_eq!(found, limit, "ceiling {ceiling}, true limit {limit}");
}
}
}
#[test]
fn the_probe_never_reports_the_ceiling_it_was_given() {
for ceiling in 1u32..40 {
let found = probe_block_limit(ceiling, |_| Some(true));
assert_eq!(found, ceiling - 1, "ceiling {ceiling}");
}
}
#[test]
fn a_failed_probe_falls_back_to_the_last_proven_fit() {
let seen = Cell::new(0u32);
let found = probe_block_limit(16, |candidate| {
seen.set(seen.get() + 1);
if seen.get() == 1 {
Some(candidate <= 8)
} else {
None
}
});
assert_eq!(found, 8);
assert_eq!(seen.get(), 2, "the search must stop at the failed query");
}
#[test]
fn a_probe_that_fails_immediately_reports_nothing_proven() {
assert_eq!(probe_block_limit(16, |_| None), 0);
}
#[test]
fn a_batch_wider_than_one_workgroup_selects_the_grid_form() {
let shape = LoopShape::new(40, 15, 15);
assert_eq!(shape.groups(), 3, "40 segments of stride 16");
let program = device_loop_program(shape, stub_body(), Vec::new());
assert!(
contains_grid_sync(&program),
"a multi-group batch must separate its waves with GridSync"
);
let chain = region_chain(program.entry());
assert_eq!(
chain.get(1).map(|entry| entry.0.as_str()),
Some(vyre_primitives::fixpoint::persistent_fixpoint::OP_ID_GRID),
"got: {chain:?}"
);
}
#[test]
fn a_batch_inside_one_workgroup_keeps_the_in_kernel_form() {
let shape = LoopShape::new(2, 4, 4);
assert_eq!(shape.groups(), 1);
let program = device_loop_program(shape, stub_body(), Vec::new());
assert!(
!contains_grid_sync(&program),
"one workgroup needs no grid barrier"
);
let chain = region_chain(program.entry());
assert_eq!(
chain.get(1).map(|entry| entry.0.as_str()),
Some(vyre_primitives::fixpoint::persistent_fixpoint::OP_ID),
"got: {chain:?}"
);
}
#[test]
fn the_changed_buffer_widens_to_the_pass_budget_only_for_the_grid_form() {
let single = device_loop_program(LoopShape::new(2, 4, 9), stub_body(), Vec::new());
assert_eq!(changed_words(&single), 1);
let grid = device_loop_program(LoopShape::new(40, 15, 9), stub_body(), Vec::new());
assert_eq!(changed_words(&grid), 9, "one word per pass of the budget");
}
fn decode_waves(changed: &[u32]) -> u32 {
changed
.iter()
.position(|word| *word == 0)
.map_or(changed.len() as u32, |index| index as u32 + 1)
}
fn dispatch_once(batch: &LoopBatch, body: Vec<Node>) -> PassWindow {
let program = device_loop_program(batch.shape(), body, Vec::new());
let mut window = PassWindow::seed(batch);
let dispatched = dispatch_window(
&vyre_driver_reference::CpuRefBackend,
&program,
batch.shape(),
&mut window,
&[],
);
assert!(dispatched.is_ok(), "reference dispatch must succeed");
window
}
fn wide_batch(segments: u32) -> LoopBatch {
let pretokens: Vec<Vec<u32>> = (0..segments).map(|_| vec![1u32, 2, 3, 4]).collect();
LoopBatch::with_sound_bound(&pretokens)
}
#[test]
fn the_harness_pass_count_agrees_with_the_primitives_own_wave_flags() {
let batch = wide_batch(200);
assert!(
batch.shape().groups() > 1,
"must span several groups, or this exercises the single-word form \
whose one flag carries no per-wave history"
);
let settled = dispatch_once(
&batch,
vec![Node::store(
NAME_STATE_NEXT,
lane(),
Expr::load(NAME_STATE_CURRENT, lane()),
)],
);
assert_eq!(settled.passes, 1, "a fixed point settles in one wave");
assert_eq!(decode_waves(&settled.staging.changed), settled.passes);
assert_eq!(
settled.staging.changed.first().copied(),
Some(0),
"the first wave moved nothing, so its flag must be clear"
);
let capped = dispatch_once(
&batch,
vec![Node::store(
NAME_STATE_NEXT,
lane(),
Expr::add(Expr::load(NAME_STATE_CURRENT, lane()), Expr::u32(1)),
)],
);
let budget = batch.shape().max_passes();
assert_eq!(capped.passes, budget, "a body that never settles runs out");
assert_eq!(decode_waves(&capped.staging.changed), capped.passes);
assert!(
capped.staging.changed.iter().all(|word| *word != 0),
"every wave moved state, so no flag may be clear"
);
}
#[test]
fn the_wave_flag_array_returns_at_its_declared_width() {
let batch = wide_batch(200);
let window = dispatch_once(
&batch,
vec![Node::store(
NAME_STATE_NEXT,
lane(),
Expr::load(NAME_STATE_CURRENT, lane()),
)],
);
assert_eq!(window.staging.changed.len() as u32, batch.shape().max_passes());
}
fn carry_through_body(shape: LoopShape) -> Vec<Node> {
let mut inner = segment_coordinates(shape);
inner.push(Node::store(
NAME_STATE_NEXT,
lane(),
Expr::load(NAME_STATE_CURRENT, lane()),
));
vec![Node::if_then(lane_is_live(shape), inner)]
}
fn shrink_body(shape: LoopShape) -> Vec<Node> {
let mut inner = segment_coordinates(shape);
inner.push(Node::if_then_else(
Expr::eq(Expr::var("slot"), Expr::u32(0)),
vec![Node::if_then_else(
Expr::eq(Expr::var("len"), Expr::u32(0)),
vec![Node::store(NAME_STATE_NEXT, lane(), Expr::u32(0))],
vec![Node::store(
NAME_STATE_NEXT,
lane(),
Expr::sub(Expr::var("len"), Expr::u32(1)),
)],
)],
vec![
Node::let_bind("token", Expr::sub(Expr::var("slot"), Expr::u32(1))),
Node::if_then_else(
Expr::ge(
Expr::add(Expr::var("token"), Expr::u32(1)),
Expr::var("len"),
),
vec![Node::store(NAME_STATE_NEXT, lane(), Expr::u32(DEAD_SLOT))],
vec![Node::store(
NAME_STATE_NEXT,
lane(),
Expr::load(NAME_STATE_CURRENT, lane()),
)],
),
],
));
vec![Node::if_then(lane_is_live(shape), inner)]
}
fn length_only_body(shape: LoopShape) -> Vec<Node> {
let mut inner = segment_coordinates(shape);
inner.push(Node::if_then(
Expr::eq(Expr::var("slot"), Expr::u32(0)),
vec![Node::store(NAME_STATE_NEXT, lane(), Expr::var("len"))],
));
vec![Node::if_then(lane_is_live(shape), inner)]
}
fn dispatch_seeded(batch: &LoopBatch, body: Vec<Node>, poison: Option<u32>) -> PassWindow {
let program = device_loop_program(batch.shape(), body, Vec::new());
let mut window = PassWindow::seed(batch);
if let Some(word) = poison {
window.staging.next_filler = pack_u32_slice(&vec![word; batch.state().len()]);
window.staging.segment_changed = vec![word; batch.shape().segments() as usize];
}
let dispatched = dispatch_window(
&vyre_driver_reference::CpuRefBackend,
&program,
batch.shape(),
&mut window,
&[],
);
assert!(dispatched.is_ok(), "reference dispatch must succeed");
if poison.is_some() {
window.staging.next_filler = Vec::new();
}
window
}
fn assert_seed_independent(batch: &LoopBatch, body: impl Fn(LoopShape) -> Vec<Node>) {
let clean = dispatch_seeded(batch, body(batch.shape()), None);
for poison in [0u32, 0xdead_beef, DEAD_SLOT ^ 1] {
let dirty = dispatch_seeded(batch, body(batch.shape()), Some(poison));
assert_eq!(
clean.staging.current, dirty.staging.current,
"state must not depend on what {poison:#x} staged into the buffers the kernel \
overwrites"
);
assert_eq!(clean.passes, dirty.passes, "pass count must not depend on it");
assert_eq!(
clean.staging.segment_passes, dirty.staging.segment_passes,
"per-segment depths must not depend on it"
);
assert_eq!(
clean.staging.segment_changed, dirty.staging.segment_changed,
"the verdict must not depend on it"
);
}
}
fn mixed_batch(longest: u32, groups: u32, max_passes: u32) -> LoopBatch {
let per_group = LOOP_WORKGROUP_WIDTH / (longest + 1);
let segments = (per_group * groups).max(2);
let pretokens: Vec<Vec<u32>> = (0..segments)
.map(|index| {
let len = if index % 2 == 0 { 1 } else { longest };
(0..len).map(|slot| index * 1000 + slot + 1).collect()
})
.collect();
LoopBatch::new(&pretokens, max_passes)
}
#[test]
fn the_seed_read_table_lines_up_with_the_binding_numbering() {
let read = |binding: u32| HARNESS_SEED_IS_READ[binding as usize];
assert!(read(BINDING_STATE_CURRENT), "the tokens themselves");
assert!(!read(BINDING_STATE_NEXT), "overwritten whole every pass");
assert!(read(BINDING_CHANGED), "must arrive zeroed");
assert!(read(BINDING_PASSES), "accumulated with atomic_add");
assert!(!read(BINDING_SEGMENT_CHANGED), "cleared by open_pass");
assert!(read(BINDING_SEGMENT_PASSES), "accumulated with atomic_add");
assert_eq!(
HARNESS_SEED_IS_READ.iter().filter(|read| !**read).count(),
2,
"exactly two harness buffers are derivable on device; a third would need its own \
proof in the IR before it may be added here"
);
}
#[test]
fn the_back_buffer_declares_a_zero_length_readback_at_its_full_allocation() {
let batch = wide_batch(200);
let shape = batch.shape();
let program = device_loop_program(shape, carry_through_body(shape), Vec::new());
let next = program
.buffers()
.iter()
.find(|buffer| buffer.name() == NAME_STATE_NEXT);
assert_eq!(
next.and_then(BufferDecl::output_byte_range),
Some(0..0),
"the host consults nothing in the back buffer, so it must come home empty"
);
assert_eq!(
next.map(BufferDecl::count),
Some(shape.state_words()),
"the allocation must still cover every word the kernel writes"
);
let current = program
.buffers()
.iter()
.find(|buffer| buffer.name() == NAME_STATE_CURRENT);
assert_eq!(
current.and_then(BufferDecl::output_byte_range),
None,
"the front buffer carries the tokens home and must not be narrowed"
);
}
#[test]
fn the_inspection_program_returns_the_back_buffer_and_is_otherwise_identical() {
let batch = wide_batch(200);
let shape = batch.shape();
let shipped = single_pass_program(shape, carry_through_body(shape), Vec::new());
let inspecting =
single_pass_program_returning_state(shape, carry_through_body(shape), Vec::new());
let next_range = |program: &Program| {
program
.buffers()
.iter()
.find(|buffer| buffer.name() == NAME_STATE_NEXT)
.and_then(BufferDecl::output_byte_range)
};
assert_eq!(
next_range(&shipped),
Some(0..0),
"the shipped single-pass program must keep the narrow window"
);
assert_eq!(
next_range(&inspecting),
None,
"the inspection program must leave the window open, or a suite reading \
the back buffer indexes an empty vector instead of failing on contents"
);
let shape_of = |program: &Program| {
program
.buffers()
.iter()
.map(|buffer| (buffer.name().to_owned(), buffer.binding, buffer.count))
.collect::<Vec<_>>()
};
assert_eq!(
shape_of(&shipped),
shape_of(&inspecting),
"the two programs must declare the same bindings at the same widths"
);
assert_eq!(
shipped.workgroup_size(),
inspecting.workgroup_size(),
"the two programs must launch at the same width"
);
}
#[test]
fn poison_seed_does_not_reach_a_contract_abiding_body() {
for body in [
carry_through_body as fn(LoopShape) -> Vec<Node>,
shrink_body as fn(LoopShape) -> Vec<Node>,
] {
assert_seed_independent(&wide_batch(200), body);
let widest = mixed_batch(LOOP_WORKGROUP_WIDTH - 1, 3, 6);
assert_eq!(widest.shape().segments_per_group(), 1);
assert_seed_independent(&widest, body);
let tailed = mixed_batch(100, 4, 6);
assert_eq!(tailed.shape().segments_per_group(), 2);
assert!(tailed.shape().groups() > 1);
assert_seed_independent(&tailed, body);
}
}
#[test]
fn poison_seed_is_visible_to_a_body_that_skips_a_live_slot() {
let batch = mixed_batch(100, 4, 6);
let clean = dispatch_seeded(&batch, length_only_body(batch.shape()), None);
let dirty = dispatch_seeded(&batch, length_only_body(batch.shape()), Some(0xdead_beef));
assert_ne!(
clean.staging.current, dirty.staging.current,
"a body that leaves live slots of `{NAME_STATE_NEXT}` unwritten must expose the \
staged bytes, or the poison never reached the device and the invariance check \
above is vacuous"
);
}
#[test]
fn a_batch_mixing_the_shortest_and_longest_admissible_pretoken_converges_exactly() {
let longest = LOOP_WORKGROUP_WIDTH - 1;
let batch = mixed_batch(longest, 3, 4);
let shape = batch.shape();
assert_eq!(shape.segment_capacity(), longest, "the admissible maximum");
assert!(shape.groups() > 1, "must span groups");
for poison in [None, Some(0u32), Some(0xdead_beef)] {
let window = dispatch_seeded(&batch, carry_through_body(shape), poison);
let outcome = window.into_outcome(shape);
assert_eq!(outcome.termination(), Termination::Converged);
for segment in 0..shape.segments() {
let expected_len = if segment % 2 == 0 { 1 } else { longest };
let expected: Vec<u32> = (0..expected_len)
.map(|slot| segment * 1000 + slot + 1)
.collect();
assert_eq!(
outcome.converged_tokens(segment).ok(),
Some(expected.as_slice()),
"segment {segment} under poison {poison:?} must converge with its own tokens"
);
}
}
}
}