Unrestricted And-Parallel Execution of Logic Programs with Dependency Directed Backtracking

1 Introduction

Logic programming has grown out of work on automatic theorem proving, and is based on the idea that logic can be used as a programming language. The widespread use of such programming languages has been hindered by what is often cited as a major disadvantage - execution can be very slow. This problem is being tackled on many fronts:

• by enhancing the control mechanism of logic program­ ming languages with various schemes of DDBT [Bruynooghe1984, Cox1985, Chang1985, Kumar1986].
• by developing special purpose machines for the execution of logic programs such as the Warren Abstract Machine (W AM) [Warren1983] and the Berkeley Programmed Logic Machine [Fagin1987, Dobry1984].
• by adapting the execution model of logic programming languages for use on a multiprocessing architecture [Li1986, Conery1987, Hermenegildo1986]

The above ideas are by no means mutually exclusive. Various parallel execution models incorporating DDBT [Kumar1986a, Dembinski1985, Borgwardt1986], have been expressed in terms of abstract machine microinstruc­ tions [Fagin1987]. But many of the parallel execution models have been criticized for expensive runtime support, forcing the computation of all solutions simultaneously, no support of "stream parallelism", etc. A common procedure call. The empty clause (denoted D) has an empty head and body.

1 This work is supported by a grant from the University of Leeds

Parallelism can be introduced in logic programming mainly in two ways. Explicit parallelism is associated with the addition of concurrent constructs resulting in extended logic languages, able to cope with processes and con­ currency so that they are suitable for applications such as systems programming (e.g. Parlog, Concurrent Prolog and GHC). Implicit parallelism involves defining parallel operational semantics equivalent to the sequential seman­ tics and without changing the syntax aiming to improve efficiency with a multiprocessor implementation. In the context of implicit parallelism, apart from low level paral­ lelism (parallel unification and parallelism in the control mechanism) the two main sources of parallelism are And­ parallelism and OR-parallelism.

And-parallelism is the attempt to resolve simultane­ ously more than one literals in the body of a program clause. The main difficulty arises from shared variables. Consider the logic program,

with goal ~f(X). X should be bound to a value that satisfies both p and q. But if p and q are executed in paral­ lel, then each will produce a different binding for X - a variable binding conflict.

One common solution to the problem of shared vari­ ables adopted in models of restricted And-parallel execu­ tion is to allow only one of the literals to bind the shared variable and postpone the solution of the others until a value has been found These models differ in their methods for detecting literal dependencies, ranging from purely static to semi-dynamic and dynamic. Once the dependencies are known (either at compile or run-time), a literal ordering strategy is adopted to schedule literal exe­ cution.

With unrestricted And-parallelism all the literals can proceed in parallel even when sharing variables. The vari­ able bindings are globally visible and tagged with the iden­ tity numbers of the processes that have created, modified or seen them. When another literal tries to assign a different value to a bound variable, these dependency tags can be used to resolve the conflict

In OR-Parallelism the main concern is a parallel definition of the search rule obtained from the parallel exe­ cution of the alternative procedure definitions. The model for unrestricted And-parallelism can be adapted to include OR-parallelism but this may increase the process creation overheads, reduce too much the granularity of a process, introduce binding environment overheads, increase the communication overheads, and force the exploration of all solutions simultaneously [Coneryl987]. For these reasons it was decided to focus on And-parallelism.

3 Unrestricted And-Parallelism

A process is an instance of a procedure in execution, allo­ cated to a distinct processor. Within each process P 1 , a goal G1 is resolved with one of the clauses in the definition of the predicate for G1· Each process proceeds indepen­ dently and communicates with the others via messages.

Suppose that a process P1 has been created to resolve the goal G1 whose predicate is Ak with a clause in the definition of Ak. If the chosen clause is A~B1 , ... , Bq and Ak 91 = A91 (i.e. Ak and A are unifiable and 91 is their m.g.u.) then the resolvent G1+1 is ~(B1 , ... , Bq)9 1 · Each BJ91, j=l, ·.. ,q is called a child of P1· Variables and vari­ able bindings may be globally visible but protected with a locking mechanism for concurrent data access [Diel1984]. Consequently, any process may read the value of a particu­ lar variable but only one process may write or update it at a time.

During forward execution, a process is created for the top goal G0 and for each of its children. A process ter­ minates when its goal is unified with a unit clause. Execu­ tion terminates when all processes terminate. But in the case of failure some of the chosen clauses within each pro­ cess must be redone (backtracking). Two types of failure can be identified:

• A shallow failure occurs when the chosen clause A~Bto··· Bq fails to resolve with Ak but there are still untried clauses in the definition of the predicate for Ak.

· A deep failure occurs when the chosen clause fails to resolve with Ak but there are no untried clauses left.

In the first case, another clause is chosen and execu­ tion continues. But in the second case, dependency infor­ mation can be used by a deeply failing process to send appropriate messages to other process to modify their choices. More formally, let t 1, ··· , tm be the finite sequence o,f terms occurring in Ak,A or in BJ, j=l, ... ,q. Let tJ = tJ9i, j = 1, ... , m. Now define the function producers from terms to ordered sets ofprocess_id's as follows:

Intuitively terms occurring in the top goal G0 or in any subgoals in the chosen clause have no producers, other­ wise if a term is modified by the substitution e, then the process-id of the current process is included in the produc­ ers of the term. In the latter case the process P1 is called the producer of the term.

When a process moves to a different alternative, it might be the case that it has produced not only ''trouble­ some'' terms but also terms that have been accepted or "consumed" by other processes. So, on undoing the vari­ able bindings of a discarded alternative, the consumer processes must be identified and be instructed to check again their choices. More formally, consider a process P 1 with goal Ak and the terms tj as before. Then P1 is the con­ sumer of a term tJ if tJ is a non-variable term and tJ e Ak. Now it is possible to define a function consumers from _··terms to sets ofprocess-id's such that

A shallow failure may occur because the current goal has inherited bindings made by other processes or simply because it cannot be satisfied. In the latter case execution trivially proceeds, but in the former, those processes block­ ing the current alternative must be "remembered" so that if at a later stage one of them changes its choice, the currently rejected alternative must be re-checked. During deep failure all the alternative clauses in a process P1 have been blocked and one of the blocking processes must change its choice. Suppose that the chosen "culprit" is PJ. Then the current alternative of PJ can be thought of as being blocked collectively by the rest of the processes causing the exhaustion of all the alternatives of P1. If one of them changes, then another alternative of P1 compatible with the current one for PJ may become available.

To summarize, there are two ways in which an alter­ native clause of P1 may be rejected. The first is direct as a result of unification failure. The other is indirect by partici­ pating in the exhaustion of all the alternatives of another process, and P1 being chosen as the one to retract its alter­ native. These notions can be captured more formally with the functions top and culprits. top is a function from ordered sets of process-id's to process-id's returning a chosen backtrack point (culprit). Now let P1 be the current process with goal +-A and the set of clauses C = { Att···' An } be the definition for the predicate of A. Then

such that t1 e A and tm e AJ, AJ e C, t1 and tm are terms failing to unify, i is the process-id of P., k is the process-id of Pk , Pk is deeply failing and top(culprits(k)) = i.

The function culprits has a dual use. Apart from being used to locate backtrack points as described above, it partly determines the "dependents" of a particular pro­ cess. A process P1 such that PJ e culprits(i) is considered as depending on PJ in the sense that if PJ changes then one (or more) of the rejected alternatives of P1 may become unifiable. But a process P1 also depends on PJ if PJ has pro­ duced variable bindings consumed by P1, so that if PJ changes its currently active alternative then P1 must be reexamined for compatibility. More formally, a function dependents can be defined from process-id's to ordered sets of process-id's as follows:

dependents(i) = {j: i e culprits(j) or i e consumers(tk)} such that iJ are process-id's, tk is a term in the goal A of process PJ, k = l, ... n, n is the number of terms in A.

Processes communicate via three kinds of messages. A KILL is sent from any process to all its children. On receiving it, a process sends a KILL message to its children and terminates. A RESET is sent from a process P1 on rejecting an alternative clause C to all process with process-id's in dependents(i). On receiving a RESET mes­ sage, a process PJ sends a KILL message to all its children, a RESET message to all processes in dependentsU) and restarts execution from its first alternative clause. A REDO is sent from a process P1 after deep failure, to the process with process-id top(culprits(i)). On receiving it, a process PJ sends a KILL message to its children, a RESET message to all in dependents(j) and moves to its next alternative clause. Consider the following example:

q(a). q(b). r(a,a). r(S, T) :- sr(S, T). sr(a,a). p(b,a). p(a,b). t(c).

The goal clause G is +-q(X), t(Z), r(Y, Y), p(X,Y). Trac­ ing the execution of the above logic program can be simplified with the following assumptions: ·

• Processes get higher process-id's in a left to right order within each clause body but a process P always has a lower process-id than its own children or the children of any of the processes created for goals in the same clause body (e.g. the process-id for sr is higher than all other process­ id's in Figure 1).
• In the case of shared variables a process with a lower process-id has precedence over any other in producing variable bindings (although in practice this will be ran­ dom).
• The function top returns the highest process-id of a set of process-id' s.

The execution of the above logic program with goal G is shown as a series of frames in Figure 1. Each frame con­ tains a forest of trees of depth 1. Each tree represents a pro­ cess with the process-id encircled to its left. The trees are rooted at the goal for the corresponding process, with each leaf being an alternative clause. The leftmost one is the currently active.

In Frame 1 P1 to P3 resolve their goals with their first alternative clauses. A shallow failure occurs in P4 due to P1 so P4 moves to its second alternative. This is blocked by P3 , a deep failure occurs and P3 is sent a REDO mes­ sage since top(culprits(4))= 3. In Frame 2 P3 receives the REDO and tries the second alternative after RESETting its dependent P4· P4 restarts and shallow fails as before but succeeds with the second alternative by binding Y to band consuming the substitution produced by P1 . Meanwhile P3 creates the child process P5 which fails deeply and sends a REDO to P4 · In the next frame P4 receives the REDO, deeply fails and sends a REDO to P3 since top(culprits(4)) = 3. P3 deeply fails and in turn sends a REDO to P1 and a KILL to P5· P1 accepts the REDO in frame 4 and moves to its next alternative after RESETting P3 and P4 and the first solution is found.

4 Circular Dependencies

If the second assumption of the previous section were relaxed, then two or more processes blocking each other could give rise to circularity problems. Consider the fol­ lowing logic program, substitutions. These make possible six different cases of direct circular dependencies. In the previous example the circularity arose out of two direct failures. It can be shown that such dependencies can be eliminated by imposing an a posteriori ordering with an overwriting rule: ·

If a process P1 receives a substitution 0 from PJ such that j > i then 0 is overwriten so that P1 becomes the producer of e. Also, if a subsequent failure occurs because of e. a RESET is sent to PJ.

The overall effect of the rule is to make "older" processes the producers, thus restoring the partial order between pro­ ducers and consumers imposed by the structure of the pro­ gram. Consider the execution of the previous logic pro­ gram under these circumstances:

P1 produces { X/1 }, P1 produces { Y /1 } as before, but eventually P1 overwrites Y and becomes the producer of { Y /2 }, sending a RESET to P1 · P1 eventually accepts the RESET, tries and rejects b(1,2) and on moving to b(2,1) the first solution is found.

An algorithmic description of the behavior of a process is -given in Program 2.

a(1,2). a(l, 1). b(1,2). b(2,1).

and the goal ~a(X, Y), b(Y ,X). Then the following scenario is possible:

Two processes P1 and P1 are created to solve the two subgoals. P1 produces the variable binding { X/1 } and P1 produces { Y /1 }. So shallow failures occur both in P1 and P1 which move to their second alternatives, send­ ing a RESET message to each other since depen­ dents(!):;::: { 2} and dependents(2):;::: { 1 }. So they both restart from their first alternative clause and the cycle may be repeated ...

In a sequential model of execution either P1 or P1 would be the producer of both X andY. Similarly, in paral­ lel execution models with variable annotations [Pereira1986] or in models of restricted And-parallelism [Chang1985,Fagin1987,Hermenegildo1986] this is not a problem as consumer processes always follow the com­ pleted execution of producers. Such solutions though, introduce a sequential element limiting the amount of parallelism and increasing the administration overheads.

There are three ways in which a process may depend on another process, i.e. (i) by direct failure, (ii) by indirect failure when receiving a REDO and (iii) by consuming

5 Opportunistic Stream Parallelism

Opportunistic stream parallelism can best be illustrated with the following logic program and the goal +-front(s(O),X,[l,2]) in the usual notation:

front(N,X,Z) :- append(X,Y,Z), length(X,N).

length{[],O). ·length([Q I R],s(N)) :- length(R,N). append([],X, X). append([U I X], Y,[U I Z]) :- append(X,Y,Z).

The predicate front(N, Y,Z) denotes the relation between a number N (in the successor notation i.e. 0 is 0, s(O) is 1, s(s(O)) is 2 etc.) and a list Y containing the first N elements of a list Z. One possible execution scenario up to the first solution is shown in Figure 3, assuming that enough pro­ cessors are available, and that variables shared by different goals but in the same argument position are bound by processes with lower process-id's (this is just a convention making more consistent the inherently sequential, frame by frame trace of the execution and is not required by the model).

In frame 1 of Fig. 3, P1 produces the substitution {X/[] } but a deep failure occurs in P1 which sends a REDO back to P1· In return, P1 sends a RESET since Pz depends on it. In the second frame, P 1 tries the second alternative and produces { X/[Ull XI], Ul/1} consumed by P1 . Note that P1 starts checking the length of the list [11 Xl] even before Xl is bound eventually by P3 (the child of P1). { Xl/[J } is consumed by the child of P1, P4 and the first solution is arrived at with { X/[1] }. In the case of multiple solutions it is assumed that all active processes participate in a "failure" when a solution is arrived at A REDO can be sent to the youngest process to resume the execution towards subsequent solutions.

··············

···············

············

Stream parallelism or data flow corouting [Clark1981, Clark1984, Fagin1987] as it is otherwise known is an alternative control strategy where a call need not be completely evaluared before execution can proceed. In the definition of front, the first subgoal can be con­ sidered as producing successively longer lists with ele­ ments from Z, and length checking if they have N ele­ ments. Conventionally, append would have to be com­ pletely evaluated before execution can move to length, but with data flow corouting it is possible for length to start checking the length of list Y even before its elements are known. Usually this is achieved with annotations designat­ ing literals as producers and consumers and with strict pro­ tocols for interleaved execution. With opportunistic stream parallelism, as shown in the example, the producers and consumers as well as the order of execution are arbitrary. As a consequence, the full potential of stream parallelism may not be exploited but on the other hand there are no administration costs.

6 Discussion

Perhaps the most serious criticism against DDBT is the expensive representation and manipulation of the depen­ dency sets. This cost can be reduced with a bit-integer representation so that a set of process-id's can be encoded as a single binary integer. Then set operations such as union and intersection can be performed with fast logical machine instructions [Drakos1988] . Decoding bit-integers into their constituent process-id's can be done efficiently ·using logarithms. The disadvantage of this encoding scheme is that very large binary numbers may be required

(2p+ 1 -1 where pis the number of activated processes).

A simulation prototype of this model is being developed in order to assess performance gains and costs, with emphasis on the large bit-integer storage costs, the extra costs of overwriting in unification, message passing overheads, etc. At a later stage the design will be expressed in terms of an abstract logic machine based on the WAM (Warren Abstract Machine [Warren1983]). The expected result is the specification of a high performance truly parallel logic machine.

Acknowledgements

I wish to thank my supervisor Richard Thomas for his sup­ port, encouragement and advice. Also thanks to Leyni.