Out-of-order instruction execution: is commit orde

Question

On the one hand, Wikipedia writes about the steps of the out-of-order execution:

1. Instruction fetch.
2. Instruction dispatch to an instruction queue (also called instruction buffer or reservation stations).
3. The instruction waits in the queue until its input operands are available. The instruction is then allowed to leave the queue before earlier, older instructions.
4. The instruction is issued to the appropriate functional unit and executed by that unit.
5. The results are queued.
6. Only after all older instructions have their results written back to the register file, then this result is written back to the register file. This is called the graduation or retire stage.

The similar information can be found in the "Computer Organization and Design" book:

To make programs behave as if they were running on a simple in-order pipeline, the instruction fetch and decode unit is required to issue instructions in order, which allows dependences to be tracked, and the commit unit is required to write results to registers and memory in program fetch order. This conservative mode is called in-order commit... Today, all dynamically scheduled pipelines use in-order commit.

So, as far as I understand, even if the instructions execution is done in the out-of-order manner, the results of their executions are preserved in the reorder buffer and then committed to the memory/registers in a deterministic order.

On the other hand, there is a known fact that modern CPUs can reorder memory operations for the performance acceleration purposes (for example, two adjacent independent load instructions can be reordered). Wikipedia writes about it here.

Could you please shed some light on this discrepancy?

Answer 1

TL:DR: memory ordering is not the same thing as out of order execution. It happens even on in-order pipelined CPUs.

In-order commit makes the current core's own code see itself as running in-order. (And allows precise exceptions that can roll-back to exactly the instruction that faulted, without any instructions after that having already retired). The golden rule of out-of-order execution is: don't break single-threaded code.

Memory ordering is all about what other cores see. Also notice that what you quoted is only talking about committing results to the register file, not to memory.

---

Since each core's private L1 cache is coherent with all the other data caches in the system, memory ordering is a question of when instructions read or write cache. This is separate from when they retire.

Loads become globally visible when they read their data from cache. This is more or less when they "execute", and definitely way before they retire (aka commit).

Stores become globally visible when their data is committed to cache. This has to wait until they're known to be non-speculative, i.e. that no exceptions or interrupts will cause a roll-back that has to "undo" the store. So a store can commit to L1 cache as early as when it retires from the out-of-order core.

But even in-order CPUs use a store queue or store buffer to hide the latency of stores that miss in L1 cache. The out-of-order machinery doesn't need to keep tracking a store once it's known that it will definitely happen, so a store insn/uop can retire even before it commits to L1 cache. The store buffer holds onto it until L1 cache is ready to accept it. i.e. it owns the cache line (M state of the MESI cache coherency protocol), and the memory-ordering rules allow the store to become globally visible now.

See also my answer on Write Allocate / Fetch on Write Cache Policy

As I understand it, a store's data is added to the store queue when it "executes" in the out-of-order core, and that's what a store execution unit does.

Loads have to probe the store queue so that they see recently-stored data.

---

For an ISA like x86, with strong ordering, the store queue has to preserve the memory-ordering semantics of the ISA. i.e. stores can't reorder with other stores, and stores can't become globally visible before earlier loads. (LoadStore reordering isn't allowed (nor is StoreStore or LoadLoad), only StoreLoad reordering).

David Kanter's article on how TSX (transactional memory) could be implemented in different ways than what Haswell does provides some insight into the Memory Order Buffer, and how it's a separate structure from the ReOrder Buffer (ROB) that tracks instruction/uop reordering. He starts by describing how things currently work, before getting into how it could be modified to track a transaction that can commit or abort as a group.