Formalizing Causality as a Desideratum for Memory Models and Transformations of Parallel Programs

It has been observed in previous work that it is desirable to avoid causal violations in any execution or transformation of a parallel program. In this paper, we formalize the notion of causality in memory consistency models and code transformations. For memory models, we introduce a framework of causality graph that can be used to analyze if a particular memory model violates causality. We show that a popular memory model as the Java memory model (JMM) [16], can lead to program executions that exhibit causality violations with respect to our definition of causality. The same analysis appears to also apply to a recent proposal of C++ specification [7] where the underline memory model may also lead to similar problems. For code transformations, we identify transformations that are causality-preserving and those that are potentially causality-violating. We found that 10 of the 13 code transformation examples that were identified as causality-preserving with respect to the Java Memory Model fail our causality graph test and thus represent causality violations in our framework. Likewise, we also present examples to illustrate how the recently proposed C++ Memory Model can lead to potential causality violations