Terminating parallel discrete event simulations

This thesis analyzes the simulation termination problem of implementing global termination conditions and collecting output measures in discrete event simulations. With regard to parallel simulations, this problem is inherently more difficult than the classic termination detection problem for two reasons. The first is that parallel simulation processes are often written as nonterminating; the second is that the decision to terminate can not be independently made by each process contributing to the simulation. A specification of a solution to the termination problem is developed as a sequence of stepwise refinements using UNITY, and proofs are given to demonstrate that each refinement satisfies the preceding specification. Termination conditions are categorized based on stability (if a condition is stable, once it becomes true it will remain true at all future times) and illustrated using space-time diagrams. A discussion is presented of how to implement termination conditions that are a combination of stable and nonstable conditions. This thesis makes two major contributions. The first is an algorithm to implement global termination conditions and to collect the corresponding output measures in discrete event simulation. The specifications and algorithm given in this thesis are architecture-independent and apply to sequential as well as synchronous and asynchronous parallel discrete event simulation algorithms. The second is the development of a generalized, formal framework in which to reason about simulation algorithms. The techniques used in this thesis to solve the simulation termination problem may be applied to solve other problems arising in parallel simulation.

Name thesis:degree_name

Master of Science

Level thesis:degree_level

masters

Discipline thesis:degree_discipline

Computer Science

Department dc:contributor.department

Computer Science

Grantor dc:publisher

Virginia Tech

Year dc:date.issued

1991

Author dc:creator

• Richardson, D. S.

Statement dc:rights

• In Copyright

Licence dc:rights.uri

• http://rightsstatements.org/vocab/InC/1.0/

Language dc:language.iso

en

Dc Identifier Other

etd-03172010-020620

OAI identifier oai:identifier

oai:vtechworks.lib.vt.edu:10919/41714