Run-time system having nodes for identifying parallel tasks in a logic program and searching for available nodes to execute the parallel tasks

• US 5,471,622 A
• Filed: 04/20/1995
• Issued: 11/28/1995
• Est. Priority Date: 10/04/1989
• Status: Expired due to Fees

• Current Assignee: Paralogic, Inc.
• Original Assignee: Paralogic, Inc.
• Inventors: Eadline, Douglas J.
• Primary Examiner(s): Kulik, Paul V.
• Assistant Examiner(s): Harrity, Paul
• Application Number:
  US08/425,712
• Time in Patent Office: 222 Days
• Field of Search: 395/650, 395/375, 395/425, 395/600, 395/800
• US Class Current: 1/1
• CPC Class Codes: G06F 8/313 Logic programming, e.g. PROLOG programming language

Abstract

A system and method for parallel execution of logic programs on a computer network comprising two or more local-memory processors includes a logic program interpreter resident on all processors in the system. The interpreter commences execution of a logic program on one processor and, based on the results of its initial execution, generates lists of parallel-executable tasks and distributes them to other processors in the network to which it is coupled. Each processor which receives parallel tasks likewise commences execution, identification of parallel sub-tasks, and further distribution. When there are no parallel tasks at a processor or other processors available for further distributions, the task is executed sequentially and all execution results are returned to the processor which distributed the tasks executed.

Claims

1. A method of operating an arbitrary computer network to solve a logic query with respect to a logic program and distribute subqueries associated with said logic query over said network, said network comprising a plurality of nodes, each node of said plurality of nodes including a processor and local memory which is accessible by said processor in said node, and a plurality of communication channels for transmitting information between said plurality of nodes, each one of said plurality of communication channels coupling one of said plurality of nodes with at least one different node of said plurality of nodes in said network, comprising the steps of:

a. receiving said logic query with a first node of said plurality of nodes;

b. partially solving said received query on said first node to provide a received query partial solution;

c. testing said received query partial solution on said first node for OR-parallel subqueries and, if said received query partial solution includes said OR-parallel subqueries, identifying and collecting said OR-parallel subqueries on said first node which are included in said received query partial solution;

d. if said received query partial solution does not include said OR-parallel subqueries, returning to step b and continuing to solve said received query on said first node;

e. if said OR-parallel subqueries are identified in step c, determining with said first node whether a second node coupled to said first node by at least one of said plurality of communication channels is available for solution of said OR-parallel subqueries without waiting for a subquery request from the second node;

f. if said OR-parallel subqueries are identified in step c and said second node is determined to be available in step e, transmitting at least one of said identified OR-parallel subqueries from said first node to said second node coupled to said first node; and

g. if said OR-parallel subqueries are identified in step c and no second node is determined to be available in step e, sequentially solving on said first node said OR-parallel subqueries identified in step c;

wherein steps a-g are performed only at run-time, and

wherein steps b-d are repeated until said received query has been solved without identification of said OR-parallel subqueries or said OR-parallel subqueries have been identified in said received query partial solution.

2. The method of claim 1, further comprising the step of performing, at each node in said network receiving a logic query or subquery, the steps of a-g set forth with respect to said first node.

3. The method of claim 2, further comprising the steps of executing each transmitted subquery to provide subquery execution results and transmitting each subquery execution result to the node which transmitted the subquery giving rise to such result.

4. The method of claim 1, further comprising the step, if the partial solution is only one subquery having multiple terms, of checking the subquery for AND-parallelism.

5. The method of claim 4, wherein said AND-parallelism checking step includes checking each term in the subquery sequentially from left to right at run time to determine whether unbound variables of the term being checked are shared with other terms in the subquery.

6. The method of claim 5, further comprising the step, if the previously checked terms of the subquery are determined to share unbound variables with the next term in the subquery, of solving the previously checked terms of the subquery.

7. The method of claim 6, wherein said previously checked term solving step includes solving each previously checked term in the subquery as a separate subquery by transmitting the term as a subquery to an available coupled node if a coupled node is available and by solving the term sequentially if no coupled node is available.

8. The method of claim 7, further comprising the step, if said previously checked term solving step results in multiple bindings for previously checked terms, of generating and solving OR-parallel queries based on each possible combination of bindings for each unchecked term in the subquery.

9. The method of claim 5, further comprising the step of determining if the remaining unchecked terms of the subquery contains at least a predetermined number of unbound variables which appear in previous checked terms of the subquery and, if so, solving the previously checked terms of the subquery.

10. A computer implemented method of executing a logic program comprising the steps of:

a. providing an arbitrary computing network which includes a plurality of nodes, each node having a node processor and each node being coupled to at least one other node in said network by a communication channel for transmission of parallel-executable tasks and task execution results between coupled nodes;

b. executing on a node processor in a first of said plurality of nodes a first portion of said logic program to provide a partial execution result;

c. identifying with said node processor in said first node, only at run time, based on said partial execution result, tasks comprising said logic program which may be executed in parallel;

d. if said tasks which may be executed in parallel are identified in step c, determining with said first node whether a second node coupled to said first node by a communication channel is available for solution of said tasks which may be executed in parallel without waiting for a task request from the second node;

e. if said tasks which may be executed in parallel are identified in step c and said second node is determined to be available in step d, transmitting at least one of said identified tasks from said first node to said second node in said network;

f. if said at least one of said identified tasks is transmitted in step e, causing a node processor in said second node to execute said tasks transmitted in step e to provide parallel execution results; and

g. if said tasks which may be executed in parallel are identified in step c and no second node is determined to be available in step d, sequentially solving on said processor of said first node said tasks which may be executed in parallel identified in step c.

11. A computer network for solving a logic query with respect to a logic program and distributing subqueries associated with said logic query over said network, comprising:

a. a plurality of nodes including first and second nodes, each node of said plurality of nodes including a processor and local memory which is accessible by said processor in said node;

b. a plurality of communication channels for transmitting information between said plurality of nodes, each one of said plurality of communication channels coupling one of said plurality of nodes with at least one different node of said plurality of nodes in said network;

c. said first node including;

i. means receiving said logic query;

ii. means for partially solving said received query to provide a received query partial solution;

iii. means for testing said received query partial solution for OR-parallel subqueries;

iv. means, responsive to said means for testing, for identifying and collecting said OR-parallel subqueries which are included in said received query partial solution if said received query partial solution includes said OR-parallel subqueries without waiting for an OR-parallel subquery request from the second node;

v. means, responsive to said means for testing, for continuing to solve said received query if said received query partial solution does not include said OR-parallel subqueries;

vi. means, responsive to said means for testing, for determining whether a second node coupled to said first node by at least one of said communication channels is available for solution of said OR-parallel subqueries;

vii. means, responsive to said means for determining, for transmitting at least one of said identified OR-parallel subqueries from said first node to said second node if said OR-parallel subqueries are identified by said means for testing and said second node is determined to be available; and

viii. means, responsive to said means for determining, for sequentially solving on said first node said OR-parallel subqueries if said OR-parallel subqueries are identified by said means for testing and no second node is determined to be available;

wherein said computer network solves said logic query only at run-time, and wherein said means for partially solving said received query continues to solve said received query until said received query has been solved without identification of said OR-parallel subqueries or said OR-parallel subqueries have been identified in said received query partial solution.

12. The computing network of claim 11, wherein said means for sequentially solving includes an interpreted, pseudo compiled, or compiled subroutine.

13. The computing network of claim 12, wherein each node of said plurality of nodes includes means for checking a multiple termed subquery for AND-parallelism.

14. The computing network of claim 13, wherein said AND-parallelism checking means includes means for sequentially checking from left to right each term of said multiple termed subquery to determine whether variables of said term being checked are shared with terms in remaining unchecked terms of said subquery.

15. The computing network of claim 14, wherein each node of said plurality of nodes includes means for solving said previously checked terms as subqueries if a term of said multiple termed subquery being checked shares a variable with an unchecked term of said subquery.

16. The computing network of claim 15, wherein said means for solving said previously checked terms as subqueries includes means for determining whether a coupled node is available for solution of a term and if said coupled node is available, transmiting a previously checked term as a subquery to said available coupled node, and if no coupled node is available, sequentially solving said previously checked terms as subqueries.

17. The computing network of claim 16, wherein each node of said plurality of nodes includes means, operable upon an occurrence of multiple bindings in a solution of previously checked terms, for generating and solving OR-parallel queries based on each possible combination of bindings for each unchecked term in said subquery.

18. The computing network in claim 14, wherein each node of said plurality of nodes includes means for determining if said unchecked terms of said subquery contain at least a predetermined number of unbound variables which appear in previously checked terms of said subquery.

19. A computer network for executing a logic program, comprising:

a. a plurality of nodes including first and second nodes, each node of said plurality of nodes including a processor and local memory which is accessible by said processor in said node;

b. a plurality of communication channels for transmitting information between said plurality of nodes, each one of said plurality of communication channels coupling one of said plurality of nodes with at least one different node of said plurality of nodes in said network;

c. means for executing on a node processor in a first of said plurality of nodes a first portion of said logic program to provide a partial execution result;

d. said node processor on said first node including;

i. means for identifying only at run time, based on said partial execution result, tasks comprising said logic program which may be executed in parallel;

ii. means, responsive to said means for identifying, for determining whether a second node coupled to said first node by a communication channel is available for solution of said tasks which may be executed in parallel without waiting for a task request from the second node if said tasks which may be executed in parallel are identified by said means for identifying;

iii. means, responsive to said means for determining, for transmitting at least one of said identified tasks from said first node to said second node in said network if said tasks which may be executed in parallel are identified by said means for identifying and said second node is determined to be available by said means for determining;

iv. means, responsive to said means for determining, for sequentially solving said tasks which may be executed in parallel identified by said means for identifying if said tasks which may be executed in parallel are identified by said means for identifying and no second node is determined to be available by said means for determining; and

e. means for causing a node processor in said second node to execute said tasks transmitted by said means for transmitting to provide parallel execution results.