US 5,471,622 AGranted

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

AssigneeParalogic, Inc.

InventorDouglas J. Eadline

Life of this patent

Estimating the term…

Loading patent…

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.

Claims19

Dependent claims

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.

7 more elements

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.

10 more elements

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.

7 more elements

Dependencies are inferred from the claim text.