Tomasulo's algorithm: Difference between revisions

Revision as of 23:58, 23 July 2022

Revision as of 00:08, 24 July 2022

Line 15:

[[File:Tomasulo Architecture.png|thumb|right|700px|Tomasulo's floating point unit]]

The following are the concepts necessary to the implementation of Tomasulo's Algorithmalgorithm:

===Common data bus===

Line 38:

===Register renaming===

Tomasulo's Algorithmalgorithm uses [[register renaming]] 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.

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.

Line 138:

|}

[[File:Example of Tomasulo's Algorithm.gif|thumb|Example of Tomasulo's Algorithmalgorithm<ref>{{cite web |url=http://courses.cs.washington.edu/courses/csep548/06au/lectures/tomasulo.pdf |title=CSE P548 - Tomasulo |date= 2006 |website=washington.edu |publisher=Washington University |access-date=8 December 2014}}</ref>]]

===Stage 2: execute===

Line 251:

== External links ==

* {{webarchive|url=https://web.archive.org/web/20171225215322/http://www.cs.umd.edu/class/fall2001/cmsc411/projects/dynamic/tomasulo.html|title=Dynamic Scheduling - Tomasulo's Algorithm|date=December 25, 2017}}

* [http://www.dcs.ed.ac.uk/home/hase/webhase/demo/tomasulo.html HASE Java applet simulation of the Tomasulo's Algorithmalgorithm]

[[Category:Algorithms]]