Data processing: structural design – modeling – simulation – and em – Simulating electronic device or electrical system – Event-driven
Reexamination Certificate
1998-07-01
2001-08-21
Teska, Kevin J. (Department: 2123)
Data processing: structural design, modeling, simulation, and em
Simulating electronic device or electrical system
Event-driven
C703S016000
Reexamination Certificate
active
06278963
ABSTRACT:
FIELD OF THE INVENTION
The invention relates generally to discrete-event simulation (DES) and parallel processing.
BACKGROUND OF THE INVENTION
A general model of a DES is described, and is not specifically oriented to any particular simulation application domain. DES is discussed in terms of objects and events, event inputs and outputs, and time and event execution of a DES.
Objects and Events
A DES attempts to predict or reproduce the behavior of a specified system by decomposing the behavior into a sequence of state changes. Each state change for the system, and each instant in time at which a state change would be possible, is referred to as an “event.”
In general, the simulated system consists of a collection of system components, referred to as “objects.” Objects may be static entities (permanent and predefined) or dynamic entities (created and destroyed as needed). Each object can maintain its own private state. This is referred to as “object local state.” In addition, the system may have a state that belongs to no particular object. This is referred to as a “system global state.”
Without loss of generality, an event is typically associated with a particular object. If, in a particular DES application, it is possible to have a single event associated with multiple objects, this system can be reduced to the general model by decomposing such events into a series of events for individual objects. In addition, if it is possible to have events associated with no particular object, a special “global object” is created to be the recipient of such events. Therefore, under the general model for a DES, exactly one object is considered “active” in response to an event. This object is called the “active object.”
Event Inputs and Outputs
During an event, the new state of the system is computed as a function of some subset of the DES's state, referred to as the event's “inputs.” Although the event is associated with a single object, any part of the system's state may be examined during the event's computation. This includes the object local state for this and other objects, as well as the system-global state and other information, as described in Table 1.
TABLE 1
Possible Event Inputs
object local state for active object
object local state for other objects
system global state
current event specifics
The term “event specifics” refers to a collection of information that describes the event that is to occur. It may include data that is “delivered” with the event, for instance, or it may represent the nature of the event itself. It should be noted that only causal DES's are considered. This means that event computations cannot be affected by information contained in future events and, therefore, future event specifics are not permitted as event inputs.
During the event, the state of the system may change in several ways. The primary agent of change is the active object, which is able to perform “actions.” In addition, the parts of the DES which manage the objects and the simulation global state are able to effect state changes as well. Collectively, these parts of the DES are referred to as the “simulation kernel.” The simulation kernel is essentially the infrastructure of the DES, and is typically not specific to the particular system being simulated, although it may be, in the case of a dedicated simulation.
All system state changes are referred to as “event outputs.” A list of event outputs is given in Table 2. These event outputs are essentially the significant results of carrying-out an event. It should be noted that insertion and deletion of new events to occur in the future are considered event outputs. Insertion of new events is the mechanism that feeds new work to the DES, allowing it to continue executing into the future. The set of future events is considered a special subset of the system global state, but is explicitly mentioned because it is a core state component in all DES's.
TABLE 2
Possible Event Outputs
active object local state change
other object local state change
system global state change
insertion of future events
deletion of future events
Time and Event Execution
Events in the DES are stored in a structure referred to as the “event list.” The event list acts externally as a list in the sense that the events form a sequence E[0], E[1], . . . E[n]. However, the actual underlying implementation may rely on more complex data structures to improve efficiency. Events are tagged with the simulation time at which they are scheduled to occur, or “be executed,” and the events can be extracted from the event list in order of monotonically increasing simulation time. Conceptually, the event list looks like Table 3.
TABLE 3
Time
Event
0.0
E [0]
0.1
E [1]
0.1
E [2]
1.0
E [4]
1.00000001
E [5]
1.00000002
E [6]
100.0
E [7]
At the start of the simulation, special “initial events” are inserted into the event list. As an event is executed, the active object can cause zero, one, or more additional events to be inserted into the event list, or “scheduled.” The active object can schedule a new event for an arbitrary time in the future, including the special case of the same exact simulation time as the current event.
If there is only one event left, and it generates no additional events, it is possible that the event list will become empty. This is one of several conditions causing the DES to terminate.
Simulation time is defined as the time of the event that is currently executing. Therefore, simulation time “jumps” by typically irregular intervals throughout the simulation, as shown on the time axis of FIG.
1
. Some DES's fall into a category called “time-stepped,” which means that all events are evenly separated on the time axis (i.e., E[n+1]−E[n] is a constant). This is merely a special case of the more general “event-scheduled” approach described above, which allows arbitrary spacing between events.
The events in a DES are conventionally executed serially. The conventional architecture for execution of a DES maintains the events in a structure that provides list-like access to the events. Events are removed one at a time from the list for execution. All available computing resources are devoted to the computation of that event until it is completed, at which time the next event may begin processing. The events are typically maintained in an ordered state to allow constant-time access to the earliest event when it is time to begin a new execution. Such a conventional system is called a “serial event execution” (SEE) DES. In such a conventional system, the significant sources of computation are listed in Table 4.
TABLE 4
Computation breakdown for a single event in a SEE DES
source
variable
time for extraction from the event list and
d
dispatch to event computation code
time for computations occurring in main
c
body of the event
time for insertion of new events into the
i
event list
number of new events scheduled during the
n
given event
Given the definitions in Table 4, the mean time required to completely process an event in an SEE DES is:
X=d+c+
(
n·i
)
where d is the average d, c is the average c, n is the average n, and i is the average i.
In the steady state, because the event list has a stable size, the average number of new events inserted into the event list during each event is one. Hence, X reduces to a simple sum of d, c, and i. Because the list can be ordered, d is essentially a very small constant time required to remove the head event of the list and call an appropriate handler for the head event. Further, c depends primarily on the complexity of the events being simulated, and can be assumed to be a given value for a particular class of simulation problems. Moreover, i is a function of the strategy used to manage the event list, since it requires ordered placement in the event list structure.
Optimization of d and i are straightforward problems and most conventional DES's are effi
Broda Samuel
OPNET Technologies Inc.
Sartori Michael A.
Teska Kevin J.
Venable
LandOfFree
System architecture for distribution of discrete-event... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System architecture for distribution of discrete-event..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System architecture for distribution of discrete-event... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2441023