In this article, the topic of Scoreboarding will be explored in depth, with the aim of exhaustively analyzing its various facets and offering a complete vision of its importance and impact on today's society. Along these lines, both historical and cultural aspects will be addressed, as well as recent studies and findings related to Scoreboarding. Additionally, different perspectives and opinions from experts in the field will be examined in order to shed light on this ever-evolving topic. It is hoped that this article will not only provide valuable information, but also generate reflection and debate about Scoreboarding, in order to promote a deeper and richer understanding of this topic.
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.
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 contraindicative 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 AND !Result); // FU can be any functional unit that can execute operation op Busy ← Yes; Op ← op; Fi ← dst; Fj ← src1; Fk ← src2; Qj ← Result; Qk ← Result; Rj ← Qj == 0; Rk ← Qk == 0; Result ← FU;
function read_operands(FU) wait until (Rj AND Rk); Rj ← No; Rk ← No;
function execute(FU) // Execute whatever FU must do
function write_back(FU) wait until (∀f {(Fj≠Fi OR Rj=No) AND (Fk≠Fi OR Rk=No)}) foreach f do if Qj=FU then Rj ← Yes; if Qk=FU then Rk ← Yes; Result] ← 0; // 0 means no FU generates the register's result RegFile] ← computed value; Busy ← 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 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. WAW hazards resolution is indeed missing from the original algorithm: the 6600 would stall at the first occurrence of a Write Hazard.