Out-of-order execution: Difference between revisions

Revision as of 13:34, 7 November 2023

Revision as of 23:00, 14 November 2023

Line 7:

=== Early use in supercomputers ===

The first machine to use out-of-order execution was the [[CDC 6600]] (1964), designed by [[James E. Thornton]], which uses a [[Scoreboarding|scoreboard]] to avoid conflicts. It permits an instruction to execute if its source operand (read) addressesregisters aren't to be written to by any unexecuted earlier instruction (true dependency) and the destination (write) addressregister not be ana addressregister used by any unexecuted earlier instruction (false dependency). The 6600 lacks the means to avoid stalling an [[execution unit]] on false dependencies ([[Hazard_(computer_architecture)#Write_after_write_(WAW)|write after write]] (WAW) and [[Hazard_(computer_architecture)#Write_after_read_(WAR)|write after read]] (WAR) conflicts, respectively termed ''first order conflict'' and ''third order conflict'' by Thornton, who termed true dependencies ([[Hazard_(computer_architecture)#Read_after_write_(RAW)|read after write]] (RAW)) as second order conflict) because each address has only a single ___location referable by it. The WAW is worse than WAR for the 6600, because when an execution unit encounters a WAR, the other execution units still receive and execute instructions, but upon a WAW the assignment of instructions to execution units stops, and they can not receive any further instructions until the WAW-causing instruction's destination register has been written to by earlier instruction.<ref>{{harvtxt|Thornton|1970|p=125-127}}</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 ("architectural") 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''. In the Model 91 the register renaming is implemented by a [[Operand forwarding|bypass]] termed ''Common Data Bus'' (CDB) and memory source operand buffers, leaving the physical architectural registers unused for many cycles as the oldest state of registers addressed by any unexecuted instruction is found on the CDB. Another advantage the Model 91 has over the 6600 is the ability to execute out-of-order the instructions ''at the same [[execution unit]]'', not just between the units like the 6600. This is accomplished by [[reservation station]]s, from which instructions go to the execution unit when ready, as opposed to the FIFO queue of each execution unit of the 6600. The Model 91 is also capable of re-ordering loads and stores to execute before the preceding loads and stores,<ref name=zs1/> unlike the 6600, which only has a limited ability to move loads past loads, and stores past stores, but not loads past stores and stores past loads.<ref>{{harvtxt|Thornton|1970|p=48-50}}</ref> Only the floating-point registers of the Model 91 are renamed, making it subject to the same WAW and WAR limitations as the CDC 6600 when running fixed-point code. The 91 and 6600 both also suffer from [[Tomasulo's algorithm#Exceptions|imprecise exceptions]], which needed to be solved before out-of-order execution could be applied generally and made practical outside supercomputers.