Tomasulo's algorithm

<h2 id="implementation-concepts">Implementation concepts</h2>

<p>The following are the concepts necessary to the implementation of Tomasulo's algorithm:
</p>
<h3>Common data bus</h3>
<p>The Common Data Bus (CDB) connects reservation stations directly to functional units. According to Tomasulo it "preserves precedence while encouraging concurrency".<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a>: 33  This has two important effects:
</p>
<ol><li>Functional units can access the result of any operation without involving a floating-point-register, allowing multiple units waiting on a result to proceed without waiting to resolve contention for access to register file read ports.</li>
<li>Hazard Detection and control execution are distributed. The reservation stations control when an instruction can execute, rather than a single dedicated hazard unit.</li></ol>
<h3>Instruction order</h3>

<p>Instructions are issued sequentially so that the effects of a sequence of instructions, such as <a href="/facts/Exception_(computing)/VrJxgb9r">exceptions</a> raised by these instructions, occur in the same order as they would on an in-order processor, regardless of the fact that they are being executed out-of-order (i.e. non-sequentially).
</p>
<h3>Register renaming</h3>
<p>Tomasulo's algorithm uses <a href="/facts/Register_renaming/m1HXzC5x">register renaming</a> to correctly perform out-of-order execution. All general-purpose and reservation station registers hold either a real value or a placeholder value. If a real value is unavailable to a destination register during the issue stage, a placeholder value is initially used. The placeholder value is a tag indicating which reservation station will produce the real value. When the unit finishes and broadcasts the result on the CDB, the placeholder will be replaced with the real value.
</p><p>Each functional unit has a single reservation station. Reservation stations hold information needed to execute a single instruction, including the operation and the operands. The functional unit begins processing when it is free and when all source operands needed for an instruction are real.
</p>
<h3>Exceptions</h3>
<p>Practically speaking, there may be exceptions for which not enough status information about an exception is available, in which case the processor may raise a special exception, called an imprecise exception. Imprecise exceptions cannot occur in <a href="/facts/Out-of-order_execution/bM0dQM8m">in-order</a> implementations, as processor state is changed only in program order (see <a href="/facts/Classic_RISC_pipeline/67UhbP04">Classic RISC pipeline § Exceptions</a>).
</p><p>Programs that experience precise exceptions, where the specific instruction that took the exception can be determined, can restart or re-execute at the point of the exception. However, those that experience imprecise exceptions generally cannot restart or re-execute, as the system cannot determine the specific instruction that took the exception.
</p>
<h2 id="instruction-lifecycle">Instruction lifecycle</h2>
<p>The three stages listed below are the stages through which each instruction passes from the time it is issued to the time its execution is complete.
</p>
<h3>Legend</h3>
<ul><li>RS - Reservation Status</li>
<li>RegisterStat - Register Status; contains information about the registers.</li>
<li>regs[x] - Value of register x</li>
<li>Mem[A] - Value of memory at address A</li></ul>
<ul><li>rd - destination register number</li>
<li>rs, rt - source registration numbers</li>
<li>imm - sign extended immediate field</li>
<li>r - reservation station or buffer that the instruction is assigned to</li></ul>
<h4>Reservation Station Fields</h4>
<ul><li>Op - represents the operation being performed on operands</li>
<li>Qj, Qk - the reservation station that will produce the relevant source operand (0 indicates the value is in Vj, Vk)</li>
<li>Vj, Vk - the value of the source operands</li>
<li>A - used to hold the memory address information for a load or store</li>
<li>Busy - 1 if occupied, 0 if not occupied</li></ul>
<h4>Register Status Fields</h4>
<ul><li>Qi - the reservation station whose result should be stored in this register (if blank or 0, no values are destined for this register)</li></ul>
<h3>Stage 1: issue</h3>
<p>In the issue stage, instructions are issued for execution if all operands and reservation stations are ready or else they are stalled. Registers are renamed in this step, eliminating WAR and WAW hazards.
</p>
<ul><li>Retrieve the next instruction from the head of the instruction queue. If the instruction operands are currently in the registers, then
<ul><li>If a matching functional unit is available, issue the instruction.</li>
<li>Else, as there is no available functional unit, stall the instruction until a station or buffer is free.</li></ul></li>
<li>Otherwise, we can assume the operands are not in the registers, and so use virtual values. The functional unit must calculate the real value to keep track of the functional units that produce the operand.</li></ul>
Pseudocode<a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a>: 180 <table><tbody><tr><th>Instruction state</th><th>Wait until</th><th>Action or bookkeeping</th></tr><tr><td>FP operation</td><td>Station r empty</td><td>if (RegisterStat[rs].Qi¦0) {	RS[r].Qj ← RegisterStat[rs].Qi}else {	RS[r].Vj ← Regs[rs];	RS[r].Qj ← 0;}if (RegisterStat[rt].Qi¦0) { 	RS[r].Qk ← RegisterStat[rt].Qi;}else {	RS[r].Vk ← Regs[rt]; 	RS[r].Qk ← 0;}RS[r].Busy ← yes;RegisterStat[rd].Qi ← r;</td></tr><tr><td>Load or Store</td><td>Buffer r empty</td><td>if (RegisterStat[rs].Qi¦0) {	RS[r].Qj ← RegisterStat[rs].Qi;}else {	RS[r].Vj ← Regs[rs];	RS[r].Qj ← 0;}RS[r].A ← imm;RS[r].Busy ← yes;</td></tr><tr><td>Load only</td><td></td><td>RegisterStat[rt].Qi ← r;</td></tr><tr><td>Store only</td><td></td><td>if (RegisterStat[rt].Qi¦0) {	RS[r].Qk ← RegisterStat[rt].Qi;}else {	RS[r].Vk ← Regs[rt];	RS[r].Qk ← 0};</td></tr></tbody></table>

<h3>Stage 2: execute</h3>
<p>In the execute stage, the instruction operations are carried out. Instructions are delayed in this step until all of their operands are available, eliminating RAW hazards. Program correctness is maintained through effective address calculation to prevent hazards through memory.
</p>
<ul><li>If one or more of the operands is not yet available then: wait for operand to become available on the CDB.</li>
<li>When all operands are available, then: if the instruction is a load or store
<ul><li>Compute the effective address when the base register is available, and place it in the load/store buffer
<ul><li>If the instruction is a load then: execute as soon as the memory unit is available</li>
<li>Else, if the instruction is a store then: wait for the value to be stored before sending it to the memory unit</li></ul></li></ul></li>
<li>Else, the instruction is an <a href="/facts/Arithmetic_logic_unit/SgIjPzSc">arithmetic logic unit</a> (ALU) operation then: execute the instruction at the corresponding functional unit</li></ul>
Pseudocode<a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a> : 180 <table><tbody><tr><th>Instruction state</th><th>Wait until</th><th>Action or bookkeeping</th></tr><tr><td>FP operation</td><td>(RS[r].Qj = 0) and (RS[r].Qk = 0)</td><td><p>Compute result: operands are in Vj and Vk</p></td></tr><tr><td>Load/store step 1</td><td>RS[r].Qj = 0 & r is head of load-store queue</td><td>RS[r].A ← RS[r].Vj + RS[r].A;</td></tr><tr><td>Load step 2</td><td>Load step 1 complete</td><td><p>Read from Mem[RS[r].A]</p></td></tr></tbody></table>
<h3>Stage 3: write result</h3>
<p>In the write Result stage, ALU operations results are written back to registers and store operations are written back to memory.
</p>
<ul><li>If the instruction was an ALU operation
<ul><li>If the result is available, then: write it on the CDB and from there into the registers and any reservation stations waiting for this result</li></ul></li>
<li>Else, if the instruction was a store then: write the data to memory during this step</li></ul>
Pseudocode<a class="footnote-ref" id="fnref:6" href="#fn:6"><sup>6</sup></a> : 180 <table><tbody><tr><th>Instruction state</th><th>Wait until</th><th>Action or bookkeeping</th></tr><tr><td>FP operation or load</td><td>Execution complete at r & CDB available</td><td>	∀x(if (RegisterStat[x].Qi = r) {		regs[x] ← result;		RegisterStat[x].Qi = 0	});	∀x(if (RS[x].Qj = r) {		RS[x].Vj ← result;		RS[x].Qj ← 0; 	});	∀x(if (RS[x].Qk = r) {		RS[x].Vk ← result;		RS[x].Qk ← 0;	});	RS[r].Busy ← no;</td></tr><tr><td>Store</td><td>Execution complete at r & RS[r].Qk = 0</td><td>	Mem[RS[r].A] ← RS[r].Vk;	RS[r].Busy ← no;</td></tr></tbody></table>
<h2 id="algorithm-improvements">Algorithm improvements</h2>
<p>The concepts of reservation stations, register renaming, and the common data bus in Tomasulo's algorithm presents significant advancements in the design of high-performance computers.
</p><p>Reservation stations take on the responsibility of waiting for operands in the presence of data dependencies and other inconsistencies such as varying storage access time and circuit speeds, thus freeing up the functional units. This improvement overcomes long floating point delays and memory accesses. In particular the algorithm is more tolerant of cache misses. Additionally, programmers are freed from implementing optimized code. This is a result of the common data bus and reservation station working together to preserve dependencies as well as encouraging concurrency.<a class="footnote-ref" id="fnref:7" href="#fn:7"><sup>7</sup></a>: 33 
</p><p>By tracking operands for instructions in the reservation stations and register renaming in hardware the algorithm minimizes <a href="/facts/Read_after_write_(Hazard)/hXItYfk1">read-after-write</a> (RAW) and eliminates <a href="/facts/Write_after_write_(hazard)/hXItYfk1">write-after-write</a> (WAW) and <a href="/facts/Write_after_read_(hazard)/hXItYfk1">Write-after-Read</a> (WAR) <a href="/facts/Computer_architecture/tHtwxgR2">computer architecture</a> <a href="/facts/Hazard_(computer_architecture)/hXItYfk1">hazards</a>. This improves performance by reducing wasted time that would otherwise be required for stalls.<a class="footnote-ref" id="fnref:8" href="#fn:8"><sup>8</sup></a>: 33 
</p><p>An equally important improvement in the algorithm is the design is not limited to a specific pipeline structure. This improvement allows the algorithm to be more widely adopted by <a href="/facts/Multiple_issue/gPxRAb25">multiple-issue</a> processors. Additionally, the algorithm is easily extended to enable branch speculation.<a class="footnote-ref" id="fnref:9" href="#fn:9"><sup>9</sup></a> : 182 
</p>
<h2 id="applications-and-legacy">Applications and legacy</h2>
<p>Tomasulo's algorithm was implemented in the System/360 Model 91 architecture. Outside of IBM, it went unused for several years. However, it saw a vast increase in usage during the 1990s for 3 reasons:
</p>
<ol><li>Once caches became commonplace, the algorithm's ability to maintain concurrency during unpredictable load times caused by cache misses became valuable in processors.</li>
<li>Dynamic scheduling and branch speculation from the algorithm enables improved performance as processors issued more and more instructions.</li>
<li>Proliferation of mass-market software meant that programmers would not want to compile for a specific pipeline structure. The algorithm can function with any pipeline architecture and thus software requires few architecture-specific modifications.<a class="footnote-ref" id="fnref:10" href="#fn:10"><sup>10</sup></a> : 183 </li></ol>
<p>Many modern processors implement dynamic scheduling schemes that are variants of Tomasulo's original algorithm, including popular <a href="/facts/Intel/SMF0gJJX">Intel</a> <a href="/facts/X86-64/cyWvUFlP">x86-64</a> chips.<a class="footnote-ref" id="fnref:11" href="#fn:11"><sup>11</sup></a><a class="footnote-ref" id="fnref:12" href="#fn:12"><sup>12</sup></a>
</p>
<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Re-order_buffer/w0nDvHt8">Re-order buffer</a> (ROB)</li>
<li><a href="/facts/Instruction-level_parallelism/2W8qvN8K">Instruction-level parallelism</a> (ILP)</li></ul>

<h2 id="further-reading">Further reading</h2>
<ul><li>Savard, John J. G. (2018) [2014]. <a href="http://www.quadibloc.com/comp/cp07.htm">"Pipelined and Out-of-Order Execution"</a>. <i>quadibloc</i>. <a href="https://web.archive.org/web/20180703004239/http://www.quadibloc.com/comp/cp07.htm">Archived</a> from the original on 2018-07-03. Retrieved 2018-07-16.</li></ul>
<h2 id="external-links">External links</h2>
<ul><li><a href="https://web.archive.org/web/20171225215322/http://www.cs.umd.edu/class/fall2001/cmsc411/projects/dynamic/tomasulo.html">Dynamic Scheduling - Tomasulo's Algorithm</a> at the <a href="/facts/Wayback_Machine/nmQ3a6JC">Wayback Machine</a> (archived December 25, 2017)</li>
<li><a href="http://www.dcs.ed.ac.uk/home/hase/webhase/demo/tomasulo.html">HASE Java applet simulation of the Tomasulo's algorithm</a></li></ul>

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

<ol>
<li id="fn:1"><p>Tomasulo, Robert Marco (Jan 1967). "An Efficient Algorithm for Exploiting Multiple Arithmetic Units". IBM Journal of Research and Development. 11 (1). IBM: 25–33. doi:10.1147/rd.111.0025. ISSN 0018-8646. S2CID 8445049. <a href="/wiki/Robert_Marco_Tomasulo" target="_blank">/wiki/Robert_Marco_Tomasulo</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>"Robert Tomasulo – Award Winner". ACM Awards. ACM. Retrieved 8 December 2014. <a href="http://awards.acm.org/award_winners/tomasulo_4008463.cfm" target="_blank">http://awards.acm.org/award_winners/tomasulo_4008463.cfm</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
<li id="fn:3"><p>Tomasulo, Robert Marco (Jan 1967). "An Efficient Algorithm for Exploiting Multiple Arithmetic Units". IBM Journal of Research and Development. 11 (1). IBM: 25–33. doi:10.1147/rd.111.0025. ISSN 0018-8646. S2CID 8445049. <a href="/wiki/Robert_Marco_Tomasulo" target="_blank">/wiki/Robert_Marco_Tomasulo</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li>
<li id="fn:4"><p>Hennessy, John L.; Patterson, David A. (2012). Computer Architecture: A Quantitative Approach. Waltham, MA: Elsevier. ISBN 978-0123838728. <a href="978-0123838728" target="_blank">978-0123838728</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li>
<li id="fn:5"><p>Hennessy, John L.; Patterson, David A. (2012). Computer Architecture: A Quantitative Approach. Waltham, MA: Elsevier. ISBN 978-0123838728. <a href="978-0123838728" target="_blank">978-0123838728</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li>
<li id="fn:6"><p>Hennessy, John L.; Patterson, David A. (2012). Computer Architecture: A Quantitative Approach. Waltham, MA: Elsevier. ISBN 978-0123838728. <a href="978-0123838728" target="_blank">978-0123838728</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li>
<li id="fn:7"><p>Tomasulo, Robert Marco (Jan 1967). "An Efficient Algorithm for Exploiting Multiple Arithmetic Units". IBM Journal of Research and Development. 11 (1). IBM: 25–33. doi:10.1147/rd.111.0025. ISSN 0018-8646. S2CID 8445049. <a href="/wiki/Robert_Marco_Tomasulo" target="_blank">/wiki/Robert_Marco_Tomasulo</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></p></li>
<li id="fn:8"><p>Tomasulo, Robert Marco (Jan 1967). "An Efficient Algorithm for Exploiting Multiple Arithmetic Units". IBM Journal of Research and Development. 11 (1). IBM: 25–33. doi:10.1147/rd.111.0025. ISSN 0018-8646. S2CID 8445049. <a href="/wiki/Robert_Marco_Tomasulo" target="_blank">/wiki/Robert_Marco_Tomasulo</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></p></li>
<li id="fn:9"><p>Hennessy, John L.; Patterson, David A. (2012). Computer Architecture: A Quantitative Approach. Waltham, MA: Elsevier. ISBN 978-0123838728. <a href="978-0123838728" target="_blank">978-0123838728</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></p></li>
<li id="fn:10"><p>Hennessy, John L.; Patterson, David A. (2012). Computer Architecture: A Quantitative Approach. Waltham, MA: Elsevier. ISBN 978-0123838728. <a href="978-0123838728" target="_blank">978-0123838728</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></p></li>
<li id="fn:11"><p>Intel 64 and IA-32 Architectures Software Developer's Manual (Report). Intel. September 2014. Retrieved 8 December 2014. <a href="http://www.intel.com/content/www/us/en/architecture-and-technology/64-ia-32-architectures-software-developer-vol-1-manual.html" target="_blank">http://www.intel.com/content/www/us/en/architecture-and-technology/64-ia-32-architectures-software-developer-vol-1-manual.html</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></p></li>
<li id="fn:12"><p>Yoga, Adarsh. "Differences between Tomasulo's algorithm and dynamic scheduling in Intel Core microarchitecture". The boozier. Retrieved 4 April 2016. <a href="http://adusan.blogspot.com.au/2010/11/differences-between-tomasulos-algorithm.html" target="_blank">http://adusan.blogspot.com.au/2010/11/differences-between-tomasulos-algorithm.html</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></p></li>
</ol>

Tomasulo's algorithm open-in-new

Tomasulo's algorithm