Patent US4844957A successfully refreshed from Google Patents.
Patent US2392183A successfully refreshed from Google Patents.
Patent US5375074A successfully refreshed from Google Patents.
US5375074A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Unboundedly parallel simulations
Assignee: AT&T Inc
•
Filing: 1990-01-23
•
Granted: 1994-12-20
•
Expires: 2010-01-23
Abstract
Abstract Efficient simulation is achieved by employing a highly efficient ordering of the events to be simulated. Specifically, the events to be simulated are grouped into layers and the layers are simulated in order. Each of the layers consists of events that are either strictly independent of the other events in the layer or are dependent of other events in the layer but possess a particular attribute. That attribute is one that permits the use of an associative operator. This operator allows the simulation of N events in O(log N) computation iterations.
Inventors
- 👤 Albert G. Greenberg
- 👤 Boris D. Lubachevsky
- 👤 Israel Mitrani
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-03 14:21
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/46; G06F9/54; G06F9/542; G06F30/00; G06F30/20
Claims Analysis
Total Claims: 39
Claim 1
Independent Claim
129 words
A method for simulating on a computer events of a system comprising the steps of: selecting a cluster of events of said system that includes primarily events that are related to each other through an associative operator, an operator being associative when the same result is reached whether the operator is applied to a first intermediate result and event C, or to event A and a second intermediate result--where the first intermediate result is obtained by applying the operator to events A and B, and the second intermediate result is obtained by applying the operator to events B and C; simulating the events of said cluster of events; and returning to said step of selecting when at least some of said events of said system have not been simulated.
Claim 2
Independent Claim
129 words
A method for simulating on a computer events of a system comprising the steps of: selecting a cluster of events of said system that includes primarily events that are related to each other through an associative operator, an operator being associative when the same result is reached whether the operator is applied to a first intermediate result and event C, or to event A and a second intermediate result--where the first intermediate result is obtained by applying the operator to events A and B, and the second intermediate result is obtained by applying the operator to events B and C; simulating the events of said cluster of events; and returning to said step of selecting when at least some of said events of said system have not been simulated.
Claim 3
Dependent Claim
17 words
The method of claim 1 wherein said step of selecting excludes events that belong to another cluster.
Claim 4
Dependent Claim
58 words
The method of claim 1 wherein said step of simulating, when simulation information about events in other clusters is required, utilizes the simulation information of said events in other clusters developed by preceding steps of simulating, and makes assumptions about the simulation information of said events in other clusters to which said step of simulating was not applied.
Claim 5
Dependent Claim
67 words
The method of claim 3 wherein said steps of selecting, simulating and returning form a sequence of cluster simulations, and at least a portion of said sequence is repeated until the simulation information for all of the events in repetition k of said sequence, where k is an integer, is the same as the simulation information for all of the events in repetition k-1 of said sequence.
Claim 6
Independent Claim
125 words
A method for simulating on a computer events of a system comprising the steps of: selecting a layer of events of said system that includes mostly event groups that are related to each other through an associative operator, an operator being associative when the same result is reached whether the operator is applied to a first intermediate result and event C, or to event A and a second intermediate result--where the first intermediate result is obtained by applying the operator to events A and B, and the second intermediate result is obtained by applying the operator to events B and C; simulating said layer of events; and returning to said step of selecting when at least some of said system events have not been simulated.
Claim 7
Independent Claim
125 words
A method for simulating on a computer events of a system comprising the steps of: selecting a layer of events of said system that includes mostly event groups that are related to each other through an associative operator, an operator being associative when the same result is reached whether the operator is applied to a first intermediate result and event C, or to event A and a second intermediate result--where the first intermediate result is obtained by applying the operator to events A and B, and the second intermediate result is obtained by applying the operator to events B and C; simulating said layer of events; and returning to said step of selecting when at least some of said system events have not been simulated.
Claim 8
Dependent Claim
17 words
The method of claim 5 wherein said step of selecting excludes events that belong to another layer.
Claim 9
Dependent Claim
58 words
The method of claim 5 wherein said step of simulating, when simulation information about events in other clusters is required, utilizes the simulation information of said events in other clusters developed by preceding steps of simulating, and makes assumptions about the simulation information of said events in other clusters to which said step of simulating was not applied.
Claim 10
Dependent Claim
67 words
The method of claim 5 wherein said steps of selecting, simulating and returning form a sequence of cluster simulations, and at least a portion of said sequence is repeated until the simulation information for all of the events in repetition k of said sequence, where k is an integer, is the same as the simulation information for all of the events in repetition k-1 of said sequence.
Claim 11
Dependent Claim
50 words
The method of claim 5 wherein the event groups that are related to each other through an associative operator are such that the groups can be ordered and the events of a group can be simulated from the events of some previous groups with the aid of said associative operator.
Claim 12
Dependent Claim
28 words
The method of claim 5 wherein said system comprises a plurality of interacting nodes and each of said layers comprises primarily the events of one of said nodes.
Claim 13
Dependent Claim
27 words
The method of claim 5 wherein said system comprises a plurality of interacting nodes and each of said layers consists the events of one of said nodes.
Claim 14
Dependent Claim
26 words
The method of claim 5 wherein said step of simulating a layer includes a step of merging the events of other layers that affect said layer.
Claim 15
Dependent Claim
49 words
The method of claim 5 wherein said step of simulating a layer includes the steps of merging the simulated events of layers that affect said layer and that have been previously simulated; and merging assumed events of layers that affect said layer but which have not been previously simulated.
Claim 16
Dependent Claim
67 words
The method of claim 13 wherein said steps of selecting, simulating and returning from a sequence of cluster simulations, and at least a portion of said sequence is repeated until the simulation information for all of the events in repetition k of said sequence, where k is an integer, is the same as the simulation information for all of the events in repetition k-1 of said sequence.
Claim 17
Independent Claim
83 words
A method for discrete event simulation on a computer of system events occurring in a plurality of nodes in a multi-node system, where events in one node correspond to a time interval having more than one time sample and affect events in another node, comprising the steps of: selecting the events of a node; simulating events of the selected node; and returning to said step of selecting until the last node in said order has been simulated and all events have been simulated.
Claim 18
Independent Claim
83 words
A method for discrete event simulation on a computer of system events occurring in a plurality of nodes in a multi-node system, where events in one node correspond to a time interval having more than one time sample and affect events in another node, comprising the steps of: selecting the events of a node; simulating events of the selected node; and returning to said step of selecting until the last node in said order has been simulated and all events have been simulated.
Claim 19
Dependent Claim
14 words
The method of claim 15 wherein said simulating comprises simulating departure times of jobs.
Claim 20
Dependent Claim
18 words
The method of claim 15 wherein said simulating is carried out with the aid of an associative operator.
Claim 21
Dependent Claim
21 words
The method of claim 17 wherein said associative operator includes a "max" function which selects the larger of said two inputs.
Claim 22
Dependent Claim
21 words
The method of claim 15 wherein said step of selecting includes a step of formulating a simulations order of said nodes.
Claim 23
Dependent Claim
47 words
The method of claim 19 wherein said step of formulating a simulations order is based on an acyclic directed graph representation of said system, which graph comprises at least one node from the set of nodes that includes strongly connected component nodes and non-strongly connected component nodes.
Claim 24
Independent Claim
116 words
A method for discrete event simulation on a computer of system events occurring in a plurality of nodes in a multi-node system, where events in one node correspond to a time interval having more than one time sample and affect events in another node, comprising the steps of: formulating a simulations order for simulating said nodes; designating said the first node in said order as the simulation node; simulating events scheduled for said simulation node; designating a new simulation node by selecting the node that follows, in said order, the current simulation node; and returning to said step of simulating until the last node in said order has been simulated and all events have been simulated.
Claim 25
Independent Claim
116 words
A method for discrete event simulation on a computer of system events occurring in a plurality of nodes in a multi-node system, where events in one node correspond to a time interval having more than one time sample and affect events in another node, comprising the steps of: formulating a simulations order for simulating said nodes; designating said the first node in said order as the simulation node; simulating events scheduled for said simulation node; designating a new simulation node by selecting the node that follows, in said order, the current simulation node; and returning to said step of simulating until the last node in said order has been simulated and all events have been simulated.
Claim 26
Dependent Claim
128 words
The method of claim 21 wherein said step of formulating a simulations order comprises: attaining a directed parent graph to represent the interaction of said plurality of nodes; creating an acyclic directed graph from said directed parent graph by representing each strongly connected component in said parent graph by node; selecting a node in said acyclic directed graph that is dependent on the fewest number of other nodes in said acyclic directed graph; assigning the selected node to a list when the selected node is nonstrongly connected component node; developing a sublist when the selected node is a strongly connected component node and appending said sublist to said list; and returning to said step of selecting until the last node in said acyclic directed graph has been selected.
Claim 27
Independent Claim
157 words
A method for discrete event simulation on a computer of system events occurring in a plurality of nodes in a multi-node system, where events in one node correspond to a time interval having more than one time sample and affect events in another node and where the termination of the appearance on independent events at one or more of the system nodes is not known, comprising the steps of: selecting a super-group of events; for events within the selected super-group, executing a simulation procedure including selecting a cluster of events from among the events within the selected super-group, which cluster includes primarily events that are related to each other through an associative operator; simulating the events of said cluster of events; and returning to said step of selecting when at least some of said events of said system have not been simulated; selecting another super-group of events; and returning to said step of executing a simulation procedure.
Claim 28
Independent Claim
157 words
A method for discrete event simulation on a computer of system events occurring in a plurality of nodes in a multi-node system, where events in one node correspond to a time interval having more than one time sample and affect events in another node and where the termination of the appearance on independent events at one or more of the system nodes is not known, comprising the steps of: selecting a super-group of events; for events within the selected super-group, executing a simulation procedure including selecting a cluster of events from among the events within the selected super-group, which cluster includes primarily events that are related to each other through an associative operator; simulating the events of said cluster of events; and returning to said step of selecting when at least some of said events of said system have not been simulated; selecting another super-group of events; and returning to said step of executing a simulation procedure.
Claim 29
Dependent Claim
20 words
The method of claim 5 wherein said step of simulating develops an order of simulating the events in said layer.
Claim 30
Dependent Claim
17 words
The method of claim 24 wherein said order is related to priority of the events being simulated.
Claim 31
Dependent Claim
23 words
The method of claim 24 wherein said order is related to constraints of hardware in which said method of simulating is carried out.
Claim 32
Dependent Claim
24 words
The method of claim 24 wherein said order is related to memory constraints of hardware in which said method of simulating is carried out.
Claim 33
Dependent Claim
21 words
The method of claim 1 wherein said step of selecting selected the events of a cluster based on said associative operator.
Claim 34
Dependent Claim
20 words
The method of claim 1 wherein said step of simulating simulates the events with the aid of said associative operator.
Claim 35
Dependent Claim
36 words
The method of claim 1 wherein said step of selecting selected the events of a cluster based on said associative operator, and said step of simulating simulates the events with the aid of said associative operator.
Claim 36
Independent Claim
98 words
A method for simulating events of a system with an available number of processors comprising the steps of: dividing the events to be simulated into layers having defined interface borders between the layers where at least in some of the layers one of the events in a layer is causally related to at least one other event in the layer; selecting an order of simulation for simulating said layers; and simulating the layers in a seriatim manner, where each step of simulating a layer completely simulates the layer by employing essentially all of the available number of processors.
Claim 37
Independent Claim
98 words
A method for simulating events of a system with an available number of processors comprising the steps of: dividing the events to be simulated into layers having defined interface borders between the layers where at least in some of the layers one of the events in a layer is causally related to at least one other event in the layer; selecting an order of simulation for simulating said layers; and simulating the layers in a seriatim manner, where each step of simulating a layer completely simulates the layer by employing essentially all of the available number of processors.
Claim 38
Dependent Claim
40 words
The method of claim 31 wherein said step of dividing the events to be simulated creates clusters of events where each cluster of events of said system includes primarily events that are related to each other through an associative operator.
Claim 39
Dependent Claim
57 words
The method of claim 31 wherein said step of dividing the events to be simulated creates clusters of events where each cluster of events of said system includes events within a lower border and an upper border of the simulated time where the lower border and the upper border encompass events of more than one particular time.
References Cited (Backward Citations)
US4306286A
Cited
US4930102A
Cited
US4751637A
Cited
US4866605A
Cited
US4814978A
Cited
US4942615A
Cited
US4901260A
Cited
US4914612A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1997-12-19 | 1998-06-20 | 1998-12-20 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2001-12-19 | 2002-06-20 | 2002-12-20 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2005-12-19 | 2006-06-20 | 2006-12-20 | $7700.00 | Window Closed / Lapsed |