transparent parallelism (was: Re: [E-Lang] Internal vs. external iteration)

[Felix A. Croes]

zooko@zooko.com wrote:

>[...]
> Nevertheless, in case someone is interested in the subject, I'll explain my
> thoughts about it.  (One reason to think about it now is that it interacts with
> certain notions of deterministic computation that I know MarkM has been
> thinking about, although hopefully we can safely put off having to commit to
> anything.)
>
>
> Someday high-powered E implementations might want to do transparent parallelism
> to compute multiple E ticks at once.  This can be done without changing the
> programmer's abstraction (i.e. without introducing any notion of
> multithreading, and its attendant consistency problems, to the programmer).  In
> fact my friend Felix Croes recently told me that he has implemented exactly
> this kind of transparent parallelism for his own event-based dynamic
> programming language in the DGD server[1].

This is not quite correct.  It is still at the top of my TODO list,
though I have used some of the underlying ideas to implement other
features.

I should also mention that my goal is not any kind of jaw-dropping
impressive neatness, but a sober speedup through massive overkill --
throw twice as many processors at a problem, and it will be solved
somewhat faster.  Whether this is appropriate for a language like E,
I leave for the reader to decide. :-)


> Transparent parallelism for an event-based language requires the implementation
> to track side effects so that it can automatically roll-back and then retry any
> event which attempts to cause inconsistency.  If you are familiar with
> traditional transaction systems you can think of this as getting a non-blocking
> read lock on every data item you read, getting a non-blocking write lock on
> every data item you update, keeping the locks until the end of the tick, and
> then in the case that it can't non-blockingly acquire a lock it rolls back the
> entire transaction (the entire event) and then retries that event.

I'm beginning to see how the confusion about what I did and did not
(yet) do happened: in my system I have implemented rollback for error
recovery, as a language construct.

Erase all notions of locking from your mind: the type of parallelism
that you were trying to describe is called "lockless".  It is
accomplished by letting events work on copies of data rather than
the actual data itself.  When the event completes, it will try to
commit the changes it made to the actual objects.  If those objects
have not been modified in the meantime, it will succeed.  Otherwise,
the modifications made by the event will be discarded, and the
event itself will be rescheduled.  Repeatedly rescheduled events
will be executed at a higher priority, or, as a last resort, in
single-threaded mode.

In this way, a system can be created in which events run in parallel,
while giving the semblance of a continuous series of non-overlapping
events to the programmer.  There is a guarantee of progress -- either
at least one of the events currently executing in parallel will
succeed, or the next started event will.  As long as the time gained
by executing events in parallel exceeds the time lost by having to
run some events more than once, the system as a whole will be faster
than a single-threaded one.


>[...]
> Now when writing this letter I realized that it should be possible to constrain
> the parallelism so that programmers are never surprised by it.  The rules would
> be that if an event A spawns event B (in E, by sending a message), then in case
> of a collision event A always wins.  Furthermore, if event A spawns event B and
> then spawns event C, then in a collision between B and C, B always wins.

In my server, event A cannot compete with event B, because event B is
not scheduled (committed to the event table) until event A completes and
commits.

You are trying to use "transparent parallelism" in a system where
events are not discrete and non-overlapping.  Many people have tried to
do this, but they have always had to expose the parallel nature of the
system to the programmer by doing so.

Regards,
Felix Croes