How can we expect a program to complete in order?

Question

Out of order execution exists on most modern microprocessors. How can we expect a program to complete in order as it was written by a programmer?

Answer 1

Right, of course you can't just run instructions in arbitrary order, on whatever register values happen to be present in architectural registers. An instruction can only execute when its correct inputs are ready. Finding when that's true for as many "future" instructions as possible is key to keeping execution units fed with work, finding instruction level parallelism (ILP).

Dependency tracking between instructions is set up during allocate/rename as instructions are copied (in program order) from the front-end to the back end. During alloc/rename, the RAT (Register Allocation Table) maps architectural registers to physical registers, allowing multiple independent dep chains using the same architectural register to be executing at once.

---

Maybe you're thinking about this backwards. An ISA (such as x86-64 or ARMv8) defines a set of rules for how machine instructions execute, often a serial model where one instruction fully finishes executing before the next one starts. (ISAs with some explicit parallelism do exist, e.g. VLIW, or The Mill's delayed-visibility loads that become visible some fixed number of instructions later, helping hide load latency on in-order CPUs. There are still well-defined rules.)

To run software for an ISA like that, hardware has to implement all the rules that are guaranteed on paper. The cardinal rule of out-of-order execution is to preserve the illusion of executing instructions in program order for a single thread¹. This is a necessary part of being a valid / non-buggy x86 or ARM CPU.

(See Observing x86 register dependencies - any architectural state that isn't renamed generally needs to serialize the pipeline on modification, so make sure any instructions that need the old value have already finished.)

This is very much like the C "as if" optimization rule: you can do whatever you want as long as the observable result is still the same, but for CPU architects instead of compilers.

As Modern Microprocessors A 90-Minute Guide! puts it: If the processor is going to execute instructions out of order, it will need to keep in mind the dependencies between those instructions. (You should definitely go read that, if you haven't already; it's a very good baseline of understanding for any more advanced stuff, and it covers a lot of ground itself. Highly recommended.)

That's why OoO exec needs so many transistors for a large scheduler and reorder buffer (ROB) to keep track of the reordering, and of dependencies between instructions. (In computer-architecture terminology, RAW hazards: read after write, where one instruction writes a register and a later instruction reads that register. Register renaming hides WAR and WAW hazards.)

Footnote 1: OoO exec does not try to maintain order of memory accesses observed by other threads. Even in-order CPUs can do memory reordering, so software always needs to take care for inter-thread communication, using fence instructions and/or acquire loads / release stores or whatever, depending on the ISA.

See also

• Observing x86 register dependencies
• Out-of-order execution vs. speculative execution - everything is speculative until in-order retirement verifies that speculation was correct and maintains a valid architectural state.
• Are loads and stores the only instructions that gets reordered? - shows the limits of OoO exec for long dependency chains.
• http://blog.stuffedcow.net/2013/05/measuring-rob-capacity/ more about limits on the out-of-order window size.
• https://www.realworldtech.com/haswell-cpu/3/ - diagram of HSW's out-of-order back end.
• Deoptimizing a program for the pipeline in Intel Sandybridge-family CPUs - includes some general background about how OoO exec does things, and links to stuff about how CPUs work.
• Can a speculatively executed CPU branch contain opcodes that access RAM? - store buffers are essential for decoupling OoO exec from global visibility of stores.
• https://softwareengineering.stackexchange.com/questions/349972/how-does-a-single-thread-run-on-multiple-cores/350024#350024 (it doesn't, but my answer there covers some basics of how OoO exec can exploit instruction-level parallelism. ILP exists when there is independent work to do, not one long dependency chain.)
• http://www.lighterra.com/papers/modernmicroprocessors/
• How is load->store reordering possible with in-order commit? - makes the point that OoO exec is separate from memory reordering, otherwise not really related to this.