Next: Binding Arrays:
Up: Overheads in Or-Parallelism
Previous: Overheads in Or-Parallelism
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:
- after a certain number of calls, each agent should check whether any request of
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
- try to share as much as possible at once, in order to reduce the frequency of
- adopt incremental copying techniques, where only the difference between the
two agent states is copied;
- try to parallelize the sharing operation.
- 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.
- 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