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

Existing Approaches to And/Or-Parallelism

The few approaches available in literature for combining and- and or-parallelism in a single framework can be roughly distinguished in three categories. The first category includes all those systems which faithfully implement Prolog semantics, guaranteeing that any Prolog program will be executed with the same external behaviour as in a sequential execution. In this category we can find only very few proposals, and most of them either have not been implemented or are still in their development stage. This is a clear indication of the challenging problems that need to be solved in order to achieve this objective. The most relevant proposals in this categories are ACE [47] and the Paged Binding Array (PBA) [43] scheme.

ACE is based on a generalization of the stack-copying scheme--described for or-parallelism in section 2.4.1. This model uses the layering scheme to and/or-parallelism described before. Computation within a team behaves exactly like a traditional and-parallel system (using recomputation). Or-parallelism is managed through stack-copying, with the novelty that the parts of the computation to be copied are spread across the stacks of the different agents belonging to the team. This makes the process of identifying the relevant parts of memory to be transferred extremely complex. Furthermore and-parallelism may lead to cases of ``trapped goals'' (i.e., computations which appear on a stack in the order opposite to that in which they will be reclaimed), which will translate in copying of garbage during stack-copying.

Paged Binding Arrays extends the binding array method for or-parallelism, and it tackles the issues of memory organization by paging the binding arrays (following a methodology similar to the paging mechanisms used in operating systems). Both these systems are in their implementation stage.

Other proposals are IDIOM [44, 43]--which extends the ACE model by allowing a restricted form of dependent and-parallelism--and Prometheus [94]--which generalizes the DDAS scheme for dependent and-parallelism by adding or-parallelism. The implementation of neither of these models has ever been attempted.

A second class of proposals is oriented to either allowing parallelism to be exploited only in programs having a certain structure, or relaxing the restriction of supporting full Prolog semantics. Various proposals have been made which allow exploitation of and/or-parallelism from pure Prolog programs, that is programs which do not contain any extra-logical operation. This is the case of the Reduced Or-Parallel Model (ROPM) [87, 88] and AO-WAM [49]. The already mentioned Andorra-I system exploits or-parallelism and determinate and-parallelism but, due to the particular nature of the Basic Andorra Model on which its computational model is based, it is unable to guarantee Prolog semantics in every case.

The third and final class of languages dealing with and/or-parallelism is characterized by the fact that the systems are based on implementing logic languages with semantics different from that of Prolog. The most relevant proposals in this area are represented by ANDOR-II [104], in which GHC is extended with don't know nondeterminism (through the so-called OR-predicates) supported using a binding stamping mechanism, and AKL [63, 50, 64], based on the notion of Concurrent Constraint Programming (the computation is based on a constraint store accessed through ask and tell operations [91]).

Web Tour

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

Tue Mar 19 14:37:09 MST 1996