US5537593A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method for solving enumerative search problems using message passing on parallel computers
Assignee: FMC Corp
•
Filing: 1993-05-24
•
Granted: 1996-07-16
•
Expires: 2013-05-24
Abstract
Abstract A method and apparatus for solving enumerative search, graph search or combinatorial optimization problems using parallel digital processors. Various nodes, representing decision points in the problem, are distributed among a plurality of digital processors. The nodes are expanded and bound values for the nodes are communicated among the processors. Non-productive solution parts are pruned to eliminate unnecessary expansion of the state space. Updated bound values are communicated in both directions along the search graph and a plurality of messages are developed to provide communication in a loosely coupled processor environment.
Inventors
- 👤 Marc D. Diamond
- 👤 Jeffrey C. Kimbel
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-01 08:44
CPC Classifications
G; G06; G06F; G06F15/00; G06F15/16; G06F15/163; G06F15/173; G06F15/17337
Claims Analysis
Total Claims: 12
Claim 1
Independent Claim
143 words
A method for solving enumerative search problems using message passing on parallel processors wherein a value of a root node is to be ascertained, the root node being dependent upon a plurality of interrelated successor nodes, having tips with directed edges comprising the steps of: generating the interrelated successor nodes to develop a state space; expanding said state space through expansion of the tips with directed edges of the interrelated successor nodes; distributing the interrelated successor nodes among a plurality of digital processors; assigning nodes to at least one of said processors by means of a hashing function; expanding said assigned nodes utilizing an expansion queue; generating application specific criteria; pruning excess nodes in compliance with said application criteria utilizing a message queue; and eliminating generation of said state space by passing results of said pruning towards and away from the root node.
Claim 2
Independent Claim
143 words
A method for solving enumerative search problems using message passing on parallel processors wherein a value of a root node is to be ascertained, the root node being dependent upon a plurality of interrelated successor nodes, having tips with directed edges comprising the steps of: generating the interrelated successor nodes to develop a state space; expanding said state space through expansion of the tips with directed edges of the interrelated successor nodes; distributing the interrelated successor nodes among a plurality of digital processors; assigning nodes to at least one of said processors by means of a hashing function; expanding said assigned nodes utilizing an expansion queue; generating application specific criteria; pruning excess nodes in compliance with said application criteria utilizing a message queue; and eliminating generation of said state space by passing results of said pruning towards and away from the root node.
Claim 3
Dependent Claim
19 words
The method according to claim 1 wherein said step of pruning excess nodes includes utilizing re-evaluate bounds upward message.
Claim 4
Dependent Claim
20 words
The method as defined in claim 1 wherein said step of pruning excess nodes includes utilizing re-evaluate bounds downward message.
Claim 5
Dependent Claim
79 words
The method as defined in claim 1 wherein the pruning of excess nodes includes a process of avoiding generation of portions of said state space that can be rapidly eliminated from consideration as a solution to the enumerative search problem and further each of said portions of said state space is associated with a node which when pruned becomes inactive and therefore does not send and does not receive message sand the node is removed from said message queue.
Claim 6
Independent Claim
210 words
A method for solving enumerative search problems of the homogenous type using message passing on parallel processors wherein a value of a root node, dependent upon a plurality of interrelated successor nodes having tips with directed edges is to be determined and wherein said successor nodes are either maximizing or minimizing said method comprising the steps of: generating the interrelated successor nodes to develop a state space; expanding said state space through expansion of the tips of the interrelated successor nodes; distributing the interrelated successor nodes among a plurality of digital processors; assigning nodes to at least one of said processors by means of a hashing function; expanding said assigned nodes utilizing an expansion queue; generating application specific pruning criteria; pruning excess nodes in compliance with said application specific criteria by utilizing a message queue; developing bounds for each node wherein an upper and a lower bound are determined and said upper and lower bound become continuously constrained through time; utilizing global bounds to curtail the size of the search problem by broadcasting said global bounds to all the parallel processors; comparing said upper and lower bounds against each other to ascertain a best bound; and broadcasting said best bound among the successor nodes in the plurality of digital processors.
Claim 7
Independent Claim
210 words
A method for solving enumerative search problems of the homogenous type using message passing on parallel processors wherein a value of a root node, dependent upon a plurality of interrelated successor nodes having tips with directed edges is to be determined and wherein said successor nodes are either maximizing or minimizing said method comprising the steps of: generating the interrelated successor nodes to develop a state space; expanding said state space through expansion of the tips of the interrelated successor nodes; distributing the interrelated successor nodes among a plurality of digital processors; assigning nodes to at least one of said processors by means of a hashing function; expanding said assigned nodes utilizing an expansion queue; generating application specific pruning criteria; pruning excess nodes in compliance with said application specific criteria by utilizing a message queue; developing bounds for each node wherein an upper and a lower bound are determined and said upper and lower bound become continuously constrained through time; utilizing global bounds to curtail the size of the search problem by broadcasting said global bounds to all the parallel processors; comparing said upper and lower bounds against each other to ascertain a best bound; and broadcasting said best bound among the successor nodes in the plurality of digital processors.
Claim 8
Dependent Claim
72 words
The method as defined in claim 5 wherein said step of pruning excess nodes includes passing results upwardly towards and downwardly from the root node by means of re-evaluate bounds upward and downward message and said upwardly passed bounds can be changed only when the root node receives a "re-evaluate bounds upward" message; and said downwardly passed bounds can be changed only when the root node generates a "re-evaluate bounds downward" message.
Claim 9
Dependent Claim
73 words
The method as defined in claim 5 wherein said step of assigning nodes includes using said hashing function provision of a state of a given node as an input and the processor assigned to the node being generated as an output; each of the processors hosting a certain subset of the nodes in the search problem to thereby maintain values pertaining to a pair of upper and lower bounds for each node hosted.
Claim 10
Independent Claim
177 words
A method for solving enumerative search problems using message passing on parallel processors wherein a value of a root node is to be ascertained, the root node being dependent upon a plurality of interrelated successor nodes, having tips with directed edges said method comprising the steps of: generating the interrelated successor nodes to develop a state space; expanding said state space through expansion of the tips of the interrelated successor nodes; distributing the interrelated successor nodes among a plurality of digital processors; assigning nodes to at least one of said processors by means of a hashing function; expanding said assigned nodes utilizing an expansion queue; generating application specific pruning criteria; pruning excess nodes in compliance with said application utilizing a message queue; preserving remaining nodes and backing up values toward the root node; expanding the remaining nodes within the digital processors; generating bounds for said remaining nodes expanded in the digital processors; determining which of said expanded remaining nodes lie outside the solution path; and removing the expanded remaining nodes which are not on the solution path.
Claim 11
Independent Claim
177 words
A method for solving enumerative search problems using message passing on parallel processors wherein a value of a root node is to be ascertained, the root node being dependent upon a plurality of interrelated successor nodes, having tips with directed edges said method comprising the steps of: generating the interrelated successor nodes to develop a state space; expanding said state space through expansion of the tips of the interrelated successor nodes; distributing the interrelated successor nodes among a plurality of digital processors; assigning nodes to at least one of said processors by means of a hashing function; expanding said assigned nodes utilizing an expansion queue; generating application specific pruning criteria; pruning excess nodes in compliance with said application utilizing a message queue; preserving remaining nodes and backing up values toward the root node; expanding the remaining nodes within the digital processors; generating bounds for said remaining nodes expanded in the digital processors; determining which of said expanded remaining nodes lie outside the solution path; and removing the expanded remaining nodes which are not on the solution path.
Claim 12
Dependent Claim
49 words
The method as defined in claim 8 wherein said assigning nodes among the digital processors further includes having each of the processors hosting a certain subset of the nodes in the search problem to maintain values pertaining to a pair of upper and lower bounds for each node hosted.
References Cited (Backward Citations)
US4218582A
Cited
US4210962A
Cited
US4583164A
Cited
US4495559A
Cited
US4466060A
Cited
US4575798A
Cited
US4719571A
Cited
US4949243A
Cited
US4918621A
Cited
US4860201A
Cited
US4837735A
Cited
US4982340A
Cited
US5008882A
Cited
US4905144A
Cited
US5170393A
Cited
US5072379A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-07-16 | 2000-01-15 | 2000-07-16 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-07-16 | 2004-01-15 | 2004-07-16 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-07-16 | 2008-01-15 | 2008-07-16 | $7700.00 | Window Closed / Lapsed |