Parallel Discrete Event Simulation



Asynchronous Parallel Discrete Event Simulation

Yi-Bing Lin, Bellcore Paul A. Fishwick, , CS-TR-95-005, University of Florida, 1999

Complex models may have model components distributed over a network and generally require significant execution times. The field of parallel and distributed simulation has grown over the past fifteen years to accommodate the need of simulating the complex models using a distributed versus sequential method. In particular, asynchronous parallel discrete event simulation (PDES) has been widely studied, and yet we envision greater acceptance of this methodology as more readers are exposed to expositions that carefully integrate real-world applications. With this in mind, we present two key methodologies (conservative and optimistic) which have been adopted as solutions to PDES systems. We discuss PDES terminology and methodology under the umbrella of the personal communications services application. Keywords: [parallel algorithm, distributed simulation, synchronization, virtual time, network communications].

Parallel and Distributed Simulation of Discrete Event Systems 

Ferscha Alois, Tripathi Satish, TCS-TR-3336, University of Maryland, August 1994.

The achievements attained in accelerating the simulation of the dynamics of complex discrete event systems using parallel or distributed multiprocessing environments are comprehensively presented. While parallel discrete event simulation (DES) governs the evolution of the system over simulated time in an iterative SIMD way, distributed DES tries to spatially decompose the event structure underlying the system, and executes event occurrences in spatial subregions by logical processes (LPs) usually assigned to different (physical) processing elements. Synchronization protocols are necessary in this approach to avoid timing inconsistencies and to guarantee the preservation of event causalities across LPs. Included in the survey are discussions on the sources and levels of parallelism, synchronous vs. asynchronous simulation and principles of LP simulation. In the context of conservative LP simulation (Chandy/Misra/Bryant) deadlock avoidance and deadlock detection/recovery strategies, Conservative Time Windows and the Carrier Nullmessage protocol are presented. Related to optimistic LP simulation (Time Warp), Optimistic Time Windows, memory management, GVT computation, probabilistic optimism control and adaptive schemes are investigated.

Parallel Discrete Event Simulation

B.J. Overeinder; L.O. Hertzberger and P.M.A. Sloot, In W.J. Withagen, editor, The Third Workshop Computersystems, Faculty of Electrical Engineering, Eindhoven University, pp. 19-30. Eindhoven, The Netherlands, May 1991.

In simulating applications for execution on specific computing systems, the simulation performance figures must be known in a short period of time. One basic approach to the problem of reducing the required simulation time is the exploitation of parallelism. However, in parallelising the simulation new problems arise. Due to the distributed generation of events causality errors can occur, as a result the sequence in which to process the events is essentially indeterminate.

In this paper we present a model to analyze the inherent parallelism of a simulation, together with a survey of existing strategies to perform the simulation in parallel. Some extensions to this model are discussed, resulting in reliable evaluation of the effectiveness of these strategies.

Some classic survey papers available only in hardcopy:



Maintained by
Last Update: 03/11/99