Render graph (frame graph)

Deep dive

How it works

Parts:

• Pass — a node: name, declared reads and writes, a side-effect flag, an execute callback (not shown).
• Resource — an edge: transient (lives only inside the graph, may share memory) or imported (swapchain image, history buffer, outlives the frame).
• Compiler — culling, topological order, lifetimes, aliasing, barrier derivation.
• Slot allocator — owns memory slots (heap ranges); each slot hosts resources one after another.
• Executor — walks the order, emits barriers, creates views, runs callbacks.

1. Setup: each pass declares read(r), write(r) or create(r); nothing allocates, nothing executes. The graph is rebuilt every frame (Frostbite).
2. Cull: start from passes with side effects (writing an imported resource) and walk producer edges backwards; unreached passes and their resources are dropped. This lets code declare optional or debug passes freely.
3. Order: Kahn's algorithm (topological sort) over live passes. Ties by declaration order keep it stable; a scheduler may instead maximise distance between producer and consumer to reduce hard barriers (Arntzen 2017).
4. Lifetimes: per resource, first and last use as positions in the order. Async compute extends a lifetime to its sync point (O'Donnell 2017).
5. Alias: sort resources by first use; give each a free slot (last use of its previous tenant strictly earlier), best fit, or grow the free slot. Same problem as register allocation and interval colouring.
6. Barriers: for each producer to consumer edge, a memory dependency plus a layout transition where the API has layouts (Vulkan spec). Each time a slot changes tenant, add an aliasing barrier and treat the new tenant as uninitialised.
7. Execute: run callbacks in order with real handles resolved from the plan.

shadow ──┐
gbuffer ─┴► lighting ─hdr─┬► down1 ─► down2 ─► down3        (edges are resources)
                          │     │       │        │
debug_view  ✗ culled      │     │       └─► up2 ◄┘          up2 = f(down3, down2)
 (nobody reads debug)     │     └─────────► up1             up1 = f(up2, down1)
                          └───────────────► tonemap ◄─ up1
                                              └─ldr─► ui ─► backbuffer (imported)
pos  0      1      2      3      4      5      6      7      8      9
pass shadow gbuf   light  dn1    dn2    dn3    up2    up1    tone   ui
S0   [shadow============]
S1          [gbufC======]                      [up2========]
S2          [depth======] [down1===========================] [ldr========]
S3          [gbufA======]        [down2=============] [up1========]
S4          [gbufB======]               [down3======]
S5                 [hdr===========================================]

A second tenant in a slot gets an aliasing barrier; every arrow gets a read-after-write barrier.

Code

Std-only Rust: cull, Kahn order, lifetimes, best-fit slots, barriers; main builds a five-pass frame with one dead pass and asserts the result (compiled and run).

use std::cmp::Reverse;
use std::collections::BinaryHeap;

pub struct Pass { pub name: String, pub reads: Vec<usize>, pub writes: Vec<usize>, pub side_effect: bool }
pub struct Res { pub name: String, pub size: u64, pub imported: bool } // imported = outlives the graph
#[derive(Default)]
pub struct Graph { pub passes: Vec<Pass>, pub res: Vec<Res> }
pub struct Barrier { pub res: usize, pub from: usize, pub to: usize, pub alias: bool }
pub struct Plan { pub order: Vec<usize>, pub slot: Vec<Option<usize>>, pub slot_size: Vec<u64>,
                  pub life: Vec<(usize, usize)>, pub barriers: Vec<Barrier> }

impl Graph {
    pub fn compile(&self) -> Plan {
        let (np, nr) = (self.passes.len(), self.res.len());
        let mut writer = vec![usize::MAX; nr];            // each resource has one producer
        for (p, ps) in self.passes.iter().enumerate() {
            for &r in &ps.writes { assert_eq!(writer[r], usize::MAX); writer[r] = p; }
        }
        // 1. cull: backwards reachability from side-effect passes
        let mut live = vec![false; np];
        let mut stack: Vec<usize> = (0..np).filter(|&p| self.passes[p].side_effect).collect();
        while let Some(p) = stack.pop() {
            if std::mem::replace(&mut live[p], true) { continue; }
            for &r in &self.passes[p].reads { if writer[r] != usize::MAX { stack.push(writer[r]); } }
        }
        // 2. Kahn's topological order over live passes; ties go to declaration order
        let mut indeg = vec![0usize; np];
        let mut succ: Vec<Vec<usize>> = vec![vec![]; np];
        for p in (0..np).filter(|&p| live[p]) {
            for &r in &self.passes[p].reads {
                let w = writer[r];
                if w != usize::MAX { succ[w].push(p); indeg[p] += 1; }
            }
        }
        let mut ready: BinaryHeap<Reverse<usize>> =
            (0..np).filter(|&p| live[p] && indeg[p] == 0).map(Reverse).collect();
        let mut order = vec![];
        while let Some(Reverse(p)) = ready.pop() {
            order.push(p);
            for &s in &succ[p] { indeg[s] -= 1; if indeg[s] == 0 { ready.push(Reverse(s)); } }
        }
        assert_eq!(order.len(), live.iter().filter(|&&l| l).count(), "cycle");
        // 3. lifetimes [first use, last use] as positions in `order`
        let mut life = vec![(usize::MAX, 0usize); nr];
        for (pos, &p) in order.iter().enumerate() {
            for &r in self.passes[p].reads.iter().chain(&self.passes[p].writes) {
                life[r].0 = life[r].0.min(pos); life[r].1 = life[r].1.max(pos);
            }
        }
        // 4. alias transients: sort by start, best-fit into slots that are free (last use < start)
        let mut ids: Vec<usize> = (0..nr).filter(|&r| !self.res[r].imported && life[r].0 != usize::MAX).collect();
        ids.sort_by_key(|&r| (life[r].0, Reverse(self.res[r].size)));
        let (mut slot, mut slot_size, mut busy_until) = (vec![None; nr], vec![], vec![]);
        let mut last_user: Vec<Option<usize>> = vec![];     // pass that last used the slot
        let mut barriers = vec![];
        for r in ids {
            let free = |s: usize| busy_until[s] < life[r].0;
            let fit = (0..slot_size.len()).filter(|&s| free(s) && slot_size[s] >= self.res[r].size)
                .min_by_key(|&s| slot_size[s]);
            let s = fit.or_else(|| (0..slot_size.len()).filter(|&s| free(s)).max_by_key(|&s| slot_size[s]))
                .unwrap_or_else(|| { slot_size.push(0); busy_until.push(0); last_user.push(None); slot_size.len() - 1 });
            slot_size[s] = slot_size[s].max(self.res[r].size);  // growing a free slot is safe
            if let Some(prev) = last_user[s] { // aliasing barrier: previous tenant's last pass -> new tenant's first
                barriers.push(Barrier { res: r, from: prev, to: order[life[r].0], alias: true });
            }
            busy_until[s] = life[r].1; last_user[s] = Some(order[life[r].1]); slot[r] = Some(s);
        }
        // 5. read-after-write barriers on producer -> consumer edges
        for &p in &order {
            for &r in &self.passes[p].reads { if writer[r] != usize::MAX {
                barriers.push(Barrier { res: r, from: writer[r], to: p, alias: false }); } }
        }
        Plan { order, slot, slot_size, life, barriers }
    }
}
impl Graph {
    fn res(&mut self, n: &str, size: u64, imported: bool) -> usize {
        self.res.push(Res { name: n.into(), size, imported }); self.res.len() - 1
    }
    fn pass(&mut self, n: &str, r: &[usize], w: &[usize], side_effect: bool) {
        self.passes.push(Pass { name: n.into(), reads: r.into(), writes: w.into(), side_effect });
    }
}

fn main() {
    let mut g = Graph::default();
    let (a, b, c) = (g.res("a", 8, false), g.res("b", 8, false), g.res("c", 4, false));
    let (dbg, back) = (g.res("dbg", 8, false), g.res("back", 8, true));
    g.pass("scene", &[], &[a], false);
    g.pass("debug", &[a], &[dbg], false); // nobody reads dbg: culled
    g.pass("blur", &[a], &[b], false);
    g.pass("post", &[b], &[c], false);
    g.pass("present", &[c], &[back], true);
    let p = g.compile();
    assert_eq!(p.order, vec![0, 2, 3, 4]);                // pass 1 (debug) is gone
    assert_eq!(p.slot[a], p.slot[c]);                     // a is dead after blur, c reuses its slot
    assert!(p.slot_size.iter().sum::<u64>() < 8 + 8 + 4); // 16 < 20
    assert!(p.barriers.iter().any(|x| x.alias && x.res == c));
}

Complexity and constants

• Cull and edge build: O(P + E). The heap in Kahn adds a log: O(P log P + E).
• Lifetimes O(E); sort O(R log R); best-fit scan O(R·S) with S slots, small because slots are reused.
• Barriers: O(E) plus one per tenant change.
• Cost drivers: allocations of the per-frame vectors, edge count, pass count. Measured on this Mac (Apple M4 Pro, release build, std only, 3 runs): sample frame 11 passes (10 live), 11 resources: about 1.1-1.2 µs per compile; synthetic 1,000 passes (942 live), each reading the pass 1 and 3 before it: about 48-50 µs per compile.
• Memory, measured by the same program: sample 94 MB naive vs 75 MB aliased in 6 slots (1080p G-buffer, 2048² shadow, bloom chain; the G-buffer lives until lighting, so overlap is modest). The synthetic chain is local, so it collapses 8,147 MB to 67 MB in 4 slots: an upper bound, not a typical frame.

Efficiency

• Cost: compile of the sample frame is about 1.1 µs, 1,000 passes about 49 µs (measured, M4 Pro, one thread, allocation-bound; no GPU work). At 60 fps a frame budget is 16.7 ms, so compile is far below 1 % even at 1,000 passes. Bound: CPU, not memory bandwidth. The GPU pays per barrier and layout transition; compile minimises, not removes, them.
• Levers:
  • Aliasing transients — 20 % less memory on the sample, far more on long chains (measured) — whenever lifetimes are disjoint.
  • Cull dead passes — removes their GPU time entirely (O'Donnell 2017 lists culling as a compile goal) — debug views, disabled effects.
  • Cache the compiled plan when declarations are identical to last frame — avoids rebuild (design choice, not measured here) — mostly static pipelines.
  • Order for distance between producer and consumer — fewer hard barriers (Arntzen 2017) — GPUs that overlap passes.
  • Opt-in async compute and split barriers — overlap across queues (O'Donnell 2017; Unreal RDG docs) — compute-heavy passes, at the price of longer lifetimes.
• Naive → standard → state of the art:
  • Hand barriers and hand-owned textures · cost grows with every added feature, bugs show up as GPU hangs or corruption.
  • Declared reads/writes, per-frame compile, interval aliasing · microseconds of CPU, less memory (above).
  • Async queues and split barriers (Unreal RDG docs), merged render-pass barriers (Arntzen 2017) · fewer stalls on top of the above; no figure measured here.

Implementation notes

• Identify resources by handle plus version so a read-modify-write is two edges (read v1, write v2), as in Frostbite's setup example; this keeps the graph acyclic.
• Imported resources (swapchain, TAA history) are never aliased and are the roots for culling. A pass that only writes to memory the CPU reads back needs the side-effect flag.
• Layout state: track the layout at the end of the last use; read-only passes in a row need no barrier if the layout and access match (Arntzen 2017).
• Slots map to heap offsets; align them to the API's requirement.

Pitfalls

• Aliased memory is undefined at first use: clear, fully overwrite or discard it, and on some GPUs reset compression metadata (O'Donnell 2017).
• An undeclared access means a missing barrier, which may only fail on some GPUs. Validate declarations in debug builds.
• A side effect the graph cannot see (readback, debug draw you want kept) gets culled; mark it as an output.
• Async compute lengthens lifetimes and can cost performance if misused (O'Donnell 2017).
• Fragmentation wastes memory (O'Donnell 2017 shows it on PS4); the greedy slot growth here can leave a big slot holding small tenants.

Variants and alternatives

In production

• Frostbite (the FrameGraph of O'Donnell 2017), Unreal Engine's Render Dependency Graph, Granite (Arntzen).
• Outside rendering: XLA buffer assignment; see DAG workflow execution for pruning by requested outputs.

Implementations

Sources

• Yuriy O'Donnell, FrameGraph: Extensible Rendering Architecture in Frostbite, GDC 2017. slides
• Hans-Kristian Arntzen, Render graphs and Vulkan - a deep dive, 2017. blog · code
• Epic Games, Render Dependency Graph in Unreal Engine. docs
• Khronos, Vulkan specification, Synchronization and Cache Control. spec
• OpenXLA, buffer_assignment.h. code
• Bevy, bevy_render::render_graph 0.15.0. docs