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

[Aurélien Campéas]

On Fri, Feb 23, 2007 at 09:00:36PM +0000, David Hopwood wrote:
> 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.

Thanks, this is appreciated :)

> 
> A propagator may suspend because a variable that it attempts to read is
> not determined. 

Well I hope not. At least I don't see currently what in the design of
propagators would lead to such a thing (and I am not talking about
constraint variables, which are obviously not determined most of the
time, the propagator's job being to shrink their domain).

So I'd tend to see propagators blocking on some undertermined logic
variables as a programming error.

Is there a use case out there that can show me how wrong this
assumption is ? (still I want to exclude from this question the usage
of logic variables as synchronisation devices for updated domains)

> 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.

hmm

> 
> 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.

Ok, then I'd be interested in seeing what's a non-monotonic propagator.

> 
> 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. 

Indeed.

> 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.)

Potentially very inefficient ? I have a hard time believing that. At
least the complexities of the various arc-consistency checking /
revision algorithms are well known. It seems (to me) quite harder to
understand what it can be when the scheduling decisions are
dynamically computed within a maze of threads-watching-their-domains
for further propagation.

Cheers,
Aurélien.