Graphs, critical paths and the exam table: list scheduling

One loop body, one graph

Lesson 19 left the compiler of a VLIW with one job: pack independent operations into bundles without changing what the program computes. The unit it works on is the basic block.

The body of every loop in the exam papers is one basic block, and the BNE that closes it is its exit. Here is the January 2026 body as the notes print it (p. 489), without its dollar signs: that paper and the July 2024 one write $F2, the June 2025 paper mixes both, the June 2026 paper writes F2 — and so does this notebook.

FOR: LD    F2, VB(R6)     # I0
     FADD  F4, F2, F6     # I1
     SD    F4, VA(R7)     # I2
     LD    F4, VC(R6)     # I3
     SD    F4, VC(R7)     # I4
     FADD  F8, F8, F8     # I5
     ADDUI R6, R6, 4      # I6
     ADDUI R7, R7, 4      # I7
     BNE   R7, R8, FOR    # I8

The compiler turns the block into a dependence graph, a DAG: one node per instruction, one edge from I to J whenever J must wait for I (p. 277). The edges are the three dependences of lesson 7, and on the exam's machine each kind has its own timing rule. Write the latency on the edge: it is the number the scheduler will use.

• RAW, the true dependence: I1 reads F2, which I0 writes. The value does not exist before the producer's latency has passed, so the consumer goes at the producer's cycle plus the latency: 3 after a load, 3 after an FP operation, 1 after an integer operation — and 2 when the consumer is the branch.
• WAR, the anti-dependence: I3 writes F4, which I2 still has to read. Only the name is shared — another destination register would remove the edge (renaming, lesson 15), but in the exam table you only reorder, so it stays. The paper says that "it is possible to read and write at the same address at the same clock cycle", so the writer may share the cycle of its last reader — never come before it.
• WAW, the output dependence: I1 and I3 both write F4, and the second result must land after the first. In the papers' loops this never binds: RAW and WAR edges already order every such pair.

Two facts about the branch close the rule book. The BNE is the exit, so nothing is scheduled after it. And the branch is resolved in ID, with one delay slot: the cycle after the BNE belongs to the iteration, because the next iteration cannot start before it. Fig. 1 shows the three rules where you will meet them — in the exam table itself.

Now draw all the edges of the January loop at once (Fig. 2). Read it as a set of promises: a solid arrow with a 3 says that the instruction at its head goes at least three cycles after the one at its tail; a dashed arrow says no earlier than its tail. Two things can be read off the picture (p. 276): which instructions are independent — no path joins them, so they may share a cycle if the units allow — and the longest chain, which limits everything else. I5 floats free: nobody else touches F8.

The notes draw the same kind of graph for their Example 1 (p. 278), the loop of the paper of 11 February 2025, numbered from I1 there. Its machine differs in one number: the FP unit has a latency of 2.

I1   LOOP: LD    F1, A(R1)
I2         LD    F2, A(R2)
I3         LD    F3, A(R3)
I4         FADD  F1, F1, F2
I5         FADD  F2, F2, F3
I6         FMUL  F1, F1, F2
I7         FADD  F3, F3, F3
I8         ADDUI R2, R1, 8
I9         ADDUI R3, R1, 8
I10        SD    F1, B(R1)
I11        ADDUI R1, R1, 4
I12        BNE   R1, R6, LOOP

Its graph has almost as many dashed edges as solid ones: nine RAW, eight WAR. R1 is read by I1, I8, I9 and I10 before I11 overwrites it, so four WAR edges converge on I11; two loads and two FADDs are the readers of the other four. Find them yourself, then compare with the playground of section 3, which draws every edge.

The longest path: a floor no machine can beat

Forget the machine for a moment and give it as many units as it wants. Every instruction can then start the moment its incoming edges allow, and the block lasts exactly as long as its heaviest chain of edges. That chain is the critical path. A kitchen knows the idea: if the sauce simmers three minutes before it goes on the plate, a second cook does not make it simmer faster.

The notes compute it node by node, from the sources down (eq. 65, p. 277; the notes write "Longest Path" and "Latency" in full). Take their Example 2: seven operations, no registers, latencies 3 for a multiply, 1 for an add or subtract, 2 for the store.

The left panel of Fig. 3 runs it on Example 2: a = 3, b = c = 1, e = 2, d = 3 + 3 = 6, f = max(2, 1) + 2 = 4, g = max(6, 4) + 1 = 7. The critical path is 7 cycles, along a → d → g. Why is that number a floor for every machine, and not just a property of this drawing? The stepper proves it.

1. Call \(t(i)\) the cycle in which \(i\) is issued and \(\ell(p \to i)\) the latency on an edge (0 on a dashed one). Every schedule, on any machine, must respect every edge:

   \[ t(i) \ge t(p) + \ell(p \to i) . \]

2. Follow a path \(p_0 \to p_1 \to \dots \to p_k\) and add its inequalities: the intermediate terms cancel.

   \[ t(p_k) \ge t(p_0) + \textstyle\sum_j \ell_j . \]

3. The first instruction issues in cycle 1 at the earliest, and the last one still needs its own latency: the block lasts at least

   \[ 1 + \textstyle\sum_j \ell_j + \text{Lat}(p_k) - 1 , \]

   which is the weight of the path as eq. 65 counts it.

4. This holds for every path, so for the heaviest one: any schedule lasts at least CP cycles. Extra units only remove reasons to wait; they remove no edge.

5. With unlimited units each instruction can go exactly at \(\max_p [\,t(p) + \ell(p \to i)\,]\). That schedule meets the bound, so the bound is tight: with unlimited units the block takes exactly CP cycles.

The schedule of the last step has a name: ASAP, as soon as possible (p. 279). It schedules every operation in the first cycle its operands allow and ignores resources — the notes compare it to planning a trip as if every traffic light were green (p. 280). On a real machine it is rarely a legal schedule — it may ask for more units than exist — but it is precious as a measuring stick: it gives the lower bound, the earliest cycle of every instruction and, early in the compiler, a first estimate of how much parallelism there is to exploit. Here is Example 2 under ASAP, with the unit columns of the notes; the ready list holds the instructions whose operands are available in that cycle.

The scheduler of the next section needs the opposite number. Not "how long did it take to reach this instruction", but "how long does the graph still run after it". That is the priority of list scheduling: the longest path from the instruction to a sink, computed backwards, from the sinks up (p. 281).

On the exam machine one detail changes: the latency belongs to the edge, not to the node. An ADDUI that feeds a store counts 1; the same ADDUI feeding the BNE counts 2. The branch itself weighs 2 — its own cycle plus the delay slot — and every other instruction must be issued no later than the branch. With these weights, I0 of the January loop gets priority 13: the floor of the puzzle, the highlighted chain of Fig. 2.

List scheduling, one cycle at a time

A real machine has a fixed number of units, and that is all list scheduling adds to ASAP (p. 281). In every cycle it collects the ready set — the instructions whose operands are available in that cycle — and hands the free units to the most urgent ones. The bookkeeping of who occupies which unit in which cycle is the resource reservation table.

1. Build the dependence graph and compute every priority.
2. Start at cycle 1. An instruction is ready when every predecessor is placed early enough: RAW at least \(\ell\) cycles before, WAR in this cycle or before.
3. While a unit is free and something ready fits it, take the highest-priority instruction (ties: program order) and place it in this cycle. Placing it may make a WAR successor ready in the same cycle.
4. Move to the next cycle; repeat until every instruction is placed.

The algorithm is greedy: it never revisits a choice, so it is a heuristic for a problem that is hard in general, not an optimiser. With the longest-path priority it finds the shortest schedule on most graphs of exam size — the June 2025 loop of the exam questions is the exception that shows why it is called a heuristic. Here is the notes' Example 3: the graph of Example 2 on one ALU, one L/S unit and one MUL.

Cycle 1: a takes the MUL; b (5) beats c (4) for the only ALU. Cycle 2: c and e tie at 4 and program order picks c. Cycle 4: d and f each have a unit of their own. The VLIW code, one bundle per row, reads {b, a}, {c}, {e}, {f, d}, two empty bundles, {g}: 7 operations in 21 slots. The schedule is 7 cycles long — the critical path. One ALU instead of two cost nothing, because the ALU operations have slack while the chain through the MUL is critical.

The playground runs the same algorithm on three graphs: the notes' Examples 2–3, their Example 1 (the February 2025 loop) and the January 2026 loop. Change the machine and watch two numbers: the floor and the schedule.

The exam table: conventions, a forced schedule, four numbers

Exercise 2 of the papers of July 2024, June 2025 and June 2026 is this algorithm on paper, worth 5 points: "complete the following table by using the list-based scheduling", one row per cycle, one column per unit — Memory Unit, Floating Point Unit, Integer Unit — with the first instruction already written in C1. The texts give the machine; the rest is the convention of the solutions worked out in the notes (pp. 491–492 and 561), which this notebook follows. Keep all of it on your formula sheet:

1. Units are fully pipelined: each takes one new instruction per cycle, and the three units are the three issue slots of a bundle.
2. RAW: the consumer goes at the producer's cycle + 3 after a load or an FP operation, + 1 after an integer operation, + 2 when the consumer is the branch.
3. WAR: the writer may share the cycle of the last reader of its register, never come before it. WAW: the second writer's result lands later.
4. The BNE is the last instruction. The row after it is the delay slot: write "(delay slot)", count it, put nothing in it.
5. No NOPs are written: an empty cell stays empty. No unrolling, no software pipelining, no change of offsets or indexes: you only reorder.
6. The answers: the critical path for a single iteration is the number of cycles of your table, delay slot included; CPI = cycles / instructions; FP ops per cycle = FP operations / cycles; code efficiency = instructions / (cycles × issue width).

Now the January 2026 loop on its machine. The stepper places the instructions in the order list scheduling meets them; every placement on the chain is forced.

1. C1. Ready: I0 (priority 13) and I5 (2). I6 is not ready although nothing feeds it a value: it overwrites R6, which I3 has not read yet. I0 takes the Memory Unit, I5 the FP unit.

2. C4. I1 needs F2 from the load: C1 + 3. Nothing else is ready in C2 and C3, so they stay empty.

3. C7. I2 needs F4 from I1: C4 + 3. I3 is ready in C7 too — its WAR with I2 allows the same cycle — but the single Memory Unit is taken.

4. C8. I3 takes the Memory Unit; I6, whose last reader of R6 is I3, joins it in the Integer Unit. C9 and C10 wait for the load.

5. C11. I4 stores the F4 just loaded: C8 + 3. I7 shares the cycle: I4 is the last reader of R7.

6. C13. The BNE needs R7 from I7: C11 + 2. C14 is the delay slot. The iteration is 14 cycles long.

Two instructions have freedom, because nothing waits for them: I5 may sit in any free FP cell up to C13, and I6 in C8, C9, C10 or C12. Moving them changes no number. The paper's four questions, answered as you would write them:

The February 2025 loop (Example 1), on the same machine but with an FP latency of 2, gives 13 cycles:

The three loads queue on one memory port (C1–C3), and each ADDUI writing R2 or R3 waits for the load that reads it. I4 needs F2 from C2: C5. I5 needs F3 from C3: C6. I7 fills C7 while FMUL waits for I5's F2 until C8. The answers: critical path 13 cycles; code efficiency = 12 / (13 × 3) = 12/39 = 30.77 %. With unlimited units the three loads would share C1 and the floor is 11: here the machine costs two cycles.

The trainer below is the exam table with the rules built in. Pick an instruction, then a cell; an illegal placement turns red and the note says which rule it breaks. When the table is complete it computes the four numbers and explains every empty cell.

Back to the puzzle. The floor of the January loop is 13 cycles: the chain of Fig. 2, which ASAP reaches when I2 and I3 share C7 (Fig. 4, left). The paper's machine has one Memory Unit, so I3 slips to C8 and the whole tail with it: 14 (right). And 14 is the best this machine allows. I3 may not go before I2 (WAR on F4) nor with it (one memory unit), so it lands in C8 at the earliest, and every later step of the chain is forced.

Now change one number of the machine sentence. A second Memory Unit gives 13: the gap closes, and nothing more can be gained by adding units. A memory latency of 2 gives 12, an FP latency of 2 or an integer-to-branch latency of 1 give 13: each of them shortens an edge of the chain, so it moves the floor itself. A second FP unit or a second integer unit gives nothing: I5 and the two ADDUI instructions never wait for their unit. Units can only close the distance to the floor; latencies move the floor.

Local and global scheduling: the map of the next lesson

Everything so far was local scheduling: it works inside one basic block, where control flow is a straight line and the compiler knows every instruction and every dependence (p. 283). Its goal is to fill the slots with real instructions instead of NOPs. Its limit is the block itself: instructions cannot cross the block's boundaries, so the parallelism is bounded by the block's size and its chains — nine instructions, one long chain, 33 empty slots.

Global scheduling works across blocks — across branches, across loop boundaries, along whole paths of control flow. It finds more parallelism and hides long latencies, at a price: control dependences must be preserved too, moves that guess wrong need compensation code, and the compiler becomes more complex and more expensive to build. The notes sort the techniques of the chapter in Table 23 (p. 284):

ASAP and list scheduling sit under all four: each technique reshapes the code, and then a list scheduler fills the bundles. The exam's Exercise 2 forbids the first two by name — "do NOT introduce any software pipelining, loop unrolling and modifications to loop indexes" — so the exercise tests the list scheduler alone. The June 2025 and June 2026 papers then hand you a loop that has already been software-pipelined and ask you to schedule it as it is: two of the exercises below.