Skip to content

Chapter 23 exercises

This chapter's implementation work is the comparison lab in labs/ch23-sched/: a list scheduler (top-down and bottom-up, two priorities, ★ register-pressure-aware) and an iterative modulo scheduler with prologue/kernel/epilogue generation for a toy VLIW machine. pebblec itself relies on LLVM's schedulers (Lesson 23.7), so there is no pebble/lib/ component this time. The SPEC is the full specification. The steps below are the order of attack, with the requirements and tests each step must pass. Run the tests after every step:

./course test 23                                        # builds, then runs every test labelled ch23
ctest --preset linux -L '^ch23$' -R 'ch23.List'         # one suite while iterating (macos preset on a Mac)
build/linux/bin/ch23-sched --algo=td-cp labs/ch23-sched/inputs/running.txt
build/linux/bin/ch23-check labs/ch23-sched/inputs/running.txt my-schedule.txt

Before you start, the lab tests fail with TODO(ch23): E1-E3: implement sched::scheduleBlock … or TODO(ch23): E4-E5: implement sched::scheduleLoop …. That's expected. Only the tests of the provided checker pass in the skeleton: ch23.Modulo.CheckerAgreesWithOracle and the lit file check-errors.test.

The contract is two functions in labs/ch23-sched/include/sched/Scheduler.h, sched::scheduleBlock and sched::scheduleLoop, stubbed in labs/ch23-sched/src/Stub.cpp. Your code goes anywhere under labs/ch23-sched/src/, and every .cpp there is compiled. The parser (sched/Program.h) and the checker/simulator (sched/Check.h) are provided. Design your own dependence graph, ready list and reservation-table types.

Stuck? Work through the hints in the SPEC (§11) in order. The reference solution is in solutions/labs/ch23-sched/src/. Only look at it after you've passed the tests, or after an honest hour.

E1: dependence DAG and top-down list scheduling

Contract: sched::scheduleBlock with Algo::TdCp and Algo::TdSucc Tests: ch23.List/td_cp.*, ch23.List/td_succ.*, tests/ch23/lit/list-running.test

Build the canonical dependence DAG of a block (SPEC §5.1; Lesson 23.2, Algorithm 23.2.6) and schedule it with cycle-driven top-down list scheduling (Lesson 23.3, Algorithm 23.3.2) under the two priority keys of SPEC R3. Print the §5.2 format.

Requirements: SPEC R1–R3 and R5. The schedule is valid, has length at least max(CP, RB), satisfies Graham's bound on the graham* machines, and matches the oracle's length on all 240 corpus blocks. Getting the tie-breaks and the "zero-latency successor in the same cycle" rule exactly right is part of the exercise.

What the tests check: the running example cycle by cycle (td-cp), the corpus lengths against tests/ch23/Inputs/goldens.txt, Graham's bound, determinism.

E2: bottom-up list scheduling

Contract: sched::scheduleBlock with Algo::BuCp and Algo::BuSucc Tests: ch23.List/bu_cp.*, ch23.List/bu_succ.*

Implement bottom-up list scheduling by reversal (Definition 23.3.5, Theorem 23.3.6, SPEC R4): reverse the edges with latencies \(\mathrm{lat}_j - \mathrm{lat}_i + \ell(i,j)\), mirror the reservation tables, run E1's scheduler and mirror the result back.

Requirements: SPEC R4 and R5. If your E1 code takes an abstract instance (latencies, tables, edges), this step is small. If it reads registers directly, refactor first.

What the tests check: the running example (length 11 for both priorities), the corpus goldens, Graham's bound.

E3 ★: register-pressure-aware list scheduling

Contract: sched::scheduleBlock with Algo::Pressure (and Options::Regs) Tests: ch23.Pressure.* (labels ch23 and star)

Schedule top-down while keeping MaxLive (SPEC §5.4, Definition 23.3.9) at most \(K\) (Algorithm 23.3.10, after Goodman and Hsu).

Requirements: SPEC R6. The schedule is valid with MaxLive ≤ K for the default K and for any K at or above the in-order MaxLive. Over the corpus it must be shorter in total than the in-order schedule and need no more registers than td-cp.

What the tests check: the limit on 240 blocks for two values of K, the running block (MaxLive ≤ 5, no longer than in-order), the corpus totals.

E4: MII and iterative modulo scheduling

Contract: sched::scheduleLoop (header and sigma lines first) Tests: ch23.Modulo.AchievesMII (the MII half), ch23.Modulo.HarderLoopsAreValid (validity)

Build the loop dependence graph with distances (SPEC §6.1, Definition 23.6.1), compute ResMII and RecMII (Algorithm 23.6.4) and find \(\sigma\) with iterative modulo scheduling (Algorithm 23.6.9, Rau's IMS).

Requirements: SPEC R7–R8. The stated MIIs equal the checker's, and \(\mathit{II} = \mathrm{MII}\) on the 120 achievable loops. Until E5 emits the code, the checker rejects the output at the group check, so write a small test of your own for \(\sigma\) (for example, check_modulo in tools/course/lib/sched.py on your printed schedule).

E5: prologue, kernel and epilogue with rotating registers

Contract: sched::scheduleLoop (the full §6.3 output) Tests: ch23.Modulo.*, tests/ch23/lit/modulo-running.test, ch23.lab.compare-smoke

Generate the code of Definition 23.6.11 and allocate rotating registers (Algorithm 23.6.12, SPEC §6.4) so that the simulator gets the sequential result for every trip count \(N \ge S\).

Requirements: SPEC R9–R10. Then run ch23-compare and fill in the measurement table of SPEC §10.

What the tests check: the running loop (II 4), 150 corpus loops simulated for four trip counts each, and the checker's structural rules (every instruction in the right groups, at offset \(\sigma \bmod \mathit{II}\), with memory offsets shifted by its stage).