Scoreboarding

<h2 id="stages">Stages</h2>
Instructions are decoded in order and go through the following four stages.

<ol><li>Issue: The system checks which registers will be read and written by this instruction and where conflicts <a href="/facts/Write_after_read/hXItYfk1">write after read</a> (WAR) and <a href="/facts/Read_after_write_(Hazard)/hXItYfk1">read after write</a> (RAW) and <a href="/facts/Write_after_write_(hazard)/hXItYfk1">write after write</a> (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 <a href="/facts/Directed_Acyclic_Graph/k6zq1os9">Directed Acyclic Graph</a>. 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.</li>
<li>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).</li>
<li>Execution: When all operands have been fetched, the Computation Unit starts its execution. After the result is ready, the scoreboard is notified.</li>
<li>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.</li></ol>
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.

<h2 id="data-structure">Data structure</h2>
To control the execution of the instructions, the scoreboard maintains three status tables:

<ul><li>Instruction Status: Indicates, for each instruction being executed, which of the four stages it is in.</li>
<li>Functional Unit Status: Indicates the state of each functional unit. Each function unit maintains 9 fields in the table:
<ul><li>Busy: Indicates whether the unit is being used or not</li>
<li>Op: Operation to perform in the unit (e.g. MUL, DIV or MOD)</li>
<li>Fi: Destination register</li>
<li>Fj,Fk: Source-register numbers</li>
<li>Qj,Qk: Functional units that will produce the source registers Fj, Fk</li>
<li>Rj,Rk: Flags that indicates when Fj, Fk are ready for and are not yet read.</li></ul></li>
<li>Register Status: Indicates, for each register, which function unit will write results into it.</li></ul>
<h2 id="the-original-6600-algorithm">The original 6600 algorithm</h2>
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;

<h2 id="remarks">Remarks</h2>
Thornton's book pre-dates modern computing terminology.

<ul><li>Function Units (pipelines) were called "Computation Units".</li>
<li>"First Order Conflict" covered both stall due to all Units being busy and also covered <a href="/facts/Hazard_(computer_architecture)/hXItYfk1">WAW conflict</a>.<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a></li>
<li>"Second Order Conflict" was the term used for <a href="/facts/RAW_conflict/hXItYfk1">RAW conflict</a>.<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a></li>
<li>"Third Order Conflict" covered <a href="/facts/Hazard_(computer_architecture)/hXItYfk1">WAR conflict</a>.<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a></li></ul>
Stalling only occurred at the issue stage, when "First Order" conflicts were detected. Some other techniques like <a href="/facts/Tomasulo%2527s_algorithm/Ro81atJm">Tomasulo's algorithm</a> additionally resolve WAW dependencies with <a href="/facts/Register_renaming/m1HXzC5x">register renaming</a>. The original <a href="/facts/CDC_6600/QpnT1Ltl">CDC 6600</a> 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.<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a> WAW hazards resolution is indeed missing from the original algorithm: the 6600 would stall at the first occurrence of a Write Hazard.<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a>

<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Instruction_level_parallelism/2W8qvN8K">Instruction level parallelism</a></li>
<li><a href="/facts/Tomasulo_algorithm/Ro81atJm">Tomasulo algorithm</a></li>
<li><a href="/facts/Out-of-order_execution/bM0dQM8m">Out-of-order execution</a></li></ul>

<ul><li><a href="/facts/Glenford_Myers/zqFKgFhl">Glenford Myers</a>, "Register scoreboarding on a microprocessor chip", United States Patent 4891753</li></ul>
<h2 id="external-links">External links</h2>
<ul><li><a href="https://www.cs.umd.edu/~meesh/cmsc411/website/projects/dynamic/scoreboard.html">Dynamic Scheduling - Scoreboard</a></li>
<li>Computer Architecture: A Quantitative Approach, John L. Hennessy & David A. Patterson</li>
<li><a href="http://www.eecs.berkeley.edu/~culler/courses/cs252-s05/lectures/cs252s05-lec06-scoreboard.ppt">EECS 252 Graduate Computer Architecture Lec XX - TOPIC</a>, Electrical Engineering and Computer Sciences, Berkeley, University of California.</li>
<li><a href="https://notsospecific.com/scoreboarding-example-advanced-computer-architecture/">Scoreboarding example</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Thornton, James E. (1965). "Parallel operation in the control data 6600". Proceedings of the October 27–29, 1964, fall joint computer conference, part II: very high speed computer systems. AFIPS '64. San Francisco, California: ACM. pp. 33–40. doi:10.1145/1464039.1464045. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Thornton (1970, p. 125) - Thornton, James (1970). Design of a Computer: The Control Data 6600 (PDF). p. 126. ISBN 9780673059536. <a href="https://archive.computerhistory.org/resources/text/CDC/cdc.6600.thornton.design_of_a_computer_the_control_data_6600.1970.102630394.pdf" target="_blank">https://archive.computerhistory.org/resources/text/CDC/cdc.6600.thornton.design_of_a_computer_the_control_data_6600.1970.102630394.pdf</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Thornton (1970, p. 126) - Thornton, James (1970). Design of a Computer: The Control Data 6600 (PDF). p. 126. ISBN 9780673059536. <a href="https://archive.computerhistory.org/resources/text/CDC/cdc.6600.thornton.design_of_a_computer_the_control_data_6600.1970.102630394.pdf" target="_blank">https://archive.computerhistory.org/resources/text/CDC/cdc.6600.thornton.design_of_a_computer_the_control_data_6600.1970.102630394.pdf</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Thornton 1970, p. 127 - Thornton, James (1970). Design of a Computer: The Control Data 6600 (PDF). p. 126. ISBN 9780673059536. <a href="https://archive.computerhistory.org/resources/text/CDC/cdc.6600.thornton.design_of_a_computer_the_control_data_6600.1970.102630394.pdf" target="_blank">https://archive.computerhistory.org/resources/text/CDC/cdc.6600.thornton.design_of_a_computer_the_control_data_6600.1970.102630394.pdf</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Transforming Tomasulo to Scoreboards <a href="https://libre-soc.org/3d_gpu/architecture/tomasulo_transformation/" target="_blank">https://libre-soc.org/3d_gpu/architecture/tomasulo_transformation/</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Thornton, James (1970). Design of a Computer: The Control Data 6600 (PDF). p. 126. ISBN 9780673059536. <a href="9780673059536" target="_blank">9780673059536</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
</ol>

Scoreboarding open-in-new

Scoreboarding