vyre_primitives/graph/persistent_bfs/
layout.rs

1use crate::graph::program_graph::BINDING_PRIMITIVE_START;
2
3/// Canonical op id.
4pub const OP_ID: &str = "vyre-primitives::graph::persistent_bfs";
5/// Canonical op id for batched persistent BFS over many seed frontiers.
6pub const BATCH_OP_ID: &str = "vyre-primitives::graph::persistent_bfs_batch";
7
8/// Canonical binding index for the input frontier bitset.
9pub const BINDING_FRONTIER_IN: u32 = BINDING_PRIMITIVE_START;
10/// Canonical binding index for the output frontier bitset.
11pub const BINDING_FRONTIER_OUT: u32 = BINDING_PRIMITIVE_START + 1;
12/// Canonical binding index for the global changed flag.
13pub const BINDING_CHANGED: u32 = BINDING_PRIMITIVE_START + 2;
14/// Canonical binding index for the converged flag.
15///
16/// `1` if the frontier reached a fixpoint (a step added nothing) before the
17/// `max_iters` budget was exhausted, `0` if the loop ran all `max_iters` steps
18/// while still growing (an under-approximated closure) or `max_iters == 0`.
19/// This is the device readback that lets a host caller reject a partial closure
20/// loudly instead of silently trusting a frontier the kernel never drove to a
21/// fixpoint. Mirrors `PersistentBfsConvergence::converged` (requires the `cpu-parity` feature).
22pub const BINDING_CONVERGED: u32 = BINDING_PRIMITIVE_START + 3;
23/// Canonical binding index for the optional per-iteration frontier-density array.
24///
25/// Present only in the density-instrumented program variants
26/// ([`super::program::persistent_bfs_with_density`] and
27/// [`super::program::try_persistent_bfs_batch_with_density`]). It is a
28/// `max_iters`-length (single) or `query_count * max_iters` (batch) u32 array
29/// where entry `i` holds the popcount of the frontier after traversal step `i`
30/// (per query for the batch variant). Because reachability growth is monotone, a
31/// host caller reconstructs every `FrontierDensityTelemetry` aggregate (active
32/// total, per-step delta, peak, last) from this array plus the seed popcount,
33/// with no per-iteration device readback loop. The base
34/// [`super::program::persistent_bfs`] programs omit this buffer entirely, so
35/// their ABI is unchanged.
36pub const BINDING_DENSITY_ACTIVE: u32 = BINDING_PRIMITIVE_START + 4;
37/// Canonical name for the per-iteration frontier-density array output buffer.
38pub const DENSITY_ACTIVE_BUFFER: &str = "density_active";
39/// Canonical workgroup size for persistent BFS programs.
40pub const PERSISTENT_BFS_WORKGROUP_SIZE: [u32; 3] = [256, 1, 1];
41/// One-block dispatch grid used by the compact single-workgroup BFS path.
42pub(crate) const PERSISTENT_BFS_SINGLE_DISPATCH_GRID: [u32; 3] = [1, 1, 1];
43
44/// Dispatch grid for a single persistent-BFS query.
45#[must_use]
46pub const fn persistent_bfs_single_dispatch_grid(node_count: u32) -> [u32; 3] {
47    [persistent_bfs_grid_x(node_count), 1, 1]
48}
49
50/// Dispatch grid for a batched persistent-BFS query set.
51#[must_use]
52pub const fn persistent_bfs_batch_dispatch_grid(node_count: u32, query_count: u32) -> [u32; 3] {
53    if query_count == 0 {
54        [1, 1, 1]
55    } else {
56        [persistent_bfs_grid_x(node_count), query_count, 1]
57    }
58}
59
60const fn persistent_bfs_grid_x(node_count: u32) -> u32 {
61    if node_count == 0 {
62        1
63    } else {
64        ((node_count - 1) / PERSISTENT_BFS_WORKGROUP_SIZE[0]) + 1
65    }
66}
67
68/// Validated persistent-BFS graph layout metadata.
69#[derive(Clone, Copy, Debug, Eq, PartialEq)]
70pub struct PersistentBfsLayout {
71    /// Number of graph nodes accepted by the primitive.
72    pub node_count: u32,
73    /// Number of logical CSR edges.
74    pub edge_count: u32,
75    /// Number of u32 words in one frontier bitset.
76    pub words: usize,
77    /// Number of u32 words in one frontier bitset, narrowed for cache keys.
78    pub words_u32: u32,
79    /// Number of u32 words required by node-indexed scratch buffers.
80    pub node_words: usize,
81    /// Number of u32 words required by physical edge buffers after padding.
82    pub edge_storage_words: usize,
83}
84
85/// Validated flat-frontier batch metadata for persistent BFS.
86#[derive(Clone, Copy, Debug, Eq, PartialEq)]
87pub struct PersistentBfsBatchLayout {
88    /// Number of queries in the batch, narrowed for GPU grid dimensions.
89    pub query_count: u32,
90    /// Total number of u32 words in the flat `[query][word]` frontier array.
91    pub total_words: usize,
92}
93
94/// Validated single-frontier metadata for resident persistent BFS.
95#[derive(Clone, Copy, Debug, Eq, PartialEq)]
96pub struct PersistentBfsFrontierLayout {
97    /// Number of u32 words in the frontier bitset.
98    pub words: usize,
99    /// Number of u32 words in the frontier bitset, narrowed for primitive metadata.
100    pub words_u32: u32,
101}
102
103/// Primitive program-cache class for persistent-BFS dispatch plans.
104#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
105pub enum PersistentBfsPlanCacheKind {
106    /// One seed frontier for one graph.
107    Single,
108    /// Many seed frontiers batched over one graph.
109    Batch,
110}
111
112/// Primitive-owned persistent-BFS program cache key.
113///
114/// Dispatch wrappers add only backend feature bits; graph identity, frontier
115/// width, query count, masks, iteration budget, and plan class are owned here
116/// so every backend caches the same primitive program shapes.
117#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
118pub struct PersistentBfsPlanCacheKey {
119    /// Stable discriminator for the cached program layout.
120    ///
121    /// Content-addressed graph staging should use [`crate::graph::persistent_bfs::persistent_bfs_layout_hash`].
122    /// Program caches should prefer [`crate::graph::persistent_bfs::persistent_bfs_program_layout_hash`] so
123    /// same-shape CSR contents reuse the same compiled persistent-BFS program.
124    pub layout_hash: u64,
125    /// Number of graph nodes in the primitive program shape.
126    pub node_count: u32,
127    /// Number of logical graph edges in the primitive program shape.
128    pub edge_count: u32,
129    /// Number of frontier words per query.
130    pub words_per_query: u32,
131    /// Number of queries represented by the program.
132    pub query_count: u32,
133    /// Edge-kind allow mask compiled into the primitive program.
134    pub allow_mask: u32,
135    /// Iteration budget compiled into the primitive program.
136    pub max_iters: u32,
137    /// Backend/device feature key supplied by the dispatch wrapper.
138    pub device_features: u64,
139    /// Single-query or batched-query plan kind.
140    pub kind: PersistentBfsPlanCacheKind,
141}
142
143/// Primitive-owned identity for immutable non-resident persistent-BFS inputs.
144///
145/// Dynamic frontier input/output and changed buffers are intentionally omitted:
146/// dispatch wrappers refresh those every call. This key covers graph contents
147/// and shape that decide when static CSR/device inputs must be refreshed.
148#[derive(Clone, Copy, Debug, Eq, PartialEq)]
149pub struct PersistentBfsStaticInputKey {
150    /// Stable graph-content hash from [`crate::graph::persistent_bfs::persistent_bfs_layout_hash`].
151    pub layout_hash: u64,
152    /// Number of graph nodes.
153    pub node_count: u32,
154    /// Number of logical CSR edges.
155    pub edge_count: u32,
156    /// Number of frontier words.
157    pub words: u32,
158}
vyre_primitives/graph/persistent_bfs/layout.rs

vyre_primitives/graph/persistent_bfs/
layout.rs
