Run-time system having nodes for identifying parallel tasks in a logic program and searching for available nodes to execute the parallel tasks
First Claim
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, andwherein 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.
0 Assignments
0 Petitions
Accused Products
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.
-
Citations
19 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, andwherein 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9)
-
-
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. - View Dependent Claims (12, 13, 14, 15, 16, 17, 18)
-
-
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.
-
Specification