Lab 23 · List scheduling and iterative modulo scheduling on a toy VLIW¶

Chapter: 23 · Instruction Scheduling & Machine-Level Optimization · Lessons: 23.1, 23.2, 23.3, 23.6, 23.8 · Time: 12–16 hours · Tests: ./course test 23 (label ch23; the ★ test also carries the label star)

1. Goal¶

You write the scheduler of a small statically scheduled machine: an in-order VLIW that issues up to two operations per cycle to pipelined and non-pipelined units, with no interlocks, so every schedule it runs must already be correct. For basic blocks you build the dependence DAG (Lesson 23.2, Algorithm 23.2.6) and implement top-down and bottom-up list scheduling with two priority functions (Lesson 23.3, Algorithm 23.3.2, Definition 23.3.5), plus a ★ register-pressure-aware variant (Algorithm 23.3.10). For loops you compute ResMII and RecMII, run iterative modulo scheduling (Algorithm 23.6.9) and generate the prologue, kernel and epilogue with rotating registers (Algorithm 23.6.12). A provided checker rebuilds the dependence graphs independently, validates every schedule and runs it on a cycle-accurate simulator against the sequential semantics. Then you measure: how close each list algorithm gets to the lower bound max(critical path, resource bound), what it costs in registers, and how often IMS reaches MII.

2. The contract and the command line¶

Two functions, declared in include/sched/Scheduler.h, are the only code the tests call. You write them in src/ (any files you like; the provided Stub.cpp stops with TODO(ch23) until you replace it):

namespace sched {
enum class Algo { TdCp, TdSucc, BuCp, BuSucc, Pressure, Modulo };
struct Options { Algo A = Algo::TdCp; int Regs = 0; };   // Regs: pressure only; 0 = default K (R6)
std::optional<Algo> parseAlgo(std::string_view Name);    // PROVIDED (provided/Algo.cpp)
std::expected<std::string, std::string> scheduleBlock(const prog::Region &Block, const Options &O);  // YOU
std::expected<std::string, std::string> scheduleLoop(const prog::Region &Loop, const Options &O);    // YOU
}

scheduleBlock receives a Region of kind Block and one of the five list algorithms and returns the text of §5.2. scheduleLoop receives a Region of kind Loop (with Algo::Modulo) and returns the text of §6.3. Return std::unexpected(message) only for inputs outside this spec (the tests never do that). Both must be deterministic: the same input gives the same text.

The provided driver runs them on a file:

ch23-sched --algo=td-cp|td-succ|bu-cp|bu-succ|pressure|modulo [--regs=K] FILE

List algorithms schedule every block of FILE and modulo every loop, printing the results one after the other. ch23-check FILE SCHEDULES validates a schedule file against its program (the same checks the tests run) and prints one NAME: ok: ... line per region, or the first error; ch23-compare is the measurement driver (§9).

3. The machine¶

A machine description (the toy machine of the lessons is in inputs/running.txt):

machine toy
  issue 2              # at most 2 instructions issue per cycle
  unit alu 2           # two ALUs
  unit mem 1
  unit mul 1
  op add alu 1         # op NAME UNIT LATENCY [OCCUPANCY]; occupancy defaults to 1
  op mul mul 3         # pipelined: a new mul may start every cycle
  op div mul 6 4       # not fully pipelined: holds the mul unit for 4 cycles
  op load mem 3
  op store mem 1
  ...
end

Timing. An instruction issued in cycle \(t\) reads its operands in cycle \(t\), and its result (register or memory) is visible from cycle \(t + \mathrm{lat}\) on. Nothing stalls: reading a register before a pending write lands reads the old value.
Reservation table (Definition 23.1.2). An instruction of class op NAME UNIT LAT OCC issued at \(t\) uses the pseudo-resource issue in cycle \(t\) and one UNIT in cycles \(t, \dots, t + \mathrm{OCC} - 1\). A schedule is resource-feasible when no resource is used more than its capacity (issue width, unit count) in any cycle.
The tests also use a wider machine and the machines graham1..graham4 of \(P \mid \mathrm{prec} \mid C_{\max}\) (m identical non-pipelined units, occupancy = latency). Nothing in your code may assume the toy machine.

4. Programs¶

4.1 Blocks and loops¶

block run              # a basic block; the name is unique among blocks of the file
  liveout r4           # registers whose final values matter (optional, any number)
  a: r1 = load A[0]
  b: r2 = load A[1]
  d: r4 = mul r1, r2
  h: store A[r2], r5   # a register index (§4.2)
  ...
end

loop run               # the body of a counted loop over i = 0, 1, ..., N-1
  liveout r6
  a: r1 = load A[i]    # element i+c of array A: A[i], A[i+1], A[i-2]
  d: r4 = mul r6, r9   # r6 is read before e defines it: the previous iteration's r6
  e: r6 = add r4, r3
  f: store C[i], r6
end

Instructions are ID: DST = OP SRC, SRC (add sub mul div and or xor), ID: DST = mov SRC, ID: DST = li IMM, ID: DST = load ARRAY[INDEX] and ID: store ARRAY[INDEX], SRC. Registers are r0, r1, …; ids are unique within a region; # starts a comment. The provided parser (sched/Program.h) reads all of this into prog::Region; Instr::uses() lists the registers an instruction reads.

A loop is simple: every register is defined at most once in the body, memory operands index with i only, and there is no control flow. A register read by an instruction at or before its definition in the body reads the value of the previous iteration (distance 1); on the first iteration, the value it had before the loop.

4.2 Memory and aliasing¶

In blocks, A[3] is element 3 of array A, and A[r2] is element \((r2 \bmod 8)\), unknown at compile time. Two memory accesses may alias when they name the same array and either both indices are the same constant or at least one is a register. Different arrays never alias. In loops, A[i+c1] and A[i+c2] of iterations \(i_1, i_2\) touch the same element iff \(i_1 + c_1 = i_2 + c_2\).

5. Blocks: list scheduling¶

5.1 The canonical dependence DAG (R2)¶

For instructions \(i\) before \(j\) in the block, with latencies \(\mathrm{lat}_i\), \(\mathrm{lat}_j\):

Edge \(i \to j\)	when	latency \(\ell(i, j)\)
true	\(j\) reads a register whose reaching definition is \(i\)	\(\mathrm{lat}_i\)
anti	\(i\) reads register \(r\) and \(j\) is the next definition of \(r\) after \(i\)	\(0\)
output	\(j\) is the next definition of the register \(i\) defines	\(\max(1, \mathrm{lat}_i - \mathrm{lat}_j + 1)\)
memory true	\(i\) is a store, \(j\) a load, and they may alias	\(\mathrm{lat}_i\)
memory anti	\(i\) is a load, \(j\) a store, and they may alias	\(0\)
memory output	both stores and they may alias	\(\max(1, \mathrm{lat}_i - \mathrm{lat}_j + 1)\)

Memory edges connect every may-alias pair with at least one store (not only the nearest). Parallel edges merge into one edge with the largest latency. A schedule \(t\) is valid when \(t_j \ge t_i + \ell(i,j)\) for every edge and it is resource-feasible (§3). Its length is \(L = \max_i (t_i + \mathrm{lat}_i)\). Validity guarantees that the cycle-accurate execution computes what sequential execution computes (§7, Lesson 23.2 §4).

5.2 Output format of `scheduleBlock` (R1)¶

block NAME length L
  ID CYCLE              one line per instruction, in block order
end

CYCLE is the issue cycle (\(\ge 0\)) and L the length. Whitespace between tokens is free and the checker ignores # comments. The running block with td-cp:

block run length 10
  a 1
  b 2
  c 0
  d 5
  e 3
  f 4
  g 5
  h 6
  i 8
  j 9
end

5.3 The list algorithms (R3, R4)¶

R3 (top-down, td-cp and td-succ). Cycle-driven list scheduling (Algorithm 23.3.2). Start at cycle \(c = 0\). An unscheduled instruction is ready in cycle \(c\) when every predecessor \(p\) is scheduled and \(t_p + \ell(p, i) \le c\). Repeatedly take the ready instruction with the smallest key whose reservation table fits at \(c\) and schedule it at \(c\); an instruction made ready by a zero-latency edge from one placed in cycle \(c\) may go in cycle \(c\) too. When no ready instruction fits, go to \(c + 1\). Keys (compared lexicographically, \(h\) = height, Algorithm 23.2.9):
cp: \((-h(i),\ \mathrm{index}(i))\) — critical path first, then block order;
succ: \((-\lvert\mathrm{succs}(i)\rvert,\ -h(i),\ \mathrm{index}(i))\) — most DAG successors first.
R4 (bottom-up, bu-cp and bu-succ). Run the top-down algorithm of R3 on the reversed instance (Definition 23.3.5) and mirror the result (Theorem 23.3.6):
instruction \(k\) of the reversed instance is instruction \(n - 1 - k\) of the block (so "index" tie-breaks favor the later instruction);
every edge \(i \to j\) becomes \(j \to i\) with latency \(\mathrm{lat}_j - \mathrm{lat}_i + \ell(i, j)\) (it may be negative);
each reservation-table entry \((r, o)\) of \(i\) becomes \((r, \mathrm{lat}_i - 1 - o)\);
heights and successor counts are those of the reversed DAG (so bu-succ counts predecessors);
map back with \(t_i = L' - s_i - \mathrm{lat}_i\), where \(s\) is the reversed schedule and \(L'\) its length.
R5 (bounds). Every list schedule is valid and \(L \ge \max(\mathrm{CP}, \mathrm{RB})\), where CP is the critical path and RB \(= \max_r \lceil \text{uses of } r / \mathrm{cap}(r) \rceil\). On the \(P \mid \mathrm{prec} \mid C_{\max}\) machines every algorithm satisfies Graham's bound \(m L \le \sum_i p_i + (m - 1)\,\mathrm{CP}\) (Theorem 23.3.3) — a consequence of never leaving a unit idle while an instruction is ready.

The tie-breaks make the four schedules unique; the tests compare your lengths with goldens from the Python oracle tools/course/lib/sched.py (list_schedule), which ./course drill list-schedule --solution also uses.

5.4 Register pressure (MaxLive)¶

A value is a definition in the block, or a register read before any definition in the block (a live-in). A value occupies a register from its definition's issue cycle (live-ins: from cycle 0) through the issue cycle of its last use; if its register is in liveout and it is the last definition of that register (or an unredefined live-in that is used), through cycle \(L - 1\). A definition that is never used occupies its issue cycle only. MaxLive is the maximum over cycles \(0 \le c < L\) of the number of values occupying a register in cycle \(c\) (Lesson 23.3, Definition 23.3.9). The checker reports it for every schedule.

5.5 ★ Pressure-aware scheduling (R6)¶

R6 (pressure). Top-down list scheduling (as R3) under a register limit \(K\): Options::Regs, or when it is 0, the MaxLive of the in-order schedule (each instruction, in block order, at the first cycle \(\ge\) the previous instruction's cycle \(+ 1\) that satisfies its dependences and fits). Your schedule must be valid with MaxLive \(\le K\); how you get there is up to you (Algorithm 23.3.10: refuse to start a new value when \(K\) registers are live, prefer instructions that end lifetimes when pressure is high, and fall back to the in-order schedule if the greedy pass gets stuck). The tests check the limit, and that over the corpus your total length is below the in-order total and your total MaxLive is at most td-cp's. The output format is §5.2.

6. Loops: modulo scheduling¶

6.1 The loop dependence graph¶

Edges \(i \to j\) carry a latency \(\ell\) and an iteration distance \(d\) (Definition 23.6.1):

Registers: flow edges only. For each use by \(j\) of a register defined by \(i\) in the body: latency \(\mathrm{lat}_i\), distance 0 if \(i\) comes before \(j\) in the body, else 1. (Anti and output dependences on registers disappear because §6.4 renames every value.)
Memory: every pair of accesses to the same array with at least one store. With offsets \(c_a, c_b\), the access with the larger offset touches each element first; the edge goes from it to the other with distance \(\lvert c_a - c_b \rvert\) (for equal offsets: from the earlier instruction in the body, distance 0). Latency as in §5.1 (store→load \(\mathrm{lat}\), load→store 0, store→store the output rule).
Parallel edges with the same distance merge (largest latency).

A modulo schedule assigns each instruction a time \(\sigma_i \ge 0\); iteration \(k\) of instruction \(i\) issues at \(k \cdot \mathit{II} + \sigma_i\). It is valid when \(\sigma_j \ge \sigma_i + \ell - \mathit{II} \cdot d\) for every edge and the modulo reservation table (every reservation \((r, o)\) of \(i\) counted in row \((\sigma_i + o) \bmod \mathit{II}\)) never exceeds a capacity (Definition 23.6.2). The number of stages is \(S = \lfloor \max_i \sigma_i / \mathit{II} \rfloor + 1\) and instruction \(i\) is in stage \(\lfloor \sigma_i / \mathit{II} \rfloor\).

6.2 Requirements¶

R7 (MII). Report \(\mathrm{ResMII} = \max(1, \max_r \lceil \text{uses of } r / \mathrm{cap}(r) \rceil)\) (counting every occupied cycle and the issue slots) and \(\mathrm{RecMII}\) = the least \(\mathit{II} \ge 1\) such that no dependence cycle has \(\ell(C) - \mathit{II} \cdot d(C) > 0\) (Theorem 23.6.7). The checker recomputes both.
R8 (II). Find a valid modulo schedule with \(\mathit{II} \ge \mathrm{MII}\) and normalize \(\sigma\) so that \(\min_i \sigma_i = 0\). On the 120 loops of tests/ch23/Inputs/loops.txt (and the running loop) an \(\mathit{II} = \mathrm{MII}\) schedule exists and your \(\mathit{II}\) must equal MII; on the 30 of loops-hard.txt any valid \(\mathit{II} \ge \mathrm{MII}\) passes. Rau's IMS with HeightR priority and a budget of \(3n\) placements per \(\mathit{II}\) (Algorithm 23.6.9) achieves this; you may use another algorithm (Swing, integer programming) if it does too.
R9 (code). Generate the prologue, kernel and epilogue with rotating registers (§6.3–§6.4) so that for every trip count \(N \ge S\) the code computes exactly what \(N\) sequential iterations compute (memory and live-out registers).
R10 (performance). ch23-compare on its default input finishes in seconds; the reference takes roughly 20–150 µs per block (depending on the algorithm and the machine's load; timings vary by 2–3× between runs on a shared machine) and 0.1–0.25 ms per loop including code generation. Any polynomial algorithm is fine; exponential search is not.

6.3 Output format of `scheduleLoop`¶

loop NAME ii II resmii R recmii C stages S
  sigma ID T               one line per instruction (any order)
  preheader                copies executed once before the pipeline
    qX = mov rY
  prologue 0               S-1 prologue groups: group g holds the instructions with stage <= g
    @OFF ID: INSTRUCTION
  ...
  kernel                   all instructions; runs N - S + 1 times
    @OFF ID: INSTRUCTION
  epilogue 0               S-1 epilogue groups: group e holds the instructions with stage > e
    @OFF ID: INSTRUCTION
  ...
  exit                     copies executed once after the pipeline
    rY = mov qX
end

Every group is \(\mathit{II}\) cycles long and an instruction issues at offset @OFF \(= \sigma \bmod \mathit{II}\) within it. Groups run back to back, group \(g\) occupying cycles \(g \cdot \mathit{II}, \dots, (g+1) \cdot \mathit{II} - 1\); results land \(\mathrm{lat}\) cycles after issue, possibly in a later group.
INSTRUCTION is the original instruction with its registers renamed (§6.4) and with a memory operand X[i+c] of an instruction in stage \(s\) written as X[i+c-s], where i is the group number (the executed group index: \(0\) for the first prologue group). The operation, the immediate and the operand count must be unchanged.
The prologue and epilogue for \(S = 1\) are empty (no groups); preheader and exit may be empty.

6.4 Rotating registers¶

The machine has 64 rotating registers q0..q63 besides the r registers. They rotate at the end of every group: the logical name qx used in group \(g\) (counting preheader as group 0 and the exit as group \(N + S - 1\)) is the physical register \((x - g) \bmod 64\). So a value written as qx in one group is read as q(x+1) in the next. Registers not written by the loop (like r9 in the running loop) may be read directly. Algorithm 23.6.12 gives one allocation: a window of consecutive logical names per value, with the use in a later group reading a larger name; the preheader copies the initial value of every register with a distance-1 use into the name its first reader expects, and the exit copies every live-out register from its last instance. Any allocation the simulator accepts passes.

The running loop with the reference solution (Lesson 23.6 §3, "Modulo code generation", walks through it):

loop run ii 4 resmii 3 recmii 4 stages 3
  sigma a 0
  sigma b 1
  sigma c 4
  sigma d 7
  sigma e 10
  sigma f 11
  preheader
    q8 = mov r6
  prologue 0
    @0 a: q0 = load A[i]
    @1 b: q2 = load B[i]
  prologue 1
    @0 a: q0 = load A[i]
    @0 c: q4 = mul q1, q3
    @1 b: q2 = load B[i]
    @3 d: q6 = mul q9, r9
  kernel
    @0 a: q0 = load A[i]
    @0 c: q4 = mul q1, q3
    @1 b: q2 = load B[i]
    @2 e: q9 = add q7, q5
    @3 d: q6 = mul q9, r9
    @3 f: store C[i-2], q9
  epilogue 0
    @0 c: q4 = mul q1, q3
    @2 e: q9 = add q7, q5
    @3 d: q6 = mul q9, r9
    @3 f: store C[i-2], q9
  epilogue 1
    @2 e: q9 = add q7, q5
    @3 f: store C[i-2], q9
  exit
    r6 = mov q10
end

7. What the checker and simulator do¶

check::checkBlock / check::checkLoop (include/sched/Check.h, provided) parse your text and reject it with a message naming the first problem: a malformed line, an instruction missing or scheduled twice, a violated dependence of their own canonical graph (§5.1 or §6.1), a resource over capacity (per cycle, or per MRT row), a wrong stated length / ResMII / RecMII / stage count, a group with a wrong or missing instruction or offset or memory offset, a rotating register outside q0..q63. Then they simulate: registers and memory start from pseudo-random values (a different seed per run); the sequential semantics executes the instructions in order (64-bit wrap-around arithmetic, div by zero gives 0, A[r] indexes element \(r \bmod 8\)); the pipelined execution issues each instruction at its cycle, reads operands at issue and commits results at issue + latency, and reports two writes to the same register or address landing in the same cycle. Memory and the live-out registers must agree. Blocks run 4 times; loops for 4 trip counts between \(S\) and \(S + 7\).

8. What the tests check¶

Test	Checks
`ch23.List/*.RunningExample` (per algorithm)	valid; CP 9, RB 5; the length of Lesson 23.3's trace (td-cp 10; td-succ, bu-cp, bu-succ 11)
`ch23.List/*.CorpusMatchesGoldens`	240 blocks on the toy and a wider machine (register reuse, register-indexed memory, `div`): valid, \(L \ge \max(\mathrm{CP}, \mathrm{RB})\), and \(L\) equal to the oracle's (R3–R4 tie-breaks)
`ch23.List/*.GrahamBound`	240 random DAGs on `graham1`..`graham4`: \(m L \le \sum p + (m-1)\,\mathrm{CP}\)
`ch23.List/*.Deterministic`	the same text twice
`ch23.Pressure.*` ★	R6 with the default \(K\), and with `Regs` = in-order MaxLive + 1, on the 240 corpus blocks; the running block with MaxLive \(\le 5\) and no longer than in-order; totals vs in-order and td-cp
`ch23.Modulo.RunningExample`	ResMII 3, RecMII 4, II 4, the code simulated
`ch23.Modulo.AchievesMII`	120 loops: stated MIIs equal the oracle's, \(\mathit{II} = \mathrm{MII}\), code simulated
`ch23.Modulo.HarderLoopsAreValid`	30 loops: valid, \(\mathit{II} \ge \mathrm{MII}\), code simulated
`ch23.Modulo.CheckerAgreesWithOracle`, `Deterministic`	the checker's MIIs on every corpus loop (infrastructure); your text twice
`tests/ch23/lit/list-running.test`	`ch23-sched --algo=td-cp` prints every issue cycle of §5.2's example; bu-cp and td-succ lengths; `ch23-check` accepts
`tests/ch23/lit/modulo-running.test`	the header line of the running loop and `ch23-check` accepts
`tests/ch23/lit/modulo-carried.test`	a loop-carried value defined in stage 2 next to a value written in group 0 (`tests/ch23/lit/Inputs/carried.txt`): the preheader's copy must survive the prologue (§6.4); `ch23-check` accepts
`tests/ch23/lit/check-errors.test`	the checker's messages on sixteen broken schedules (dependences of every kind, resources, length, II, stage count, MRT, group contents and offsets, memory offsets, rotating registers, colliding writes) and acceptance of three right ones (infrastructure; passes in the skeleton too)
`ch23.lab.compare-smoke`	`ch23-compare --quick` runs every algorithm and validates every result

The corpora are generated by tests/ch23/update_goldens.py from the Python oracle; there are no hidden inputs.

9. Milestones¶

Read and check (no code of yours yet): build/<preset>/bin/ch23-check labs/ch23-sched/inputs/running.txt tests/ch23/lit/Inputs/bad-dep.txt prints an error; write §5.2's example into a file by hand and see it accepted.
E1 — DAG and top-down (R1–R3, R5): ./course test 23 → ch23.List/td_cp.*, ch23.List/td_succ.*, list-running.test (TDCP lines).
E2 — bottom-up (R4): ch23.List/bu_cp.*, ch23.List/bu_succ.*.
E3 ★ — pressure (R6): ch23.Pressure.*.
E4 — MII and IMS (R7–R8): print only the header and sigma lines first, and check them with a scratch test of your own against ch23.Modulo.AchievesMII's goldens (tests/ch23/Inputs/goldens.txt, lines NAME mii MII RESMII RECMII).
E5 — code generation (R9): ch23.Modulo.*, modulo-running.test, ch23.lab.compare-smoke.
Measure (§10).

10. Measurement¶

build/<preset>/bin/ch23-compare [FILE...] (default: inputs/bench.txt, 200 blocks and 100 loops) prints, per list algorithm, the total length, the total lower bound, the ratio, the share of blocks at the bound, total MaxLive and microseconds per block; then the in-order totals; then the modulo totals. Run it on inputs/bench.txt and on tests/ch23/Inputs/blocks.txt tests/ch23/Inputs/loops.txt tests/ch23/Inputs/loops-hard.txt, and fill in:

Input	td-cp L / bound	td-succ	bu-cp	bu-succ	pressure	MaxLive td-cp / pressure / in-order	II = MII
bench.txt
test corpora

The reference solution on the test corpora: total lengths td-cp 4110, td-succ 4118, bu-cp 4153, bu-succ 4171, pressure 4298 against a bound of 3943; total MaxLive 1224 (td-cp), 1079 (pressure), 1086 (in-order); sum of II 985 against sum of MII 944, \(\mathit{II} = \mathrm{MII}\) on 120 of 150 loops, 2.22 stages on average. Explain in two sentences why critical-path priority wins on these blocks, and what the pressure scheduler trades (Lesson 23.3 §8, Lesson 23.8 §8).

11. Hints¶

Hint 1 — where to start

Build one scheduling instance type — latencies, reservation tables, capacities, and an edge map (i, j) → latency — from a block. Then the top-down scheduler takes an instance and a key per instruction and knows nothing about registers or memory. Bottom-up scheduling is then "reverse the instance, run the same function, mirror", and your DAG code is written once.

Hint 2 — the ready rule and the reservation table

Keep a map (resource, cycle) → count for the partial schedule. In each cycle, recompute the ready set after every placement (a zero-latency successor can become ready at once), and try candidates in key order until none fits. Cycles in which nothing is ready or nothing fits are normal: they are latency or resource stalls.

Hint 3 — MII and IMS

RecMII: for a candidate \(\mathit{II}\), give each edge the weight \(\ell - \mathit{II} \cdot d\) and look for a positive cycle (Floyd–Warshall with max-plus on these small graphs); increase \(\mathit{II}\) from 1. HeightR is the longest path to a virtual stop node with the same weights (Bellman–Ford). In IMS, remember each instruction's previous slot so a forced placement moves forward, and make eviction explicit: remove the victim's reservations from the MRT and mark it unscheduled.

Hint 4 — code generation

Write the preheader, groups and exit for one value first: d and e of the running loop form the recurrence, and the lesson's example lists every register. For a value defined by \(d\) in stage \(s_d\) and read by \(u\) with distance \(\delta\), the reader runs \(\delta + s_u - s_d\) groups after the writer, so it reads the logical name \(b + \delta + s_u - s_d\). Reserve a window per value large enough for its longest-living instance (the write can land one group later than it issues), and pad values with a distance-1 use so the preheader's copy has a name of its own. Use ch23-check on a single loop while debugging: its messages name the group and the instruction.

12. Stretch goals¶

★ Swing modulo scheduling (Algorithm 23.6.10) as a seventh algorithm: compare the total register requirement (sum of window sizes) with IMS on the same II.
★ Modulo variable expansion instead of rotating registers: unroll the kernel \(u = \max_v \lceil \mathrm{lifetime}(v) / \mathit{II} \rceil\) times; handle a trip count that is not a multiple of \(u\).
★ Balanced scheduling: replace the fixed load latency by Kerns–Eggers weights and compare lengths when the simulator's load latency varies.
★ Optimal block scheduling for small blocks by branch and bound or an ILP, to measure how far each list algorithm is from the optimum instead of the lower bound.