Out-of-order execution: Difference between revisions

Revision as of 14:15, 11 July 2025

Revision as of 12:27, 19 July 2025

Line 9:

=== Early use in supercomputers ===

Arguably the first machine to use out-of-order execution is the [[CDC 6600]] (1964), which used a [[Scoreboarding|scoreboard]] to resolve conflicts. The 6600 however lacked [[Hazard_(computer_architecture)#Write_after_write_(WAW)|WAW conflict]] handling, choosing instead to stall. This situation was termed a "First Order Conflict" by Thornton.<ref>{{harvtxt|Thornton|1970|p=125}}</ref>. Whilst it had both [[RAW conflict]] resolution (termed "Second Order Conflict"<ref>{{harvtxt|Thornton|1970|p=126}}</ref>) and [[Hazard_(computer_architecture)#Write_after_read_(WAR)|WAR conflict]] resolution (termed "Third Order Conflict"<ref>{{harvnb|Thornton|1970|p=127}}</ref>) all of which is sufficient to declare it capable of full out-of-order execution, the 6600 did not have precise exception handling. An early and limited form of Branch prediction was possible as long as the branch was to locations on what was termed the "Instruction Stack" which was limited to within a depth of seven words from the Program Counter.<ref>{{harvnb|Thornton|1970|p=112,123}}</ref>

About two years later, the [[IBM System/360 Model 91]] (1966) introduced [[register renaming]] with [[Tomasulo's algorithm]],<ref>{{citation |title=An Efficient Algorithm for Exploiting Multiple Arithmetic Units |journal=[[IBM Journal of Research and Development]] |volume=11 |issue=1 |pages=25–33 |date=1967 |author-first=Robert Marco |author-last=Tomasulo |author-link=Robert Marco Tomasulo |doi=10.1147/rd.111.0025 |url=https://pdfs.semanticscholar.org/8299/94a1340e5ecdb7fb24dad2332ccf8de0bb8b.pdf |archive-url=https://web.archive.org/web/20180612141530/https://pdfs.semanticscholar.org/8299/94a1340e5ecdb7fb24dad2332ccf8de0bb8b.pdf |url-status=dead |archive-date=2018-06-12 |citeseerx=10.1.1.639.7540|s2cid=8445049 }}</ref> which dissolves false dependencies (WAW and WAR), making full out-of-order execution possible. An instruction addressing a write into a register ''r_n'' can be executed before an earlier instruction using the register ''r_n'' is executed, by actually writing into an alternative (renamed) register ''alt-r_n'', which is turned into a normal register ''r_n'' only when all the earlier instructions addressing ''r_n'' have been executed, but until then ''r_n'' is given for earlier instructions and ''alt-r_n'' for later ones addressing ''r_n''.