Proceedings

The Intelligent Channel: A Scheme for Result Sharing in Logic Programs

Download BibTeX Cite

Proceedings of the Ninth International Joint Conference on Artificial Intelligence. AI Architectures. Pages 29-30.

© 1985 International Joint Conferences on Artificial Intelligence

Abstract

Full text extracted automatically from the PDF; figures, tables and equations may differ. The PDF is the version of record.

1. Introduction

The separation of !ogle and control In !ogle pro­ grams allows the programmer to write programs whose execution Is determined by the Interpreter. This charac­ teristic of logic programs spurred research towards diversifying the means for controlling the execution of !ogle programs, and towards understanding and explor­ Ing the value of parallelism In !ogle programming. Much of these e!Iorts belong to the study of AND/OR­ parallellsm, I.e., p~rallel execution of conjunctlvejdlsjunctlve goals respectively.

A brute force approach to AND /OR-parallellsm, I.e., executing every possible subgoal In a conjunctive goal has two major drawbacks: combinatorial explosion of processes and the need for many active binding environments. The latter arises due to the Interaction of shared variables In conjunctive goals.

We propose a scheme to alleviate the above diiDcultles. For slmpllclty, we demonstrate our approach with examples where atoms share a single variable. The approach Is appllcable to Horn-clause !ogle programs [1].

2. A Model for AND/OR Parallelism

We first Introduce a rriodel that serves as a unify­ Ing basis for constructing various schemes for parallel execution of !ogle programs. (see [1] for details.

OR-nodes are created when a conjunctive goal of n atoms (n> 1) Is spilt Into n subgoals, that may be exe­ cuted In parallel. When such OR-nodes are created as descendants of an AND-node, a new environment Is created at each of the newly created sons. The environ­ ment of an OR-node Is a set of variable templates v 1 , where each variable template Is a pair:

Formula not decoded

v1 Is a new private variable ld, in 1 Is the location of the current Instantiation of the variable v 1 , and out,. Is the location where the partial bindings for v 1 are stored.

The environment of AND-node which Is the direct ancestor of the new OR-nodes Is modified with an equa­ tion:

Formula not decoded

where v1 -s are all the newly created variables (Fig. La). The functional semantics of UNIF Is that of determining If the bindings for the v 1 s unify. The communication able. We refer to partial bindings so obtained as can­ didate bindings. Once a candidate binding Is chosen, only those suspended nodes whose execution Is consistent with this binding are fired. When some partial binding Is established to be a failure binding, this Information Is propagated up, and all the computations contingent on this partial binding are terminated.

For example, consider the logic program below for the goal +-P(x),Q(x).

P(x)+-P1(x). Q(a)+-Q1(a). P1(b). P(a)+-P2(a). Q(c)+-Q2(c). Q3(b). P(b)+-P3(b). Q(c)+-Q3(c).

A parallel execution of the program Is given In Fig. 1. In Fig. l.b I(P,P1) Is compatible with I(Q,Q1), I(Q,Q2) and I(Q,Q3). The path I(P,P2) Is compatible with I(Q,Q1), and I(P,P3) Is compatible with I(Q,Q3). The Interpreter selects ·a· as a candidate binding for x. In Fig. l.c 'a' was recognized to be a failure for P and subsequently for <P,Q>. Similarly, 'c' Is chosen for execution and Is marked as a failure binding for <P,Q>. As a result all the computations depending on a/x and c/x are removed yielding the snapshot In Fig. l.d. Finally, the binding 'b · /x Is selected yielding a successful parallel search, Fig. l.e.

The evident benefits that stem from maintaining compatibility of parallel executions of OR-paths are not Immediately lmplementable within the framework of existing control constructs. Below we present an algo­ rithm, termed Intelligent Channel 1 (IC-1), that com­ bines AND-parallelism with backtracking on partial bindings. IC-1 Is based on a new control construct, SELECT BINDING that restricts the parallel execution of multiple branches In an AND/OR tree to the branches compatible with the selected binding.

Algorithm Intelligent Channel 1 (IC-1)

To clarify the presentation of the algorithm we present a semi-synchronous algorithm In which expan­ sions of an OR-node are obtained simultaneously.

IC-1 consists of three parts: OR/ AND-node execu­ tion and Channel Process execution. The creation of AND/OR nodes Is as described In Section 2. OR/ AND-node executions extend the creation of AND/OR-nodes with communication among conjunctive goals, and with pruning branches based on failure bind­ Ings. The Channel Process Is delegated to the solution of MERGE-UNIF equations accumulated during a partial execution of a program and to the selection of candidate

bindings. IC-1 follows:

OR-node execution

  1. If the node Is null or solved report success to the parent and terminate. Otherwise:
  2. If the node Is enabled, expand It by generating ALL possible successors. The enabling criteria for AND/OR nodes Is the selection of a candidate binding which Is consistent with the composed substitution used to derive the node. The successors are generated as

usual, by unifying the node with the set of axioms In the program. However, the Instantiation of free variables In the node Is determined by the candidate binding selected by the CHANNEL assigned to the free variable. and Is obtained by accessing the "In" field of the variable tem­ plate. This Is how communication takes place among conjunctive goals

  1. Suspend all newly created sons until the Channel process selects a candidate binding which Is consistent with the composed substitution used to generate the new sons.
  2. Report ALL newly computed partial bindings to the Channel Process; I.e., all partial bindings obtained by a substitution of the form: t/x are reported to the CHANNEL x. For simplicity, In the first version we Insisted on mutual exclusion In Step 4 among all active AND-node processes, I.e., only one AND-node at a time communicates Its partial bindings to the CHANNEL.

AND-node execution

  1. If a node Is enabled,- create all Its OR-sons, other­ wise, suspend. Sons of an AND-node are created by splitting the conjunctive goal associated with the node Into Independent subgoals that Interface through the UNIF equation.
  2. For each new shared variable x create a shared channel data-structure denoted as CHANNEL x, and a Channel process that monitors the nondeterministic exe­ cution of Its sons. This Is achieved by setting the vari­ able template of vi to be vi:< in ,outi > for all such variables vi that emerged from the variable x. Thus, all vis that emerge from x share the same current Instan­ tiation.
  3. Propagate up final/failure bindings for the node.

Channel Process Execution

  1. For each CHANNEL check newly computed par­ tial bindings against the set of candidate-bindings, thus, performing a partial solution of the MERGE-UNIF equa­ tions.
  2. Whenever a failure binding Is discovered, ter­ minate the failure paths.
  3. Whenever the set of candidate bindings Is empty, SELECT a new candidate binding and activate all AND-nodes suspended on this binding.

ALGORITHM IC-1

Assign goal to AND-process and enable lt.

Repeat until the goal Is solved:

Execute all active AND-node processes.

Execute all active OR-node processes.

Execute all Channel processes.

4. Discussion

The major advantages of our approach are that only compatible computational paths are executed simultane­ ously, I.e., several branches of an AND/OR tree are explored In parallel while maintaining only one active environment; The degree of parallelism may be moni­ tored by modifying Step 1 In the Channel process to select multiple bindings. The combinatorial explosion that arises as a result of expanding the complete AND/OR tree Is reduced, and many useless computa­ tions are eliminated.

Step 1 In the Channel Process Is the key to complete­ ness and efficiency of IC-1. Analogous to procedure Select node In a conventional !ogle programming Inter­ preter [2], select binding Is the control component of IC-1. It Is not difficult to verify that If we select bind­ Ings In a breadth-first fashion, IC-1 Is a complete search strategy. However, If a ""depth-first""-llke selection stra­ tegy Is used completeness Is not guaranteed.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards