Abstract:
This article proposes the development of a standard interface for Parallel Discrete Event Simulation (PDES) frameworks. PDES has been in existence for more than 20 years. This technology is now starting to see widespread use in the DoD M&S community. We believe it is in the best interest of the M&S community to define a set of interfaces that encompass most PDES techniques and existing frameworks. With this standard, it will be possible to more easily port models and software between frameworks, and to more fairly compare framework implementations. This will spur performance, quality and usability improvements that will benefit the M&S community as a whole.

A Parallel Discrete Event Simulation Standard for Modeling and Simulation.
Darrin West (SAIC), Richard Fujimoto (GIT) & Louis Lome (BMDO)
This article proposes the development of a standard interface for Parallel Discrete Event Simulation (PDES) frameworks. PDES has been in existence for more than 20 years. This technology is now starting to see widespread use in the DoD Modeling and Simulation (M&S) community. We believe it is in the best interest of the M&S community to define a set of interfaces that encompass most PDES techniques and existing frameworks. With this standard, it will be possible to more easily port models and software between frameworks, and to more fairly compare framework implementations. This will spur performance, quality, and usability improvements that will benefit the M&S community as a whole.
How to define PDES
Parallel Discrete Event Simulation is concerned with executing a single discrete event simulation on more than one processor. The simulation is broken into Logical Processes (LP’s) which are mapped to the different processors. Typically, many LP’s reside within a single processor. Processors may be tightly coupled in a multi-processor machine, may be clustered, or may be loosely coupled over a network. LP’s communicate using only time-stamped messages. The avoidance of state variables shared between LP’s enables concurrent execution on multiple processors, location independence, and, ideally, enables dynamic migration for the LP’s. The sending LP applies the time-stamp to the message. The receiver must process the messages in time-stamp order. Since processor load may not be perfectly even, a synchronization mechanism (commonly referred to as time management) is used to ensure that events are executed in the correct order.
Conservative schemes block processing until it can be guaranteed that no earlier events will arrive for an LP. To maximize performance, conservative algorithms sometimes declare fixed communication channels and minimum lookahead values for message time-stamps.
Optimistic schemes use a detection and recovery paradigm rather than avoiding out of order event processing. When a message arrives with a time stamp less than the current time of the LP, that LP is rolled back using previously saved states. Messages that were sent by the rolled back computation are retracted using a mechanism called anti-messages. Memory consumed by saved states and messages must be fossil collected based on a globally calculated minimum time called Global Virtual Time (GVT).
PDES was originally envisioned to allow simulations to run as quickly as possible in order to reduce the time required to obtain results, or to support the execution of very large-scale simulations. PDES simulations normally run independently of wall-clock time, and the rate of progress through simulation time may fluctuate with respect to advances in wall-clock time. However, it is straightforward to pace simulation time advances to be made synchronously with wall-clock time. Using well-known time-stamp management techniques, repeatable results may be obtained regardless of the number of processors used. This is important for analytic uses of simulation.
Need/Benefits of a standard
There are numerous implementations of PDES frameworks, both academic and commercial. These implementations each have their advantages, but a user must make an early decision about which framework to use when there is often little information with which to make that selection. This creates a difficult environment for users to compare implementations. Further, once the choice has been made, it is very difficult for users to later switch to a different implementation should the selected system prove to be deficient or unavailable. Needless to say, this significantly increases the user’s risk in exploiting this technology.
Creating and adopting an acceptable PDES standard enables the M&S community to take a large step toward addressing these issues. The result will be a more productive, coordinated framework development community, and a more efficient user community. The challenge is in developing a standard that is acceptable to the entire community. The proliferation of existing interfaces indicates that the community has accepted no single current interface. Creating an arbitrary standard based on a small group of contributors may produce results only slightly more acceptable than the divergent interfaces already existing in various PDES frameworks.
The process used in standards development efforts such as CORBA, promises a better approach toward realizing a PDES standard. By this we mean the framework development community and the user community together create a standard interface. The development is accomplished incrementally and only after features are implemented, demonstrated, and accepted by a majority of voting members of the community. This has the positive feedback property of encouraging the widest possible participation in the process, ideally resulting in the most widely acceptable standard. At each point in the evolution of the standard, an implementation exists. As a result, users are able to immediately develop their application in accordance with the standard. The net result is that users will have a choice of frameworks, competition is enhanced while precluding the divergence of interfaces, and the quality of the implementation choices available to the user is improved.
It is expected that multiple implementations will exist because it is impossible to have a single framework that is both general purpose and provides maximum performance. Thus, different frameworks will be built to address the specific requirements of groups of users, while continuing to adhere to the standard. Benchmarks may be developed that will indicate the properties of each framework and the suitability that a given framework has for a particular user need. It will be much easier to re-host a simulation to a new framework through this methodology than if the frameworks had divergent interfaces. This opens to the user the option of moving to a framework that has properties more suitable to a particular need based on experience, rather than on a decision made earlier in the development cycle. The simulation may even be hosted on several frameworks simultaneously to serve a user that has multiple different scale or hardware requirements.
Standards Structure and Evolution.
The primary goal of PDES is to make simulations execute faster. Therefore, performance issues will dominate the standards development. The PDES M&S Standard needs to be modular, allowing users to select properties that are of interest to them, without incurring a performance penalty for features they are not using. The initial standard should be simple and allow for very efficient framework implementations. More complex features should be added in a modular fashion and may make use of existing features. This approach allows “special interests” to be accommodated without compromising core performance and features. Once those “middleware” pieces obtain a wide enough interest, they may be used to extend the standard. This sort of incremental evolution has worked in the CORBA standards development model.
Authors
Darrin West is a senior computer scientist with SAIC. He received his M.S. (1988) and B.S. (Honors, 1985) degrees from University of Calgary, Canada, in Computer Science. His research interests include distributed systems and parallel simulation, and he has published a number of papers in the field. He is the technical lead for various parallel simulation projects funded through DARPA, and HPCMO. He is the chief architect for the parallel simulation products Toccata, Thema, Tempo, and Sim++. (703) 907-2551, mailto:west@jade.saic.com
Dr. Richard Fujimoto is a professor in the College of Computing at the Georgia Institute of Technology (GIT).  He received his Ph.D. (1983) and M.S. (1980) degrees from the University of California (Berkeley) in Computer Science and Electrical Engineering, and two B.S. degrees from the University of Illinois (Urbana) in Computer Science and Computer Engineering. He has been an active researcher in the parallel and distributed simulation community since 1985 and has published over 100 technical papers in conferences and journals.  He has given several tutorials on parallel and distributed simulation at leading conferences, and has co-authored a book on parallel processing.  He served as chair of the technical working group responsible for defining the time management services for the DoD High Level Architecture (HLA).  Fujimoto is an area editor for Association for Computing Machinery (ACM) Transactions on Modeling and Computer Simulation.  He also served as chair of the steering committee for the Workshop on Parallel and Distributed Simulation (PADS) from 1990 to 1998, and served on the conference committee for the Simulation Interoperability Workshop (SIW) in 1996-97.  He also served on the program review panel for the RTI and Communications Forum for the 1996-97 SIW. mailto:fujimoto@cc.gatech.edu
Louis Lome. B.A. and M.A. in Mathematics from Northwestern and U. of Illinois, Urbana-Champaigne, respectively. 24 years R&D program manager in government, last nine years being at the Ballistic Missile Defense Office (BMDO), managing programs in computing, materials, sensors, and electronics. He is a Senior member of the Institute of Electrical and Electronics Engineers (IEEE), a member of numerous other societies, organizer and chair of many conferences in many different disciplines, including recent conferences on polymer devices, WDM communications, computer security, and laser guided surgery. mailto: Louis.Lome@bmdo.osd.mil