CPSC 531:

System Modeling and Simulation

Carey Williamson
Department of Computer Science
University of Calgary
Fall 2017
 Recap: Performance Evaluation

Performance
Evaluation

Performance Performance
Measurement Modeling

Analytic Modeling Simulation

2
Simulation Model Taxonomy (preview)

3
 Terminology (1 of 2)

▪ A system is defined as a group of objects that

interact with each other to accomplish some purpose
— A computer system: CPU, memory, disk, bus, NIC
— An automobile factory: Machines, components parts and
workers operate jointly along assembly line
▪ A system is often affected by changes occurring
outside the system: system environment
— Hair salon: arrival of customers
— Warehouse: arrival of shipments, fulfilling of orders
▪ Effect of supply on demand: relationship between factory
output from supplier and consumption by customers

4
 Terminology (2 of 2)

▪ Entity
— An object of interest in the system: Machines in factory
▪ Attribute
— The property of an entity: speed, capacity, failure rate
▪ State
— A collection of variables that describe the system in any
time: status of machine (busy, idle, down,…)
▪ Event
— An instantaneous occurrence that might change the state
of the system: breakdown

5
 Simulation Modeling

▪ Develop a simulation program that implements a

computational model of the system of interest
▪ Run the simulation program and use the data
collected to estimate the performance measures of
interest (often involves the use of randomization)
▪ A system can be studied at an arbitrary level of detail

▪ Quote of the day:

“The hardest part about simulation is
deciding what NOT to model.”
- Moe Lavigne, Stentor, Summer 1995
6
 Advantages of Simulation

▪ New policies and procedures can be explored without

disrupting the ongoing operation of the real system
▪ New designs can be tested without committing resources
for their acquisition
▪ Time can be compressed or expanded to allow for a
speed-up or slow-down of the phenomenon under study
▪ Insight can be obtained about the interactions of
variables, and which ones have the most impact on
system performance
▪ Can obtain answers to “What if…” questions

7
 Disadvantages of Simulation

▪ Model building requires special training

— An important role for courses like CPSC 531!!
— Vendors of simulation software have been actively
developing packages that contain models that only need
input (templates), which simplifies things for users
▪ Simulation results can be difficult to interpret
— Need proper statistical interpretation for output analysis
▪ Simulation modeling and analysis can be time-
consuming and expensive, both for the modeler, as
well as in compute time (if not done judiciously)

8
 When Simulation Is Not Appropriate

▪ When the problem can be solved by common sense

▪ When the problem can be solved analytically
▪ When it is easier to perform direct experiments
▪ When cost of simulations exceeds (expected) savings
for the real system
▪ When system behavior is too complex (e.g., humans)

9
 Common Mistakes in Simulation

▪ Poor (pseudo) random number generators

— Best to use well-known or well-understood generator
▪ Improper selection of seeds for PRNG
— Short periods; same seeds for all streams
▪ Inappropriate level of detail:
— More detail  more time  more bugs
— More parameters ≠ more accurate
▪ Improperly handled initial conditions (warmup)
▪ Improperly handled ending conditions (cooldown)
▪ Run-length too short to achieve steady-state
— Need proper output analysis, confidence intervals

10
 Types of Simulations

▪ Monte Carlo simulation

▪ Time-stepped simulation
▪ Trace-driven simulation
▪ Discrete-event simulation
▪ Continuous simulation

11
Simulation Model Taxonomy

12
 Simulation Examples

▪ Monte Carlo simulation (see Assignment 1)

— Estimating π
— Craps (dice game)
▪ Time-stepped simulation
— Mortgage scenarios
▪ Trace-driven simulation (see Assignment 2)
— Single-server queue (ssq1.c)
▪ Discrete-event simulation (see Assignments 3 and 4)
— Witchcraft hair salon

13
 Monte Carlo Simulation

Named after Count Montgomery de Carlo, who

was a famous Italian gambler and random-
number generator (1792-1838).

▪ Static simulation (no time dependency)

▪ To model probabilistic phenomenon
▪ Can be used for evaluating non-probabilistic
expressions using probabilistic methods
▪ Can be used for estimating quantities that are “hard”
to determine analytically or experimentally
14
 Trace-Driven Simulation

▪ Trace = time-ordered record of events in system

▪ Trace-driven simulation = Trace input
▪ Often used in evaluating or tuning resource
management algorithms (based on real workloads):
— Paging, cache analysis, CPU scheduling, deadlock
prevention, dynamic storage allocation
▪ Example: Trace = start time + duration of processes
▪ Example: Trace = size in bytes of file written to disk
▪ Example: Trace = mobile device ID and call duration

15
 Advantages of Trace-Driven Simulations

▪ Credibility
▪ Easy validation: compare simulation with
measurement
▪ Accurate workload: models correlation and
interference
▪ Fair comparison: better than random input
▪ Similarity to the actual implementation:
— trace-driven model is similar to the system
— can understand complexity of implementation

16
 Disadvantages of Trace-Driven Simulations

▪ Complexity: more detailed

▪ Representativeness: workload changes with time,
equipment
▪ Data Collection: few minutes fill up a disk
▪ Instrumentation: granularity; intrusiveness
▪ Single Point of Validation: one trace = one point
▪ Difficult to change workload

17
 Discrete-Event Simulation

▪ A simulation model with three features:

1. Stochastic:
some variables in the simulation model are random
2. Dynamic:
system state evolves over time
3. Discrete-Event:
changes in system state occur at discrete time instances

18
 Discrete and Continuous Systems

▪ A discrete system is one in which the system state

changes only at a discrete set of points in time
— Example: A restaurant

19
 Discrete and Continuous Systems

▪ A continuous system is one in which the system state

changes continuously over time
— Example: Water level in Bow River (or Bearspaw dam)

20
 Discrete-Event Simulation

▪ A simulation model in which system state evolves

over a discrete sequence of events in time
— System state changes only when an event occurs
— System state does not change between the events

Departure
Arrival

Arrival
Arrival

Restaurant Example 21
 Continuous Simulation

▪ A simulation model in which system state evolves

continuously over time
— Time is divided to small time slices
— System state changes in every time slice

Dam Example 22
 Characterizing a Simulation Model

▪ Deterministic or Stochastic
— Does the model contain stochastic components?
▪ Static or Dynamic
— Is time a significant variable?
▪ Continuous or Discrete
— Does the system state evolve continuously or only at
discrete points in time?

23
Simulation Model Taxonomy

24
 DES Model Development

▪ How to develop a simulation model:

1. Determine the goals and objectives
2. Build a conceptual model
3. Convert into a specification model
4. Convert into a computational model
5. Verify the model
6. Validate the model
▪ Typically an iterative process

25
 Three Model Levels

▪ Conceptual Model
— Very high level (perhaps schematic diagram)
— How comprehensive should the model be?
— What are the state variables?
— Which ones are dynamic, and which are most important?
▪ Specification Model
— On paper: entitites, interactions, requirements, rules, etc.
— May involve equations, pseudocode, etc.
— How will the model receive input?
▪ Computational Model
— A computer program
— General-purpose programming language or simulation language?

26
 Simulation Software

▪ General purpose programming languages

— Flexible and familiar
— Well suited for learning DES principles and techniques
— E.g., C++, Java
▪ Simulation programming languages
— Good for building models quickly
— Provide built-in features (e.g., queue structures)
— Graphics and animation provided
— Domain specific
▪ Network protocol simulation: ns2, Opnet
▪ Electrical power simulation: ETAP
▪ Design and engineering: Ansys, Autodesk
▪ Process simulation: Simul8

27
 Verification and Validation

▪ Verification
— Computational model should be consistent with
specification model
— Did we build the model right?
▪ Validation
— Computational model should be consistent with the
system being analyzed
— Did we build the right model?
— Can an expert distinguish simulation output from system
output?

28