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. 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. 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. Conversely, the memory order is called weak or relaxed when one thread cannot predict the order of operations arising from another thread. Many naïvely written parallel algorithms fail when compiled or executed with a weak memory order. The problem is most often solved by inserting memory barrier instructions into the program. 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. 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. On the other end of the spectrum, DEC Alpha processors make practically no guarantees about memory order.
Compile-time memory ordering Most programming languages have some notion of a thread of execution which executes statements in a defined order. Traditional compilers translate high-level expressions to a sequence of low-level instructions relative to a program counter at the underlying machine level. Execution effects are visible at two levels: within the program code at a high level, and at the machine level as viewed by other threads or processing elements in concurrent programming, or during debugging when using a hardware debugging aid with access to the machine state (some support for this is often built directly into the CPU or microcontroller as functionally independent circuitry apart from the execution core which continues to operate even when the core itself is halted for static inspection of its execution state). Compile-time memory order concerns itself with the former, and does not concern itself with these other views.
General issues of program order
Program-order effects of expression evaluation During compilation, hardware instructions are often generated at a finer granularity than specified in the high-level code. The primary observable effect in a procedural programming language is assignment of a new value to a named variable.
sum = a + b + c; print(sum);
The print statement follows the statement which assigns to the variable sum, and thus when the print statement references the computed variable sum it references this result as an observable effect of the prior execution sequence. As defined by the rules of program sequence, when the print function call references sum, the value of sum must be that of the most recently executed assignment to the variable sum (in this case the immediately previous statement). At the machine level, few machines can add three numbers together in a single instruction, and so the compiler will have to translate this expression into two addition operations. If the semantics of the program language restrict the compiler into translating the expression in left-to-right order (for example), then the generated code will look as if the programmer had written the following statements in the original program:
sum = a + b; sum = sum + c;
If the compiler is permitted to exploit the associative property of addition, it might instead generate:
sum = b + c; sum = a + sum;
If the compiler is also permitted to exploit the commutative property of addition, it might instead generate:
sum = a + c; sum = sum + b;
Note that the integer data type in most programming languages only follows the algebra for the mathematics integers in the absence of integer overflow and that floating-point arithmetic on the floating point data type available in most programming languages is not associative due to intermediate rounding, making effects of the order of expression visible in small differences of the computed result (small initial differences may however cascade into arbitrarily large differences over a longer computation). If the programmer is concerned about integer overflow or rounding effects in floating point, the same program may be coded at the original high level as follows:
sum = a + b; sum = sum + c;
Program-order effects involving function calls Many languages treat the statement boundary as a sequence point, forcing all effects of one statement to be complete before the next statement is executed. This will force the compiler to generate code corresponding to the statement order expressed. Statements are, however, often more complicated, and may contain internal function calls.
sum = f(a) + g(b) + h(c);
At the machine level, calling a function usually involves setting up a stack frame for the function call, which involves many reads and writes to machine memory. In most compiled languages, the compiler is free to order the function calls f, g, and h as it finds convenient, resulting in large-scale changes of program memory order. In a pure functional programming language, function calls are forbidden from having side effects on the visible program state (other than its return value) and the difference in machine memory order due to function call ordering will be inconsequential to program semantics. In procedural languages, the functions called might have side-effects, such as performing an I/O operation, or updating a variable in global program scope, both of which produce visible effects with the program model. Again, a programmer concerned with these effects can become more pedantic in expressing the original source program:
sum = f(a); sum = sum + g(b); sum = sum + h(c);
In programming languages where the statement boundary is defined as a sequence point, the function calls f, g, and h must now execute in that precise order.
Specific issues of memory order
Program-order effects involving pointer expressions Now consider the same summation expressed with pointer indirection, in a language such as C or C++ which supports pointers:
sum = *a + *b + *c;
… excerpt ends here. Continue reading the full article.
