Lab 02 — Stream & Event Scheduler (C++)

Phase: 05 — Runtime Systems | Difficulty: ⭐⭐⭐⭐☆ | Time: 5–8 hours Language: C++17 (std::thread, no deps) | Hardware: none — a CPU model of CUDA stream semantics

Concept primer: ../WARMUP.md Ch. 6–8.

Run

make && ./scheduler_test

0. The mission

Build the CUDA execution model in ~200 lines and use it to make three production failure modes tangible:

  • Stream = a worker thread + FIFO queue. Ops on one stream run in order.
  • Event = a counter + condition variable. record(stream) enqueues a bump; stream_wait(s, e) makes stream s block until the event fires. Events are the edges of the dependency DAG (WARMUP Ch. 6).
  • Scheduler owns streams and lets the host join the DAG.

Each "op" is just a std::function with a simulated duration — enough to observe overlap, serialization, and lifetime bugs without a GPU.

1. The three scenarios (the heart of the lab)

ScenarioDemonstratesPass condition
1. Pipeline overlapH2D copy ∥ compute ∥ D2H across two streams with event edges≥1.7× faster than serial
2. Default-stream serializationthe legacy default stream as a global barrier"concurrent" ops actually serialize; measured
3. Stream-ordered lifetimeuse-after-free when free is host-ordered; safety when it's stream-orderedunsafe path corrupts (detected); ordered path never does

Expected output:

[scenario 1] serial=282ms  pipelined=140ms  speedup=2.01x   PASS (>=1.7x)
[scenario 2] one-stream=83ms  two-stream=45ms  overlap=1.84x  PASS
             (legacy default stream forces the one-stream case — that's the 2x you lose)
[scenario 3] host-ordered free: CORRUPTION detected (as expected)
             stream-ordered free: no corruption across 200 trials  PASS
[scenario 4] acyclic accepted / circular wait detected   PASS

2. Why each scenario matters

  • Scenario 1 is the entire reason streams exist: separate copy and compute engines, wired with event edges, double-buffer so chunk N+1's copy overlaps chunk N's compute (WARMUP Ch. 9). The speedup is the Phase 02 Ch. 9 pipeline, measured.
  • Scenario 2 is the bug hiding in every naive codebase: issue to the default stream and your carefully-separated work silently serializes. The fix (per-thread default stream / explicit streams) is a one-line policy with a 2× consequence.
  • Scenario 3 is the unreproducible-corruption ticket: the host runs ahead of the device, frees a buffer still in use, the allocator hands it out, and a scheduling coincidence corrupts data once a week. The lab makes it reproducible — then shows stream-ordered free making the class impossible (WARMUP Ch. 7). This connects directly to Lab 01's cross_stream_syncs.

3. Reading order (scheduler.hpp)

  1. Stream — worker loop pulling from a std::queue under a mutex/condvar. In-order execution falls out of the FIFO for free.
  2. Event — record enqueues a counter bump onto a stream; stream_wait enqueues a blocking wait onto another stream. This is the whole ordering algebra.
  3. Scheduler::synchronize — the host joining the DAG (the blunt cudaDeviceSynchronize).
  4. The scenarios in scheduler_test.cpp — predict each result from the DAG before reading the assert.

4. Extensions

  1. Capture/replay ("mini CUDA Graphs"): record a scenario-1 sequence into a Graph object, then replay it with one call; measure per-op issue cost before/after (WARMUP Ch. 8). Note what you can't capture (data-dependent branches) — the real restriction.
  2. Priority streams: a high-priority stream's ops jump the worker queue; show a latency-sensitive op finishing ahead of bulk work.
  3. Deadlock detector: build the wait-for graph from event edges and reject cycles at issue time (scenario 4 stubs this).
  4. Integrate Lab 01: make the allocator's free stream-ordered using this scheduler's events — the two halves of the runtime layer, joined.

5. Common pitfalls

  1. Data race in the test harness itself — the "corruption" in scenario 3 must come from the modeled lifetime bug, not from unsynchronized std::thread access in your scaffolding. The provided harness uses a deterministic interleaving hook; keep it.
  2. Busy-waiting instead of condvars — works but pegs a core and hides ordering bugs; use the condition variables as written.
  3. Joining workers in the wrong order at shutdown — a classic; the destructor drains queues then joins.
  4. Concluding overlap from wall-clock without warmup — same discipline as Phase 02 Ch. 9; the harness discards the first run.

6. What this lab proves about you

You can implement and reason about the execution model that every async GPU program obeys — and you can name, reproduce, and prevent the three failure modes (lost overlap, accidental serialization, cross-stream UAF) that cost real serving fleets latency and correctness. Combined with Lab 01, you've built the runtime layer this JD calls "runtime systems programming."