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 metadatas

Cited literature [10 references]  Display  Hide  Download

https://hal.inria.fr/hal-01930890
Contributor : Paul Feautrier <>
Submitted on : Thursday, November 22, 2018 - 12:59:15 PM
Last modification on : Thursday, November 21, 2019 - 2:21:58 AM
Long-term archiving on: Saturday, February 23, 2019 - 2:36:06 PM

File

bernstein.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01930890, version 1

Collections

Citation

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

Share

Metrics

Record views

58

Files downloads

97