For seven scalar packets, put two on the diagonal and \(-1\) on each declared incoming edge. The edges are \(0\to2\), \(1\to2\), \(1\to3\), \(2\to4\), \(3\to4\), \(3\to5\), \(4\to6\), and \(5\to6\). Solve \((2I+K)x={\mathbf{1}}\).
Reading the drawing
Bars place packet tasks into four dependency stages. Later stages follow the declared predecessor dependencies. The vector at right gives the supplied solve’s exact output.
Drawing labels and data 20 labels
Read the original labels as selectable text. Tables preserve grid relationships; other short labels are grouped compactly.
- 0
- 1
- 2
- 3
- 4
- 5
- 6
- stage 1
- stage 2
- stage 3
- stage 4
\(x=(2I+K)^{-1}\mathbf1\)
\(\frac{1}{2}\)
\(\frac{1}{2}\)
- \(1\)
\(\frac{3}{4}\)
\(\frac{11}{8}\)
\(\frac{7}{8}\)
\(\frac{13}{8}\)
- packet task
Read the stages as dependencies
Packets zero and one are ready first. Packets two and three use those values. Packets four and five then become available, followed by packet six. For instance,
All entries in the displayed solution are checked by multiplying the original triangular matrix by the resulting vector.
When is four a minimum?
There are four vertices on a longest dependency path. Under the paper's unit-duration, unlimited-concurrency model, four stages are both necessary and attainable. If only one execution slot is available, seven tasks require seven slots of work. If task durations differ, the relevant critical path is weighted.
The theorem is not a universal GPU scheduling result. Transfers, synchronization, contention, and nonunit task costs change the model. The exact benefit here is that independent rows in one level need not wait for one another's mathematical results.
Read this as
A topological schedule separates dependencies from resources. Its optimal depth is conditional on the task-duration and concurrency model that defines a stage.