A question about concurrent propagators (was: a silly question...)

[David Hopwood]

Aurélien Campéas wrote:
> Dear Mozart/Oz users and hackers,
> 
> While we are doing some 'final touches' (read : last-minute debugging
> of vital functionality) to a dumbed-down (non-nestable) version of the
> computation space concept for inclusion in PyPy (see the pypy project
> at : http://codespeak.net/pypy/) I also have to polish the technical
> report that explains what we did, and why, and I have a hard time
> remembering the rationale behind constraint propagators running in
> their own threads. (I'am quite sure I asked Raphael at some point but
> I didn't record reliably his answer, whatever it was)
> 
> The problem with that is that it seems to add gratuitous overhead
> (compared to a simple algorithm like AC3) without any visible (to me,
> yet) gain in *practical* expressive power. For both practicality and
> performance reasons, neither Logilab constraint package nor Gecode
> do that kind of stuff.

I'm not a Mozart/Oz hacker, but I'll try to answer this anyway.

A propagator may suspend because a variable that it attempts to read is
not determined. In that case, one approach is to save a continuation for
that propagator, which can be continued when the variable becomes (more)
determined. In a language with lightweight threads, it makes sense to
represent this continuation as a thread, which leads to the
thread-per-propagator design.

However, *for monotonic propagators*, rerunning the propagator from scratch
should be equivalent to running its continuation. Any individual propagator
is unlikely to have done very much work before it suspends. So in a language
implementation that doesn't provide lightweight continuations or threads, and
if only monotonic propagators need to be supported, it is reasonable to just
rerun propagators from scratch.

Note that in the thread-per-propagator design, the language implementation
would maintain a wait queue for each dataflow/constraint variable, to record
which threads are dependent on it. When not using threads, there will
still be something equivalent to this, although it may be part of the
constraint satisfaction algorithm. (Repeatedly running all propagators
that are not yet entailed in a round-robin fashion would be semantically
valid, but potentially very inefficient.)

-- 
David Hopwood <david.nospam.hopwood at blueyonder.co.uk>