10 Device scheduling and amortization
On this page · Permalink · Source line 1722
10.1 Shape classes
On this page · Permalink · Source line 1724
Definition 10.1: Shape class
Two active packet blocks lie in the same shape class when their input dimension, output dimension, right hand side count, scalar type, accumulation type, and kernel contract agree.
Permalink · Source line 1726 · Claim record · Lean coverage · Code · Worked examples
Proposition 10.2: Launch reduction by shape
Suppose \(B\) independent active blocks fall into \(g\) shape classes, and suppose the backend accepts one batched array or pointer list for each class. Grouped execution then requires at most \(g\) launches instead of \(B\), without changing the arithmetic or the output.
Read proof · Visual guide: Batch shapes, account for traffic · Read statement and proof side by side · Permalink · Source line 1730 · Claim record · Lean coverage · Code · Worked examples
Proof of Proposition 10.2
Place all blocks in one class along a batch dimension and invoke one batched kernel for that class. Every block receives the same local computation. One launch per class is sufficient.
Back to statement · Read statement and proof side by side · Permalink · Source line 1734 · Claim record · Lean coverage · Code · Worked examples
CUDA provides graph capture and replay for repeated dependency graphs [NVIDIA2026]. These mechanisms reduce repeated launch work, but they do not change the operator or its arithmetic count.
10.2 Critical path
On this page · Permalink · Source line 1740
Theorem 10.3: Acyclic schedule depth
Let a packet task graph be acyclic. Assume every task takes one normalized stage, every edge is a dependency, and an unlimited number of independent tasks may run concurrently. For a nonempty finite graph, the minimum possible number of sequential stages equals the number of vertices on a longest directed path. The empty task graph has depth zero.
Read proof · Visual guide: A solve has a dependency clock · Read statement and proof side by side · Permalink · Source line 1742 · Claim record · Lean coverage · Code · Worked examples
Proof of Theorem 10.3
Every path gives a lower bound because its tasks must execute in order. The topological level schedule in Theorem 6.5 achieves exactly this depth. With no tasks, the empty schedule has depth zero.
Back to statement · Read statement and proof side by side · Permalink · Source line 1746 · Claim record · Lean coverage · Code · Worked examples
10.3 One time costs
On this page · Permalink · Source line 1750
Theorem 10.4: Amortization threshold
Let \(s\geq0\) be a one time setup cost. Let \(t_b,t_c\ge0\) be the baseline and candidate times per use and let \(R\in{\mathbb N}\) be a reuse count. If \(t_b>t_c\), the candidate is faster after \(R\) uses exactly when
The smallest integer reuse count is
If \(t_b\leq t_c\), no positive reuse count amortizes a positive setup cost.
Read proof · Visual guide: The first win comes after the tie · Read statement and proof side by side · Permalink · Source line 1752 · Claim record · Lean coverage · Code · Worked examples
Proof of Theorem 10.4
Compare
with
Rearranging gives the stated inequality.
Back to statement · Read statement and proof side by side · Permalink · Source line 1771 · Claim record · Lean coverage · Code · Worked examples
Corollary 10.5: Graph replay threshold
If graph capture costs \(c\ge0\), ordinary execution costs \(t_o\ge0\), and replay costs \(0\le t_r<t_o\), then capture is profitable when
Read proof · Visual guide: The first win comes after the tie · Read statement and proof side by side · Permalink · Source line 1783 · Claim record · Lean coverage · Code · Worked examples
Proof of Corollary 10.5
Apply Theorem 10.4 with setup cost \(c\).
Back to statement · Read statement and proof side by side · Permalink · Source line 1791 · Claim record · Lean coverage · Code · Worked examples
Corollary 10.6: Materialization threshold
Suppose a compressed representation costs \(t_c\ge0\) per downstream use, an explicit representation costs \(t_e\ge0\) per use, and one time materialization costs \(m\ge0\), with reuse count \(R\in{\mathbb N}\). Materialization is profitable exactly when
and \(t_c>t_e\).
Read proof · Visual guide: The first win comes after the tie · Read statement and proof side by side · Permalink · Source line 1795 · Claim record · Lean coverage · Code · Worked examples
Proof of Corollary 10.6
Compare repeated compressed use with materialization followed by repeated explicit use.
Back to statement · Read statement and proof side by side · Permalink · Source line 1804 · Claim record · Lean coverage · Code · Worked examples