.jpg "#image7")
Parallel and Distributed Simulation
Richard M. Fujimoto
|
Learning Objectives
TBD
Description
This course is concerned with the realization of simulations on parallel or distributed computing platforms for analytic (e.g., systems analysis) and virtual environment applications. The emphasis is on discrete event simulations. I have offered these materials in advanced undergraduate and introductory graduate level courses to computer science (CS) students as well as classes composed of both CS and engineering/math/science students. Students should have had one or two introductory computer science classes, e.g., courses in programming and data structures.
The lecture notes are broken into three main parts:
- Part I (Modules 1-4) includes an introduction and motivation, and provides a foundation by covering topics in sequential discrete event simulation. The emphasis is on model execution issues. The material on event-oriented simulation is essential to understand the material on parallel discrete event simulation that follows.
- Part II (Modules 5-17) covers parallel discrete event simulation (PDES) that is used for analytic simulations. Much of this material is concerned with solving the synchronization problem (module 5). The first part (modules 6-10) covers conservative approaches to PDES. The next section (modules 11-15) covers optimistic approaches to PDES, focusing on the Time Warp algorithm. The final part (modules 16-17) covers an entirely different approach called time-parallel simulation that is applicable to certain specific simulation problems.
- Part III (Modules 18-25) focus on distributed simulations for interactive virtual environments that are commonly used for training and gaming. Much of this material focuses on approaches such as Distributed Interactive Simulation that was standardized by IEEE, and associated technologies. This section also covers the High Level Architecture for simulation that encompasses simulations used for both training and analysis.
Most of the lecture materials closely follow the textbook, described below. Some notes correspond to technical papers, cited below. Most modules contain from 10 to 20 slides, so one could cover two to three modules in a 50 minute lecture. I have found student comprehension is better, however, moving at a slower pace, and in many cases cover only one or two modules in a single lecture, punctuated with questions to the students to encourage thought and probe for deeper understanding.
Prerequisites
Students should have taken a minimum of two programming courses before taking this course. An undergraduate course in operating systems (processes, concurrency issues, semaphores, etc.) would also be useful, but not essential. No prior knowledge of simulation or parallel or distributed computing is assumed. I have successfully taught this material in courses that include computer science, mathematics, engineering, and science students, though computer science students typically find the material easier to digest.
Textbook
R. M. Fujimoto (2000), Parallel and Distributed Simulation Systems, John Wiley & Sons, New York, NY.
Additional Readings
- R. Brown (1988), “Calendar Queues: A Fast O(1) Priority Queue Implementation for the Simulation Event Set Problem,” Communications of the ACM 31, 10 (Oct.), 1220-1227.
- R. M. Fujimoto (1998), “Time Management in the High Level Architecture,” Simulation 71, 6 (Dec.), 88-400.
- D. Jones (1986), “An Empirical Comparison of Priority-Queue and Event-Set Implementations,” Communications of the ACM 29, 4 (Apr.), 300-311.
- D. Sleator and R. Tarjan (1985), “Self-Adjusting Binary Search Trees,” Journal of the ACM 32, 3 (July), 652-686.
- W.-T. Tang, R. Goh, I. Thng (2005), “Ladder Queue: An O(1) Priority Queue Structure for Large-Scale Discrete Event Simulation,” ACM Transactions on Modeling and Computer Simulation 15, 3 (July), 175-204.
