Loading AI tools
From Wikipedia, the free encyclopedia
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.
Instructions are decoded in order and go through the following four stages.
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.
To control the execution of the instructions, the scoreboard maintains three status tables:
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; Fi[FU] ← dst; Fj[FU] ← src1; Fk[FU] ← src2; Qj[FU] ← Result[src1]; Qk[FU] ← Result[src2]; Rj[FU] ← Qj[FU] == 0; Rk[FU] ← Qk[FU] == 0; Result[dst] ← FU;
function read_operands(FU) wait until (Rj[FU] AND Rk[FU]); Rj[FU] ← No; Rk[FU] ← No;
function execute(FU) // Execute whatever FU must do
function write_back(FU) wait until (∀f {(Fj[f]≠Fi[FU] OR Rj[f]=No) AND (Fk[f]≠Fi[FU] OR Rk[f]=No)}) foreach f do if Qj[f]=FU then Rj[f] ← Yes; if Qk[f]=FU then Rk[f] ← Yes; Result[Fi[FU]] ← 0; // 0 means no FU generates the register's result RegFile[Fi[FU]] ← computed value; Busy[FU] ← No;
Thornton's book pre-dates modern computing terminology.
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.[5] WAW hazards resolution is indeed missing from the original algorithm: the 6600 would stall at the first occurrence of a Write Hazard.[6]
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.