Dependent And-parallelism:

this occurs when and-parallelism is allowed between subgoals which share unbound variables, even in presence of possible binding conflicts (i.e., different computations try to bind differently the same variables).

 

Only few proposals have been made in the literature to tackle this class of parallelism, and this is mainly related to the complexity of the problem. In particular, very few approaches have been described which are capable of maintaining Prolog semantics, while the large majority of the others introduce new languages with different semantics, in which exploitation of parallelism becomes simpler and more efficient.

Prolog Implementations:

in order to support Prolog semantics, a model for dependent and-parallelism needs to guarantee that the bindings to variables are produced in the correct order (i.e., in sequential Prolog order). This can be seen in the following example. Let's consider the program containing the three facts p(1), q(2), and q(1), and the query <- p(X) & q(X). In a sequential execution p(X) is executed first, producing a binding , and successively the subgoal q(1) will be completed. On the other hand, if q(X) is executed first, then it will produce a binding and successively the subgoal p(2) will fail, leading to an unsuccessful execution. To tackle this problem within and-parallel systems, the notions of producer and consumer of a variable have been introduced. At every step of the execution, for each shared variable we identify exactly one producer (i.e., the subgoal which has the ``right'' to bind the variable). All the other subgoals accessing the shared variable are only allowed to read the value--i.e., they are consumers. A consumer accessing an unbound variable will suspend its execution (since it is not allowed to bind it), waiting either for a binding to be produced or for its turn to become itself a producer for such variable. The producer and consumer status is determined according to Prolog's operational semantics. Thus, the producer for a variable is the leftmost subgoal in the goal chain accessing such variable. All the other goals containing the same variable are designated as consumers. A consumer becomes a producer for a variable when the designated producer finishes execution without binding the shared variable and the consumer in question is the leftmost among all potential consumers of the shared variable. The (few) models presented in the literature dealing with dependent and-parallelism [94, 76, 108, 31] (of which DDAS [94, 93] is the most relevant) can be simply distinguished depending on the way in which the role of producer/consumers is computed and handled.

New Languages :

the complexity of supporting full Prolog semantics in presence of dependent and-parallelism--especially concerning its interactions with don't know non-determinism--lead many researchers to consider simplified frameworks in which the exploitation of this form of parallelism could be realized without suffering excessive overheads.

The most interesting approach is represented by the class of Committed-choice Languages (CCL) [92]. The languages belonging to this family (e.g., GHC [112], Parlog [15], Concurrent Prolog [92], KL1 [67]) are characterized by the fact that producer/consumer roles are statical (e.g., through mode declarations), and don't know nondeterminism has been eliminated (i.e., selection of a clause will not leave choice points behind).

These restrictions guarantee the possibility of efficiently implementing dependent and-parallelism--as confirmed by the practical experience [23]. Nevertheless, these languages implement a semantic considerably different from that of Prolog (e.g., no don't know nondeterminism).

Web Tour

• Laboratory for Logic and DBs
• Penny - Parallel AKL