Home Page PDES Course : PDES Course Home

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

#DateTitleSlidesVideo
1Jan 23, 2014Introduction

LLNL-PRES-648682
.pdf (1.2 MB)

LLNL-VIDEO-651236
.mov (1.2 GB)
.mp4 (0.7 GB)
.wmv (0.8 GB)

2Jan 30, 2014The General Paradigm of Parallel Discrete Event Simulation, and
the
Fundamental PDES Synchronization Problem

LLNL-PRES-648846
.pdf (1.4 MB)

LLNL-VIDEO-651392
.mov (5.3 GB)
.mp4 (4.0 GB)
.wmv (0.9 GB)
3Feb 6, 2014Ties, LBTS, and Lookahead

LLNL-PRES-649156
.pdf (1.3 MB)

LLNL-VIDEO-651237
.mov (5.4 GB, 1.5 GB)
.mp4 (0.2 GB)
.wmv (1.0 GB, 64 MB)
4Feb 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)
5Feb 27, 2014

Deadlock and Null Messages, Bounded Lag

LLNL-PRES-650779
.pdf (1.9 MB)

LLNL-VIDEO-652486
.mov (8.7 GB)
.mp4 (3.8 GB)
.wmv (1.0 GB) 

6Mar 13, 2014

Dynamic Object and Channel Creation
Critical Path Theory and Speedup Metrics
Optimistic Simulation and Time Warp

LLNL-PRES-651651
.pdf (1.9 MB)

LLNL-VIDEO-652616
.mov (8.9 GB)
.mp4 (3.6 GB)
.wmv (1.0 GB) 

7Mar 20, 2014Classic 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) 
8Mar 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) 
9Apr 3, 2014

Other Issues in Optimistic Simulation:

Runtime Errors
Infinite Loops 
Scheduling in shared memory/multi-core
Throttling excess optimism
Message flow control, Cancelback protocol 

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) 
10April 10, 2014

Checkpointing-in virtual time
Variations on state saving for rollback
Variations on message cancellation, lazy cancellation
Mixed conservative and optimistic synchronization 

LLNL-PRES-652953   
.pdf (1.7 MB)
LLNL-VIDEO-654832  
.mov (9.3 GB) 
.mp4 (3.6 GB) 
.wmv (1.0 GB) 
11April 17, 2014

Reverse computation, Backstroke

Up front state saving
Incremental (copy on write) state saving
Path-oriented regenerative methods 

LLNL-PRES-653234
.pdf (2.2MB)
LLNL-VIDEO-654834  
.mov (8.1 GB) 
.mp4 (3.7 GB) 
.wmv (1.0 GB) 
12April 24, 2014

Reversing Topics

Function calls
Classes and structs
Arrays and loops
Heap allocation/deallocation
Output 

LLNL-PRES-653678
.pdf (5.7MB)
LLNL-VIDEO-654836  
.mov (7.7 GB) 
.mp4 (3.6 GB) 
.wmv (1.0 GB) 
13May 1, 2014

Optimistic PDES Performance Examples
Dynamic Load Balancing
PHOLD Benchmark Model
ROSS: RPI Optimistic Simulation System

LLNL-PRES-653913
.pdf (6.2MB)
LLNL-VIDEO-655035  
.mov (12 GB) 
.wmv (1.1 GB) 
14May 8, 2014

Virtual Time for All Distributed Computation I

Determinism
Debugging, fault detection and recovery
Synchronization, mutual exclusion, atomic transactions
Barrier synchronization
 

LLNL-PRES-654176
.pdf (2.0MB)

LLNL-VIDEO-654835  
.mov (13 GB) 
.mp4 (4.3 GB) 
.wmv (1.1 GB) 

15May 21, 2014

Virtual Time for All Distributed Computation II

Load balancing by

Dynamic configuration management
Energy management
Object migration

Space-time symmetries

Relation to virtual memory
Jump-forward optimization
Objects and anti-objects

 Continuous and discrete simulation

LLNL-PRES-654663
.pdf (1.2 MB)

 

LLNL-VIDEO-655727  
.mov (16 GB) 
.wmv (1.3 GB) 

 

 
LLNL-WEB-649721 Privacy and Legal Notice


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)