US4901260A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Bounded lag distributed discrete event simulation method and apparatus
Assignee: Nokia Bell Labs
•
Filing: 1987-10-28
•
Granted: 1990-02-13
•
Expires: 2007-10-28
Abstract
Abstract A discrete event simulation system that avoids all blocking and advances the simulation time in an efficient manner by treating the simulated system as a set of subsystems and simulating the subsystems concurrently. The simulation proceeds iteratively by restricting the simulation of scheduled events for each subsystem at any one time to a chosen simulated time segment (bounded lag) beginning with the lowest simulation time found among the subsystems. With each simulation iteration, an "at risk", demarcation time is evaluated based only on a subset of the subsystems that can potentially affect the simulation at the considered subsystem. Events scheduled for a time earlier than the "at risk" time are simulated. In simulating systems where some subsystems affect other subsystems only through intermediate subsystems, opaque periods can be experienced when, because of the specific process that is being simulated, such an intermediate subsystem "promises" that a particular route emanating from this subsystem would be busy for a set period of time, and thereby also "promises" that no other subsystem can use this route as a conduit to affect other subsystems. That tends to push forward the "at risk" demarcation time.
Inventors
- 👤 Boris D. Lubachevsky
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-27 07:22
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/20
Claims Analysis
Total Claims: 28
Claim 1
Independent Claim
111 words
A method for simulating behavior of a system containing interacting subsystems, where a known minimum delay exists between changes occurring at one of said subsystems and the effects of said changes on others of said subsystems, said simulating being performed with a simulation system having a plurality of interconnected processors with each of said subsystems to be simulated being simulated on one of said processors, wherein the improvement comprises: in each of said processors, a step of simulating events of subsystems, to be simulated in each of said processors, whose simulated time lies within a preselected interval following the earliest simulation time of events yet to be simulated by said processors.
Claim 2
Independent Claim
111 words
A method for simulating behavior of a system containing interacting subsystems, where a known minimum delay exists between changes occurring at one of said subsystems and the effects of said changes on others of said subsystems, said simulating being performed with a simulation system having a plurality of interconnected processors with each of said subsystems to be simulated being simulated on one of said processors, wherein the improvement comprises: in each of said processors, a step of simulating events of subsystems, to be simulated in each of said processors, whose simulated time lies within a preselected interval following the earliest simulation time of events yet to be simulated by said processors.
Claim 3
Dependent Claim
32 words
The method of claim 1 wherein each of said steps of simulating is followed by a step of advancing said earliest simulation time of events yet to be simulated by said processors.
Claim 4
Dependent Claim
39 words
The method of claim 1 wherein said step of simulating includes a step of evaluating whether a scheduled event is to be simulated, based on changes occurring at a subset of said subsystems in response to previous simulation steps.
Claim 5
Dependent Claim
18 words
The method of claim 3 wherein the subsystems belonging to said subset are dependent on said preselected interval.
Claim 6
Dependent Claim
20 words
The method of claim 3 wherein said subset is controlled by said preselected interval and said delays between said subsystems.
Claim 7
Dependent Claim
18 words
The method of claim 4 wherein said subset includes the subsystems whose delays are within said preselected interval.
Claim 8
Dependent Claim
32 words
The method of claim 3 wherein said step of evaluating computes a simulated time value of α and said step of simulating simulates events whose simulated time is not greater than α.
Claim 9
Dependent Claim
81 words
The method of claim 7 wherein said α for subsystem i, α i , is computed by ##EQU7## where d(j,i) is said delay between changes occurring at subsystem j and their possible effect on system i,d(i,j) is said delay between changes occurring at subsystem i and their possible effect on system j, and T j is the simulation time of subsystem j event to be simulated having the earliest simulation time from among all other subsystem j events to be simulated.
Claim 10
Dependent Claim
36 words
The method of claim 4 wherein said step of evaluating includes consideration of the condition that the effect of a change in one of said subsystems is blocked from propagating through another one of said subsystems.
Claim 11
Dependent Claim
102 words
The method of claim 3 wherein said step of evaluating computes a simulated time value of α and said step of simulating simulates events whose simulated time is not greater than α, where α for subsystem i, α i , is the value of α i k in the final iteration that follows the steps: ##EQU8## where T i is the time of the event in subsystem i having the earliest simulation time, β i k is an auxiliary variable value at iteration k, and d(j,i) is said delay between changes occurring at subsystem j and their possible effect on subsystem i.
Claim 12
Dependent Claim
116 words
The method of claim 3 wherein said step of evaluating computes a simulated time value of α and said step of simulating simulates events whose simulated time is not greater than α, where α for subsystem i, α i , is the value of α i k in the final iteration that follows the steps: ##EQU9## where T i is the time of the event in subsystem i having the earliest simulation time, β i k is an auxiliary variable value at iteration k,d(j,i) is said delay between changes occurring at subsystem j and their possible effect on subsystem i, and op ji is the opaque period for subsystem j in the direction of subsystem i.
Claim 13
Dependent Claim
58 words
The method of claim 4 wherein said step of evaluating computes a value of α and said step of simulating simulates events whose simulated time is not greater than α, where α for subsystem i, α i , is equal to ##EQU10## where op ij is the opaque period for subsystem j in the direction of subsystem i.
Claim 14
Independent Claim
135 words
A system for performing discrete event simulation of a system having a plurality of interacting subsystems, comprising: a plurality of blocks, each block simulating a preselected subsystem and including an event list associated with said preselected subsystem and means for maintaining information concerning the state of said preselected subsystem, and α, where α is an estimate of the earliest simulated time for which modification parameters can be modified by neighboring subsystems, where said modification parameters include the information in said associated state registers and the events in said associated event; and a controller system for repetitively performing simulation of events in said event lists and re-evaluating the values of said α and of T floor , where T floor is the lowest event time of scheduled events to be simulated by said plurality of blocks.
Claim 15
Independent Claim
135 words
A system for performing discrete event simulation of a system having a plurality of interacting subsystems, comprising: a plurality of blocks, each block simulating a preselected subsystem and including an event list associated with said preselected subsystem and means for maintaining information concerning the state of said preselected subsystem, and α, where α is an estimate of the earliest simulated time for which modification parameters can be modified by neighboring subsystems, where said modification parameters include the information in said associated state registers and the events in said associated event; and a controller system for repetitively performing simulation of events in said event lists and re-evaluating the values of said α and of T floor , where T floor is the lowest event time of scheduled events to be simulated by said plurality of blocks.
Claim 16
Dependent Claim
38 words
The system of claim 14 wherein said controller system comprises a plurality of interconnected controllers communicating with said blocks, with each controller repetitively performing simulation of events in said event lists and re-evaluating the value of said α.
Claim 17
Dependent Claim
127 words
The system of claim 14 wherein said controller system comprises an event evaluation processor associated with each of said blocks, connected to its associated event list, its associated means for maintaining state information, and to neighboring blocks, which are blocks that simulate subsystems that directly affect, or can be affected by, said preselected subsystem, where said event processor performs simulation of events in said associated event list and modifies said associated event list and the event lists of said neighboring blocks, as required by said simulation of events; a synchronization processor associated with each of said blocks, connected to its associated event list and means for maintaining α, for developing values of said α; and means for interconnecting said plurality of event evaluation processors and synchronization processors.
Claim 18
Dependent Claim
46 words
The system of claim 16 wherein said synchronization processor develops a value of α based on values of T j , from a preselected subset of said subsystems, where T j is the simulation time of the event in subsystem j having the earliest simulation time.
Claim 19
Dependent Claim
31 words
The system of claim 16 where each of said synchronization processors develops a value of α for its block based on a consideration of potential changes in neighbors of its block.
Claim 20
Dependent Claim
10 words
The system of claim 17 wherein said consideration is iterative.
Claim 21
Dependent Claim
13 words
The system of claim 18 wherein said consideration takes into account opaque periods.
Claim 22
Dependent Claim
29 words
The system of claim 16 where each of said synchronization processors develops a value of α for its block based on a consideration of opaque periods of its neighbors.
Claim 23
Dependent Claim
43 words
The system of claim 14 wherein said controller system comprises a plurality of controllers communicating with said blocks, with each controller repetitively performing simulation of events in said event lists and re-evaluating the value of said α; and means for interconnecting said controllers.
Claim 24
Dependent Claim
60 words
The system of claim 21 wherein said means for interconnecting receives a T i from each of said event lists, where T i is the simulated time of the event to be simulated in said event list having the earliest simulation time, develops T floor which is min (T i ), and returns T floor to each of said controllers.
Claim 25
Independent Claim
238 words
A system for performing discrete event simulation comprising: a plurality of blocks equal in number to the number of simulated interacting subsystems, each block simulating a preselected subsystem and including an event list associated with said preselected subsystem and registers for storing information concerning T floor , α, β and state information of said preselected subsystem; means for interconnecting said plurality of blocks; an event processing controller associated with each of said blocks, connected to its associated event list, its associated state registers, and to neighboring blocks, which are blocks that simulate subsystems that directly affect, or can be affected by, said preselected subsystem, where said event controller performs simulation of events in said associated event list and modifies said associated event list and the event lists of said neighboring blocks, as required by said simulation of events; and a synchronization controller connected to its associated event list, T floor , α, and β registers, and also connected to said means for interconnecting, for developing values for said T floor , α, and β registers, where T floor is the earliest simulated time of an event to be simulated found in any of said event lists, α is an estimate of the earliest simulated time for which the information in said associated state registers or the events in said associated event list can be modified by neighboring subsystems, and β is an auxiliary estimate employed in evaluating α.
Claim 26
Independent Claim
238 words
A system for performing discrete event simulation comprising: a plurality of blocks equal in number to the number of simulated interacting subsystems, each block simulating a preselected subsystem and including an event list associated with said preselected subsystem and registers for storing information concerning T floor , α, β and state information of said preselected subsystem; means for interconnecting said plurality of blocks; an event processing controller associated with each of said blocks, connected to its associated event list, its associated state registers, and to neighboring blocks, which are blocks that simulate subsystems that directly affect, or can be affected by, said preselected subsystem, where said event controller performs simulation of events in said associated event list and modifies said associated event list and the event lists of said neighboring blocks, as required by said simulation of events; and a synchronization controller connected to its associated event list, T floor , α, and β registers, and also connected to said means for interconnecting, for developing values for said T floor , α, and β registers, where T floor is the earliest simulated time of an event to be simulated found in any of said event lists, α is an estimate of the earliest simulated time for which the information in said associated state registers or the events in said associated event list can be modified by neighboring subsystems, and β is an auxiliary estimate employed in evaluating α.
Claim 27
Independent Claim
211 words
A system for performing discrete event simulation comprising: a plurality of blocks equal in number to the number of simulated interacting subsystems, each block simulating a preselected subsystem and including an event list associated with said preselected subsystem and registers for storing information concerning T floor , α, and state information of said preselected subsystem; means for interconnecting said plurality of blocks; an event processing controller associated with each of said blocks, connected to its associated event list, its associated state registers, and to a subset of said blocks, where said event controller performs simulation of events in said associated event list and modifies said associated event list and the event lists of said neighboring blocks, as required by said simulation of events; and a synchronization controller connected to its associated event list, T floor and, α, registers, and also connected to said means for interconnecting, for developing values for said T floor , and α, registers, where T floor is the earliest simulated time of an event to be simulated found in any of said event lists, and α is an estimate of the earliest simulated time for which the information in said associated state registers or the events in said associated event list can be modified by neighboring subsystems.
Claim 28
Independent Claim
211 words
A system for performing discrete event simulation comprising: a plurality of blocks equal in number to the number of simulated interacting subsystems, each block simulating a preselected subsystem and including an event list associated with said preselected subsystem and registers for storing information concerning T floor , α, and state information of said preselected subsystem; means for interconnecting said plurality of blocks; an event processing controller associated with each of said blocks, connected to its associated event list, its associated state registers, and to a subset of said blocks, where said event controller performs simulation of events in said associated event list and modifies said associated event list and the event lists of said neighboring blocks, as required by said simulation of events; and a synchronization controller connected to its associated event list, T floor and, α, registers, and also connected to said means for interconnecting, for developing values for said T floor , and α, registers, where T floor is the earliest simulated time of an event to be simulated found in any of said event lists, and α is an estimate of the earliest simulated time for which the information in said associated state registers or the events in said associated event list can be modified by neighboring subsystems.
References Cited (Backward Citations)
US4204633A
Cited
US4527249A
Cited
US4644487A
Cited
US4636967A
Cited
US4751637A
Cited
US4680784A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1993-02-12 | 1993-08-14 | 1994-02-13 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1997-02-12 | 1997-08-14 | 1998-02-13 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2001-02-12 | 2001-08-14 | 2002-02-13 | $7700.00 | Window Closed / Lapsed |