US4931931A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and a system for processing logic programs
Assignee: European Computer Ind Res Centre GmbH
•
Filing: 1987-07-02
•
Granted: 1990-06-05
•
Expires: 2007-07-02
Abstract
Abstract In a method for processing logic programs--especially in Prolog-like languages--using at least one processor, which allows parallelism--also retroactively--by an existing process, called "father", creating at optional OR-parallel nodes at least one process, called "son", standing in an OR-parallel relationship to the father, a deep-binding list, called "hash-window" is created only for the newly created son in which--while processing the split-off OR-parallel branch--it performs bindings to variables commonly accessible to it and its father, called "commonly accessible variables."
Inventors
- 👤 Jean-Claude Syre
- 👤 Harald Westphal
- 👤 Max Hailperin
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-27 15:29
CPC Classifications
G; G06; G06F; G06F8/00; G06F8/30; G06F8/31; G06F8/313; G06F9/00; G06F9/06; G06F9/44; G06F9/448; G06F9/4496
Claims Analysis
Total Claims: 10
Claim 1
Independent Claim
167 words
A method of parallel processing a logic program in a computer system, said logic program including a plurality of OR-parallel nodes from which a father process may split off a first son process, said father process having variables commonly accessible by the father and the first son processes, comprising the steps of; executing said father process until a first OR-parallel node is reached; determining whether parallel processing of said first son process may occur; creating a first OR-branch-level label in said father process which identifies said first OR-parallel node; if parallel processing of said first son process may occur, creating a first son hash window in said first son process having bindings to said variables commonly accessible by said father and first son processes said bindings indicating whether each of said variables was set before said first OR-parallel node as identified by said first OR-branch-level label; and executing said first son process in parallel with said father process using the bound variables in said first hash window.
Claim 2
Independent Claim
167 words
A method of parallel processing a logic program in a computer system, said logic program including a plurality of OR-parallel nodes from which a father process may split off a first son process, said father process having variables commonly accessible by the father and the first son processes, comprising the steps of; executing said father process until a first OR-parallel node is reached; determining whether parallel processing of said first son process may occur; creating a first OR-branch-level label in said father process which identifies said first OR-parallel node; if parallel processing of said first son process may occur, creating a first son hash window in said first son process having bindings to said variables commonly accessible by said father and first son processes said bindings indicating whether each of said variables was set before said first OR-parallel node as identified by said first OR-branch-level label; and executing said first son process in parallel with said father process using the bound variables in said first hash window.
Claim 3
Dependent Claim
41 words
The method of claim 1 wherein said determining step is followed by the step of: if parallel processing of said first son process cannot occur, executing said first son process after completion of said father process using said first hash window.
Claim 4
Dependent Claim
33 words
The method of claim 1 wherein said creating step further comprises the step of: tagging the bindings to commonly accessible variables with a binding label, said binding label comprising said first OR-branch-level label.
Claim 5
Dependent Claim
35 words
The method of claim 1 wherein said method is performed for all of said plurality of OR-parallel nodes, to thereby form a plurality of OR-branch-level labels in a sequence ordered by said plurality OR-parallel nodes.
Claim 6
Dependent Claim
32 words
The method of claim 1 wherein said determining step is repeatedly performed during said executing said father process step to repeatedly determine whether parallel processing of said first son process may occur.
Claim 7
Dependent Claim
31 words
The method of claim 1 wherein said executing said father process step is preceded by the step of performing sequential processing of a logic program until said father process is reached.
Claim 8
Independent Claim
231 words
A method of parallel processing a logic program in a computer system, said logic program including a plurality of AND-parallel nodes from which a father process may split into at least left and right son processes each having a plurality of left and right son process steps, respectively, said father process having variables, comprising the steps of: executing said father process until a first AND-parallel node is reached; creating first and second hash windows for said left and right son processes respectively, said first and second hash windows in said left and right son processes having bindings to said variables commonly accessible by said father, and said left and right son processes respectively, said bindings indicating a step in said plurality of left and right son process steps at which each of said variables was set; executing said left and right son processes using the bound variables in said first and second hash windows respectively to produce left and right son solutions respectively for each of said left and right son processes for each of said commonly accessible variables; generating cross products from the left and right son solutions for each of said commonly accessible variables; and forming join cells for each of said cross products, each join cell comprising three pointers, one to each of said first and second windows and a pointer to the variables of said father process.
Claim 9
Independent Claim
231 words
A method of parallel processing a logic program in a computer system, said logic program including a plurality of AND-parallel nodes from which a father process may split into at least left and right son processes each having a plurality of left and right son process steps, respectively, said father process having variables, comprising the steps of: executing said father process until a first AND-parallel node is reached; creating first and second hash windows for said left and right son processes respectively, said first and second hash windows in said left and right son processes having bindings to said variables commonly accessible by said father, and said left and right son processes respectively, said bindings indicating a step in said plurality of left and right son process steps at which each of said variables was set; executing said left and right son processes using the bound variables in said first and second hash windows respectively to produce left and right son solutions respectively for each of said left and right son processes for each of said commonly accessible variables; generating cross products from the left and right son solutions for each of said commonly accessible variables; and forming join cells for each of said cross products, each join cell comprising three pointers, one to each of said first and second windows and a pointer to the variables of said father process.
Claim 10
Dependent Claim
91 words
The method of claim 7 wherein the step of executing said left and right son processes comprises the steps of: executing said left son process using said first hash window; determining whether parallel processing of said right son process may occur; if parallel processing of said right son process may occur, executing said right son process in parallel with said left son process using said second hash window; and if parallel processing of said right son process cannot occur, executing said right son process after completion of said left son process.
References Cited (Backward Citations)
US4811210A
Cited
US4775934A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1993-06-04 | 1993-12-04 | 1994-06-05 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1997-06-04 | 1997-12-04 | 1998-06-05 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2001-06-04 | 2001-12-04 | 2002-06-05 | $7700.00 | Window Closed / Lapsed |