Deterministic OpenMP
What is Deterministic OpenMP ?
Deterministic OpenMP is an implementation of OpenMP which guarantees an OoO execution of all its parallel structures (i.e. with a parallel omp pragma).
Wikipedia definition of a deterministic algorithm: a deterministic algorithm is an algorithm which, given a particular input, will always produce the same output, with the underlying machine always passing through the same sequence of states.
A deterministic algorithm implemented in Deterministic OpenMP is run OoO and gives a deterministic output for any input.
The underlying machine running a Deterministic OpenMP program is assumed to be able to synchronize any producer to consumer dependency between any (writer, reader) couple (ensure all RAW dependencies).
A processor like LBP runs a Deterministic OpenMP program OoO, hence deterministically.
Deterministic OpenMP is an implementation of a subset of OpenMP with a runtime to launch a set or ordered threads at the start of parallel omp structures (fork) and to serialize them at the end (join).
A Deterministic OpenMP program distributes its computation on the available computing resources to accelerate the run speed.
The parts are distributed on harts (hardware threads).
Harts are directly related to the core harts in a multithreaded processor, not to OS threads.
Each hart is mapped on a unique and statically identified hardware thread of a multithreaded processor.
How are the runs made deterministic (1) ?
A sequential code defines a sequential referential total order.
The existence of this sequential reference is the main difference with classic OpenMP implementations.
How are the runs made deterministic (2) ?
The fork-join model on which OpenMP relies is implemented to preserve the sequential referential total order:
-
play_arrow
a hart maybe forked into multiple (sub)-harts being run in parallel,
-
play_arrow
a set of forked harts join in order when they finish,
-
play_arrow
after a join of its forked harts, a forking hart resumes.
Why a sequential referential order (1) ?
The sequential referential order constrains the links between the forked harts:
-
play_arrow
an instruction in a hart can only export its data result to successor harts, not to predecessors,
-
play_arrow
an instruction in a hart can only import its data sources from predecessor harts, not from successors.
Why a sequential referential order (2) ?
The sequential referential order simplifies the core linking topology.
Why a sequential referential order (3) ?
The sequential referential order helps to eliminate race conditions and to ensure deterministic runs.
