When developing code for a multiprocessor system, it seems natural to use multiple cores. However, writing multithreaded code is more than just launching different threads to execute code in parallel by exploiting TLP, as threads sharing memory may communicate implicitly through loads and stores. Modern cores may reorder many memory
When developing code for a multiprocessor system, it seems natural to use multiple cores. However, writing multithreaded code is more than just launching different threads to execute code in parallel by exploiting TLP, as threads sharing memory may communicate implicitly through loads and stores.
Modern cores may reorder many memory accesses to enhance performance (e.g., via non-FIFO write buffers), which can lead to aberrant program execution and incorrect behavior. This includes Store-Store, Load-Load, Load-Store, and Store-Load reordering.
While memory reordering has no effect on the observable behavior of a single-threaded execution (i.e. the von Neumann model), when multiple processors read and write to a single shared address space, the behavior of the shared memory is dictated (or specified) by the memory consistency model. Therefore, we need to look at the memory consistency model (which could be Sequential Consistency (SC), Total Store Order (TSO), or a relaxed memory consistency model); otherwise, it is difficult to reason about what the hardware can and cannot do, that is, what micro-optimizations are involved and can be observed.
The performance of a program when executed on a processor can be determined by looking at the clock cycles required to execute the program; that is, we could inspect \(IPC × clock cycle duration^{-1}\). Thus, one way to improve the performance of a processor is to increase its clock frequency (i.e. shorten the clock cycle, e.g., through increased pipelining), something superpipelined microprocessors employ. However, frequency cannot be increased indefinitely due to practical physical limitations.
So, modern processors attempt to cope with the IPC term by increasing Instructions Per Cycle (IPC), doing useful work rather than staying idle, and tolerating the growing gap between the processor and DRAM. By useful work, we mean, for example, reordering ALU instructions or memory instructions, that is, allowing load and store instructions to be executed without obeying the original program order.
By overlapping memory traffic with the execution of independent instructions, long-latency memory operations can be tolerated while preserving the original program semantics and precise exceptions.
However, out-of-order execution imposes many hardware changes at the microarchitecture level. Some of these microarchitectural mechanisms are introduced below.
Register renaming was introduced to cope with false or name dependencies. In this case, each destination register is renamed to a physical register (which could be a ROB ID if two storage structures are used, one architectural register file for the committed state and one temporary speculative storage in the ROB [6,7], or an entry in a unified physical register file where mappings/RATs are maintained between logical architectural registers and physical registers used to recover the committed state [6,7]). This way, register renaming enables more instructions to become available for selection from the reservation stations (RS) and dispatch to execution units, thus raising IPC and thus processor performance.
As said above, modern microprocessors stay busy by overlapping long-latency operations with other operations that are ready to execute, but this requires having a hardware structure where the circuitry can select instructions that are ready to execute, i.e., whose source operands are ready, each cycle, and then issue them to an execution unit, which could be a load/store unit or another functional unit. This hardware structure is commonly referred to as a Reservation Station (RS) or an issue/instruction queue, depending on the microarchitecture. These structures form part of the processor's instruction window, from which ready instructions can be selected for out-of-order execution.
Reservation stations allow dispatched instructions to wait until their operands and the required execution units are available. Instead of halting younger independent instructions when an older instruction is not ready, the processor can select ready instructions from the reservation stations hosting unexecuted instructions and issue them to the appropriate execution units (e.g., load/store unit) for out-of-order execution.
Every dispatched instruction occupies an entry in the RS until it is issued for execution. Thus, the larger the RS, the more opportunities the circuitry has to exploit an application's inherent ILP. Unfortunately, increasing the size of such hardware structures can increase critical-path latencies, making it more difficult to meet high clock frequencies.
The reorder buffer (ROB) is introduced to ensure that instructions become architecturally visible (i.e. visible to software) in program order, even though they may execute out of the original program order (i.e. instructions do not update the architectural state when they finish executing, but only when they commit/retire out of the ROB), thereby exploiting instruction-level parallelism (ILP) and improving IPC performance.
Another purpose of the ROB is to provide precise interrupts/exceptions and cope with branch mispredictions.
Basically, the ROB stores all instructions currently in-flight, whether waiting, executing, or already executed, and is used to ensure in-order commitment or retirement of instructions.
At the hardware level, it is typically implemented as a circular buffer using head and tail pointers and can host a predefined number of entries. If, during the dispatch/rename phase, the buffer is full, then the allocation of new instructions is halted. Specifically, an instruction from the front-end is assigned to an RS and a ROB entry in parallel.
When an instruction is executed, its ROB entry is marked as completed, and its result is made available for dependent instructions. An instruction retires when it leaves the ROB head. If the instruction is a conditional branch and the branch predictor mispredicts, then all younger instructions following the branch have to be squashed, and this is why branch misprediction has a penalty cost.
Instructions whose operands depend on a value produced by an earlier instruction do not have to wait for that instruction to be committed; the produced value can be forwarded to dependent instructions instead of halting them until the producing instruction is committed and the architectural register state is updated.
Naturally, the ROB must be rather large to support many in-flight instructions, and this can create a bottleneck if the ROB becomes full, as it prevents new instructions from being allocated.
Every dispatched instruction requires a ROB entry until the instruction commits. For example, a long-latency instruction at the head of the ROB, such as a load suffering a long-latency cache miss, can prevent younger instructions from committing even if they have already completed. As more instructions accumulate behind it, the ROB can eventually become saturated and the processor can no longer accept new instructions. Thus, in-order commit can become a performance limitation in the presence of large memory-access latencies.
As covered later, the store buffer allows stores to commit and leave the ROB while their memory operations are still pending (e.g. their target cache lines are not yet available), as long as there is sufficient space in the store buffer. This is possible because stores do not update the register file when they complete, so they can be retired to unblock the pipeline and sit in the store buffer waiting for their memory transaction to complete (i.e. retirement can proceed while store visibility remains pending).
The store buffer is employed by modern processors to hold all the in-flight, committed/retired stores, which are issued in program order and hide the latency of store misses.
Basically, once a store's operands are ready, the store address and data are stored in the associated entry in the store or write buffer, that is, a store enters the store buffer when the store commits.
The store buffer allows a store instruction to retire from the processor pipeline or more specifically the ROB while its memory transaction is still pending that is before the store instruction has actually written its data in the cache/memory system. A store is said to be performed when it exits the store buffer and is written into the cache; which happens when the associated line in the cache is in a read-write coherence state.
Store operations can take many cycles to complete, for example, when waiting to obtain ownership of a cache line. Without a store buffer, the store could remain at the head of the ROB and block the retirement of subsequent instructions, since instructions retire from the ROB in program order.
Additionally, a non-FIFO store buffer allows coalescing of writes; that is, two stores that are not consecutive in program order can write to the same entry in the write buffer. As we will cover later, this means that two stores may be reordered if a core employs a non-FIFO store buffer.
Even if the store buffer is drained using a FIFO policy, Store-Load reordering is still possible due to both local bypassing and store forwarding, that is, either when there is no address conflict and a younger load bypasses older stores to read from the cache, or when there is an address conflict and the younger load reads its value directly from a pending store.
The load queue (LQ) is introduced to allow speculative loads to execute and, similar to the store buffer, it hosts in-flight loads in program order. When a load is executed, the load address is written into the associated entry in the load queue, and then the cache and the store queue are solicited. The processor could take aggressive measures to improve performance and allow a younger load to execute before an older store's address is known. If this speculation turns out to be incorrect, the circuitry squashes and re-executes the affected instructions.
A load may be retired from the ROB and dequeued from the load queue even if there are older posted stores remaining in the store buffer [3].
Additionally, there must be cooperation between the load and store buffers. For example, for data dependencies during a load, the store buffer is inspected, and if the address of a load does not match one of the previous stores, then the load can be issued to the cache subsystem. Otherwise (i.e a true data dependency on a store instruction) it must halt until the conflicting stores are retired. A wiser approach is to forward directly to the load the value hosted in the speculative store, as this is anyway the value that would be hosted in the cache once the store proceeds, thereby reducing memory traffic.
If the address of the store is not resolved yet, then the processor can aggressively delay the address-conflict check (i.e until a store address is generated). If it turns out that previous stores were in fact conflicting, then the load will be re-issued, e.g., by supplying the data directly from the store buffer, and following instructions need to be squashed due to dependent instructions (store-load order violation).
As we will cover in the next subsections, stores and loads can be executed and drained from the store buffer and load queue, respectively, out of program order.
When a core wants to operate on a memory location, e.g., perform a store, the corresponding cache line must first be brought into a cache close to the processor. When multiple cores are involved, coherence protocols ensure that only one core can hold a cache line in a writable/modified state at a given time. Otherwise, multiple cores could independently modify different copies of the same cache line.
Each cache line maintains a coherence state indicating whether its contents are valid and whether the current core has sufficient ownership to modify it. If the core already owns the cache line in a writable state, it does not need to issue a coherence transaction to obtain ownership. Otherwise, it must issue a transaction through the cache-coherence subsystem to obtain the required ownership and invalidate other cached copies as necessary. Once ownership has been obtained, the core can update the cache line.
The aforementioned process is involved during a store. Instead of keeping the store in the ROB until the memory operation becomes globally visible, a committed store can leave the ROB and remain in our previously introduced pending structure, the store buffer. The store may have to wait for the required coherence transaction to complete before its value can update the corresponding cache line and become globally visible.
Once the cache line is owned, the memory location can be updated. A different core that subsequently wants to read that location obtains the coherent value through the cache hierarchy and coherence protocol. Similarly, a core that wants to modify the cache line must first obtain the required ownership through a coherence transaction.
When the store buffer is drained in FIFO order, stores maintain their ordering with respect to one another. If this ordering constraint is relaxed, stores may become visible in an order different from program order, that is, entries may drain whenever their cache lines are ready. This is what enables Store-Store reordering.
When a non-FIFO store buffer is employed, one can prevent Store-Store reordering using a store fence or store barrier. A possible implementation is to stall younger memory instructions until the fence retires, which happens when the store buffer is drained, that is, when all L1 cache controller buffers are empty[1]. Put simply, stores following a barrier or fence can be allowed to proceed only after all older stores have completed.
Load instructions are the second type of memory request served by the processor. If one wants to preserve the ordering of loads with respect to other loads, i.e., prevent younger loads from being executed ahead of older loads, a load fence can be used.
Similar to a store fence, a load fence creates an ordering boundary between loads older than the fence and loads younger than the fence. The required older loads must complete before younger loads are allowed to proceed past the fence. A possible implementation is to stall the execution of younger loads (younger than the fence) until the load fence completes [2,3]. For example, subsequent load operations can be put to sleep when they detect an unfinished older load-fencing operation and awakened once the fence has completed [3].
A load barrier can do more than halt subsequent load instructions from execution until older loads complete. In some architectures [5], it may involve processing an invalidation queue that hosts deferred cache-line invalidation transactions. The coherence protocol prevents other cores to load stale or incoherent data, however, to boost performance, invalidation queues were introduced to speed up the process of invalidating a cache line by sending an immediate acknowledgment (ACK) to the sender, allowing it to complete the coherent transaction and proceed with the modification of that cache line.
Defeating Store-Load and Load -Store reordering is similar to what we discussed above. Basically, a dedicated memory fence can be used to enforce the required ordering between the two types of memory operations.
For Store-Load ordering, the fence ensures that older stores are globally visible before younger loads are allowed to execute or proceed past the fence. For Load- Store ordering, the fence ensures that older loads are completed before younger stores are allowed to proceed past the fence.
A full memory fence [2] combines ordering constraints on loads and stores. It ensures that the relevant memory operations older than the fence are globally visible before subsequent memory operations are allowed to proceed past the fence. The implementation prevent younger loads and stores from being dispatched or executed past the fence until the required older loads and stores have completed.
An atomic operation is basically an operation that runs without being interrupted, ensuring that it is completed as a single, indivisible unit.
For instance, in a reference-counting algorithm, different cores may be executing different programs or code while still manipulating a shared data structure, and both may have to update the reference counter to enable automatic memory scavenging. In this case, the reference count should be updated atomically (increment operation comprises at least three instruction). Otherwise, both cores could first load the same value at the same time from a cache line that is still valid. At some point, both cores could decrement the value, check that it is still not 0, and race to update the reference count to a value greater than 0, say 1, resulting in a memory leak.
With an atomic operation, you can first load the previous value and then perform the update only if it has not changed in the meantime, retrying the operation if it has. This can be achieved using atomic intrinsics.
The same problem occurs when updating a counter, if both cores load the same value, update it in their respective registers, and then race to write the value back to the cache, the result would be incorrect because the operation is not atomic. In this case, the ISA can provide an atomic instruction that performs the addition while accounting for the possibility that the value in the cache line was updated in the meantime (remember, we want the operation to appear uninterrupted).
Atomic operations are similar to critical sections, except that exclusivity is confined to a single assignment or read-modify-write operation.
A critical section needs to be visited by only one thread at a time. Ignoring memory reordering, this can be achieved using a lock value which is updated using atomic operations. In this case, we can guarantee that only one core enters the critical section at a time.
When the microarchitecture makes use of reordering, then the publisher must make sure that stores are not reordered after the unlock operation by placing a store fence before the lock is set to false, while the consumer must ensure that the lock value is read and checked and also place a memory barrier before entering the critical section to ensure that subsequent loads are not reordered before the lock acquisition.
Thus, we need a store barrier on the producer, referred to as release, and a load or read barrier on the consumer, referred to as acquire. So basically, we are sandwiching the critical section between acquire and release operations.
If the producer fails to add the required release ordering, then the consumer may enter the critical section while stores from the previous critical section are still pending, meaning that memory operations from the two critical sections may overlap even though the atomic lock itself still guarantees a single logical owner.
On the other hand, if the consumer fails to position the acquire barrier, then the consumer can load data ahead of time and read invalid or stale data.
When a lock is not available, the waiting thread can continue spinning until the lock is released. This is referred to as a spinlock and is usually optimized to reduce memory traffic during contention and speed up handover, while some implementations may guarantee fairness (e.g., the eBPF ring buffer uses a spinlock).
A spinlock is typically used when the thread cannot sleep or when the lock is expected to be released soon.
Now, if the lock is to be held for an unknown or longer amount of time, a mutex can be used, which puts the calling thread or task to sleep, and the thread can then be woken up when the lock is released.
There is a plethora of work studying the performance of locking, including spinlocks and mutexes. There are also lock-free projects that avoid using locks, like mimalloc, which makes use of atomic operations to support multithreaded memory allocation and deallocation.
If you want to see memory reordering live, I have shared some small experiments at https://github.com/mouadk/memory-reordering.
Increasing the clock frequency is not always possible to boost processor performance, while at the same time, increasing IPC demands increasing the size of hardware structures like the ROB, RS, and store buffer, which will at some point hurt clock cycle time. So, this is a challenge that manufacturers have to deal with carefully.
Reordering ALU instructions does not really have an impact on program semantics, while the reordering of memory instructions can affect program execution. Additionally, executing memory instructions in an order different from the original program order can negatively impact an application's cache locality [4].
Memory barriers can be used to defeat compiler and hardware reordering, but if extensively used, they can hurt performance.
[2]https://patentimages.storage.googleapis.com/af/9e/79/f5f6cd2a2e5d6c/US9612835.pdf
[3]https://patentimages.storage.googleapis.com/62/ed/f5/5e8ae69f5b6098/US11175916.pdf
[4] https://www.jaleels.org/ajaleel/publications/ajaleel-PhD-proposal.pdf
[6] https://docs.boom-core.org/en/latest/sections/rename-stage.html
[7] https://upcommons.upc.edu/server/api/core/bitstreams/529656e0-bb26-4951-a762-8c3f76cf1a84/content
[8]https://patentimages.storage.googleapis.com/fe/41/a3/ddea1fb5732c17/US6651151.pdf