Strategies

The splitting trees show what kind of parallel problems that dynamic evaluation generates: from a given splitting point, each case is independent of the others, and consequently may be evaluated by a separate thread of execution.

Most common parallel libraries (including RPC, Linda, and PVM) assume that a parallel task can be described by a function, plus some arguments, and the parallel execution simply obtains a processor, branches to the function and when the function returns, marks itself as finished in some way. Unfortunately, dynamic evaluation is not suited to these kinds of model, as the parallel work is the remainder of the computation (ie. a continuation) rather than a well defined subpart of it.

In the previous implementation of dynamic evaluation, one starts the computation (for example the function dynamicRank) with a call to the function allCases. This initiates the computation. The process may then reach a point where a split is needed (the question a=1 in the rank algorithm). At this point it picks one branch ( ) saving the other possibility onto a list ([a=1 ]). Execution continues until the process is complete (and we have the result 2 for the case ). The next stage takes the first condition on the list (a=1) and re-evaluates the function ( dynamicRank) using those conditions, possibly generating more list entries. When this list has been exhausted, a complete set of solutions has been found. This mechanism walks every possible path in the splitting tree, from the root node down to each leaf. This mechanism therefore evaluates the first part (up to a splitting point) of the function redundantly (in fact, if n answers are produced, the execution up to the first splitting point will have been repeated n times).

There are two possible solutions to this problem:

• to save the initial part preceding the split, to choose one branch, and re-instantiate the initial part in order to get the other branch when the first one is complete.
• to start two independent threads of computation at a splitting point,

The first of these may be implemented as a continuation save and restart, and the second by using a primitive similar to fork. Note that for the program to be useful, any independent threads must be re-synchronised and the results combined. This makes the two roughly equivalent, and gives us a way of describing fork as a continuation saving device.

Naturally, for any mechanism to be judged useful, the expense involved in either taking a continuation or forking a process should be less than the expense of re-evaluating the program up to the point at which the split occurs.