Simulation and Modelling

Module aims

This course provides an introduction to system performance analysis and prediction using computer simulation and mathematical techniques based on Markov Processes and queueing theory. The applications are wide-ranging, although the emphasis is on computer systems performance.

Learning outcomes

Knowledge and Understanding

·         To recall the fundamental laws and explain bounds on throughput and response time for light and heavily loaded systems

·         To state and prove basic properties of Poisson processes and the exponential distribution

·         To explain the internal workings of a discrete-event simulation

·         To describe the principal methods for distribution sampling and prove their correctness

·         To explain ergodicity and both time and ensemble averages in simulation

·         To recall the derivation of the global balance equations for an arbitrary Markov process as a linear system of equations

·         To explain the principles of parallel discrete-event simulation and common approaches to the problem of synchronization

Intellectual Skills

·         To design and implement discrete-event simulations for modelling a specified system

·         To derive correct and efficient sampling algorithms for given probability distributions

·         To compute confidence intervals from independent measures obtained from simulation

·         To specify a Markov Process for modelling a given system

·         To derive closed-form solutions for selected single-queue systems and open networks of Markovian queues

·         To define a Markovian queueing network for modelling a given system and solve for specified performance measures

Practical Skills

To use software tools to model and analyse a real-world system

Module syllabus

  1. Introduction and motivation
  2. Modelling principles
    • Performance measures and Operational laws
    • Bottlenecks and performance bounds
    • Poisson processes
  3. Discrete-event simulation
    • Event scheduling and process interaction models
    • Distribution sampling
    • Equilibrium and transient measures
    • Output analysis
  4. Markov processes
    • Global balance equations
    • Numerical solution

5.       Markovian queues

o    Single-queue systems (M/M/1, M/M/n, M/M/infinity)

o    Open queueing networks

o    Fork-join subsystems

o    Application examples: Apache web server, I/O subsystems, RAID disks

6.       Parallel discrete-event simulation

o    Causality violations

o    Logical processes

o    Conservative simulation (null messages, lookahead)

o    Other synchronisation algorithms (synchronous, optimistic) 

Pre-requisites

245 - Statistics

Teaching methods

Integrated lectures and problem-solving classes

Assessments

Written examination

Assessed coursework

Reading list

Supplementary Reading

Module leaders

Dr Anthony Field