[cpp-threads] Temporal models

[Nick Maclaren]

I apologise in advance for going into lecturing mode, but I don't see
how to explain without it.  I am posting this to both the C++ threads
list and the UK Fortran list, as exactly the same issue has arisen in
both.  In my view, both are about to make catastrophic mistakes in the
introduction of parallelism.

Yes, I KNOW that replying won't work :-(

This is normally phrased as "are implementations allowed to break the
laws of physics", but no pure mathematician gives a damn about those,
and this is a mathematical issue.  It is about what temporal model a
language standard defines/requires/assumes/whatever.  Note that this
is not quite the same as a serialisation model.

I assert that almost all programmers will think in terms of (possibly
non-scalar) "arrows of time", and very few will be able to write correct
code if the language does not support any kind of temporal model.  Even
Hoare and Lamport usually restrict themselves in that way.

The problem about the current approaches in both C++ and Fortran is
that they break that, and introduce language specifications where there
is no temporal model for the language as a whole, but only for certain
aspects of it.  This is a recipe for chaos, at best.


1. An aside, primarily for Fortran
----------------------------------

This problem depends solely on the parallelism model being MIMD in the
weakest sense, and is otherwise completely independent of the model.  It
doesn't make any difference whether the units of parallelism are called
tasks, processes, threads, images, or doppelgangers - all that is
necessary to raise this problem is that sequencing of process
interactions due to causality does not necessarily imply sequencing in
the language specification and that processes can run different code
which is executed in an indeterminate order.

Communicating sequential processes do not show it, because sequencing
due to causality DOES imply sequencing in the specification.  One reason
that C++ and Fortran have trouble is that the languages do not require
execution to be sequential in terms of the abstract machine (for good
reasons).

SIMD models, BSP and so on do not show it, because they do not allow
code to be executed in an indeterminate order - any such programs are
illegal.  Co-array Fortran could eliminate this problem by removing the
facilities that allow images to execute different code (which also means
making teams a static concept).


2. What I Mean by a Temporal Model
----------------------------------

There is a concept of a SINGLE partial ordering of "A happens before B",
almost exactly like Hans Boehm's memory model, but extended to include
causality.  For example, if thread/image P writes some data to a file
which is read by thread/image Q, and that data causes a change in Q's
state, then there is a sequencing constraint.

Note that I am NOT asking for any more precision in when events are
serialised - i.e. the current lack of definition on when dubious memory
actions take place can stay.  What I am saying is that, WHEN the
language provides a construction that states that A causes B, then A
happens before B.  Where this differs from the current approaches is
that it permits the use of causality as a sequencing operator, which I
assert is what almost all users will expect.

The current situation in both languages is that there is a partial
ordering of memory accesses - fine - but there is another due to the
causality of external actions, which is not required to be consistent
with the first.  This is one of the worst "gotchas" that I can imagine.


3. An aside for C++
-------------------

Atomic operations define a third partial order, which is tolerable
because it is a refinement of one of the other partial orders.
Unfortunately, allowing both atomic and non-atomic operations on
the same objects means that the atomic partial order now provides a
causality ordering that is not defined to be a serialisation ordering
in the language.

That is why I would take a hard line and forbid such mixed uses.  It
would be possible to bring the atomic causality into the temporal model,
but that is very messy.


4. The Problem
--------------

The problem is, of course, that programmers will write code that is
perfectly correct assuming a temporal model (i.e. relying on causality
to impose ordering), and will get results that indicate that time is
running backwards.


Regards,
Nick Maclaren,
University of Cambridge Computing Service,
New Museums Site, Pembroke Street, Cambridge CB2 3QH, England.
Email:  nmm1 at cam.ac.uk
Tel.:  +44 1223 334761    Fax:  +44 1223 334679