  The memory consistency model is a fundamental system property characterizing
a multiprocessor. The relative merits of strict versus relaxed memory models
have been widely debated in terms of their impact on performance, hardware
complexity and programmability. This paper adds a new dimension to this
discussion: the impact of memory models on software reliability. By allowing
some instructions to reorder, weak memory models may expand the window between
critical memory operations. This can increase the chance of an undesirable
thread-interleaving, thus allowing an otherwise-unlikely concurrency bug to
manifest. To explore this phenomenon, we define and study a probabilistic model
of shared-memory parallel programs that takes into account such reordering. We
use this model to formally derive bounds on the \emph{vulnerability} to
concurrency bugs of different memory models. Our results show that for 2 (or a
small constant number of) concurrent threads, weaker memory models do indeed
have a higher likelihood of allowing bugs. On the other hand, we show that as
the number of parallel threads increases, the gap between the different memory
models becomes proportionally insignificant. This suggests the
counter-intuitive rule that \emph{as the number of parallel threads in the
system increases, the importance of using a strict memory model diminishes};
which potentially has major implications on the choice of memory consistency
models in future multi-core systems.

Distributed, Parallel, and Cluster Computing