Phase 05 — Runtime Systems: Allocators, Streams, and Async Execution
Difficulty: ⭐⭐⭐⭐☆ | Estimated Time: 2 weeks Roles supported: Head of Engineering [GPU], Runtime Systems Engineer, ML Framework Engineer Hardware needed: none — both labs are CPU-only models of GPU runtime components (Rust + C++)
Why This Phase Exists
The JD asks for "runtime systems programming" by name. Between the driver (Phase 04) and the serving engine (Phase 07) lives the runtime: the layer that decides where memory comes from and when work runs. Every ML framework ships one (PyTorch's caching allocator, CUDA's stream machinery, TensorRT's execution contexts), and every inference platform's worst incidents — fragmentation OOMs at 60% utilization, deadlocked streams, mysterious sync stalls — happen here.
You will build the two canonical components yourself: a caching memory allocator in Rust (the PyTorch design: size-binned free lists, block splitting, stream-aware reuse) and a stream/event scheduler in C++ (dependency DAGs, ordered queues, fences). Both are faithful CPU-side models of the GPU originals, with tests that demonstrate the failure modes you'll spend your career preventing.
Concepts
- Why
cudaMalloc/cudaFreeare slow (device synchronization!) and fragmenting — the motivation for every framework allocator - Allocator zoology: bump, buddy, slab, size-binned free lists; what malloc/jemalloc do vs what GPU pools need
- The PyTorch caching allocator design: bins, block splitting, rounding,
empty_cache, fragmentation vs reserved-vs-allocated metrics, expandable segments - Fragmentation: internal vs external; why long-running serving processes OOM at 60% "utilization"; defragmentation options (none, really — and what that implies for design)
- Stream semantics: ordered queues, default-stream legacy behavior, events as cross-stream edges (
cudaStreamWaitEvent) - The dependency DAG: how frameworks order kernels, copies, and frees; stream-ordered allocation (
cudaMallocAsync) and why "free" is an event in a stream, not a moment in time - Use-after-free across streams — the classic GPU runtime bug class and how stream-aware allocators prevent it
- CUDA Graphs: amortizing the ~5–10 µs launch cost; capture/replay semantics and their restrictions (why serving engines capture decode steps)
- Pinned-memory pools and H2D/D2H staging pipelines (Phase 02 Ch. 9, productionized)
Labs
Lab 01 — Caching GPU Allocator (Rust)
| Field | Value |
|---|---|
| Goal | Implement the PyTorch-style caching allocator: size bins, splitting, stream-tagged free lists — and demonstrate (then fix) fragmentation OOM. |
| Concepts | Free lists, binning, splitting/coalescing, stream-aware reuse, fragmentation metrics. |
| Steps | 1) cargo test — all green. 2) Read src/lib.rs against the WARMUP Ch. 3–5. 3) Run cargo run --release --bin fragdemo — watch the naive allocator OOM at ~55% utilization while the caching one survives. 4) Extensions: coalescing of adjacent free blocks, empty_cache(), an allocation-trace replayer. |
| Stack | Rust (no unsafe, no external crates) |
| Output | A library with 12+ passing tests + the fragmentation demo with its utilization table. |
| How to Test | cargo test: correctness (no double-handout, splitting math, stream safety) + the fragdemo's OOM-point comparison. |
| Talking Points | Why GPU pools can't just use jemalloc (no paging, sync-on-free, stream semantics); reserved vs allocated in nvidia-smi vs framework metrics (the #1 "is it leaking?" confusion); why a serving engine wants per-stream pools. |
| Resume Bullet | "Implemented a PyTorch-style caching GPU allocator in Rust (size-binned free lists, block splitting, stream-aware reuse); demonstrated and mitigated fragmentation OOM, raising survivable utilization from 55% to 92% on adversarial traces." |
| Extensions | Best-fit vs first-fit measurement; expandable-segments mode; export Prometheus-style metrics (Phase 10 tie-in). |
Lab 02 — Stream & Event Scheduler (C++)
| Field | Value |
|---|---|
| Goal | Build the CUDA stream/event model in C++17: ordered streams, cross-stream event dependencies, a worker-driven executor — then use it to demonstrate overlap, false serialization, and a use-after-free caught by stream-ordered lifetime. |
| Concepts | Ordered queues, events/fences, DAG scheduling, stream-ordered deallocation, deadlock from circular waits. |
| Steps | 1) make && ./scheduler_test — all scenarios PASS. 2) Read scheduler.hpp against WARMUP Ch. 6–8. 3) Study the three scenario tests: overlap speedup, default-stream serialization, the use-after-free that the stream-ordered free prevents. 4) Extensions: graph capture/replay, priority streams, a deadlock detector. |
| Stack | C++17, std::thread (no external deps) |
| Output | A header-lib + scenario suite proving overlap (~2× on the pipeline test) and lifetime safety. |
| How to Test | Built-in scenario asserts: pipelined execution beats serial by ≥1.7×; the unsafe-free scenario corrupts (detected) while stream-ordered free never does; circular event waits are detected. |
| Talking Points | Why "free" must be an event in stream order; what cudaMallocAsync changed for frameworks; why serving engines capture decode into CUDA Graphs (launch overhead amortization — numbers from Phase 02). |
| Resume Bullet | "Built a CUDA-semantics stream/event scheduler in C++17 (ordered queues, cross-stream fences, stream-ordered deallocation); scenario suite demonstrates 2× pipeline overlap and elimination of cross-stream use-after-free." |
| Extensions | Capture/replay ("mini CUDA Graphs") with measured per-launch overhead reduction; integrate Lab 01's allocator for fully stream-ordered alloc/free. |
Deliverables Checklist
- Allocator: all tests pass; fragdemo table reproduced and explained
- You can sketch the bin/split/cache design and the reserved-vs-allocated distinction from memory
- Scheduler: all scenarios pass; you can explain each failure mode it demonstrates
- One extension implemented per lab
- One page: "what our serving platform requires from its runtime layer" (feeds Phase 12 capstone)
Interview Relevance
- "Why does PyTorch have its own allocator? Walk me through its design."
- "nvidia-smi says 78 GB used but the framework reports 51 GB. Explain."
- "Your serving process OOMs after 3 days at constant load. Hypotheses?" (fragmentation, pinned leak, cache growth)
- "Design stream-ordered deallocation. What goes wrong without it?"
- "When do CUDA Graphs help, and what can't they capture?"