A Sequential View of AND-Parallelism Through Partial AND-Processes

1 Introduction

In process based systems AND-parallelism is usually realized by introducing producer/consumer relationships among clause literals and their corresponding OR-processes. Therewith independent literals act as parallel producers of variable bindings, which will be consumed by dependent literals in subsequent steps. Dividing clause literals into producers and consumers shows the advantage of avoiding binding conflicts since shared variables can have only one producer at a time. Realizing the producer/consumer approach to AND-parallelism, however, requires a sophisticated synchronization scheme to guarantee correct process interaction. Especially in the backward phase of clause evaluation [Chang, 1985, Conery, 1987], a lot of activities have to be controlled, ranging over message passing, reordering literals, cancellation and creation of processes. Moreover, to complicate things, the whole synchronization job is settled on a single AND-process in most systems. But loading a process with so much work may seriously affect its message passing capacity and thus tum it into a communication bottleneck. With all these drawbacks in mind one might question, whether producer/consumer parallelism can actually be realized in a better arranged manner. Obviuosly it would help a system designer if he could view parallel clause execution in terms of a well known and easy to understand sequential system. Offering such a view through partial AND-processes, a new kind of process, will be the subject of this paper.

The paper starts by introducing some notational framework. After that, the principles of process based program execution will be illustrated by the hand of AND/OR-trees. Two fundamental search strategies for such trees will be discussed then, before the special strategy giving AND-parallelism a sequential touch is explained in section four. Finally we pick up the task of producing output substitutions through intelligent backtracking in order to demonstrate how partial AND-processes solve a typical implementation problem of AND-parallelism.

2 Notation

For the rest of the paper the reader is assumed to be familiar with the basic terminology of logic programming as introduced by Lloyd [1984], for example. Some supplementary notation used subsequently is given below.

Variables will be named by letters x, y, z, u, and v. Letters a, b, c, and d denote constants, and f, g, h function symbols. An expression can be a term or literal. If e represents an expression, Var(e) is the set of all variables occuring in e. Two expressions e1 and e 2 are called dependent if Var(e 1 ) n Var(e 2 ) "# 0 . Substitutions are named by Greek letters like a, a, andy; a substitution a= {xtftp····xJtn}, n ~o. binds variable xi to the term ti, !!:; i $ n. Composition e 1 oe 2 of two substitutions is defined as e 1° e2(e) = e 1 (e2(e)) for every expression e. Finally, the number of elements of a finite set M will be denoted by IMI.

3 Program Execution by AND/OR-processes

Every logic program - started with some goal - implicitly defines an AND/OR-tree [Kowalski 1979], which makes program execution a matter of searching all the answers to the user's query. In this connection an execution strategy for logic programs naturally turns into a search strategy, which tells a system how to traverse the tree under consideration. To illustrate the effects of different search strategies, we now describe the behaviour of some fictitious process systems when executing the first clause from figure 1.

Figure 1 Example program

Based on AND/OR-trees, processes created during program execution constitute an AND/OR-process tree. By the way, viewing processes as nodes of a tree allows us, for instance, to talk of the AND-father of a process, just saying the father is an AND-process. Conventions for drawing process trees are shown in figure 2.

As the special strategy coming up with partial AND-processes will be both, sequential and parallel in nature, the single components of this mixture will be considered first

Sequentia{ Searcfi StrateBY

The sequential component within our mixed strategy is a left to right one comparable to that used in standard Prolog systems. Figure 3 mirrors its effect on execution of clause p(x,y) f-- q(x), r(y), s(x), which- for the sake of simplicity- is assumed to be called with the empty input eo= 0.

The process tree resulting from our left to right strategy shows an AND-process, named P[{p(x,y)}l(q(x),r(y),s(x)}], which is created to execute our example clause. In order to solve this task, the AND-process initially starts a descendant OR-process Pq(x) to compute solutions for e 0 q(x) = q(x). Having found the answer y1 = {x/a}, process Pq(x) produces its output substitution e1 = 'Y1 ° eo= {x/a} and then creates a descendant OR-process Pr(y) to solve literal e1r(y) = r(y). On the basis of our example program, Pr(y) subsequently finds the answer y2 = { y/c} and computes the output e 2 = y 2 o e 1 = {x/a, y/c}. Next, OR-process Ps(x)' created for e2s(x) = s(a), will find y 3 =0 as a solution and send substitution e 3 =y 3 oe2 = (x/a,y/c} to the AND-process above. Finally, e 3 represents a solution for the whole program clause.

ParaUe{ Searcli Strate.DY

In contrast with a sequential strategy, using a parallel one causes some body literals to be executed in parallel. Figure 4 shows the effect of a somehow extremely parallel strategy since it solves all body literals simultaneously.

According to the parallel strategy, all body literals are executed independently by corresponding OR-processes. Process Pq(x)' for instance, works on 9 0 q(x) = q(x) and produces the output substitution 9 1 = {x/a}. In the same way, processes Pr(y) and Ps(x) compute answers for 9 0 r(y) and 9 0 s(x), which we assume to be 9 2 = { y/c} and 9 3 = { x/b}, respectively. Yet, from the point of the AND-process above, e 1' 92 and e3 represent only partial solutions for its own problem, which is to find answers for whole program clause. Therefore, having received the single solutions, an AND-process has to join them to a complete one, provided values of shared variables are consistent with each other. Consistency of variable bindings, however, is not guaranteed. Just look at processes Pq(x) and Ps(x) from above, which bind variable x to non unifiable values.

To get around the consistency problem, most systems [Chang, 1985, Conery, 1987, DeGroot, 1984] synchronize OR-processes by making them producers or consumers of variable bindings. Since shared variables can have only one producer at a time, no conflicting bindings will arise. But as mentioned before, producer/consumer parallelism often leads to a rather intricate interplay of processes. The intention of this paper, therefore, is to give a more perspicuous view of AND-parallelism and - by doing so - convey new ideas of how typical implementation problems can be solved in a more understandable and efficient manner. A new type of process, called partial AND-process, will play a central role thereby.

4 Partial AND-processes

As their name already indicates, partial AND-processes bear some likeness to normal AND-processes, but differ in the scope of the problem to deal with. Whereas an AND-process has to solve all the literals of a clause body, a partial AND-process works on a subset of body literals only. Such a subset just corresponds to a group of independent literals selected for parallel execution. Whereas literals within a group will be solved in parallel, group execution is purely sequential in nature. Consequently, we get a Prolog like clause execution on the level of p(artial)AND-processes and their corresponding literal groups (see upper half of figure 5).

In regard of a more detailed description of what happens in figure 5, we first of all claim that special routines for dependency checking and literal grouping are available to AND- and pAND-processes. Due to lack of space, we simply view these routines as black boxes and describe their behaviour only superficially. Again, for the execution of our program clause we assume its input substitution 9 0 being empty.

The AND-process P[{p(x,y)) I{ q(x),r(y),s(x))] starts clause execution by determining literal dependencies within the environment 9 0 · This practically means testing, whether Var(9oL) n Var(9oL') ""- 0 for all pairs (L,L') of distinct body literals. As a result we get two alternatives for grouping independent literals, namely G 1 = { q(x),r(y)} and G 2 = { s(x),r(y)}. Next, the AND-process decides to group q(x) and r(y) together, and upon that, has them executed by a pAND-process P[(q(x),r(y))l(s(x)}]. This one starts OR-processes Pq(x) and Pr(x) to solve literals 9 0 q(x) and Sof(Y) in parallel. On the basis of our example program from figure 1 the answers Y1={x/a} and y2 = {y/c} will be computed and send to P[(q(x),r(y)}l(s(x)}]. Having received both substitutions, the pAND-process produces the output substitution 9 1 = (y 1 uy2)·9 0 = {x/a,y/c} and immediately creates its son P[ (s(x)} 10] with input substitution 9 1 . In order to solve 9 1 s(x) = s(a) the pAND-son starts an OR-process Ps(x)' from which it receives the answer substitution y3 = 0. Finally, P[ (s(x)} I 0] computes its output e2 = 'Y3·9o = {x/a,y/c} and transfers it via message to the AND-process above.

The last example showed partial AND-processes acting as producers and consumers of variable bindings. Yet, unlike Conery's model [Conery, 1987], bindings are not produced for single literals, but for whole groups of literals. To identify the literal group a pAND-process is executing we have used the notation P[rJil] with r and n being sets of clause literals. Separation by a stroke characterizes r as the the literal group actually executed by the process, whereas literals in n have to be solved by other pAND-processes in subsequent steps. Due to this separation, literals in r get an active and literals in n a passive character from the point of P[nn].

Definition 4.1

Suppose Pis an AND- orpAND-process named P[nn]. Then .9fL(P)= r is the set of active and PL(P)= n the set of passive literals of P.

Active literals and their corresponding OR-processes can be regarded as producers of variable bindings, which are gathered by a pAND-process to built its own output substitutions. However, that there are several OR-processes contributing to an output, is completely hidden to the pAND-son, which consumes it as an input substitution. From the point of a consuming son, its pAND-father together with all its active literals simply appears as a single module just producing output substitutions.

5 Producing Output Substitutions

Solutions produced by pAND-processes will be sent as output substitutions to the consuming process, which itself receives them as input substitutions. In general, sending of solutions is demand driven, since new output/input substitutions are only produced when explicitly requested by the consumer. Output substitutions generated by pAND-processes are characterized below.

Definition 5.1

Let P be a pAND-process with input substitution 9in and its active literal set 5'1.L(P) = {L1' ... ,Ln}, n ~ 1. Further, let 51' .. ,5n be the sets of answer substitutions computed by descendant OR-processes, i.e. 5j contains all answers found for 9inLj, 1 sj sn.

Then 05(P,9in) = {Join(Yp····'Yn)·9miYjE5j, 1sjsn) is the set of output substitutions of P, where Join(Yp····'Yn) = y 1 u ... U 'Yn·

The definition above points out that every output substitution produced by a pAND-process consists of a constant and variable part. The first one corresponds to the input substitution 9in and the latter to a tuple (Yp····'Yn) of answers computed by descendant OR-processes. Therefore, given a fixed input substitution 9in, each output substitution 9out = Join(Yp····'Yn)·9in is practically determined by the tuple (Yl'····'Yn). Moreover every such tuple in its tum may be identified with a tuple of natural numbers. Simply realize that the elements of a setS can be numbered in some way, for J

instance, in the order they are computed by the corresponding OR-process. Conversely, to get an output substitution from a tuple (mp····mn) of element numbers, just take· the m 1 -th element from 51' the ~-th element from 5 2 , ... , the mn-th element from 5n, join them together and produce a 9out through composition with 9in .

This strong relationship between number tuples and output substitutions allows us to make production of output substitutions more perspicuous by reducing it to a problem of generating tuples of natural numbers. For solving the generation problem we simply adopt the nested loop model introduced by Conery [1987]. A pAND-process will always start tuple generation with the initial tuple ( 1 , ... , 1 ), subsequently changing its components as if they were variables of nested for-loops, i.e. the rightmost components _run faster than the ones to the left. Note, if component i, 1 sis n, is increased, all components j, i <j s n, are reset to 1. As number tuples of the kind mentioned above directly determine output substitutions, they are called output tuples from now on.

As said before, production of output tuples and substitutions is demand driven, i.e. a pAND-process produces a new output only when explicitly requested by its pAND-son. Such a request always goes along with a backtracking between partial AND-processes. What's behind this type of backtracking will be demonstrated below with a slightly modified version of our example program.

1. p(x,y) +- q(x), r(y), s(x), t(y)
2. q(a)+-­ (4) r(c) +-­ (6) s(b) +--
3. q(b)+-

To execute clause (1) with input substitution 9 0 = 0, an AND-process, named P[(p(x,y)}l{q(x),r(y),s(x),t(y)}], will be started initially. Let us assume q(x) and r(y) to be grouped together after dependency checking and executed by a pAND-process P[{q(x),r(y))l{s(x),t(y)}]. For solving 9 0 q(x) and 9 0 r(y), OR-processes Pq(x) and Pr(y) will be created subsequently, which compute the answers y 11 = {x/a). y 12 = { x/b) for the first, and y 21 = { y/c), y 22 = { y/d) for the second literal. Suppose that the pAND-process receives the substitutions in the order y 1 1' y 12 and y 2 1' y 22 , respectively. According to the nested loop model, the initial tuple ( 1, 1) is used to produce the first output substitution 9( 1 , 1 )=Join(y 11 ,y 21 )·9m= {x/a,y/c). Next, the process creates its pAND- son P[{s(x),t(y))l0] with input 9( 1 , 1 )" This son in return starts the OR-processes Ps(x) and Pt(y)' the fust of which detects that there are no matching clauses for its literal 9( 1 , 1 )s(x) = s(a). Figure 6 shows a snapshot of the process tree Process Ps(x) reports its failure to P[{s(x),t(y)}l0], which immediately reacts by requesting a new input substitution from its pAND-father P[{q(x),r(y)}l{s(x),t(y)}] . Based on the nested loop model, the father generates the next output tuple (1,2) and sends the corresponding substitution 9(1,2> = Join(YwY22) ·9in = (x/a,y/d} to the requesting pAND-son. However, 8(1·2) will obviously lead to a failure, too, because the value of variable x remaines unchanged by the new substitution. So, our pAND-process generated just another failure tuple.

Definition 5.2

Let P be a pAND-process with output tuple t and corresponding output substitution 9t. Tuple tis called a failure tuple if 9~ is unsolvable for . some active literal of the pAND-son of P. Else it will be called a success tuple.

To avoid repeated generation of failure tuples- like (1,1) and (1,2) in the example above - a pAND-process must incorporate some kind of intelligent backtracking [Conery, 1987, Woo and Choe, 1986], or equivalently, use some form of intelligent tuple generation. This should, for instance, allow process P[{q(x),r(y))l{s(x),t(y)}] of figure 6 to generate tuple (2,1) directly without regarding (1 ,2). Tuple (2, 1) and its corresponding output substitution 8( 2 , 1 ) = Join(y 12 ,y 21 )·9in = {x/b,y/c} bind x to a different value, with which clause execution succeeds finally.

The question now is, how tuple generation can be made intelligent. To achieve this aim, a pAND-process P obviously needs some kind of information about what was wrong with its actual output substitution. Within the parallel execution scheme presented here, this information will be supplied by the

Definition 5.3

Let P be a pAND-process named P [fliT]. An active literal L e r is called a failure literal if its corresponding OR-process fails to compute any answer substitution. The set of all failure literals of P is denoted by '.f L(P). For an AND-process P, we set '.JL(P)= r by definition.

Our example process P[{s(x),t(y)}l0] from figure 6, for instance, would report s(x) as a failure literal to its pAND-father P[{q(x),r(y)}l{s(x),t(y)}] . Now the father process can conclude that it must produce a new binding for variable x, for changing the value of y would definitely not repair the failure and thus lead to another backtracking. As a new value for x can only be achieved by changing the first component of the actual tuple (1,1), we automatically know (1,2) to be another failure tuple. This is confirmed by looking at its corresponding output substitution 8( 1 , 2 ) = {x/a, y/d}, which changes the value of y, but not that of x.

In order to determine all its failure literals a pAND-process proceeds as follows: After descendant OR-processes have been created for every active literal, it enters a kind of test state. There the process waits until all OR-sons have acknowledged by sending a success or failure message. The literal of a failing OR-process will be recorded as a failure literal thereby. Note, a pAND-process will wait forever if one of its OR-sons is caught in an infinite loop. By the way, waiting for all OR-processes to acknowledge allows us to handle so called multiple failures [Conery, 1987, Woo and Choe, 1986] in a rather simple manner. Further, collecting all failure literals before backtracking results in a more intelligent version since information about failures gets more comprehensive. This information will be used to repair the failure by generating a new output tuple, the corresponding substitution of which binds at least one variable in each failure literal to another value. Such tuples and substitutions will be called failure relevant from now on.

In terms of our nested loop model the whole problem of generating tuples intelligently may now be stated as: What loop variable, or equivalently, what tuple component should be changed in order to make its corresponding output substitution relevant to the failure ? To answer this question we first of all introduce a successor relation on AND- and pAND-processes. Definition of the relation is based on the process tree of figure 7, which shows an AND-process P[r 0 1rro1 with descendant pAND-processes P[r 1 1II 1 ], .·. , P[rniiin]. Note, I\= 0 .

Definition 5.4

Let P 0 , Pp···· Pn, n 2: 1, be the processes of figure 7 with 1i = P[r;ln;] and 0 ~ i ~ n. The successor of 1i is defined by succ('li) = 1j with j = i+ 1Illil!l n+ 1. Similarly we define the predecessor of 1j by pred(1j) = 1i iff succ('li) = 1J· Instead of succ(1? and pred(P), we also use the notations Psucc and Ppred· respectively.

Next, we relate active literals of a pAND-process to active literals of its successor. Literals of the first will be treated as producers, literals of the second as consumers of variable bindings. In addition, a special function is introduced for mapping active literals to tuple components and vice versa.

Definition 5.5

Let P be a pAND-process with input substitution e, Lp E JlL(1? and Lc E JlL(Psucc).

1. consumer(L~ = (L' E JlL(Psucc) I Var(9L~ n Var(9L') *- 0} .
2. producer(Lc) = (L' E JlL(1? I Var(9Lc) n Var(9L') *- 0}.
3. c)# is a bijective mapping from JlL(1? to { l, ... ,n}, n = IJIL(P)I. For a set r of literals we define #r = {#L I Ler}.

To get an idea of intelligent tuple generation, imagine a pAND-process P with input substitution 9 0 = 0 and JIL(P}= (p(x),q(y),r(z)}, where #p(x)= 1, #q(y)=2 and #r(z) = 3. In addition, let (2,3,3) be the actual failure tuple of P and FL = (s(x,y),u(z)} the set offailure literals reported by its successor. First of all P computes producer(L) for every L E FL resulting in producer(s(x,y)) = (p(x),q(y)} and producer(u(z)) = (r(z)} . Mapping producer literals to tuple indices by the hand of function#, we get #producer(s(x,y)) = (1 ,2} and #producer(u(z))= (3}. Now, set {1,2} expects us to change the first or second component of (2,3,3), in order to produce an output substitution which binds a variable in s(x,y) to another value. Accordingly, set ( 3} demands the third component to be changed in order to get a new binding for u(z). Alltogether, both requirements can be satisfied by increasing the second tuple component, because this will automatically reset the third component to 1. Hence, the resulting tuple (2,4,1) causes producer literals q(y) and r(z) to contribute to the new output substitution, and all in all, modified variable bindings will be brought to their consumers s(x,y) and u(z).

In general, the simple algorithm below will be used by pAND-processes to determine the tuple component to be changed after backtracking.

Al~orjthm for Chan~jn~ Tuvle Comnonents

Let P be a pAND-process P[nn] and FL the set of failure literals reported by its successor. Further, for a literal L E FL let maxL = max { #L' I L'e producer(L)}.

if producer(L) *- 0 for every L E FL

then i := min{maxLILeFL};

"change the i-th tuple component"

else "stop tuple generation".

In the example above we had FL = {s(x,y), u(z)} . Computing maxL for every failure literal L results in max < ) s x,y = max{l,2} = 2 and maxu(z) = max{3} = 3. Using the algorithm for changing tuples, we get the 2-nd component, 2 = min { 2,3}, as the one to be changed.

In general, changing the i-th component of a tuple usually means increasing its value by one. However, this may be impossible sometimes because all members of the answer setS; have already been considered, i.e. the value of the i-th component corresponds to the number of elements in S;. Should this happen, a pAND-process reacts by looking for the first component to the left of i which can be changed. If there is such a component, its value will be increased therewith resetting all components to its right to 1. After having produced the corresponding output substitution, the process enters a kind of forward state, in which dependency checking and literal grouping is done again based upon the new substitution. If the resulting literal group is different from that of the actual pAND-son, the son process will be cancelled and a new one created. Otherwise no cancelling is necessary and the substitution is directly sent to the actual pAND-son. Upon that, all consumer literals receiving a new input substitution will be resolved, i.e. their corresponding OR-processes are initialized and restarted with the new bindings. Finally, having restarted its OR-sons, a pAND-process enters the test state mentioned before, waiting again for success or failure messages.

Over against this, if a pAND-process should fail to fmd an increasable tuple component, no more output tuples can be generated and tuple generation is finfished. A pAND-process, which is unable to produce new output substitutions, initiates backtracking to its own predecessor. In this manner backtracking eventually arrives at the AND-process above, telling it that clause execution is done.

At the end of this section some aspects of our backtracking scheme should be discussed:

The nested loop model for tuple generation shows the advantage of being easy to implement. But its simplicity must be paid for in some sense as tuple generation may become incomplete if OR-processes compute infinite answer sets. One might expect this a serious drawback since many tuples will never be considered. Yet, generating all of infinitely many tuples is impossible, anyway. The only disadvantage is that successful output substitutions are probably not produced if a pAND-process is stuck in an infinite answer set. Fortunately loops of this kind may be stopped through intelligent backtracking.

Requesting a new output/input substitution through backtracking is generally not restricted to pAND-processes, but also used by an AND-process to obtain all solutions for its clause. This is simply done by backtracking to its own predecessor immediately after having received an input substitution from it. The head literal of the clause will be reported as the failure literal thereby.

6 Conclusions

Implementing AND-parallelism in the producer/consumer style requires a sophisticated synchronization scheme for controlling OR-processes, which work on body literals independently. Especially handling failures through intelligent backtracking makes clause execution a rather complicated problem, the solution of which often results in a confusing interplay of processes in practice. To make AND-parallel clause execution more perspicuous and therefore easier to implement, this paper conveyed a sequential view of AND-parallelism. Based on a heterogeneous execution strategy, which is sequential and parallel in nature, independent literals are grouped together and treated as a single module. Literal groups are solved sequentially by partial AND-processes, which in their turn start descendant OR-processes for executing group literals in parallel. The main advantage resulting from the sequential part of the execution strategy is that clause execution may be tackled in a simple Prolog like manner. As an example, the backtracking scheme presented here bears some similarity to the naive right to left method of Prolog, except that it is made intelligent on the basis of producer/consumer relations. Multiple failures of OR-processes can be handled efficiently by partial AND-processes, all the more since information about failing literals is gathered to achieve a more intelligent backtracking version. Apart from this, the load on AND-processes will be eased significantly, allowing them to react to incoming messages promptly.