HOME       UP       PREV       NEXT (Classical High-Level Synthesis Example: Kiwi compilation of Sieve of Eratosthenes.)  

Atomic Commutable Effects

By `effects' we mean side effects: ie. imperative mutations of the surrounding state (such a write to file).

A number of operations fall into classes of atomic commutable effects.

These typically operate on a single word, where a load or store is intrinsically an atomic action, but involve both a load and a store and so are potentially non-atomic in some implementations.

   counter += 3;
   flags |= (1<<9);
   counter -= 21;
   flags |= (1<<10);

Classic examples of atomic operations are test-and-set, increment, and bit-set.

A pair of increments may be commuted in order without altering the final result stored in the word. Clearly increments and decrements of any amount can be commuted provided the range of the underlying word is not exceeded. Bit-sets of the same or different bits within the word may also be commuted with each other.

But bit-set and increment to the same word cannot be commuted and are said to be in different atomic effects classes (by DJG at least).

But note that test-and-set (or compare-and-swap) operations, despite being (and needing to be) atomic, are not commutable: they are not meerly side-effecting, they return a result that generally affects the caller's behaviour.

Where all commutable atomic effects on a shared variable within the bodies of parallel code are in the same effects class, then the resulting composition is race free. In other words, the system will accumulate the same result in the shared variable regardless of schedulling order.


33: (C) 2012-18, DJ Greaves, University of Cambridge, Computer Laboratory.