Computation-centric memory models
Matteo Frigo, Victor Luchangco · 1998
We present a computation-centric theory of memory models.Unlike traditional processor-centric models, computation-centric models focus on the logical dependencies among instructions rather than the processor that happens to execute them.This theory allows us to define what a memory model is, and to investigate abstract properties of memory models.In particular, we focus on constructibility, which is a necessary property of those models that can be implemented exactly by an online algorithm.For a nonconstructible model, we show that there is a natural way to define the constructible version of that model.We explore the implications of constructibility in the context of dag-consistent memory models, which do not require that memory locations be serialized.The strongest dag-consistent model, called NN-dag consistency, is not constructible.However, its constructible version is equivalent to a model that we call locution consistency, in which each location is serialized independently.