Can Out-of-Order Instruction Execution in Multiprocessors Be Made Sequentially Consistent?

摘要

We investigate all possible combinations of re-ordering of read and write instructions and their effects on the correctness of programs that are designed for sequential consistency. With certain combinations of re-orderings, any program that accesses shared memory through only reads and writes and that is correct assuming sequential consistency, can be transformed to a new program that does not use any explicit synchronization, and that remains correct in spite of the instruction re-ordering. With other combinations of re-ordering, such transformations do not exist, without resorting to explicit synchronization.