Edit Parallelism

Title:

Last edited: 2:09:08 am on 21 June 2004 by c-24-19-39-179.client.comcast.net

A very interesting parallelism model was adapted from some experiments in Eiffel to the Merlin project. It is called "wait by necessity" and is described in "process model" on this page: *http://www.lsi.usp.br/~jecel/selfdiff.html*. A test implementation of this idea was made in tinySelf 1 (see *http://www.lsi.usp.br/~jecel/tiny.html*).

This model was broken in that recursive methods would deadlock. So this was tested for and the deadlock broken by forcing a different execution order.

The main problem is finding the boundaries of an object's "state". In the Eiffel system this was solved by separating regular passive objects from the active ones. The programmer should only share active objects, while passive ones would be subcomponents (part of the state) of active ones.

That is not orthogonal enough for my taste, so a related model would be to separate objects into groups where execution is sequential within a group and parallel between groups. A group would be like an isolated virtual machine, with its own memory and processor. Objects can point directly at other objects in their own group, but have to go through proxies to point to objects from other groups. You don't have to worry about which is which when sending a message, but a message to a remote object has the "wait by necessity" semantics described in the page linked above.

Many groups can be multiplexed on a single physical processor, but a group can't be split between processors or nodes. A group can easily migrate from one node to the other, however.

Since any object in a group can point to any object in another group, we don't have the strict active graph with passive subgraphs organization of the Eiffel solution. At least not in theory. In practice, we must make a decision about where to create a new object when cloning an old one. Suppose that the 'copyHere' message causes the new object to belong to the same group as the sender, while the 'copyAsActor' message would create an entirely new group in which the new object would be the lone member. By having different kinds of objects implement 'copy' as either one, we would get by default an object graph very much like the one in Eiffel. The difference is that we can override the default as needed.

Each group is supported by a special object called "mux". This uses a set of helper objects (meta-objects) representing resources (memory, processing power, communication channels, etc...) and shares these resources among the objects of its group. Some of the objects in a group can themselves be muxes, each supporting their own group. So we have a tree structure rooted in a mux representing the actual hardware. In the case of multiple processors we have a forest instead of a tree.

An example: the lowest level mux might use the timer hardware to give 50ms slices in a round robin policy among the four objects currently in its group. Each of these objects might be a mux itself, with the first one splitting each of the 50ms slices it gets among its objects using, for example, a first deadline first policy.

One kind of meta-object complicates this picture slightly: pools. They create virtual resources by joining those of several other meta-objects. A virtual disk, for example, made up in RAID style from a few smaller ones.

Send e-mail alerts to these addresses upon next save: