Skip to Main content Skip to Navigation

Bernstein's Conditions

Paul Feautrier 1
1 COMPSYS - Compilation and embedded computing systems
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : 1 Definition Bersntein's conditions [4] are a simple test for deciding if statements or operations can be interchanged without modifying the program results. The test applies to operations which read and write memory at well defined addresses. If u is an operation, let M(u) be the set of (adresses of) the memory cells it modifies, and R(u) the set of cells it reads. Operations u and v can be reordered if: M(u) ∩ M(v) = M(u) ∩ R(v) = R(u) ∩ M(v) = ∅ (1) If these conditions are met, one says that u and v commute or are independent. Note that in most languages, each operation writes at most one memory cell: W (u) is a singleton. However, there are exceptions: multiple and parallel assignments, vector assignments among others. The importance of this result stems from the fact that most program optimizations consist-or at least, involve-moving operations around. For instance, to improve cache performance, one must move all uses of a datum as near as possible to its definition. In parallel programming, if u and v are assigned to different threads or processors, their order of execution may be unpredictable, due to arbitrary decisions of a scheduler or to the presence of competing processes. In this case, if Bernstein's conditions are not met, u and v must be kept in the same thread. Checking Bernstein's conditions is easy for operations accessing scalars-but beware of aliases-, is more difficult for array accesses, and is almost impossible for pointer dereferencing.
Complete list of metadata

Cited literature [10 references]  Display  Hide  Download
Contributor : Paul Feautrier Connect in order to contact the contributor
Submitted on : Thursday, November 22, 2018 - 12:59:15 PM
Last modification on : Saturday, September 11, 2021 - 3:19:00 AM
Long-term archiving on: : Saturday, February 23, 2019 - 2:36:06 PM


Files produced by the author(s)


  • HAL Id : hal-01930890, version 1



Paul Feautrier. Bernstein's Conditions. [Research Report] ENS Lyon. 2011, pp.1-9. ⟨hal-01930890⟩



Record views


Files downloads