Dynamic Scheduling

Prev (Introduction) Next (Tomasulo)

Scoreboard

Introduced in the CDC 6600, the scoreboard is one method of implementing dynamic scheduling. Like any good dynamically scheduled machine, the scoreboard monitors each instruction waiting to be dispatched. Once it determines that all the source operands and the required functional units are available, it dispatches the instruction so that it can be executed. However, the scoreboard is limited in that it does not handle WAR and WAW hazards very well.

The scoreboard is a central location where information about the currently active instructions is kept. The scoreboard determines when and where an instruction begins and ends execution. In a scoreboard machine, instructions go through four main stages:

  1. Issue - In the issue stage, the scoreboard checks for an available functional unit as well as any potential WAW hazards. If it detects a WAW hazard or there are no functional units available for the instruction, the instruction stalls.
  2. Read operands - In this stage, the scoreboard checks for the availability of the source operands. If the source operands are available, the scoreboard instructs the functional unit to read the operands from the register file and begin executing, i.e. it resolves RAW hazards. An operand is considered available if no currently issued instruction is going to write to it, or if it is currently being written to the register file. This last idea is important, since it is the reason why WAW hazards cause stalls whereas (as we'll see) WAR hazards are allowed to propagate further down the pipeline. If there were more than one active instruction writing to the same register, there would be ambiguity about when an operand should be read from the register file (i.e. the scoreboard wouldn't know whether the operand should be read after the first or second write).
  3. Execution - The execution stage; nothing fancy here, except the functional unit notifies the scoreboard when it has finished execution.
  4. Write result - Once the scoreboard receives the notification that a functional unit has finished execution, it checks for any potential WAR hazards, i.e if an earlier instruction which is still in the read operands stage has the destination register as one of its source operands. If a WAR hazard is found, the scoreboard instructs the functional unit to stall until the hazard clears. In the meantime, the functional unit is unavailable to other instructions.
As an example of how scoreboarding works, consider the following code: 
Loop:	LD	F2,0(R1)
	ADDD	F6,F2,F4
	MULTD	F8,F6,F0
	SUBI	R1,R1,#8
	BNEZ	R1,Loop
However, we'll assume that the compiler was nice enough to unroll the loop for us without rescheduling the code (we'll see later how dynamic branch prediction and a reorder buffer allows the loop unrolling to be done by the hardware). Thus the code we'll examine looks like: 
Loop:	LD	F2,0(R1)
	ADDD	F6,F2,F4
	MULTD	F8,F6,F0
	LD	F10,-8(R1)
	ADDD	F12,F10,F4
	MULTD	F14,F12,F0
	SUBI	R1,R1,#16
	BNEZ	R1,Loop
Scoreboard example

Prev (Introduction) Next (Tomasulo)

Author: Allan Tong
Contact actong@wam.umd.edu