Memory ordering

Memory ordering is a group of properties of the modern microprocessors, characterising their possibilities in memory operations reordering. It is a type of out-of-order execution. Memory reordering can be used to fully utilize different cache and memory banks.

On most modern uniprocessors memory operations are not executed in the order specified by the program code. But from the programmer's point of view, all operations appear to have been executed in the order specified, with all inconsistencies hidden by hardware.

In SMP microprocessor systems

There are several memory-consistency models for SMP systems:

• sequential consistency (All reads and all writes are in-order)
• relaxed consistency (Some types of reordering are allowed)
  • Loads can be reordered after Loads (for better working of cache coherency, better scaling)
  • Loads can be reordered after Stores
  • Stores can be reordered after Stores
  • Stores can be reordered after Loads
• weak consistency (Reads and Writes are arbitrarily reordered, limited only by explicit memory barriers)

On some CPUs atomic operations can be reordered with Loads and Stores.

Also, there can be

• Dependent Loads Reordered is unique for Alpha. This processor can fetch data before it fetches pointer to this data. It make cache hardware simpler and faster, but leads to the requirement of memory barriers for readers and writers.
• Incoherent Instruction cache pipeline (which prevent self-modifying code to be executed without special ICache flush/reload instructions)

Memory ordering in some architectures ^[1][2]

Type	Alpha	ARMv7	PA-RISC	POWER	SPARC RMO	SPARC PSO	SPARC TSO	x86	x86 oostore	AMD64	IA64	zSeries
Loads reordered after Loads	Y	Y	Y	Y	Y				Y		Y
Loads reordered after Stores	Y	Y	Y	Y	Y				Y		Y
Stores reordered after Stores	Y	Y	Y	Y	Y	Y			Y		Y
Stores reordered after Loads	Y	Y	Y	Y	Y	Y	Y	Y	Y	Y	Y	Y
Atomic reordered with Loads	Y	Y		Y	Y						Y
Atomic reordered with Stores	Y	Y		Y	Y	Y					Y
Dependent Loads reordered	Y
Incoherent Instruction cache pipeline	Y	Y		Y	Y	Y	Y	Y	Y		Y	Y

Some older x86 and AMD systems have weaker memory ordering^[3]

SPARC memory ordering modes:

• SPARC TSO = total-store order (default)
• SPARC RMO = relaxed-memory order (not supported on recent CPUs)
• SPARC PSO = partial store order (not supported on recent CPUs)

Memory barriers types

See also: Memory barrier

Compiler memory barrier

These barriers prevent a compiler from reordering instructions, they do not prevent reordering by CPU.

• The GNU inline assembler statement

asm volatile("" ::: "memory");

or even

__asm__ __volatile__ ("" ::: "memory");

forbids GCC compiler to reorder read and write commands around it.^[4]

• Intel ECC compiler uses "full compiler fence"

__memory_barrier()

intrinsics.^[5][6]

• Microsoft Visual C++ Compiler:^[7]

_ReadWriteBarrier()

Hardware memory barrier

Many architectures with SMP support have special hardware instruction for flushing reads and writes.

• x86, x86-64

lfence (asm), void_mm_lfence(void)
sfence (asm), void_mm_sfence(void) [8]
mfence (asm), void_mm_mfence(void) [9]

• PowerPC

sync (asm)

• POWER

dcs (asm)

• ARMv7

dmb (asm)

GCC since version 4.1.0 and intel c++ compiler have special builtin for calling full hardware memory barrier:

__sync_synchronize().

Asm memory barrier (see above, "Compiler memory barrier") is also issued by this builtin in GCC;

See also

• Memory model (computing)
• Memory barrier

References

1. ^ Memory Ordering in Modern Microprocessors by Paul McKenney
2. ^ Memory Barriers: a Hardware View for Software Hackers, Figure 5 on Page 16
3. ^ Table 1. Summary of Memory Ordering, from "Memory Ordering in Modern Microprocessors, Part I"
4. ^ GCC compiler-gcc.h
5. ^ ECC compiler-intel.h
6. ^ Intel(R) C++ Compiler Intrinsics Reference

   Creates a barrier across which the compiler will not schedule any data access instruction. The compiler may allocate local data in registers across a memory barrier, but not global data.

7. ^ Visual C++ Language Reference _ReadWriteBarrier
8. ^ SFENCE — Store Fence
9. ^ MFENCE — Memory Fence

Further reading

• Computer Architecture — A quantitative approach. 4th edition. J Hennessy, D Patterson, 2007. Chapter 4.6
• Sarita V. Adve, Kourosh Gharachorloo, Shared Memory Consistency Models: A Tutorial
• Intel® 64 Architecture Memory Ordering White Paper
• Memory ordering in Modern Microprocessors part 1
• Memory ordering in Modern Microprocessors part 2