Memory ordering

Memory ordering is the order of accesses to computer memory by a CPU. Memory ordering depends on both the order of the instructions generated by the compiler at compile time and the execution order of the CPU at runtime.[1][2] However, memory order is of little concern outside of multithreading and memory-mapped I/O, because if the compiler or CPU changes the order of any operations, it must necessarily ensure that the reordering does not change the output of ordinary single-threaded code.[1][2][3]

The memory order is said to be strong or sequentially consistent when either the order of operations cannot change or when such changes have no visible effect on any thread.[1][4] Conversely, the memory order is called weak or relaxed when one thread cannot predict the order of operations arising from another thread.[1][4] Many naïvely written parallel algorithms fail when compiled or executed with a weak memory order.[5][6] The problem is most often solved by inserting memory barrier instructions into the program.[6][7]

In order to fully utilize the bandwidth of different types of memory such as caches and memory banks, few compilers or CPU architectures ensure perfectly strong ordering.[1][5] Among the commonly used architectures, x86-64 processors have the strongest memory order, but may still defer memory store instructions until after memory load instructions.[5][8] On the other end of the spectrum, DEC Alpha processors make practically no guarantees about memory order.[5]

  1. ^ a b c d e Preshing, Jeff (30 September 2012). "Weak vs. Strong Memory Models". Preshing on Programming. Retrieved 3 August 2024.
  2. ^ a b Howells, David; McKenney, Paul E; Deacon, Will; Zijlstra, Peter. "Linux Kernel Memory Barriers". The Linux Kernel Archives. Retrieved 3 August 2024.
  3. ^ Preshing, Jeff (25 June 2012). "Memory Ordering at Compile Time". Preshing on Programming. Retrieved 3 August 2024.
  4. ^ a b Sewell, Peter. "Relaxed-Memory Concurrency". University of Cambridge. Retrieved 3 August 2024.
  5. ^ a b c d McKenney, Paul E (19 September 2007). "Memory Ordering in Modern Microprocessors" (PDF). Retrieved 3 August 2024.
  6. ^ a b Torvalds, Linus (8 December 2003). "Re: branch prediction, renaming, joins". Retrieved 3 August 2024.
  7. ^ Manson, Jeremy; Goetz, Brian (February 2004). "JSR 133 (Java Memory Model) FAQ". University of Maryland. Retrieved 3 August 2024.
  8. ^ "Intel 64 Architecture Memory Ordering White Paper" (PDF). Intel. August 2007. Retrieved 3 August 2024.