[squeak-dev] parallelism models (was: Selectors with underscores)

Jecel Assumpcao Jr jecel at merlintec.com
Tue Mar 16 20:11:12 UTC 2010


Sam Adams wrote on Fri, 12 Mar 2010 11:02:53 -0500
[I'm still trying to catch up]

> The Renaissance project is going on nicely.  Dave Ungar and I
> have VMs for both Tilera Tile64 and Intel Multicore (thanks to
> our collaborator Stefan Marr of Vrije Univ).  We have also
> defined an experimental language for using our new massively
> parallel programming model concepts.  Its a variant of
> Javascript/Self, and we have a fledgling IDE developed for
> it in Squeak.  More details soon as we are hoping to open source
> the effort.

I am really looking forward to seeing that!

On the same subject, I have a three level plan for parallelism within
Squeak. One requirement is that the result should be simple enough that
I can explain it to a bright child. This rules out some very elegant
solutions that require thinking in ways that most people find hard to
learn.

=== Level 1 - Islands and promises, TeaTime

Though the "wait by necessity" model using future object (promises) from
parallel Eiffel has worked out very well for me so far, giving each
object its own thread has had advantages and problems.

http://www.merlintec.com/lsi/selfdiff.html#process

http://www.merlintec.com/lsi/tiny.html#rel1

The main issue is that any recursion, direct or indirect, will cause
deadlock with this model. The hack I used to fix this for tinySelf 1
wasn't very nice. The Eiffel solution was to only allow certain objects,
called actors, to have their own thread. You have to take care that
other objects, the passive ones, are only ever referenced by a single
actor. That makes it hard to program since it is so each to let
references to passive objects "leak" through arguments or return values.
By grouping objects into islands this worry goes away since all objects
are now equal.

One possible island model is to allow objects to migrate between them,
but I prefer to have the partition be permanent. In fact, I feel that
you should only be able to create a new object in your own island or as
the very first object in a completely new island. You wouldn't be able
to directly create objects in any other existing island (which seems
horrible in terms of security) but you could send a message to an object
in the other island and ask it to create an object there for you (if it
wants to). We could have #newHere and #newRemote with each class
implementing #new in terms of the most appropriate one (user code can
use the explicit selectors to override the class default).

You should be able to have replicas of a single island on different
machines, and TeaTime could be used to keep them in sync. An alternative
for replication is read-only islands. This would be a dynamic property
(just like in the work that Sam and Dave have done on the Tilera).

http://www.opencroquet.org/images/0/0d/2005_Teatime_Framework_Design.pdf

=== Level 2 - Concurrent Aggregates, APL/FScript

Versions of the Collection objects can be built on top of Level 1 such
that they appear to exist on multiple islands at the same time. So a
1000 element ConcurrentArray can have 100 elements each on 10 islands
and it will seem like a local object on each of those. Using the normal
APL or FScript style methods (#collect:, #detect:, etc) instead of the
lower level looping ones, you will get a significant performance boost.

> http://www-csag.ucsd.edu/teaching/cse291s03/Lectures/Concurrent%20Aggregates%20(CA).ppt

=== Level 3 - Linda, Agora, Announcements, Subscribe and Publish,
Kedama, FScript

Something like a Linda TupleSpace can be implemented using
ConcurrentAggregates. If we limit tuples to the form
("selector",?arg1,?arg2) then we will have normal Smalltalk messages
with an unspecified receiver. Though extremely limited compared to the
general Linda scheme, this would be enough for nearly all applications
in practice.

This one-to-many communication system would implement most of the
FScript funcionality not in Level 2 and could trivially host something
very similar to Kedama. If some meta information is added to the
messages going through these "agoras", this would also double as an
implementation of Annoucements. While in Linda a thread can only wait
for one kind of tuple at a time, it would be nice for an island to be
able to define a set of messages it would like to receive (so we would
have the equivalent of ALT in Occam).

http://en.wikipedia.org/wiki/Tuple_space

http://www.fscript.org/

> http://www.cincomsmalltalk.com/userblogs/vbykov/blogView?showComments=true&entry=3310034894

-- Jecel




More information about the Squeak-dev mailing list