CPSC 531: System Modeling and Simulation: Carey Williamson Department of Computer Science University of Calgary Fall 2017

CPSC 531:
System Modeling and Simulation
Carey Williamson
Department of Computer Science
University of Calgary
Fall 2017
Recap: Performance Evaluation
Performance Evaluation
Performance Performance Modeling

Measurement
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

CPSC 531: System Modeling and Simulation: Carey Williamson Department of Computer Science University of Calgary Fall 2017

Uploaded by

Copyright:

Available Formats

CPSC 531: System Modeling and Simulation: Carey Williamson Department of Computer Science University of Calgary Fall 2017

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

CPSC 531: System Modeling and Simulation: Carey Williamson Department of Computer Science University of Calgary Fall 2017

Uploaded by

Copyright:

Available Formats

CPSC 531:

System Modeling and Simulation

Performance Performance Modeling

Analytic Modeling Simulation

 A system is defined as a group of objects that

 Develop a simulation program that implements a

 Quote of the day:

 New policies and procedures can be explored without

 Model building requires special training

 When the problem can be solved by common sense

 Poor (pseudo) random number generators

 Monte Carlo simulation

 Monte Carlo simulation (see Assignment 1)

Named after Count Montgomery de Carlo, who

 Static simulation (no time dependency)

 Trace = time-ordered record of events in system

 Complexity: more detailed

 A simulation model with three features:

 A discrete system is one in which the system state

 A continuous system is one in which the system state

 A simulation model in which system state evolves

 A simulation model in which system state evolves

 How to develop a simulation model:

 General purpose programming languages

You might also like