triblespace_gpu/batch_confirm.rs
1//! Batched WGPU confirmation for [`SuccinctArchive`] queries.
2//!
3//! The engine's [`Constraint::confirm`] protocol is kill-only: a confirmer
4//! receives one [`Candidates`] region (read-only values and parent tags,
5//! killable liveness bits packed into `u32` words) and may only clear them.
6//! That contract makes the archive's per-candidate membership probes
7//! embarrassingly parallel — every candidate's verdict is independent, and
8//! merging GPU verdicts back is a plain word-wise AND.
9//!
10//! A region spans a whole [`Frontier`], so its candidates do **not** share
11//! one parent binding: entry `i` carries the frontier row it was proposed
12//! for, and it has to be checked against *that* row's bound values. This is
13//! what makes the batched tier reachable below the root — with a width-1
14//! frontier only the root's proposal is wide, and every deeper level offers
15//! the device a handful of candidates.
16//!
17//! [`WgpuSuccinctArchive`] wraps a CPU [`SuccinctArchive`] and keeps the
18//! structures the confirm probes touch resident on the default WGPU device:
19//! the value universe (as big-endian `u32` words for lexicographic binary
20//! search), the three axis occupancy boundaries, and the six Ring wavelet
21//! matrices. Its [`WgpuSuccinctArchiveConstraint`] mirrors the canonical
22//! constraint exactly, except that `confirm` calls whose region holds at
23//! least [`min_confirm_batch`](WgpuSuccinctArchive::min_confirm_batch) live
24//! candidates are evaluated on the device:
25//!
26//! * **Unbound membership** (no other position bound; the confirmed variable
27//! is E, A, or V): one fused kernel per region — binary search of each
28//! candidate value in the resident universe plus an axis-boundary
29//! occupancy check — writes one packed verdict word per 32 candidates.
30//! Parent tags do not enter: the verdict does not depend on the parent
31//! binding.
32//! * **Range restriction** (one or two other positions bound): the host
33//! ships a *parent table* — one row per distinct parent tag in the region,
34//! holding that parent's bound values — plus one table slot per candidate.
35//! The device resolves the table to one row band per parent out of the
36//! same resident universe and boundary tables the probes use, then every
37//! candidate reads its own parent's band through its slot. The host never
38//! searches the universe or ranks a wavelet; it copies bound values and
39//! assigns slots.
40//!
41//! Below the threshold, on any device error, and for every other protocol
42//! method, the wrapper defers to the canonical CPU constraint, so results are
43//! bit-identical either way. `tests/batch_confirm_parity.rs` holds the two
44//! paths to identical liveness words for every arm against a frontier of
45//! one; `tests/mixed_parent_parity.rs` does the same for engine-produced
46//! regions spanning many parents.
47//!
48//! # Packed verdict words
49//!
50//! Core's liveness is bit-packed: a `u32` carries
51//! [`LIVENESS_WORD_BITS`] candidates and a region does not start on a word
52//! boundary. So the verdict kernels write **packed** verdict words — the flat
53//! index is the bit position in the region's liveness word array, one
54//! `plane_ballot` per plane yields a whole 32-candidate word already in the
55//! right bit order, and one lane per word stores it. See
56//! `membership_confirm_ballot_kernel` for the layout argument and its
57//! store-exclusivity conditions, and
58//! `WgpuSuccinctArchive::require_plane_packing` for the device property they
59//! rest on.
60//!
61//! The probe-fill kernels stay **candidate**-indexed: their outputs feed
62//! Jerky's per-candidate rank batch, which knows nothing about liveness. Only
63//! their liveness *input* is bit-addressed, through `candidate_is_live`.
64//!
65//! The host merge — `live_words()`, [`and_words`], `set_live_words()` over a
66//! *private* copy — knows nothing about the packing, because those three are
67//! an abstraction over liveness *words* rather than over candidates. The
68//! device never touches the shared `ProposalBuffer` liveness, so a confirm
69//! cannot disturb the neighbouring regions that share its first and last
70//! word: the copy-in/copy-out boundary is the guard, `live_words()` zeroes the
71//! bits the region does not own on the way out, and `set_live_words()`
72//! refuses to write them on the way back in.
73
74// The `#[cube]` kernels below nest their guards rather than joining them
75// with `&&`. That is load-bearing, not style: a device `&&` evaluates both
76// sides, so `d < m && universe[d * 8] == ..` would index past the resident
77// universe for the `d == m` (value absent) case that the guard exists to
78// exclude. Nesting is uniform across the kernels so no reader has to work
79// out which guards may be joined and which may not.
80#![allow(clippy::collapsible_if)]
81
82use std::sync::atomic::{AtomicU64, Ordering};
83
84use cubecl::prelude::*;
85use cubecl::wgpu::WgpuRuntime;
86use jerky::bit_vector::BitVectorIndex;
87use jerky::bit_vector::{BitVector, Select};
88use jerky::gpu::{DeviceU32Buffer, GpuContext, GpuWaveletMatrix};
89use triblespace_core::blob::encodings::succinctarchive::{
90 SuccinctArchive, SuccinctArchiveConstraint, SuccinctRotation, Universe,
91};
92use triblespace_core::inline::encodings::genid::GenId;
93use triblespace_core::inline::{InlineEncoding, RawInline};
94use triblespace_core::query::{
95 and_words, Binding, Candidates, Constraint, Frontier, ProposalBuffer, RawTerm, Term,
96 TriblePattern, VariableId, VariableSet, LIVENESS_WORD_BITS,
97};
98
99const THREADS: u32 = super::THREADS;
100
101/// The core/device liveness geometry contract, made a compile error.
102///
103/// Every packed kernel below hardcodes 32 in three separate places: the
104/// ballot component it reads (`ballot[0]` covers lanes 0..32), the
105/// `UNIT_POS_PLANE == 0` store guard (one store per 32-candidate word), and
106/// the `b / 32` / `b % 32` arithmetic that turns a flat bit position into a
107/// word index and a bit within it. None of that is derived from core's
108/// [`LIVENESS_WORD_BITS`] — WGSL has no `u64`, and the ballot is a hardware
109/// primitive whose width is the plane's, not the liveness word's.
110///
111/// So if core ever widens its liveness word, this crate would keep writing
112/// 32-bit verdict words into a wider array. That does not fail to compile and
113/// does not crash: every buffer length still type-checks, every index stays
114/// in range, and the only symptom is **verdict bits landing on the wrong
115/// candidates** — silently wrong query answers, on the confirm path, with no
116/// diagnostic anywhere. Whoever widens the word should instead get a build
117/// failure that names the kernels they have to widen with it.
118///
119/// This is deliberately stronger than the assert it replaces on the
120/// pre-collapse branch, which only checked that two crates agreed on *which*
121/// of two liveness representations was compiled in. With one representation
122/// left there is no such choice; the geometry is the whole contract.
123const _: () = assert!(
124 LIVENESS_WORD_BITS == 32,
125 "packed confirm hardcodes 32 bits per liveness word: the plane ballot's \
126 component 0, the one-store-per-plane guard, and the bit/word arithmetic \
127 in the confirm kernels all assume it. Widen those with the word."
128);
129
130/// Condition (a) of the packed kernels' store-exclusivity invariant: each
131/// cube's range of flat indices starts on a 32-bit word boundary, so no
132/// verdict word is split across two cubes. It holds because the flat id is
133/// `linear_cube_index * CUBE_DIM + local_index` and `CUBE_DIM` is a multiple
134/// of 32. Nothing else would notice a change to `THREADS`; this would produce
135/// wrong query answers and no diagnostic, so make it a compile error instead.
136const _: () = assert!(
137 THREADS % 32 == 0,
138 "packed confirm needs a cube dim that is a multiple of the 32-bit liveness word"
139);
140
141/// Jerky's out-of-range marker for a batched rank result.
142const RANK_OUT_OF_RANGE: u32 = u32::MAX;
143
144/// Jerky's wavelet matrix resident on the default CubeCL WGPU device.
145pub type WgpuWaveletMatrix = GpuWaveletMatrix<WgpuRuntime>;
146
147/// Jerky's shared compatibility domain on the default CubeCL WGPU device.
148pub type WgpuContext = GpuContext<WgpuRuntime>;
149
150/// Default minimum number of live candidates in a confirm region before the
151/// verdicts are computed on WGPU; smaller regions run the canonical CPU
152/// probes.
153///
154/// Measured on an Apple M4 Max (Metal via wgpu, cubecl 0.10), release
155/// profile, with the two ignored sweep benchmarks. `cpu/gpu` is total CPU
156/// probe time over total device time for the same regions, so above 1.00 the
157/// device wins.
158///
159/// **Mixed-parent regions** — `mixed_parent_crossover_sweep` in
160/// `tests/mixed_parent_parity.rs`: a 414,801-trible / 81,632-value archive
161/// driven through a real [`Query`](triblespace_core::query::Query) whose
162/// variable order is pinned, over frontier widths 256…16384 and fanouts
163/// 1/4/16, so every routed range confirm sees a genuine batch of parents.
164/// The spread in each cell is across those sweep points.
165///
166/// | mean region | 1-bound arm | 2-bound arm |
167/// |------------:|------------:|------------:|
168/// | 1 024 | 0.16 – 0.21 | — |
169/// | 4 096 | 0.42 – 0.81 | 0.56 – 0.65 |
170/// | 16 384 | 1.62 – 2.72 | 1.92 – 2.42 |
171/// | 65 536 | 3.58 – 6.82 | 5.75 – 6.84 |
172/// | 262 144 | 6.87 | 10.2 – 11.1 |
173///
174/// **Frontier of one** — `confirm_crossover_sweep` in
175/// `tests/batch_confirm_parity.rs`, a 262,135-trible / 68,422-value archive,
176/// one parent, which is where the membership arm is measured (it is
177/// parent-independent, so a batch tells it nothing new):
178///
179/// | region | membership | range |
180/// |-------:|-----------:|------:|
181/// | 1 024 | 0.04 | 0.14 |
182/// | 4 096 | 0.16 | 0.64 |
183/// | 16 384 | 0.72 | 2.02 |
184/// | 65 536 | 2.41 | 3.32 |
185///
186/// The device round trip is nearly flat (~1.2–2.6 ms) while CPU probe cost
187/// scales linearly, putting both range shapes' crossover at ~6–8k
188/// candidates. The lighter membership arm — one universe search and one
189/// boundary compare per candidate, no wavelet rank at all — is still at
190/// 0.72x at 16 384 and only wins from ~24k up, so it is membership, not the
191/// range shapes, that sets the knob.
192///
193/// 16384 is the single-knob compromise: the range shapes are a 1.6–2.7x win
194/// there and membership costs 1.4x, and it equals
195/// [`DEFAULT_FRONTIER_WIDTH`](triblespace_core::query::DEFAULT_FRONTIER_WIDTH),
196/// so a level whose rows each contribute one candidate already reaches the
197/// batched tier. Lowering it to the range shapes' own crossover would trade
198/// their gain for a deeper membership loss.
199///
200/// The number is unchanged from the pre-frontier measurement, but what it
201/// buys is not: resolving parent bands on the device rather than on the host
202/// took the mixed-parent range shapes from 1.6–5.4x to 2.7–11.1x at width
203/// 16384 (device time for a 262k-candidate 2-bound region: 13.4 ms → 7.3 ms),
204/// because the host no longer ranks a wavelet once per frontier row before
205/// it can dispatch.
206pub const DEFAULT_MIN_CONFIRM_BATCH: usize = 16384;
207
208/// Observational dispatch counters for one [`WgpuSuccinctArchive`].
209///
210/// Counters use relaxed atomics: snapshots taken after query completion are
211/// exact, concurrent snapshots are telemetry.
212#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
213pub struct WgpuConfirmStats {
214 /// Confirm calls whose verdicts were computed on the device.
215 pub gpu_confirms: u64,
216 /// Region entries (live and dead) shipped through device confirms.
217 pub gpu_candidates: u64,
218 /// Parent-table rows resolved on the device, summed over routed
219 /// confirms — one per distinct parent tag in a routed region, and the
220 /// measure of how wide the frontiers reaching the device actually are.
221 pub gpu_parents: u64,
222 /// Confirm calls routed to the canonical CPU constraint by the
223 /// live-candidate threshold.
224 pub cpu_fallback_confirms: u64,
225 /// Region entries handled by threshold fallbacks.
226 pub cpu_fallback_candidates: u64,
227 /// Device errors that demoted a routed confirm to the CPU path.
228 pub gpu_errors: u64,
229}
230
231#[derive(Default)]
232struct ConfirmStats {
233 gpu_confirms: AtomicU64,
234 gpu_candidates: AtomicU64,
235 gpu_parents: AtomicU64,
236 cpu_fallback_confirms: AtomicU64,
237 cpu_fallback_candidates: AtomicU64,
238 gpu_errors: AtomicU64,
239}
240
241impl ConfirmStats {
242 fn record_gpu(&self, candidates: usize, parents: usize) {
243 self.gpu_confirms.fetch_add(1, Ordering::Relaxed);
244 self.gpu_candidates
245 .fetch_add(candidates as u64, Ordering::Relaxed);
246 self.gpu_parents
247 .fetch_add(parents as u64, Ordering::Relaxed);
248 }
249
250 fn record_cpu(&self, candidates: usize) {
251 self.cpu_fallback_confirms.fetch_add(1, Ordering::Relaxed);
252 self.cpu_fallback_candidates
253 .fetch_add(candidates as u64, Ordering::Relaxed);
254 }
255
256 fn record_error(&self) {
257 self.gpu_errors.fetch_add(1, Ordering::Relaxed);
258 }
259
260 fn snapshot(&self) -> WgpuConfirmStats {
261 WgpuConfirmStats {
262 gpu_confirms: self.gpu_confirms.load(Ordering::Relaxed),
263 gpu_candidates: self.gpu_candidates.load(Ordering::Relaxed),
264 gpu_parents: self.gpu_parents.load(Ordering::Relaxed),
265 cpu_fallback_confirms: self.cpu_fallback_confirms.load(Ordering::Relaxed),
266 cpu_fallback_candidates: self.cpu_fallback_candidates.load(Ordering::Relaxed),
267 gpu_errors: self.gpu_errors.load(Ordering::Relaxed),
268 }
269 }
270
271 fn reset(&self) {
272 self.gpu_confirms.store(0, Ordering::Relaxed);
273 self.gpu_candidates.store(0, Ordering::Relaxed);
274 self.gpu_parents.store(0, Ordering::Relaxed);
275 self.cpu_fallback_confirms.store(0, Ordering::Relaxed);
276 self.cpu_fallback_candidates.store(0, Ordering::Relaxed);
277 self.gpu_errors.store(0, Ordering::Relaxed);
278 }
279}
280
281/// Byte-lexicographic three-way comparison between universe entry `d` and
282/// entry `i` of `probes`, both stored as 8 big-endian `u32` words.
283///
284/// Returns 0 when equal, 1 when the universe entry orders below the probe,
285/// 2 when it orders above.
286#[cube]
287fn value_order(universe: &Array<u32>, d: u32, probes: &Array<u32>, i: u32) -> u32 {
288 let mut order = u32::new(0);
289 let mut w = u32::new(0);
290 while w < 8u32 {
291 if order == 0u32 {
292 let dv = universe[(d * 8u32 + w) as usize];
293 let cv = probes[(i * 8u32 + w) as usize];
294 if dv < cv {
295 order = 1u32;
296 }
297 if dv > cv {
298 order = 2u32;
299 }
300 }
301 w += 1u32;
302 }
303 order
304}
305
306/// Lower-bound binary search for entry `i` of `probes` over the sorted
307/// resident universe of `m` entries. Returns `m` when every entry orders
308/// below the probe; equality still has to be checked at the returned slot.
309#[cube]
310fn universe_lower_bound(universe: &Array<u32>, m: u32, probes: &Array<u32>, i: u32) -> u32 {
311 let mut lo = u32::new(0);
312 let mut hi = m;
313 while lo < hi {
314 let mid = lo + (hi - lo) / 2u32;
315 if value_order(universe, mid, probes, i) == 1u32 {
316 lo = mid + 1u32;
317 } else {
318 hi = mid;
319 }
320 }
321 lo
322}
323
324/// The universe code of entry `i` of `probes`, or `m` when the value is
325/// absent from the universe.
326#[cube]
327fn universe_code(universe: &Array<u32>, m: u32, probes: &Array<u32>, i: u32) -> u32 {
328 let mut code = m;
329 let d = universe_lower_bound(universe, m, probes, i);
330 if d < m {
331 if value_order(universe, d, probes, i) == 0u32 {
332 code = d;
333 }
334 }
335 code
336}
337
338/// Whether candidate `i` of a region whose entry 0 sits at bit `bit_offset`
339/// is still live, read out of the region's packed liveness words.
340///
341/// The one place the device spells core's bit layout for *reading*: entry `i`
342/// is bit `bit_offset + i`, i.e. bit `(bit_offset + i) % 32` of word
343/// `(bit_offset + i) / 32`. Callers must have bounded `i` by the region's
344/// candidate count, which bounds the word index by `live`'s length.
345#[cube]
346fn candidate_is_live(live: &Array<u32>, bit_offset: u32, i: u32) -> u32 {
347 let b = bit_offset + i;
348 (live[(b / 32u32) as usize] >> (b % 32u32)) & 1u32
349}
350
351/// Packed verdict words for the unbound membership arms: a live candidate's
352/// bit survives exactly when its value occurs in the universe *and* the axis
353/// boundary table shows at least one row on the confirmed axis — the same
354/// probe as the CPU arm's `base_range(..).is_empty().not()`. One
355/// `plane_ballot` per plane, one store per 32 candidates.
356///
357/// # The flat index is a bit position, not a candidate
358///
359/// `ABSOLUTE_POS` is `b`, the bit position inside the region's liveness word
360/// array — candidate `i` is `b - bit_offset`, and bit `b` is bit `b % 32` of
361/// word `b / 32` *by construction*. That change of variable is the whole
362/// trick: a plane's 32 lanes cover `b .. b + 32`, so the hardware's ballot
363/// mask already carries each verdict in the bit its word wants it in. No
364/// rotation by `bit_offset`, no read-modify-write of a word two lanes share,
365/// no atomic. The price is that the dispatch covers `bit_offset + n` slots
366/// instead of `n` — at most 31 idle lanes, i.e. at most one extra cube.
367///
368/// Bit slots below `bit_offset`, or at and above `bit_offset + n`, belong to
369/// the *neighbouring* regions of the same buffer. They take verdict `false`,
370/// which is the value that survives both host masks unchanged: `live_words()`
371/// already handed those bits out as `0`, and `set_live_words()` will not write
372/// them back.
373///
374/// # Store exclusivity
375///
376/// Verdict word `w` is written by exactly one invocation of the whole
377/// dispatch — the one whose `b` equals `32 * w`. Three conditions buy that:
378///
379/// * **(a)** `CubeDim` is 1-D and a multiple of 32 (`THREADS == 64`), and the
380/// WGSL backend's flat id reduces to `linear_cube_index * CUBE_DIM +
381/// local_index`, so `ABSOLUTE_POS` is dense and every cube's range starts on
382/// a word boundary. This holds whether or not cubecl spreads the dispatch
383/// over 2 or 3 grid dimensions, because the `y`/`z` strides it uses are both
384/// multiples of `CUBE_DIM`.
385/// * **(b)** the plane is exactly 32 lanes, so one plane owns exactly one word
386/// and no word straddles two planes. Checked on the host in
387/// [`WgpuSuccinctArchive::require_plane_packing`]: below 32, two planes would
388/// each store the same word and the last writer would win; above 32, lane 32
389/// would need ballot component 1 and this kernel hardcodes component 0.
390/// * **(c)** `UNIT_POS_PLANE` (WGSL `subgroup_invocation_id`) is the lane's
391/// position in the linear order the flat id follows, so ballot bit `L` is the
392/// verdict of the lane whose `b` is `plane_base + L`. True on every Metal and
393/// CUDA adapter; *not* promised by the WGSL subgroups extension, whose
394/// invocation-to-subgroup mapping is implementation-defined. A violation
395/// produces wrong query answers and no diagnostic — the non-zero
396/// `bit_offset` bases in `tests/batch_confirm_parity.rs` are what would
397/// catch it.
398///
399/// Every word of `verdicts` is stored, which matters because `empty_u32`
400/// hands back uninitialized device memory: the dispatch rounds
401/// `bit_offset + n` up to whole cubes of 64 lanes, and that always contains
402/// the lane `b == 32 * w` for every `w < words`.
403///
404/// The `plane_ballot` sits at the kernel's top-level control flow, so every
405/// unit of every plane reaches it. That is deliberate rather than incidental:
406/// `cubecl-wgpu` never claims `Plane::NonUniformControlFlow` on the plain WGSL
407/// path this crate builds, so a ballot inside the liveness branch would be
408/// betting on semantics the backend does not promise. The branch costs nothing
409/// to keep *below* the ballot — dead candidates still skip the binary search.
410#[cube(launch_unchecked)]
411fn membership_confirm_ballot_kernel(
412 cands: &Array<u32>,
413 live: &Array<u32>,
414 universe: &Array<u32>,
415 bounds: &Array<u32>,
416 verdicts: &mut Array<u32>,
417 n: u32,
418 m: u32,
419 bit_offset: u32,
420) {
421 let b = ABSOLUTE_POS as u32;
422 let n_bits = bit_offset + n;
423 let words = (n_bits + 31u32) / 32u32;
424
425 let mut verdict = u32::new(0);
426 if b >= bit_offset {
427 if b < n_bits {
428 // `b < n_bits` bounds `b / 32` by `words`, so this load is in
429 // range; the bit it reads is candidate `b - bit_offset`.
430 let i = b - bit_offset;
431 if candidate_is_live(live, bit_offset, i) != 0u32 {
432 let d = universe_code(universe, m, cands, i);
433 if d < m {
434 if bounds[(d + 1u32) as usize] > bounds[d as usize] {
435 verdict = 1u32;
436 }
437 }
438 }
439 }
440 }
441
442 // UNIFORM: reached by every unit of the plane, see the note above.
443 let ballot = plane_ballot(verdict != 0u32);
444
445 // One store per word. Deliberately not `plane_elect`, which returns the
446 // lowest *active* lane and so couples this store's correctness to the
447 // uniformity we are separately maintaining. With condition (b) the plane
448 // is 32 wide, so this is its lane 0 and its ballot occupies component 0 of
449 // the 128-bit result.
450 if UNIT_POS_PLANE == 0u32 {
451 let w = b / 32u32;
452 if w < words {
453 verdicts[w as usize] = ballot[0];
454 }
455 }
456}
457
458/// Writes candidate `i`'s rank-probe pair given the row band `start..end`
459/// its parent restricts the archive to: probe positions are the band, probe
460/// values the candidate's universe code. Dead, absent, or empty-band
461/// candidates get `flag = 0` and a harmless `(0, code 0)` pair — an empty
462/// band restricts to nothing, exactly as the CPU arm's
463/// `restrict_range(..).is_empty()` does.
464///
465/// `flags`, `positions` and `probes` are indexed by the **candidate**, not by
466/// a bit position: they feed Jerky's per-candidate rank batch. Only the
467/// liveness input is bit-addressed, at `bit_offset + i`.
468#[cube]
469#[allow(clippy::too_many_arguments)]
470fn emit_candidate_probe(
471 cands: &Array<u32>,
472 live: &Array<u32>,
473 universe: &Array<u32>,
474 i: u32,
475 m: u32,
476 bit_offset: u32,
477 start: u32,
478 end: u32,
479 flags: &mut Array<u32>,
480 positions: &mut Array<u32>,
481 probes: &mut Array<u32>,
482) {
483 let mut flag = u32::new(0);
484 let mut code = u32::new(0);
485 let mut lo = u32::new(0);
486 let mut hi = u32::new(0);
487 if candidate_is_live(live, bit_offset, i) != 0u32 {
488 if start < end {
489 let d = universe_code(universe, m, cands, i);
490 if d < m {
491 flag = 1u32;
492 code = d;
493 lo = start;
494 hi = end;
495 }
496 }
497 }
498 flags[i as usize] = flag;
499 positions[(2u32 * i) as usize] = lo;
500 positions[(2u32 * i + 1u32) as usize] = hi;
501 probes[(2u32 * i) as usize] = code;
502 probes[(2u32 * i + 1u32) as usize] = code;
503}
504
505/// Probe fill for the **single-bound** range arms. Each candidate reads its
506/// own parent's bound value through its table slot and resolves that
507/// parent's row band inline — the CPU arm's
508/// `base_range(domain, axis, value)`, read straight out of the resident
509/// boundary table instead of two `select1`s, with an absent value yielding
510/// an empty band exactly as `base_range`'s `else` branch does.
511///
512/// Resolving per candidate rather than per parent repeats one universe
513/// search for candidates that share a parent. That is deliberate: the search
514/// is a handful of coalesced compares in a thread that is running anyway,
515/// while a separate parent pass would cost a whole dispatch — measurably
516/// more than the redundancy at every region size above the routing
517/// threshold.
518#[cube(launch_unchecked)]
519fn base_probe_fill_kernel(
520 cands: &Array<u32>,
521 live: &Array<u32>,
522 universe: &Array<u32>,
523 slots: &Array<u32>,
524 parent_values: &Array<u32>,
525 bounds: &Array<u32>,
526 flags: &mut Array<u32>,
527 positions: &mut Array<u32>,
528 probes: &mut Array<u32>,
529 n: u32,
530 m: u32,
531 bit_offset: u32,
532) {
533 let i = ABSOLUTE_POS as u32;
534 if i < n {
535 let mut start = u32::new(0);
536 let mut end = u32::new(0);
537 if candidate_is_live(live, bit_offset, i) != 0u32 {
538 let slot = slots[i as usize];
539 let d = universe_code(universe, m, parent_values, slot);
540 if d < m {
541 start = bounds[d as usize];
542 end = bounds[(d + 1u32) as usize];
543 }
544 }
545 emit_candidate_probe(
546 cands, live, universe, i, m, bit_offset, start, end, flags, positions, probes,
547 );
548 }
549}
550
551/// Parent pass for the **double-bound** range arms: the outer bound value's
552/// base range becomes a rank probe pair on the inner rotation, the inner
553/// bound value's code the probe symbol. Either value absent from the
554/// universe clears the flag, which
555/// [`restrict_probe_fill_kernel`] reads as an empty band — the CPU arm's
556/// nested `restrict_range(.., base_range(..))` with both `else` branches
557/// folded into one.
558///
559/// This pass cannot be fused into the candidate kernel: its result *is* a
560/// wavelet rank, and that is a dispatch of its own.
561#[cube(launch_unchecked)]
562fn parent_restrict_probe_kernel(
563 universe: &Array<u32>,
564 outer_bounds: &Array<u32>,
565 outer_values: &Array<u32>,
566 inner_values: &Array<u32>,
567 codes: &mut Array<u32>,
568 flags: &mut Array<u32>,
569 positions: &mut Array<u32>,
570 probes: &mut Array<u32>,
571 p: u32,
572 m: u32,
573) {
574 let j = ABSOLUTE_POS as u32;
575 if j < p {
576 let mut flag = u32::new(0);
577 let mut code = u32::new(0);
578 let mut lo = u32::new(0);
579 let mut hi = u32::new(0);
580 let outer = universe_code(universe, m, outer_values, j);
581 if outer < m {
582 let inner = universe_code(universe, m, inner_values, j);
583 if inner < m {
584 flag = 1u32;
585 code = inner;
586 lo = outer_bounds[outer as usize];
587 hi = outer_bounds[(outer + 1u32) as usize];
588 }
589 }
590 codes[j as usize] = code;
591 flags[j as usize] = flag;
592 positions[(2u32 * j) as usize] = lo;
593 positions[(2u32 * j + 1u32) as usize] = hi;
594 probes[(2u32 * j) as usize] = code;
595 probes[(2u32 * j + 1u32) as usize] = code;
596 }
597}
598
599/// Probe fill for the **double-bound** range arms: each candidate folds its
600/// own parent's rank pair into that parent's row band —
601/// `restrict_range`'s `base + rank(r.start, d) .. base + rank(r.end, d)` —
602/// and emits its own probe against it.
603#[cube(launch_unchecked)]
604fn restrict_probe_fill_kernel(
605 cands: &Array<u32>,
606 live: &Array<u32>,
607 universe: &Array<u32>,
608 slots: &Array<u32>,
609 parent_flags: &Array<u32>,
610 parent_codes: &Array<u32>,
611 parent_ranks: &Array<u32>,
612 inner_bounds: &Array<u32>,
613 flags: &mut Array<u32>,
614 positions: &mut Array<u32>,
615 probes: &mut Array<u32>,
616 n: u32,
617 m: u32,
618 out_of_range: u32,
619 bit_offset: u32,
620) {
621 let i = ABSOLUTE_POS as u32;
622 if i < n {
623 let mut start = u32::new(0);
624 let mut end = u32::new(0);
625 if candidate_is_live(live, bit_offset, i) != 0u32 {
626 let slot = slots[i as usize];
627 if parent_flags[slot as usize] != 0u32 {
628 let lo = parent_ranks[(2u32 * slot) as usize];
629 let hi = parent_ranks[(2u32 * slot + 1u32) as usize];
630 // A band read out of the resident boundary tables is always
631 // a valid rank position, so `out_of_range` cannot occur
632 // here; an empty band is the kill-only reading if it ever
633 // did.
634 if lo != out_of_range {
635 if hi != out_of_range {
636 let base = inner_bounds[parent_codes[slot as usize] as usize];
637 start = base + lo;
638 end = base + hi;
639 }
640 }
641 }
642 }
643 emit_candidate_probe(
644 cands, live, universe, i, m, bit_offset, start, end, flags, positions, probes,
645 );
646 }
647}
648
649/// Folds the batched wavelet ranks into packed verdict words: a flagged
650/// candidate survives exactly when its code occurs inside its parent's row
651/// band — `rank(r.start, d) != rank(r.end, d)`, the CPU arm's
652/// `restrict_range(..).is_empty().not()` with the shared `select1` base
653/// offset cancelled.
654///
655/// Identical in structure to `membership_confirm_ballot_kernel` — flat index
656/// is the bit position `b`, out-of-region slots vote `false`, one ballot per
657/// plane, one store per word — with the universe probe replaced by the rank
658/// comparison. Its store-exclusivity argument is the one documented there.
659/// Note that `flags` and `ranks` are still indexed by the **candidate**
660/// `b - bit_offset`, because the probe fills wrote them per-candidate.
661#[cube(launch_unchecked)]
662fn range_verdict_ballot_kernel(
663 flags: &Array<u32>,
664 ranks: &Array<u32>,
665 verdicts: &mut Array<u32>,
666 n: u32,
667 out_of_range: u32,
668 bit_offset: u32,
669) {
670 let b = ABSOLUTE_POS as u32;
671 let n_bits = bit_offset + n;
672 let words = (n_bits + 31u32) / 32u32;
673
674 let mut verdict = u32::new(0);
675 if b >= bit_offset {
676 if b < n_bits {
677 // `flags` already folded in liveness: the probe fill zeroed it for
678 // every dead, absent, or empty-band candidate.
679 let i = b - bit_offset;
680 if flags[i as usize] != 0u32 {
681 let lo = ranks[(2u32 * i) as usize];
682 let hi = ranks[(2u32 * i + 1u32) as usize];
683 // Same kill-only reading of an impossible out-of-range rank as
684 // in the parent fold.
685 if lo != out_of_range {
686 if hi != out_of_range {
687 if lo != hi {
688 verdict = 1u32;
689 }
690 }
691 }
692 }
693 }
694 }
695
696 // UNIFORM: reached by every unit of the plane.
697 let ballot = plane_ballot(verdict != 0u32);
698
699 if UNIT_POS_PLANE == 0u32 {
700 let w = b / 32u32;
701 if w < words {
702 verdicts[w as usize] = ballot[0];
703 }
704 }
705}
706
707/// One of the three trible positions — which axis boundary table to read,
708/// and which position's value to take from a binding.
709#[derive(Clone, Copy, Debug, Eq, PartialEq)]
710enum Axis {
711 Entity,
712 Attribute,
713 Value,
714}
715
716/// What a routed confirm needs from each parent binding of the frontier.
717///
718/// The *bound set* is shared by every row of a frontier, so the arm — and
719/// therefore this plan — is classified once for the whole region. Only the
720/// bound *values*, and hence each parent's row band, vary by row.
721#[derive(Clone, Copy, Debug, Eq, PartialEq)]
722enum ConfirmPlan {
723 /// No other position is bound: an axis-occupancy probe per candidate,
724 /// identical for every parent.
725 Membership { axis: Axis },
726 /// One other position is bound: the parent's band is that value's base
727 /// range on `bound`; candidates probe `rotation`.
728 Base {
729 bound: Axis,
730 rotation: SuccinctRotation,
731 },
732 /// Two other positions are bound: the band is `outer`'s base range
733 /// narrowed through `inner_col` to `inner`'s value.
734 Restrict {
735 outer: Axis,
736 inner: Axis,
737 inner_col: SuccinctRotation,
738 rotation: SuccinctRotation,
739 },
740}
741
742/// Packs values into big-endian `u32` words, so the kernels' word-wise `u32`
743/// comparison equals byte-lexicographic order.
744fn pack_be_words(values: &[RawInline]) -> Vec<u32> {
745 let mut words = Vec::with_capacity(values.len() * 8);
746 for value in values {
747 for chunk in value.chunks_exact(4) {
748 words.push(u32::from_be_bytes(chunk.try_into().unwrap()));
749 }
750 }
751 words
752}
753
754fn count_live(cands: &Candidates<'_>) -> usize {
755 (0..cands.len()).filter(|&i| cands.is_live(i)).count()
756}
757
758/// The region's parent tags compacted into a table: one entry per *distinct*
759/// tag, in first-seen order, plus the table slot of every candidate.
760///
761/// Compacting matters twice over. The host resolves one band per table row
762/// rather than one per frontier row, so a region that touches three parents
763/// of a 16k-wide frontier costs three; and the device receives `slots.len()`
764/// plus `rows.len()` words instead of a band per candidate. Correct for any
765/// tag order — runs are the common shape, but nothing here assumes them.
766fn parent_table(
767 frontier: &Frontier<'_>,
768 cands: &Candidates<'_>,
769) -> jerky::Result<(Vec<u32>, Vec<u32>)> {
770 let width = frontier.len();
771 let mut slot_of_row = vec![u32::MAX; width];
772 let mut slots = Vec::with_capacity(cands.len());
773 let mut rows: Vec<u32> = Vec::new();
774 for &parent in cands.parents() {
775 let row = parent as usize;
776 if row >= width {
777 return Err(jerky::Error::invalid_argument(format!(
778 "candidate parent tag {parent} exceeds the {width} rows of its frontier"
779 )));
780 }
781 let mut slot = slot_of_row[row];
782 if slot == u32::MAX {
783 slot = rows.len() as u32;
784 slot_of_row[row] = slot;
785 rows.push(parent);
786 }
787 slots.push(slot);
788 }
789 Ok((slots, rows))
790}
791
792/// A [`SuccinctArchive`] whose confirm probes can run batched on the default
793/// CubeCL WGPU device.
794///
795/// Construction uploads the value universe (8 big-endian `u32` words per
796/// entry), one cumulative occupancy boundary table per axis
797/// (`bounds[d] = select1(d) - d`, so `bounds[d+1] > bounds[d]` iff code `d`
798/// occurs on that axis, and `bounds[d]..bounds[d+1]` *is* that code's base
799/// range), and the six Ring wavelet matrices. Planning, estimates, and
800/// proposals always use the wrapped CPU archive; only
801/// [`Constraint::confirm`] regions at or above
802/// [`min_confirm_batch`](Self::min_confirm_batch) live candidates dispatch to
803/// the device.
804pub struct WgpuSuccinctArchive<U>
805where
806 U: Universe,
807{
808 archive: SuccinctArchive<U>,
809 context: WgpuContext,
810 /// Resident universe image: `domain_len * 8` big-endian words, ascending.
811 universe_words: DeviceU32Buffer<WgpuRuntime>,
812 domain_len: usize,
813 /// Per-axis cumulative row counts, `domain_len + 1` words each.
814 e_bounds: DeviceU32Buffer<WgpuRuntime>,
815 a_bounds: DeviceU32Buffer<WgpuRuntime>,
816 v_bounds: DeviceU32Buffer<WgpuRuntime>,
817 /// Resident Ring columns in canonical [`SuccinctRotation`] order.
818 ring: [WgpuWaveletMatrix; SuccinctRotation::ALL.len()],
819 min_confirm_batch: usize,
820 stats: ConfirmStats,
821}
822
823fn axis_bounds<I: BitVectorIndex>(
824 context: &WgpuContext,
825 prefix: &BitVector<I>,
826 domain_len: usize,
827 axis: &'static str,
828) -> jerky::Result<DeviceU32Buffer<WgpuRuntime>> {
829 let mut bounds = Vec::with_capacity(domain_len + 1);
830 for d in 0..=domain_len {
831 let position = prefix.select1(d).ok_or_else(|| {
832 jerky::Error::invalid_argument(format!(
833 "{axis} prefix is missing delimiter {d} of {domain_len}"
834 ))
835 })?;
836 let count = position - d;
837 bounds.push(u32::try_from(count).map_err(|_| {
838 jerky::Error::invalid_argument(format!(
839 "{axis} prefix count {count} does not fit the resident u32 domain"
840 ))
841 })?);
842 }
843 context.upload_u32(&bounds)
844}
845
846impl<U> WgpuSuccinctArchive<U>
847where
848 U: Universe,
849{
850 /// Wraps `archive`, enqueueing its universe, axis boundaries, and Ring
851 /// columns on the default WGPU device.
852 ///
853 /// Fails when the archive exceeds the resident `u32` geometry (universe
854 /// or row count near `u32::MAX`) or when the universe's `access` order
855 /// is not strictly ascending — the [`Universe`] contract the device
856 /// binary search depends on, revalidated here because a violation would
857 /// silently corrupt query results.
858 pub fn new(archive: SuccinctArchive<U>) -> jerky::Result<Self> {
859 let domain_len = archive.domain.len();
860 let triple_count = archive.eav_c.len();
861 if domain_len >= (u32::MAX as usize) / 8 {
862 return Err(jerky::Error::invalid_argument(format!(
863 "universe of {domain_len} values does not fit the resident u32 domain"
864 )));
865 }
866 if triple_count >= u32::MAX as usize {
867 return Err(jerky::Error::invalid_argument(format!(
868 "archive of {triple_count} rows does not fit the resident u32 domain"
869 )));
870 }
871
872 let mut universe_values = Vec::with_capacity(domain_len);
873 for d in 0..domain_len {
874 let value = archive.domain.access(d);
875 if let Some(previous) = universe_values.last() {
876 if *previous >= value {
877 return Err(jerky::Error::invalid_argument(format!(
878 "universe access order is not strictly ascending at code {d}"
879 )));
880 }
881 }
882 universe_values.push(value);
883 }
884 let universe_image = pack_be_words(&universe_values);
885
886 let context = WgpuContext::on_wgpu();
887 let universe_words = context.upload_u32(&universe_image)?;
888 let e_bounds = axis_bounds(&context, &archive.e_a, domain_len, "entity")?;
889 let a_bounds = axis_bounds(&context, &archive.a_a, domain_len, "attribute")?;
890 let v_bounds = axis_bounds(&context, &archive.v_a, domain_len, "value")?;
891 let ring = [
892 WgpuWaveletMatrix::with_context(context.clone(), &archive.eav_c)?,
893 WgpuWaveletMatrix::with_context(context.clone(), &archive.vea_c)?,
894 WgpuWaveletMatrix::with_context(context.clone(), &archive.ave_c)?,
895 WgpuWaveletMatrix::with_context(context.clone(), &archive.vae_c)?,
896 WgpuWaveletMatrix::with_context(context.clone(), &archive.eva_c)?,
897 WgpuWaveletMatrix::with_context(context.clone(), &archive.aev_c)?,
898 ];
899 Ok(Self {
900 archive,
901 context,
902 universe_words,
903 domain_len,
904 e_bounds,
905 a_bounds,
906 v_bounds,
907 ring,
908 min_confirm_batch: DEFAULT_MIN_CONFIRM_BATCH,
909 stats: ConfirmStats::default(),
910 })
911 }
912
913 /// Sets the minimum live-candidate region size dispatched to the device.
914 ///
915 /// Zero forces every routed confirm through WGPU (parity testing);
916 /// `usize::MAX` disables the device path without dropping residency.
917 pub fn with_min_confirm_batch(mut self, min_confirm_batch: usize) -> Self {
918 self.min_confirm_batch = min_confirm_batch;
919 self
920 }
921
922 /// Changes the minimum live-candidate region size dispatched to the device.
923 pub fn set_min_confirm_batch(&mut self, min_confirm_batch: usize) {
924 self.min_confirm_batch = min_confirm_batch;
925 }
926
927 /// Returns the minimum live-candidate region size dispatched to the device.
928 pub fn min_confirm_batch(&self) -> usize {
929 self.min_confirm_batch
930 }
931
932 /// Returns the canonical CPU archive wrapped by this adapter.
933 pub fn archive(&self) -> &SuccinctArchive<U> {
934 &self.archive
935 }
936
937 /// Removes the resident adapter and returns its canonical CPU archive.
938 pub fn into_archive(self) -> SuccinctArchive<U> {
939 self.archive
940 }
941
942 /// Returns the compatibility domain shared by all resident components.
943 pub fn context(&self) -> &WgpuContext {
944 &self.context
945 }
946
947 /// Returns a snapshot of this wrapper's confirm dispatch counters.
948 pub fn stats(&self) -> WgpuConfirmStats {
949 self.stats.snapshot()
950 }
951
952 /// Resets this wrapper's confirm dispatch counters.
953 pub fn reset_stats(&self) {
954 self.stats.reset();
955 }
956
957 /// Returns the resident last-column mirror of `rotation`.
958 pub fn ring_col(&self, rotation: SuccinctRotation) -> &WgpuWaveletMatrix {
959 &self.ring[rotation.index()]
960 }
961
962 fn axis_bounds_buffer(&self, axis: Axis) -> &DeviceU32Buffer<WgpuRuntime> {
963 match axis {
964 Axis::Entity => &self.e_bounds,
965 Axis::Attribute => &self.a_bounds,
966 Axis::Value => &self.v_bounds,
967 }
968 }
969
970 fn elemwise(&self, len: usize) -> (CubeCount, CubeDim) {
971 let cube_dim = CubeDim::new_1d(THREADS);
972 let cube_count =
973 cubecl::calculate_cube_count_elemwise(self.context.client(), len, cube_dim);
974 (cube_count, cube_dim)
975 }
976
977 /// Rejects a device whose planes are not exactly 32 lanes wide.
978 ///
979 /// The packed kernels put ballot bit `L` in word bit `L` and store one
980 /// word per plane from its lane 0, reading ballot component 0. That is
981 /// correct iff a plane is exactly 32 lanes: narrower and several planes
982 /// share a word, each storing it whole (lost update); wider and lane 32
983 /// stores the *next* word out of component 0 instead of component 1.
984 /// Neither failure has any symptom other than wrong query answers, and
985 /// the supported hardware (NVIDIA warps, Apple Silicon — where cubecl
986 /// hardcodes 32) always satisfies it, so this is a guard against a
987 /// surprise adapter rather than a portability layer. `Plane::Ops` is
988 /// checked in the same breath because without it the shader's
989 /// `enable subgroups;` directive is rejected at pipeline creation.
990 ///
991 /// Returning an error rather than branching keeps the demotion honest:
992 /// `Constraint::confirm` counts it as a device error and recomputes the
993 /// region on the CPU arm.
994 fn require_plane_packing(&self) -> jerky::Result<()> {
995 use cubecl::ir::features::Plane;
996
997 let properties = self.context.client().properties();
998 if !properties.features.plane.contains(Plane::Ops) {
999 return Err(jerky::Error::invalid_argument(
1000 "device does not support plane (subgroup) operations",
1001 ));
1002 }
1003 let (min, max) = (
1004 properties.hardware.plane_size_min,
1005 properties.hardware.plane_size_max,
1006 );
1007 if min != 32 || max != 32 {
1008 return Err(jerky::Error::invalid_argument(format!(
1009 "packed confirm needs a plane size of exactly 32, device reports {min}..={max}"
1010 )));
1011 }
1012 Ok(())
1013 }
1014
1015 /// Device evaluation of one unbound membership arm: one fused kernel,
1016 /// one readback, one AND into the region's liveness.
1017 ///
1018 /// The verdict buffer and its dispatch are sized from the region's *word*
1019 /// geometry — `bit_offset` and `live_word_len`, never the candidate count
1020 /// — because a region's candidates start at an arbitrary bit of its first
1021 /// word.
1022 fn confirm_membership_gpu(&self, axis: Axis, cands: &mut Candidates<'_>) -> jerky::Result<()> {
1023 let n = cands.len();
1024 self.require_plane_packing()?;
1025
1026 let bit_offset = cands.bit_offset();
1027 let words = cands.live_word_len();
1028 let cand_words = self.context.upload_u32(&pack_be_words(cands.values()))?;
1029 let mut live = cands.live_words();
1030 let live_words = self.context.upload_u32(&live)?;
1031 let mut verdict_words = self.context.empty_u32(words)?;
1032
1033 // Bit slots, not candidates: the kernel's flat index is a bit
1034 // position, and the region's first `bit_offset` bits belong to the
1035 // neighbour below it.
1036 let (cube_count, cube_dim) = self.elemwise(bit_offset + n);
1037 unsafe {
1038 membership_confirm_ballot_kernel::launch_unchecked::<WgpuRuntime>(
1039 self.context.client(),
1040 cube_count,
1041 cube_dim,
1042 cand_words.input_arg(),
1043 live_words.input_arg(),
1044 self.universe_words.input_arg(),
1045 self.axis_bounds_buffer(axis).input_arg(),
1046 verdict_words.output_arg(),
1047 n as u32,
1048 self.domain_len as u32,
1049 bit_offset as u32,
1050 )
1051 };
1052
1053 let verdicts = verdict_words.read();
1054 and_words(&mut live, &verdicts);
1055 cands.set_live_words(&live);
1056 Ok(())
1057 }
1058
1059 /// Device evaluation of one **single-bound** range arm: probe fill
1060 /// (which resolves each candidate's parent band inline), Jerky's batched
1061 /// wavelet rank, and verdict fold — three dispatches, one readback, one
1062 /// AND into the region's liveness.
1063 ///
1064 /// `slots` maps candidate `i` to its parent's row in `parent_values`, so
1065 /// one dispatch serves a region spanning the whole frontier.
1066 fn confirm_base_gpu(
1067 &self,
1068 axis: Axis,
1069 rotation: SuccinctRotation,
1070 slots: &[u32],
1071 parent_values: &[RawInline],
1072 cands: &mut Candidates<'_>,
1073 ) -> jerky::Result<()> {
1074 let n = cands.len();
1075 self.require_plane_packing()?;
1076
1077 let bit_offset = cands.bit_offset() as u32;
1078 let slot_words = self.context.upload_u32(slots)?;
1079 let value_words = self.context.upload_u32(&pack_be_words(parent_values))?;
1080 let cand_words = self.context.upload_u32(&pack_be_words(cands.values()))?;
1081 let live_words = self.context.upload_u32(&cands.live_words())?;
1082 let mut flags = self.context.empty_u32(n)?;
1083 let mut positions = self.context.empty_u32(2 * n)?;
1084 let mut probes = self.context.empty_u32(2 * n)?;
1085
1086 // The probe fill stays candidate-indexed (its outputs feed Jerky's
1087 // per-candidate rank batch); only the verdict fold indexes bits.
1088 let (cube_count, cube_dim) = self.elemwise(n);
1089 unsafe {
1090 base_probe_fill_kernel::launch_unchecked::<WgpuRuntime>(
1091 self.context.client(),
1092 cube_count,
1093 cube_dim,
1094 cand_words.input_arg(),
1095 live_words.input_arg(),
1096 self.universe_words.input_arg(),
1097 slot_words.input_arg(),
1098 value_words.input_arg(),
1099 self.axis_bounds_buffer(axis).input_arg(),
1100 flags.output_arg(),
1101 positions.output_arg(),
1102 probes.output_arg(),
1103 n as u32,
1104 self.domain_len as u32,
1105 bit_offset,
1106 )
1107 };
1108 self.fold_range_verdicts(rotation, &flags, &positions, &probes, cands)
1109 }
1110
1111 /// Device evaluation of one **double-bound** range arm. The parent bands
1112 /// need a wavelet rank of their own, so this shape pays a parent pass —
1113 /// probe fill and one batched rank over the *table*, not the region —
1114 /// before the candidate pass folds each parent's rank into its band.
1115 /// Five dispatches, still one readback.
1116 #[allow(clippy::too_many_arguments)]
1117 fn confirm_restrict_gpu(
1118 &self,
1119 outer: Axis,
1120 inner: Axis,
1121 inner_col: SuccinctRotation,
1122 rotation: SuccinctRotation,
1123 slots: &[u32],
1124 outer_values: &[RawInline],
1125 inner_values: &[RawInline],
1126 cands: &mut Candidates<'_>,
1127 ) -> jerky::Result<()> {
1128 let n = cands.len();
1129 self.require_plane_packing()?;
1130
1131 let bit_offset = cands.bit_offset() as u32;
1132 let p = outer_values.len();
1133 let outer_words = self.context.upload_u32(&pack_be_words(outer_values))?;
1134 let inner_words = self.context.upload_u32(&pack_be_words(inner_values))?;
1135 let mut parent_codes = self.context.empty_u32(p)?;
1136 let mut parent_flags = self.context.empty_u32(p)?;
1137 let mut parent_positions = self.context.empty_u32(2 * p)?;
1138 let mut parent_probes = self.context.empty_u32(2 * p)?;
1139 let mut parent_ranks = self.context.empty_u32(2 * p)?;
1140
1141 let (parent_count, cube_dim) = self.elemwise(p);
1142 unsafe {
1143 parent_restrict_probe_kernel::launch_unchecked::<WgpuRuntime>(
1144 self.context.client(),
1145 parent_count,
1146 cube_dim,
1147 self.universe_words.input_arg(),
1148 self.axis_bounds_buffer(outer).input_arg(),
1149 outer_words.input_arg(),
1150 inner_words.input_arg(),
1151 parent_codes.output_arg(),
1152 parent_flags.output_arg(),
1153 parent_positions.output_arg(),
1154 parent_probes.output_arg(),
1155 p as u32,
1156 self.domain_len as u32,
1157 )
1158 };
1159 self.ring_col(inner_col).rank_batch_into(
1160 &parent_positions,
1161 &parent_probes,
1162 &mut parent_ranks,
1163 )?;
1164
1165 let slot_words = self.context.upload_u32(slots)?;
1166 let cand_words = self.context.upload_u32(&pack_be_words(cands.values()))?;
1167 let live_words = self.context.upload_u32(&cands.live_words())?;
1168 let mut flags = self.context.empty_u32(n)?;
1169 let mut positions = self.context.empty_u32(2 * n)?;
1170 let mut probes = self.context.empty_u32(2 * n)?;
1171
1172 let (cube_count, cube_dim) = self.elemwise(n);
1173 unsafe {
1174 restrict_probe_fill_kernel::launch_unchecked::<WgpuRuntime>(
1175 self.context.client(),
1176 cube_count,
1177 cube_dim,
1178 cand_words.input_arg(),
1179 live_words.input_arg(),
1180 self.universe_words.input_arg(),
1181 slot_words.input_arg(),
1182 parent_flags.input_arg(),
1183 parent_codes.input_arg(),
1184 parent_ranks.input_arg(),
1185 self.axis_bounds_buffer(inner).input_arg(),
1186 flags.output_arg(),
1187 positions.output_arg(),
1188 probes.output_arg(),
1189 n as u32,
1190 self.domain_len as u32,
1191 RANK_OUT_OF_RANGE,
1192 bit_offset,
1193 )
1194 };
1195 self.fold_range_verdicts(rotation, &flags, &positions, &probes, cands)
1196 }
1197
1198 /// The tail both range arms share: Jerky's batched wavelet rank over the
1199 /// filled probes, the verdict fold, one readback, one word-wise AND into
1200 /// the region's liveness.
1201 fn fold_range_verdicts(
1202 &self,
1203 rotation: SuccinctRotation,
1204 flags: &DeviceU32Buffer<WgpuRuntime>,
1205 positions: &DeviceU32Buffer<WgpuRuntime>,
1206 probes: &DeviceU32Buffer<WgpuRuntime>,
1207 cands: &mut Candidates<'_>,
1208 ) -> jerky::Result<()> {
1209 let n = cands.len();
1210 let bit_offset = cands.bit_offset();
1211 let mut ranks = self.context.empty_u32(2 * n)?;
1212 let mut verdict_words = self.context.empty_u32(cands.live_word_len())?;
1213 self.ring_col(rotation)
1214 .rank_batch_into(positions, probes, &mut ranks)?;
1215
1216 // Bit slots, not candidates — see `membership_confirm_ballot_kernel`.
1217 let (cube_count, cube_dim) = self.elemwise(bit_offset + n);
1218 unsafe {
1219 range_verdict_ballot_kernel::launch_unchecked::<WgpuRuntime>(
1220 self.context.client(),
1221 cube_count,
1222 cube_dim,
1223 flags.input_arg(),
1224 ranks.input_arg(),
1225 verdict_words.output_arg(),
1226 n as u32,
1227 RANK_OUT_OF_RANGE,
1228 bit_offset as u32,
1229 )
1230 };
1231
1232 let verdicts = verdict_words.read();
1233 let mut live = cands.live_words();
1234 and_words(&mut live, &verdicts);
1235 cands.set_live_words(&live);
1236 Ok(())
1237 }
1238}
1239
1240impl<U> TriblePattern for WgpuSuccinctArchive<U>
1241where
1242 U: Universe + Send + Sync,
1243{
1244 type PatternConstraint<'a>
1245 = WgpuSuccinctArchiveConstraint<'a, U>
1246 where
1247 U: 'a;
1248
1249 fn pattern<'a, V: InlineEncoding>(
1250 &'a self,
1251 e: impl Into<Term<GenId>>,
1252 a: impl Into<Term<GenId>>,
1253 v: impl Into<Term<V>>,
1254 ) -> Self::PatternConstraint<'a> {
1255 WgpuSuccinctArchiveConstraint::new(e, a, v, self)
1256 }
1257}
1258
1259/// The canonical [`SuccinctArchiveConstraint`] with device-batched confirm.
1260///
1261/// Every protocol method except [`confirm`](Constraint::confirm) delegates to
1262/// the wrapped CPU constraint verbatim. `confirm` mirrors the CPU arm
1263/// dispatch; regions with at least
1264/// [`min_confirm_batch`](WgpuSuccinctArchive::min_confirm_batch) live
1265/// candidates run their probes on the device, everything else (including any
1266/// device error) falls back to the CPU arm. Both paths satisfy the kill-only
1267/// contract — the device path merges verdicts by word-wise AND, so it can
1268/// never revive a dead entry.
1269pub struct WgpuSuccinctArchiveConstraint<'a, U>
1270where
1271 U: Universe,
1272{
1273 inner: SuccinctArchiveConstraint<'a, U>,
1274 gpu: &'a WgpuSuccinctArchive<U>,
1275 term_e: RawTerm,
1276 term_a: RawTerm,
1277 term_v: RawTerm,
1278}
1279
1280impl<'a, U> WgpuSuccinctArchiveConstraint<'a, U>
1281where
1282 U: Universe,
1283{
1284 /// Builds the constraint over `gpu`'s wrapped archive. Each position
1285 /// takes a [`Term`]: a variable to solve for or a constant pinned at
1286 /// construction (constants never enter the variable set and enter the
1287 /// arm dispatch as born-bound, exactly as on the CPU constraint).
1288 pub fn new<V: InlineEncoding>(
1289 e: impl Into<Term<GenId>>,
1290 a: impl Into<Term<GenId>>,
1291 v: impl Into<Term<V>>,
1292 gpu: &'a WgpuSuccinctArchive<U>,
1293 ) -> Self {
1294 let e: Term<GenId> = e.into();
1295 let a: Term<GenId> = a.into();
1296 let v: Term<V> = v.into();
1297 WgpuSuccinctArchiveConstraint {
1298 inner: SuccinctArchiveConstraint::new(e, a, v, &gpu.archive),
1299 gpu,
1300 term_e: e.erase(),
1301 term_a: a.erase(),
1302 term_v: v.erase(),
1303 }
1304 }
1305
1306 fn term(&self, axis: Axis) -> &RawTerm {
1307 match axis {
1308 Axis::Entity => &self.term_e,
1309 Axis::Attribute => &self.term_a,
1310 Axis::Value => &self.term_v,
1311 }
1312 }
1313
1314 /// Which shape of probe this confirm is, classified once for the whole
1315 /// batch from any row — every row of a frontier shares its bound set, so
1316 /// they all classify the same.
1317 fn plan(&self, variable: VariableId, binding: &Binding) -> ConfirmPlan {
1318 let e_var = self.term_e.is_var(variable);
1319 let a_var = self.term_a.is_var(variable);
1320 let v_var = self.term_v.is_var(variable);
1321
1322 let e_bound = self.term_e.position_value(binding).is_some();
1323 let a_bound = self.term_a.position_value(binding).is_some();
1324 let v_bound = self.term_v.position_value(binding).is_some();
1325
1326 match (e_bound, a_bound, v_bound, e_var, a_var, v_var) {
1327 (false, false, false, true, false, false) => {
1328 ConfirmPlan::Membership { axis: Axis::Entity }
1329 }
1330 (false, false, false, false, true, false) => ConfirmPlan::Membership {
1331 axis: Axis::Attribute,
1332 },
1333 (false, false, false, false, false, true) => {
1334 ConfirmPlan::Membership { axis: Axis::Value }
1335 }
1336 (true, false, false, false, true, false) => ConfirmPlan::Base {
1337 bound: Axis::Entity,
1338 rotation: SuccinctRotation::Eva,
1339 },
1340 (true, false, false, false, false, true) => ConfirmPlan::Base {
1341 bound: Axis::Entity,
1342 rotation: SuccinctRotation::Eav,
1343 },
1344 (false, true, false, true, false, false) => ConfirmPlan::Base {
1345 bound: Axis::Attribute,
1346 rotation: SuccinctRotation::Ave,
1347 },
1348 (false, true, false, false, false, true) => ConfirmPlan::Base {
1349 bound: Axis::Attribute,
1350 rotation: SuccinctRotation::Aev,
1351 },
1352 (false, false, true, true, false, false) => ConfirmPlan::Base {
1353 bound: Axis::Value,
1354 rotation: SuccinctRotation::Vae,
1355 },
1356 (false, false, true, false, true, false) => ConfirmPlan::Base {
1357 bound: Axis::Value,
1358 rotation: SuccinctRotation::Vea,
1359 },
1360 (false, true, true, true, false, false) => ConfirmPlan::Restrict {
1361 outer: Axis::Attribute,
1362 inner: Axis::Value,
1363 inner_col: SuccinctRotation::Aev,
1364 rotation: SuccinctRotation::Vae,
1365 },
1366 (true, false, true, false, true, false) => ConfirmPlan::Restrict {
1367 outer: Axis::Entity,
1368 inner: Axis::Value,
1369 inner_col: SuccinctRotation::Eav,
1370 rotation: SuccinctRotation::Vea,
1371 },
1372 (true, true, false, false, false, true) => ConfirmPlan::Restrict {
1373 outer: Axis::Entity,
1374 inner: Axis::Attribute,
1375 inner_col: SuccinctRotation::Eva,
1376 rotation: SuccinctRotation::Aev,
1377 },
1378 _ => unreachable!("invalid trible constraint state"),
1379 }
1380 }
1381
1382 /// The `axis` position's value in each of the frontier rows named by
1383 /// `rows` — the parent table's payload.
1384 fn parent_values(
1385 &self,
1386 axis: Axis,
1387 frontier: &Frontier<'_>,
1388 rows: &[u32],
1389 ) -> jerky::Result<Vec<RawInline>> {
1390 let term = self.term(axis);
1391 let mut values = Vec::with_capacity(rows.len());
1392 for &row in rows {
1393 let binding = frontier.row(row as usize);
1394 let value = term.position_value(&binding).ok_or_else(|| {
1395 jerky::Error::invalid_argument(format!(
1396 "frontier row {row} left a bound position of the arm unbound"
1397 ))
1398 })?;
1399 values.push(*value);
1400 }
1401 Ok(values)
1402 }
1403
1404 /// The device evaluation of one confirm call over a whole frontier,
1405 /// mirroring the CPU arm dispatch. Returns the number of parent-table
1406 /// rows the dispatch resolved.
1407 fn confirm_gpu(
1408 &self,
1409 variable: VariableId,
1410 frontier: &Frontier<'_>,
1411 cands: &mut Candidates<'_>,
1412 ) -> jerky::Result<usize> {
1413 match self.plan(variable, &frontier.row(0)) {
1414 ConfirmPlan::Membership { axis } => {
1415 self.gpu.confirm_membership_gpu(axis, cands)?;
1416 Ok(0)
1417 }
1418 ConfirmPlan::Base { bound, rotation } => {
1419 let (slots, rows) = parent_table(frontier, cands)?;
1420 let values = self.parent_values(bound, frontier, &rows)?;
1421 self.gpu
1422 .confirm_base_gpu(bound, rotation, &slots, &values, cands)?;
1423 Ok(rows.len())
1424 }
1425 ConfirmPlan::Restrict {
1426 outer,
1427 inner,
1428 inner_col,
1429 rotation,
1430 } => {
1431 let (slots, rows) = parent_table(frontier, cands)?;
1432 let outer_values = self.parent_values(outer, frontier, &rows)?;
1433 let inner_values = self.parent_values(inner, frontier, &rows)?;
1434 self.gpu.confirm_restrict_gpu(
1435 outer,
1436 inner,
1437 inner_col,
1438 rotation,
1439 &slots,
1440 &outer_values,
1441 &inner_values,
1442 cands,
1443 )?;
1444 Ok(rows.len())
1445 }
1446 }
1447 }
1448}
1449
1450impl<'a, U> Constraint<'a> for WgpuSuccinctArchiveConstraint<'a, U>
1451where
1452 U: Universe,
1453{
1454 fn variables(&self) -> VariableSet {
1455 self.inner.variables()
1456 }
1457
1458 fn estimate(&self, variable: VariableId, binding: &Binding) -> Option<usize> {
1459 self.inner.estimate(variable, binding)
1460 }
1461
1462 fn propose(
1463 &self,
1464 variable: VariableId,
1465 frontier: &Frontier<'_>,
1466 proposals: &mut ProposalBuffer,
1467 ) {
1468 self.inner.propose(variable, frontier, proposals)
1469 }
1470
1471 fn confirm(&self, variable: VariableId, frontier: &Frontier<'_>, cands: &mut Candidates<'_>) {
1472 if !self.term_e.is_var(variable)
1473 && !self.term_a.is_var(variable)
1474 && !self.term_v.is_var(variable)
1475 {
1476 return;
1477 }
1478 if frontier.is_empty() || cands.is_empty() {
1479 return;
1480 }
1481 let live = count_live(cands);
1482 if live < self.gpu.min_confirm_batch {
1483 self.gpu.stats.record_cpu(cands.len());
1484 self.inner.confirm(variable, frontier, cands);
1485 return;
1486 }
1487 match self.confirm_gpu(variable, frontier, cands) {
1488 Ok(parents) => self.gpu.stats.record_gpu(cands.len(), parents),
1489 Err(_) => {
1490 // The helpers only write liveness after a complete verdict
1491 // readback, so a failed dispatch left the region untouched
1492 // and the CPU arm computes it from scratch.
1493 self.gpu.stats.record_error();
1494 self.inner.confirm(variable, frontier, cands);
1495 }
1496 }
1497 }
1498
1499 fn satisfied(&self, binding: &Binding) -> bool {
1500 self.inner.satisfied(binding)
1501 }
1502
1503 fn influence(&self, variable: VariableId) -> VariableSet {
1504 self.inner.influence(variable)
1505 }
1506}