An open LLNL course in Parallel Discrete Event Simulation (PDES)
Instructor: David Jefferson
Meetings: Starting January 23 and every Thursday thereafter at 4:00 PM PST
B453 / R1012 (Black Diamond) for 12 – 15 weeks
Starting in January I will offer a free course on a topic of growing interest at LLNL: parallel discrete event simulation. It will be a series of lectures similar to a graduate course at a university, one hour per week for 12-15 weeks. However there will be no homework, no textbook, no attendance records, no exams, and no grades — just technical content and discussion. The course is open to anyone in the LLNL community without restriction. Foreign nationals should get access to B453 and B451 to attend that course (because some sessions may be held in B451). Slides (and possibly video) will be available.
Discrete event simulation is a simulation paradigm suitable for systems of discrete objects whose state changes are discontinuous and occur at dynamically-calculated moments in simulation time. There is usually no equational description of the system's behavior. It is most often used for simulating artificial systems as opposed to natural ones. Examples include:
- Packet network and switching networks
- Computer architecture
- Distributed software and protocol performance
- Power grid control and other infrastructure
- Vehicular traffic flow (ground, water, and air)
- Particle systems and kinetic Monte Carlo models
- Economies, commodity flow, markets, banking
- Demography, ecology, epidemiology
- Logistics models
- Tactical and strategic military models
Although there is a straightforward algorithm for sequential discrete event simulation, parallel discrete event simulation is dramatically more complex, and in many ways both elegant and counterintuitive. This course will describe in detail all of the complexity and elegance of the field, and help you think differently about the fundamentals of a dramatically different style of parallel computation than you may be familiar with. A partial contents of the course includes the following:
- What is discrete event simulation?
- How does it relate to other simulation paradigms?
- What are the fundamental issues with parallelizing discrete event simulation?
- Two broad categories of synchronization algorithms: conservative vs. optimistic
- Conservative synchronization algorithms: scope and limits
- Optimistic synchronization algorithms: scope and limits
- Forward and backward in time: the Time Warp synchronization algorithm
- Two methods of rollback: state saving and reverse computation
- Reverse computation
- Ancillary topics:
- Critical path calculations of the degree of parallelism inherent in a discrete event model
- Shared memory, and mixed multiprocessor, multicore environments
- Optimistic storage management and flow control
- Dynamic load balancing in parallel discrete event simulations
- Snapshots and other approaches to fault recovery in discrete event simulations
- Extreme scale parallel discrete event simulation
- Largest and fastest parallel discrete event simulations ever (done on our own Sequoia!)
- Extreme Scale Parallel Discrete Event Simulation (XPDES) Consortium and its research agenda
- Bonus: Optimistic parallel discrete event simulation as a paradigm for general purpose parallel computation
- Should every complex parallel computation be viewed as a parallel discrete event simulation?
Sessions
| # | Date | Title | Slides | Video |
|---|---|---|---|---|
| 1 | Jan 23, 2014 | Introduction | LLNL-PRES-648682 | |
| 2 | Jan 30, 2014 | The General Paradigm of Parallel Discrete Event Simulation, and the Fundamental PDES Synchronization Problem | LLNL-PRES-648846 | LLNL-VIDEO-651392 .mov (5.3 GB) .mp4 (4.0 GB) .wmv (0.9 GB) |
| 3 | Feb 6, 2014 | Ties, LBTS, and Lookahead | LLNL-PRES-649156 | LLNL-VIDEO-651237 .mov (5.4 GB, 1.5 GB) .mp4 (0.2 GB) .wmv (1.0 GB, 64 MB) |
| 4 | Feb 13, 2014 | Chandy, Misra, Bryant | LLNL-PRES-649697 .pdf (0.7 MB) | LLNL-VIDEO-651238 .mov (2.9 GB) .mp4 (3.0 GB) .wmv (0.8 GB) |
| 5 | Feb 27, 2014 | Deadlock and Null Messages, Bounded Lag | LLNL-PRES-650779 .pdf (1.9 MB) | |
| 6 | Mar 13, 2014 | Dynamic Object and Channel Creation | LLNL-PRES-651651 .pdf (1.9 MB) | |
| 7 | Mar 20, 2014 | Classic Time Warp State–Message Symmetry Global Virtual Time | LLNL-PRES-652107 .pdf (1.9 MB) | LLNL-VIDEO-652986 .mov (8.9 GB) .mp4 (3.6 GB) .wmv (1.0 GB) |
| 8 | Mar 27, 2014 | Estimated GVT and Commitment | LLNL-PRES-652291 .pdf (2.1 MB) | LLNL-VIDEO-652987 .mov (7.3 GB) .mp4 (3.6 GB) .wmv (1.0 GB) |
| 9 | Apr 3, 2014 | Other Issues in Optimistic Simulation: Runtime Errors TimeWarp as an Operating System (TWOS)
| LLNL-PRES-652636 .pdf (1.8 MB) | LLNL-VIDEO-654833 .mov (7.2 GB) .mp4 (3.5 GB) .wmv (1.0 GB) |
| 10 | April 10, 2014 | Checkpointing-in virtual time | LLNL-PRES-652953 .pdf (1.7 MB) | LLNL-VIDEO-654832 .mov (9.3 GB) .mp4 (3.6 GB) .wmv (1.0 GB) |
| 11 | April 17, 2014 | Reverse computation, Backstroke Up front state saving | LLNL-PRES-653234 .pdf (2.2MB) | LLNL-VIDEO-654834 .mov (8.1 GB) .mp4 (3.7 GB) .wmv (1.0 GB) |
| 12 | April 24, 2014 | Reversing Topics Function calls | LLNL-PRES-653678 .pdf (5.7MB) | LLNL-VIDEO-654836 .mov (7.7 GB) .mp4 (3.6 GB) .wmv (1.0 GB) |
| 13 | May 1, 2014 | Optimistic PDES Performance Examples | LLNL-PRES-653913 .pdf (6.2MB) | LLNL-VIDEO-655035 .mov (12 GB) .wmv (1.1 GB) |
| 14 | May 8, 2014 | Virtual Time for All Distributed Computation I Determinism | LLNL-PRES-654176 .pdf (2.0MB) | |
| 15 | May 21, 2014 | Virtual Time for All Distributed Computation II Load balancing by Dynamic configuration management Space-time symmetries Relation to virtual memory Continuous and discrete simulation | LLNL-PRES-654663
| LLNL-VIDEO-655727 .mov (16 GB) .wmv (1.3 GB) |
Learn about the Department of Energy's Vulnerability Disclosure Programs
Attachments:
Nance 1993.pdf (application/pdf)
Dahl 2001.pdf (application/pdf)
Chandy and Misra 1979.pdf (application/pdf)
Chandy and Misra 1981.pdf (application/pdf)
PDES Course Slides Lecture 1.pdf (application/pdf)
PDES Course Slides Lecture 3.pdf (application/pdf)
PDES Course Slides Lecture 4.pdf (application/pdf)
PDES Course Slides Lecture 2.pdf (application/pdf)
PDES Course Slides Lecture 5.pdf (application/pdf)
Lubachevsky 1989.pdf (application/pdf)
PDES Course Slides Lecture 6.pdf (application/pdf)
Jefferson 1985.pdf (application/pdf)
PDES Course Slides Lecture 7.pdf (application/pdf)
PDES Course Slides Lecture 8.pdf (application/pdf)
PDES Course Slides Lecture 9.pdf (application/pdf)
Jefferson 1990.pdf (application/pdf)
tw-2.7.1.tar.gz (application/x-upload-data)
patch-bellenet-2.7.1.tar.gz (application/x-upload-data)
PDES Course Slides Lecture 10.pdf (application/pdf)
Carothers, et al 1999.pdf (application/pdf)
PDES Course Slides Lecture 11.pdf (application/pdf)
PDES Course Slides Lecture 12.pdf (application/pdf)
PDES Course Slides Lecture 13.pdf (application/pdf)
PDES Course Slides Lecture 14.pdf (application/pdf)
Vulov, et al.pdf (application/pdf)
Fujimoto 1990.pdf (application/pdf)
Bauer, et al 2009.pdf (application/pdf)
Barnes, et al 2013.pdf (application/pdf)
Barnes, et al 2013.pdf (application/pdf)
Nance 1993.pdf (application/pdf)
PDES Course Slides Lecture 15.pdf (application/pdf)