next up previous contents
Next: Binding Arrays: Up: Overheads in Or-Parallelism Previous: Overheads in Or-Parallelism

Stack Copying:

The stack-copying approach has a very attractive feature, the fact that the local execution carried on by each agent is exactly a standard sequential execution, at least as long as this computation is limited to the ``private'' part of the tree (i.e., the computation is not backtracking back on the copied part of the execution).

Overheads appears only in three situations:

  1. after a certain number of calls, each agent should check whether any request of work sharing have been sent to him by other (idle) agents. If such request is present, then a sharing operation takes place--involving detection of the areas to be copied and the actual copy operation. This sharing operation can be time consuming. In order to contain its cost, the usual implementations
  2. whenever the execution falls back in a part of the computation that has been copied, special actions are required. Access to the copied choice points should be a critical section and the detection of no alternatives should lead to the invocation of the scheduler.
  3. the execution of side-effects requires special attention: these are order-sensitive predicates across the branches of the or-tree, and the agents should guarantee that their execution is realized in the correct order. This typically involves delaying the execution as long as the current branch is not leftmost in the or-tree.

Tue Mar 19 14:37:09 MST 1996