185.A80 Reverse Code Generation for Optimistic Parallel Discrete Event Simulation (PDES)
Diese Lehrveranstaltung ist in allen zugeordneten Curricula Teil der STEOP.
Diese Lehrveranstaltung ist in mindestens einem zugeordneten Curriculum Teil der STEOP.

2015S, VU, 1.0h, 1.5EC


  • Semesterwochenstunden: 1.0
  • ECTS: 1.5
  • Typ: VU Vorlesung mit Übung

Ziele der Lehrveranstaltung

Einsicht und vertieftes Verständnis der Rolle und Relevanz von "reverse code generation for optimistic parallel discrete event simulation (PDES)".

Inhalt der Lehrveranstaltung

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. Discrete
event simulation is most often used for simulating artificial systems
as opposed to natural ones!

Example applications include models of packet network and switching
networks, distributed software and protocol performance, vehicular
traffic flow, particle systems and kinetic Monte Carlo models,
commodity flow, banking, logistics models, etc.

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 counter intuitive.

This course describes in detail all of the complexity and elegance of
optimistic parallel descrete event simulation (PDES) with the
time warp algorithm and code generation of reverse code, implementing
the required roll back of the time warp algorithm.


* What is discrete event simulation and how does it subsume other simulation paradigms?
* Fundamental issues with parallelizing discrete event simulations
* Two broad categories of synchronization algorithms: conservative vs. optimistic
  - Conservative synchronization algorithms: scope and limits
  - Optimistic synchronization algorithms: scope and limits

Algorithm for optimistic PDES: Time Warp
* Forward and backward in time: the Time Warp synchronization algorithm
* Two methods of rollback: reverse computation and state saving
* Critical path calculations of the degree of parallelism inherent in a discrete event model
* Simulators using time warp (ROSS)
* Example models

Reverse computation:
* Approaches to reverse computation
* Reversible programming languages (with an overview of Janus)
* Information loss and irreversible programs

State saving:
* Approaches to state saving
  - addressing general purpose languages (and irreversible programs)
* Incremental state saving (allowing "reverse memory restoration")
  - automated forward/reverse/commit code generation
  - static analysis for optimizing performance and memory consumption
  - a technique for addressing C++11
  - correctness of reverse code
  - combining incremental state saving and reverse computation
  - tool support (LLNL tool backstroke 2.x)
* input/output and operating system functions

Performance aspects of PDES:
* The largest and fastest parallel discrete event simulations ever (done at LLNL on Sequoia in 2013)
   - paper: Executing Time Warp on 1,966,080 Cores (2013).
* Storage management and flow control
* Load balancing of parallel discrete event simulations
* Snapshots and other approaches to fault recovery in discrete event simulations
* Extreme scale parallel discrete event simulation

Vortragende Personen




Nicht erforderlich



Es wird kein Skriptum zur Lehrveranstaltung angeboten.


bei Bedarf in Englisch