The chalkboard that beat the pipeline: the scoreboard

The machine and its six promises

Recall the in-order pipeline of lesson 7. Its ID stage decodes the instruction and reads its operands in the same cycle, so an instruction whose operand is not ready stalls in ID — and because the pipeline is a queue, every instruction behind it stalls too, however independent. Lesson 8 called the cure dynamic scheduling: let the hardware decide at run time which instruction may go next. The scoreboard is the first way of doing it.

The whole lesson runs on one fragment, written in the mnemonics of the exam papers (older papers write $F2 for F2; the 2026 paper drops the dollar sign, and so does this notebook). The latencies are the ones this exercise gives; an exam text always states its own.

I0: LD   F2, 0(R1)
I1: FMUL F4, F2, F0      ; RAW on F2 with I0
I2: FADD F6, F4, F8      ; RAW on F4 with I1
I3: LD   F8, 8(R1)       ; WAR on F8 with I2 (I2 reads F8)
I4: FMUL F8, F2, F0      ; WAW on F8 with I3
I5: SD   F6, 16(R1)      ; RAW on F6 with I2

Units and latencies: one Integer unit for loads, stores and integer operations (1 cycle, cache hits), one Add unit for FADD and FSUB (2 cycles), two multipliers Mult1 and Mult2 for FMUL (4 cycles), and a Divide unit that stays idle here. The fragment is deliberately nasty: I3 loads F8 and I4 overwrites it unread. A compiler would never write that, but exam fragments do, because it is the cleanest test of what a WAW hazard costs.

In the in-order pipeline, I2 would wait in ID for F4 until the multiply is done, and I3, a load that needs nothing from anybody, would wait behind it. The scoreboard's promise is that I3 goes past. To keep that promise safe, the model makes six assumptions (notes, page 103), each of them examinable.

The last point in one sentence: if a later instruction has already written the register file when an earlier one raises an exception, the state is not the one a sequential machine would have had — "imprecise interrupts" (page 104); the reorder buffer of lesson 17 is the later fix.

Page 104 of the notes sums the architecture up as three phases — issue in order, execution out of order, completion out of order — and its Figure 24, redrawn below, shows what makes them possible: a shared register file, the units, data buses between them, and the scoreboard at the bottom connected to everything by control and status lines only. The scoreboard moves no data. Operands still travel from the register file to the units and results back; the scoreboard only answers, for every instruction, three questions — may I read my operands, may I start, may I write my result.

The scoreboard moves no data: for every instruction it answers three questions — may I read, may I start, may I write — and it answers them from a table.

Split the decoder: four stages, four checks

The classic ID stage hides an assumption: that the operands are ready when the instruction is decoded. With a four-cycle multiply and a forty-cycle divide that is often false, so the scoreboard cuts ID in two. Issue decodes the instruction and asks about resources: is a unit of the right kind free (a structural hazard), and is nobody still due to write my destination (a WAW hazard)? If so, the instruction is handed to a unit and recorded in the tables; otherwise it waits, and because issue is in order, everything behind it waits too. Read Operands asks about values: are both of my sources written into the register file (a RAW hazard)? That question is asked separately for every instruction in flight, so a later instruction whose sources are ready reads them while an earlier one is still waiting. That is the whole trick; the picture shows it.

Walk the first five cycles of the fragment by hand; the stepper of the next section continues from there. Cycle 1: I0 issues on the Integer unit. Cycle 2: I0 reads R1; I1 issues on Mult1 — F2 is not written yet, so it will wait. Cycle 3: I0 accesses memory (its one execution cycle); I2 issues on the Add unit and will wait for F4. Cycle 4: I0 writes F2. I3 wants to issue and needs nothing from anybody — but it needs the Integer unit, and that unit is still Busy in the cycle in which I0 writes. I3 waits one cycle: structural hazard. Cycle 5: I3 issues; I1, which saw F2 arrive at the end of cycle 4, reads F2 and F0. Its four cycles of multiplying are 6 to 9, and the product is written at 10.

Two more stages follow. Execute runs the operation in the unit for its latency; a load spends its memory access here, cache miss included. Write Result asks the last question, about earlier readers: is an earlier instruction still waiting to read the register I am about to overwrite (a WAR hazard)? If so, the result stays inside the unit and the write is postponed; execution is finished and is not repeated. A register-file write port must also be free. The table restates pages 110–111 of the notes with the column names of the January 2026 paper.

Page 106 of the notes lists what the board must track to answer these questions: whether each source operand is available, whether each unit is busy, which writes to which registers are pending, and which instructions have finished and may write back. The notes' Figure 25 (page 109) draws the four stages as a map, with the scoreboard underneath consulted at every gate; Figure 3 redraws it with the three gate conditions written out.

Issue asks about the unit and the destination (structural, WAW); Read Operands asks about the sources (RAW); Write Result asks about earlier readers (WAR).

Three tables run the show

Everything the scoreboard knows fits in three tables (notes, page 113). The instruction status table records, for every instruction, which of the four stages it has completed — write cycle numbers into it and you have exactly the I / RR / E / WB table the exam asks for. The functional-unit status table has one row per unit and is where the decisions are made. The register result status table says, for every register, which unit will write it next, or nothing if no write is pending. Here are the fields of the unit row, with the moment each one is set and the moment it changes.

Two pairs of fields get confused. Qj says who, Rj says whether. Qj names the unit the operand will come from; Rj says whether the instruction may read the operand now. At issue they are set together: Rj is Yes exactly when Qj is blank. Take I1, FMUL F4, F2, F0, issued on Mult1 at cycle 2 — the notes' Example 6 (page 114) with our registers. Busy becomes Yes, Op = Mult, Fi = F4, Fj = F2, Fk = F0. The register result entry of F2 says "Integer" (I0 has not written it), so Qj = Integer and Rj = No; nobody is due to write F0, so Qk is blank and Rk = Yes. Finally the register result entry of F4 is set to Mult1: from now on a later reader of F4 copies "Mult1" into its own Qj, and a later writer of F4 is refused at issue.

The second confusion is the one the notes fall into. Rj and Rk do not mean "ready"; they mean ready and not yet read, and both flags go back to No when the instruction reads its operands. Why spend a flag on that? Because Write Result needs it. When I3 wants to write F8, the scoreboard looks for a row that has F8 as a source with its flag still Yes — an earlier instruction that has not yet taken the old value. At the end of cycle 8 the Add row reads Fk = F8, Rk = Yes: I2 is still waiting for F4 and has not read F8, so I3 waits. At cycle 11 I2 reads, Rk flips to No, and at cycle 12 I3 writes. Figure 4 is that before/after.

Qj says who will produce the operand, Rj says whether it may be read now — and Rj = No means either "not ready yet" or "already read".

The exact rules, and the four numbers of an exam row

Now the rules that connect stages and tables, as Hennessy and Patterson write them (Appendix C, Figure C.57; the notes do not print them, but every number of their 62-cycle example follows from them, and the stepper above is these four steps in a loop). Read \(FU\) as the unit assigned to the instruction, \(D\) as its destination, \(S_1, S_2\) as its sources, \(\mathrm{Result}[r]\) as the register result entry of \(r\), and \(f\) as any unit row.

1. Issue — wait until the unit is free and nobody is due to write the destination:

   \[ \neg\,\mathrm{Busy}[FU] \;\wedge\; \mathrm{Result}[D] = \varnothing . \]

   Then record the instruction: \(\mathrm{Busy} \leftarrow \text{Yes}\), \(\mathrm{Op}\), \(F_i \leftarrow D\), \(F_j \leftarrow S_1\), \(F_k \leftarrow S_2\), \(Q_j \leftarrow \mathrm{Result}[S_1]\), \(Q_k \leftarrow \mathrm{Result}[S_2]\), \(R_j \leftarrow (Q_j = \varnothing)\), \(R_k \leftarrow (Q_k = \varnothing)\), and \(\mathrm{Result}[D] \leftarrow FU\). Why here: the first test is the structural hazard, the second is WAW — and because issue is in order, the instruction being issued is always the later of the two writers, so one lookup settles it.

2. Read Operands — wait until both sources are ready and not yet read:

   \[ R_j = \text{Yes} \;\wedge\; R_k = \text{Yes} . \]

   Then read from the register file and set \(R_j \leftarrow \text{No}\), \(R_k \leftarrow \text{No}\), \(Q_j, Q_k \leftarrow \varnothing\), \(\mathrm{Time} \leftarrow L\). Why: with no forwarding a flag can become Yes only when the producer's write has landed in the register file, which is the RAW test; flipping it back to No records "already read" for the test of step 4.

3. Execute — wait until the unit is done. Time counts down from \(L\); the instruction completes in the cycle in which it reaches 0, i.e. \(E = RR + L\). No hazard is checked here.

4. Write Result — wait until no earlier instruction still has to read the destination, i.e. for every unit row \(f\):

   \[ F_j[f] \neq F_i \;\vee\; R_j[f] = \text{No} \] \[ F_k[f] \neq F_i \;\vee\; R_k[f] = \text{No} . \]

   Then write, and for every row with \(Q_j[f] = FU\) set \(R_j[f] \leftarrow \text{Yes}\) (same for \(Q_k\), \(R_k\)); set \(\mathrm{Result}[F_i] \leftarrow \varnothing\) and \(\mathrm{Busy}[FU] \leftarrow \text{No}\). Why: a row with my destination as a source and its flag still Yes is an earlier reader that has not taken the old value — the WAR test. The wake-up loop is how a waiting instruction learns that its value has arrived.

On paper you never run the loop: each row of the exam table is four maxima, one per wait, plus the convention that a stage takes at least one cycle. With \(L\) the latency of the unit:

The rules fill the whole fragment. Check two rows yourself. I2 waits for F4 from I1, which writes at 10:

I3 completes at 7, but I2 reads F8 only at 11:

The CPI of the fragment is the cycle of the last write result over the instruction count, as the formula sheet defines CPI: \(19 / 6 \approx 3.17\).

Now a second fragment, with a different trap in it, for the court. Same machine, same latencies.

I0: LD    F0, 0(R1)
I1: LD    F2, 8(R1)
I2: FMUL  F4, F0, F2
I3: FADD  F2, F0, F6
I4: SD    F4, 16(R1)
I5: ADDUI R1, R1, 8

Four maxima fill a row: unit free and destination unpromised, sources written, latency added, earlier readers done.

What the chalkboard cannot do

Back to the puzzle. The cell that holds I4 for seven cycles is the register result entry of F8: from cycle 5 to cycle 12 it says "Integer", because I3 has promised to write F8 and has not done so yet. I4 needs no value from I3; it needs the name F8, and the scoreboard has only one of each name. That is the cost of no register renaming: a WAW hazard is pure bookkeeping, and the basic scoreboard pays for it at Issue, where a stall also stops everything behind. Tomasulo's machine gives I4 a reservation station as a temporary name for its result, and the two writes to F8 never collide — lesson 11. The second half of the puzzle, the store finishing before the multiply, is out-of-order completion, and its price is the imprecise exception of section 1.

Hennessy and Patterson close with four factors that limit how much a scoreboard can gain; the notes do not list them, and the open question of the exam ("explain the main concepts and benefits of dynamic scheduling …") is the place to show you know them.

1. The parallelism available among the instructions. If every instruction depends on the previous one, there is nothing to overlap, however clever the controller.
2. The number of scoreboard entries — how far ahead of a stalled instruction the pipeline may look for independent ones: the instruction window, one entry per unit in the basic model.
3. The number and types of functional units — structural hazards. I3 lost a cycle to the single Integer unit; a second load unit would have removed it, as the January 2026 paper's two load/store units show.
4. Antidependences and output dependences — the WAR and WAW stalls, which exist only because there is no renaming.

Add what the notes stress on pages 111–112: no forwarding, so every RAW dependence costs one more cycle between the producer's write and the consumer's read; centralized control, simpler than Tomasulo's distributed stations but a limit on speculation and aggressive scheduling; and out-of-order completion without a reorder buffer, so exceptions are imprecise. The notes' 62-cycle example — lesson 10, which also switches the exam's two optimisations on and off — shows all of these at once, and its closing praise of "clean and scalable hardware coordination" (page 139) is better read backwards: the example shows the limits, and the next algorithm removes them.

The scoreboard overlaps independent instructions without a compiler and without renaming; what limits it are the parallelism in the window, the number of entries and units, and the WAR/WAW stalls that renaming would remove.