Skip to main content

qualia_core_db/inference/runtime/scheduler/
ragged_backend.rs

1//! Multi-sequence ragged decode backend with CUDA graph replay bucketing (Work Package F6).
2//!
3//! Replaces test mocks with a zero-heap continuous-batching backend that supports:
4//! - Padded batch bucketing (1, 2, 4, 8) for fixed-shape CUDA graph capture/replay.
5//! - Strict isolation between real requests and dummy/padded rows.
6//! - Independent per-sequence KV block-table indexing and execution.
7//! - Deterministic execution receipts and device-to-host bandwidth accounting.
8
9use super::batch::{
10    RaggedBackendError, RaggedBatchItem, RaggedBatchOutput, RaggedBatchReceipt, RaggedDecodeBackend,
11};
12
13/// Maximum supported graph replay bucket size.
14pub const MAX_BATCH_BUCKET: usize = 8;
15
16/// Standard power-of-two graph replay buckets.
17pub const GRAPH_BUCKET_SIZES: [usize; 4] = [1, 2, 4, 8];
18
19/// Sentinel request ID for padded dummy rows.
20pub const PADDED_REQUEST_ID: u64 = u64::MAX;
21
22/// Sentinel slot ID for padded dummy rows.
23pub const PADDED_SLOT_ID: u32 = u32::MAX;
24
25/// Find the smallest graph bucket size that fits `batch_size`.
26#[inline]
27pub fn select_graph_bucket(batch_size: usize) -> Option<usize> {
28    if batch_size == 0 || batch_size > MAX_BATCH_BUCKET {
29        return None;
30    }
31    for &bucket in &GRAPH_BUCKET_SIZES {
32        if bucket >= batch_size {
33            return Some(bucket);
34        }
35    }
36    None
37}
38
39/// Statistics and accounting for the ragged decode backend.
40#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
41pub struct RaggedBackendStats {
42    pub total_rounds: u64,
43    pub total_items_processed: u64,
44    pub total_padded_rows: u64,
45    pub bucket_launches: [u64; GRAPH_BUCKET_SIZES.len()],
46}
47
48impl RaggedBackendStats {
49    /// Percentage of total processed execution slots consumed by padding (0..100).
50    pub fn padding_overhead_percent(&self) -> u32 {
51        let total_slots = self.total_items_processed + self.total_padded_rows;
52        if total_slots == 0 {
53            0
54        } else {
55            ((self.total_padded_rows * 100) / total_slots) as u32
56        }
57    }
58}
59
60/// A zero-heap multi-sequence decode backend with padded graph bucketing.
61pub struct MultiSequenceRaggedBackend<F>
62where
63    F: FnMut(u64, u32, u32, u32, &[u32]) -> u32,
64{
65    step_fn: F,
66    stats: RaggedBackendStats,
67    allow_unbucketed_fallback: bool,
68}
69
70impl<F> MultiSequenceRaggedBackend<F>
71where
72    F: FnMut(u64, u32, u32, u32, &[u32]) -> u32,
73{
74    /// Construct a new backend with a token-step function.
75    pub fn new(step_fn: F) -> Self {
76        Self {
77            step_fn,
78            stats: RaggedBackendStats::default(),
79            allow_unbucketed_fallback: false,
80        }
81    }
82
83    /// Enable or disable unbucketed execution when batch size exceeds `MAX_BATCH_BUCKET`.
84    pub fn with_unbucketed_fallback(mut self, allow: bool) -> Self {
85        self.allow_unbucketed_fallback = allow;
86        self
87    }
88
89    /// Get current backend statistics.
90    pub fn stats(&self) -> &RaggedBackendStats {
91        &self.stats
92    }
93}
94
95impl<F> RaggedDecodeBackend for MultiSequenceRaggedBackend<F>
96where
97    F: FnMut(u64, u32, u32, u32, &[u32]) -> u32,
98{
99    fn execute_ragged(
100        &mut self,
101        items: &[RaggedBatchItem],
102        block_tables: &[u32],
103        out: &mut [RaggedBatchOutput],
104    ) -> Result<RaggedBatchReceipt, RaggedBackendError> {
105        let item_count = items.len();
106        if item_count == 0 {
107            return Ok(RaggedBatchReceipt::default());
108        }
109        if out.len() < item_count {
110            return Err(RaggedBackendError::OutputTooSmall);
111        }
112
113        // 1. Determine graph bucket size
114        let bucket_size = match select_graph_bucket(item_count) {
115            Some(bucket) => bucket,
116            None => {
117                if self.allow_unbucketed_fallback {
118                    item_count
119                } else {
120                    return Err(RaggedBackendError::Rejected);
121                }
122            }
123        };
124
125        // 2. Validate all real items and their block table slices first (fail-fast)
126        for item in items {
127            let table_start = item.block_table_offset as usize;
128            let table_end = table_start.saturating_add(item.logical_pages as usize);
129            if table_end > block_tables.len() {
130                return Err(RaggedBackendError::Rejected);
131            }
132        }
133
134        // 3. Prepare padded batch slots in stack storage (zero heap)
135        let mut padded_batch = [RaggedBatchItem::default(); MAX_BATCH_BUCKET];
136        let copy_count = item_count.min(MAX_BATCH_BUCKET);
137        padded_batch[..copy_count].copy_from_slice(&items[..copy_count]);
138
139        let padded_count = bucket_size.saturating_sub(item_count);
140        for pad_idx in item_count..bucket_size.min(MAX_BATCH_BUCKET) {
141            padded_batch[pad_idx] = RaggedBatchItem {
142                request_id: PADDED_REQUEST_ID,
143                slot: PADDED_SLOT_ID,
144                token_id: 0,
145                position: 0,
146                block_table_offset: 0,
147                logical_pages: 0,
148                _reserved: 0,
149            };
150        }
151
152        // 4. Execute active sequence steps
153        for (index, item) in items.iter().enumerate() {
154            let table_start = item.block_table_offset as usize;
155            let table_end = table_start + item.logical_pages as usize;
156            let page_slice = &block_tables[table_start..table_end];
157
158            let next_token = (self.step_fn)(
159                item.request_id,
160                item.slot,
161                item.token_id,
162                item.position,
163                page_slice,
164            );
165
166            out[index] = RaggedBatchOutput {
167                request_id: item.request_id,
168                slot: item.slot,
169                next_token_id: next_token,
170            };
171        }
172
173        // 5. Execute padded dummy steps if inside bucket (guaranteeing side-effect isolation)
174        for pad_idx in item_count..bucket_size.min(MAX_BATCH_BUCKET) {
175            let pad_item = &padded_batch[pad_idx];
176            let _dummy_token = (self.step_fn)(
177                pad_item.request_id,
178                pad_item.slot,
179                pad_item.token_id,
180                pad_item.position,
181                &[],
182            );
183            // Padded results are deliberately NEVER written to `out`
184        }
185
186        // 6. Update telemetry and accounting
187        self.stats.total_rounds += 1;
188        self.stats.total_items_processed += item_count as u64;
189        self.stats.total_padded_rows += padded_count as u64;
190
191        if let Some(bucket_idx) = GRAPH_BUCKET_SIZES.iter().position(|&b| b == bucket_size) {
192            self.stats.bucket_launches[bucket_idx] += 1;
193        }
194
195        let d2h_bytes = (item_count * core::mem::size_of::<RaggedBatchOutput>()) as u64;
196
197        Ok(RaggedBatchReceipt {
198            batch_size: item_count as u32,
199            backend_launches: 1,
200            device_to_host_bytes: d2h_bytes,
201        })
202    }
203}
204
205#[cfg(test)]
206mod tests {
207    use super::*;
208
209    #[test]
210    fn test_select_graph_bucket() {
211        assert_eq!(select_graph_bucket(0), None);
212        assert_eq!(select_graph_bucket(1), Some(1));
213        assert_eq!(select_graph_bucket(2), Some(2));
214        assert_eq!(select_graph_bucket(3), Some(4));
215        assert_eq!(select_graph_bucket(4), Some(4));
216        assert_eq!(select_graph_bucket(5), Some(8));
217        assert_eq!(select_graph_bucket(8), Some(8));
218        assert_eq!(select_graph_bucket(9), None);
219    }
220
221    #[test]
222    fn test_multi_sequence_execution_and_padding_isolation() {
223        let executed_ids = std::sync::Arc::new(std::sync::Mutex::new(Vec::new()));
224        let executed_ids_clone = executed_ids.clone();
225        let mut backend =
226            MultiSequenceRaggedBackend::new(move |req_id, slot, token_id, pos, page_slice| {
227                executed_ids_clone.lock().unwrap().push(req_id);
228                token_id + pos + page_slice.len() as u32 + slot
229            });
230
231        let items = [
232            RaggedBatchItem {
233                request_id: 101,
234                slot: 0,
235                token_id: 10,
236                position: 5,
237                block_table_offset: 0,
238                logical_pages: 2,
239                _reserved: 0,
240            },
241            RaggedBatchItem {
242                request_id: 202,
243                slot: 1,
244                token_id: 20,
245                position: 8,
246                block_table_offset: 2,
247                logical_pages: 3,
248                _reserved: 0,
249            },
250            RaggedBatchItem {
251                request_id: 303,
252                slot: 2,
253                token_id: 30,
254                position: 12,
255                block_table_offset: 5,
256                logical_pages: 1,
257                _reserved: 0,
258            },
259        ];
260
261        let block_tables = [10, 11, 20, 21, 22, 30];
262        let mut out = [RaggedBatchOutput::default(); 3];
263
264        let receipt = backend
265            .execute_ragged(&items, &block_tables, &mut out)
266            .unwrap();
267
268        assert_eq!(receipt.batch_size, 3);
269        assert_eq!(receipt.backend_launches, 1);
270
271        // Verification of real outputs
272        // item 0: token_id(10) + pos(5) + pages(2) + slot(0) = 17
273        assert_eq!(out[0].request_id, 101);
274        assert_eq!(out[0].slot, 0);
275        assert_eq!(out[0].next_token_id, 17);
276
277        // item 1: token_id(20) + pos(8) + pages(3) + slot(1) = 32
278        assert_eq!(out[1].request_id, 202);
279        assert_eq!(out[1].slot, 1);
280        assert_eq!(out[1].next_token_id, 32);
281
282        // item 2: token_id(30) + pos(12) + pages(1) + slot(2) = 45
283        assert_eq!(out[2].request_id, 303);
284        assert_eq!(out[2].slot, 2);
285        assert_eq!(out[2].next_token_id, 45);
286
287        // Bucket chosen was 4 (items = 3 -> bucket = 4)
288        // Check executed_ids: 101, 202, 303, and one PADDED_REQUEST_ID
289        assert_eq!(
290            *executed_ids.lock().unwrap(),
291            vec![101, 202, 303, PADDED_REQUEST_ID]
292        );
293
294        // Check stats
295        let stats = backend.stats();
296        assert_eq!(stats.total_rounds, 1);
297        assert_eq!(stats.total_items_processed, 3);
298        assert_eq!(stats.total_padded_rows, 1);
299        // bucket_launches[2] is bucket size 4 (indices: 0=1, 1=2, 2=4, 3=8)
300        assert_eq!(stats.bucket_launches[2], 1);
301        assert_eq!(stats.padding_overhead_percent(), 25); // 1 / (3 + 1) = 25%
302    }
303
304    #[test]
305    fn test_rejects_out_of_bounds_block_table() {
306        let mut backend = MultiSequenceRaggedBackend::new(|_, _, token, _, _| token + 1);
307        let items = [RaggedBatchItem {
308            request_id: 1,
309            slot: 0,
310            token_id: 10,
311            position: 0,
312            block_table_offset: 4,
313            logical_pages: 2, // 4 + 2 = 6, but block_tables has len 5
314            _reserved: 0,
315        }];
316        let block_tables = [0, 1, 2, 3, 4];
317        let mut out = [RaggedBatchOutput::default(); 1];
318
319        let err = backend
320            .execute_ragged(&items, &block_tables, &mut out)
321            .unwrap_err();
322        assert_eq!(err, RaggedBackendError::Rejected);
323    }
324}