Out-of-order execution: Difference between revisions

Revision as of 10:10, 11 July 2025

Revision as of 10:24, 11 July 2025

Line 9:

=== Early use in supercomputers ===

TheArguably the first machine to use out-of-order execution wasis the [[CDC 6600]] (1964), designed by [[James E. Thornton]], which usesused a [[Scoreboarding|scoreboard]] to avoidresolve conflicts. ItThe permits6600 anhowever instruction to execute if its source operandlacked [[Hazard_(readcomputer_architecture)#Write_after_write_(WAW)|WAW registersconflict]] aren'thandling, tochoosing be writteninstead to bystall. anyThis unexecutedsituation earlierwas instruction (true dependency) and the destination (write) register not betermed a register"First usedOrder Conflict" by any unexecuted earlier instruction (false dependency)Thornton<ref>{{harvtxt|Thornton|1970|p=125}}</ref>. The 6600Whilst lacksit thehad means to avoidboth [[PipelineRAW stall|stallingconflict]] anresolution [[execution(termed unit]]"Second onOrder falseConflict"<ref>{{harvtxt|Thornton|1970|p=126}}</ref>) dependenciesand ([[Hazard_(computer_architecture)#Write_after_write_Write_after_read_(WAWWAR)|writeWAR after writeconflict]] (WAW) and [[write after read]]resolution (WAR) conflicts, respectively termed ''first-order"Third conflict'' and ''third-order conflict'' byOrder Conflict"<ref>{{harvnb|Thornton, who termed true dependencies ([[Hazard_(computer_architecture)#Read_after_write_(RAW)|read after write]] (RAW)1970|p=127}}</ref>) asall second-orderof conflict)which becauseis eachsufficient addressto has only a single ___location referable bydeclare it. Thecapable WAWof isfull worseout-of-order than WAR forexecution, the 6600, becausedid whennot anhave executionprecise unitexception encountershandling. aAn WAR,early theand otherlimited executionform unitsof stillBranch receiveprediction andwas executepossible instructions,as butlong upon a WAWas the assignmentbranch of instructionswas to executionlocations unitson stops,what andwas theytermed canthe not"Instruction receiveStack" anywhich furtherwas instructionslimited untilto thewithin WAW-causinga instruction'sdepth destinationof registerseven haswords beenfrom written to bythe earlierProgram instructionCounter.<ref>{{harvtxtharvnb|Thornton|1970|p=125-127112,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''.