Lecture Materials
Slides, readings, and related lecture material will appear here gradually throughout the semester.
-
Introduction (1 week)
Modeling. Simulation. Computer systems performance evaluation. Types of simulations. Simulation examples from different application domains.
Slides: Course Overview (PPT,PDF) Simulation Methods (PPT,PDF)
Examples: mortgage.c pi.c craps.c ssq1.c ssq1.dat
Readings: Sections 1.1 and 1.2 -
Random Numbers (1.5 weeks)
Random number generators. Basics of random variate generation. Monte Carlo simulation.
Slides: Random Number Generation (PPT,PDF,Guest Lecture) Random Variate Generation (PPT,PDF) RVG Testing (PPT,PDF)
Examples: flipper.c demo.c rng.h rng.c rngs.h rngs.c rvgs.h rvgs.c
Tools/Utilities: avg.c iat.c buckets.c autocorr.c graphs.gnuplot
Readings: Sections 2.1, 2.2, 2.3, and 2.4 -
Probability Models (1.5 weeks)
Random variables. Probability density function (pdf). Cumulative distribution function (CDF). Common probability distributions. Inverse transformation for random variate generation. Discrete random variables. Continuous random variables. Stochastic processes. Basic queueing theory: the M/M/1 queue.
Slides: Probability (PPT,PDF) Fundamentals (PPT,PDF) Stochastic Processes (PPT,PDF)
Examples: heights.c heights.pdf
Readings: Sections 6.1, 6.2, 7.1, and 7.2
Readings: Sections 6.4.1, 6.4.2, 6.4.3, 6.4.5, 6.4.6, 7.4.1, and 7.4.2 -
Discrete-Event Simulation (2 weeks)
Time-stepped simulation. Trace-driven simulation. Discrete-event simulation (DES). DES concepts and event scheduling. DES examples. Simulation verification and validation.
Slides: Discrete-Event Simulation (PPT,PDF) Event-List Management (PPT,PDF) Validation Example (PPT,PDF)
Examples: grocer.c pancakes.c ssq3.c msq.c ttr.c twit.c twit2.c
Readings: Sections 3.1, 3.2, 5.1, 5.2.2, and 5.3 -
Simulation Output Analysis (2 weeks)
Stochastic properties of simulations. Transient and steady-state analysis. Confidence intervals. Batch means analysis. Correlation analysis. Analysis of variance (ANOVA).
Slides: Output Analysis (PPT,PDF) Experimental Design (PPT,PDF) Statistical Methods (PPT,PDF) Data Presentation (PPT,PDF)
Examples: parksim.c arrivaltimes.dat servicetimes.dat parksim2.c mm1val.pdf compare.pdf covariance.c covariance2.c linreg.cc anova.c
Readings: Sections 8.1, 8.2, 8.3, and 8.4 -
Simulation Input Analysis (2 weeks)
Trace-driven simulation. Workload characterization. Histograms. QQ plots. Goodness of fit tests.
Slides: Input Analysis (PPT,PDF)
Examples: xify.c iat.c qq.c qq2.c chime.c quiz.dat occupancy.dat electric.dat heating.dat doors.dat march1-d2l.dat sizes.dat sizes2010.dat uni1000.dat att2014.dat papers.dat
Readings: Sections 9.1 and 9.2 -
Queueing Models (2 weeks)
Elements of a queue. Markov chains. Classic queues: M/M/1, M/M/1/K, M/M/c/c, M/M/∞, M/G/1. Open/closed queueing network models.
Slides: Queueing Theory (PPT,PDF) Autoscaling (PPT,PDF)
Examples: erlangloss.c calls.c
Readings: Section 8.5 -
Parallel Simulation (30 minutes)
Sequential versus parallel versus distributed simulation. Conservative versus optimistical parallel simulation. History of PDES.
Slides: Parallel Simulation (PPT,PDF) History of Parallel Simulation (PDF)
Acknowledgements: Much of the content for the Fall 2017 offering of CPSC 531 has drawn heavily from materials provided by colleague Majid Ghaderi, who taught the most recent version of this course (Fall 2015), as well as former colleague Anirban Mahanti (Winter 2007). Several ideas have also been inspired or informed by my many research interactions with retired colleague Brian Unger, who first created this course several decades ago. Selected code examples have been obtained from the Web site of Larry Leemis, who co-authored (with Steve Park) the textbook that we are using for this course.