Scoreboarding Explained

Scoreboarding is a centralized method, first used in the CDC 6600 computer, for dynamically scheduling instructions so that they can execute out of order when there are no conflicts and the hardware is available.^[1]

In a scoreboard, the data dependencies of every instruction are logged, tracked and strictly observed at all times. Instructions are released only when the scoreboard determines that there are no conflicts with previously issued ("in flight") instructions. If an instruction is stalled because it is unsafe to issue (or there are insufficient resources), the scoreboard monitors the flow of executing instructions until all dependencies have been resolved before the stalled instruction is issued. In essence: reads proceed on the absence of write hazards, and writes proceed in the absence of read hazards.

Scoreboarding is essentially a hardware implementation of the same underlying algorithm seen in dataflow languages, creating a Directed Acyclic Graph, where the same logic is applied in the programming language runtime.

Stages

Instructions are decoded in order and go through the following four stages.

1. Issue: The system checks which registers will be read and written by this instruction and where conflicts write after read (WAR) and read after write (RAW) and write after write (WAW) are detected. RAW and WAR hazards are recorded using a Dependency Matrix (constructed from SR NOR latches in the original 6600 design) as it will be needed in the following stages. Simultaneously, an entry is recorded in a second Matrix, which records the instruction order as a Directed Acyclic Graph. In order to avoid output dependencies (WAW) the instruction is stalled until instructions intending to write to the same register are completed. The instruction is also stalled when required functional units are currently busy. No instruction is ever issued unless it is fully trackable from start to finish.
2. Read operands: After an instruction has been issued and correctly allocated to the required hardware module (named a Computation Unit in Thornton's book), the Unit waits until all operands become available. The read only proceeds when write dependencies (RAW) have been dropped from all other Units. To avoid Register File Port contention, a Priority Picker selects one Computational Unit (in the case where several Units are clear of hazards).
3. Execution: When all operands have been fetched, the Computation Unit starts its execution. After the result is ready, the scoreboard is notified.
4. Write Result: In this stage the result is ready but has not yet been written to its destination register. The write may not proceed until the Unit is clear of all WAR hazards. The only additional delays here are based on availability of register file ports: in the 6600 a Priority Picker was used to select one result per write port. Once written the unit is marked as no longer busy, and all hazards and state is dropped. Note that only in advanced (augmented, precise) scoreboards with "Shadow" capability will the Write Result phase be prevented (delayed). The original 6600 did not have this capability.

It is critical to note above that Reads only proceed in the absence of write hazards, and that writes proceed in the absence of Read hazards. This is logical but contrary to expectations. In particular, note that Writes must wait to write after read in order to give other units the opportunity to read the current value in a register, before overwriting it with the new one. Hence why writes must wait until the absence of WAR hazards.

Data structure

To control the execution of the instructions, the scoreboard maintains three status tables:

• Instruction Status: Indicates, for each instruction being executed, which of the four stages it is in.
• Functional Unit Status: Indicates the state of each functional unit. Each function unit maintains 9 fields in the table:
  • Busy: Indicates whether the unit is being used or not
  • Op: Operation to perform in the unit (e.g. MUL, DIV or MOD)
  • F_i: Destination register
  • F_j,F_k: Source-register numbers
  • Q_j,Q_k: Functional units that will produce the source registers F_j, F_k
  • R_j,R_k: Flags that indicates when F_j, F_k are ready for and are not yet read.
• Register Status: Indicates, for each register, which function unit will write results into it.

The original 6600 algorithm

The detailed algorithm for the scoreboard control, outlined in the original patent, is described below:

function issue(op, dst, src1, src2) wait until (!Busy[FU] AND !Result[''dst'']); // FU can be any functional unit that can execute operation op Busy[FU] ← Yes; Op[FU] ← op; F_i[FU] ← dst; F_j[FU] ← src1; F_k[FU] ← src2; Q_j[FU] ← Result[''src1'']; Q_k[FU] ← Result[''src2'']; R_j[FU] ← Q_j[FU]

0; R_k[FU] ← Q_k[FU]

0; Result[''dst''] ← FU;

function read_operands(FU) wait until (R_j[''FU''] AND R_k[''FU'']); R_j[''FU''] ← No; R_k[''FU''] ← No;

function execute(FU) // Execute whatever FU must do

function write_back(FU) wait until (∀f) foreach f do if Q_j[f]=FU then R_j[f] ← Yes; if Q_k[f]=FU then R_k[f] ← Yes; Result[F_i[''FU'']] ← 0; // 0 means no FU generates the register's result RegFile[F_i[''FU'']] ← computed value; Busy[''FU''] ← No;

Remarks

Thornton's book pre-dates modern computing terminology.

• Function Units (pipelines) were called "Computation Units".
• "First Order Conflict" covered both stall due to all Units being busy and also covered WAW conflict.
• "Second Order Conflict" was the term used for RAW conflict.
• "Third Order Conflict" covered WAR conflict.

Stalling only occurred at the issue stage, when "First Order" conflicts were detected. Some other techniques like Tomasulo's algorithm additionally resolve WAW dependencies with register renaming. The original CDC 6600 likely did not have WAW hazard tracking simply because its designers had to deliver product, and then moved on to the 7600: stalling instead was the most expedient option. There is no technical reason why Register renaming should not be added to Scoreboards.

An analysis of both algorithms was carried out by Luke Leighton and a transformation process outlined which shows equivalence between the Tomasulo algorithm and the 6600 Scoreboard algorithm.^[2] WAW hazards resolution is indeed missing from the original algorithm: the 6600 would stall at the first occurrence of a Write Hazard.^[3]

See also

• Instruction level parallelism
• Tomasulo algorithm
• Out-of-order execution

References

• Glenford Myers, "Register scoreboarding on a microprocessor chip", United States Patent 4891753

External links

• Dynamic Scheduling - Scoreboard
• Computer Architecture: A Quantitative Approach, John L. Hennessy & David A. Patterson
• EECS 252 Graduate Computer Architecture Lec XX - TOPIC, Electrical Engineering and Computer Sciences, Berkeley, University of California.
• Scoreboarding example

Notes and References

1. Parallel operation in the control data 6600 . James E. . Thornton . 1965 . AFIPS '64 . Proceedings of the October 27–29, 1964, fall joint computer conference, part II: very high speed computer systems . ACM . San Francisco, California . 33–40 . 10.1145/1464039.1464045 . free .
2. https://libre-soc.org/3d_gpu/architecture/tomasulo_transformation/ Transforming Tomasulo to Scoreboards
3. Book: Thornton, James . Design of a Computer: The Control Data 6600 . 1970 . 9780673059536 . 126.