next up previous contents
Next: Problems in Combining And- Up: Multiple Parallel Systems Previous: Multiple Parallel Systems

And- Under Or-parallelism


Figure 9: Reuse vs. Recomputation

As evident from figure 9, adopting reuse has some advantages, since the amount of work performed is considerably reduced (each subgoal is computed in its entirety only once). On the other hand, the reuse of subgoals creates many problems when order sensitive predicates are present in the subgoals. Reuse, in fact, does not guarantee anything regarding the relative order of execution of the various subgoals. Furthermore, in presence of predicates causing side-effects (e.g., write, read, etc.) the semantics of the program may change due to reuse--a program which performs one write has a different semantics from one performing five write operations. For these reasons (and others [45]), Reuse has not been considered as a viable approach to and/or-parallelism, and its use is limited to some old proposals (e.g., the Reduce Or-parallel Model by Kalé and Ramkumar [88]). Furthermore, the use of recomputation is substained by experimental studies [96], showing that, on average, real-life Prolog programs contain a limited amount of recomputation--e.g., because the programmer is aware of the structure of the search space and writes his program in such a way to reduce the amount of backtracking.

Tue Mar 19 14:37:09 MST 1996