Lecture Notes for Simulation

Outline

An entity is a set of activities that reacts to events.
- Particular events trigger particular activities.
- The activities can be general.
An entity's attributes set maintains the entity's state.
- Attributes can be related to the system or to the simulation.
Entities may be permanent or transitory.
- A permanent entity exists throughout the simulation.
- A transitory entity exists for only part of the simulation.
- Events control transitory-entity lifetimes.
This sounds like object-oriented programming, doesn't it?
- Yes, it does.

An event's attribute set maintains the attribute's state.
- The attributes distinguish one event from another, and specialize individual events.
An event indicates a change in the model's state.
- How the model's state changes is determined by the entities reacting to the event.
A system event can be traced back to the system being modeled.
A program (or simulation) event is related to the model or the simulation.
The model is responsible for handling external events.

An event schedule is the set of all events that have created but not yet issues.
- Created but not yet issued events are pending events.
The simulation clock determines when pending events are issued.
- Each event has a trigger-time attribute.
- A pending event is issued when its trigger time is at most the simulated time.
  event trigger time <= simulated time.
- The details are determined by the model's time management.

Event scheduling inserts pending events into the event schedule.
- Both event scheduling and issue testing should be efficient (that is, should have sub-linear complexity).
Non-contingent events are pending events which cannot be modified or removed from the event schedule.
Contingent events can be modified or removed from the event schedule.
- Cancelling a heart-beat alarm signal, for example.
More generally a decision event conditionally change model state.
- A non-decision event always changes model state.

Event sequencing (or synchronization) actually issues pending events.
Event sequencing must order simultaneous events.
- The orderings determined by the associated system.
- Respecting contingent-event chains makes ordering difficult.
  - Simultaneous alarm and alarm-cancel events.
Decision events have to be resolved too.

An event list data structure implements the event schedule.
The operations needed are
- Inserting into the list (always ordered),
- Removing from the list (ordered and unordered),
- Searching through the list (extremes and arbitrary), and
- (Possibly) indexing into the list.
These should also be scalable, fast, and efficient.

A vector of event buckets, useful for fixed-increment time management.
- The vector index is an interval number i.
- The vector element is a set of events occurring during the ith interval.
- Treating the vector as a circular list saves space, but requires a future horizon.
Linked lists, ordered by trigger time.
- Singly or doubly linked, although deleting's easier with double links.

A def(heap) is a binary tree in which the parent value is larger than either child value.
- Heaps have weaker value constraints than do binary search trees.
- Weaker constraints == more efficient implementation.
The top of the heap is the nearest future event.

A skip list is a probabilistic, link-list-based implementation of a balanced binary tree.
- Balanced binary trees have logarithmic behavior, but are complicated.
- Ordered linked lists are linear, but are simple.
- Indexing the linked list results in logarithmic search behavior, but insertions and deletions are a pain.
- Probabilistically assigning index nodes trades-off potentially bad behavior for simple implementation.

How should entities and events be brought together?
- Events can know about entities (event active),
- Entities can know about events (entity active), or
- a matchmaker can bring them together.
An active event refers to the entities that are interested in the event.
- Subtype polymorphism is useful here, assuming entities aren't too widely differing.
An active entity watches for events in which it is interested.
- Distributed simulations using publish-subscribe.
A matchmaker (or dispatch software) knows about events and entities and pairs them.

The principle simulation data types define events and entities.
- Typically entities define activities.
The principle simulation data structure is the entity list.
- Some form of balanced tree.
Events can select entities, entities can select events, or a matchmaker can pair them.

This page last modified on 15 February 2005.