Lecture Notes for Simulation

21 February 2005 - Designing Experiments

Outline

Data Collection
Workload and System Parameters
- Defining Parameters
- Parameter Management
Analysis Methods
- Hybrid Analysis
Validation, verification, and debugging.

Simulation

Overall, a simulation has four phases:
1. Understand the problem to extract a system.
2. Abstract the system as a model.
3. Experiment with the model.
  - Design the experiments.
  - Run the experiments.
4. Analyze the experiment results.
Each phase has sub-phases, including be validation and verification.

simulation phases

Data Collection

A model parameter is an influential but uninteresting part of the model.
- "Uninteresting" because it's not part of the problem statement.
Model parameters have to be identified and defined.
- Parameter definitions may be given as fixed values or a distribution of values.
Model parameters can be categorized as workload or system parameters.
- Workload parameters are dynamic and system parameters are static.

Workload and System Parameters

A workload parameter refers to some aspect of the model not determined by the model itself.
- Examples of workload parameters include inter-arrival times, execution or service times, storage requirements, record types and lengths.
A system parameter refers to some aspect of the system too small to be abstracted by the model.
- Examples of system parameters include operation timings and memory cycle times.

Defining Parameters

Parameters can be defined as particular values or a distribution of values.
Parameters can be defined by observation or by experience (guessing).
Observations have problems with measurement and analysis.
Experience is narrowly circumscribed and hard to justify.
These problems lead to few false negatives but many false positives.

Parameter Management

Parameter management binds values to parameters in the model implementation.
- Values can be bound at compile-time or at run-time.
Compile-time binding is simple and requires a one-time check, but is inflexible.
- Languages vary in their support of compile-time binding.
Run-time binding requires complex input and checking, but allows for faster and easier changes.
- Most languages don't support run-time bindings, but simulation packages might.

When in doubt, favor run-time parameter management.

Especially if simulation software does the hard work.

Analysis Methods

The analysis method determines how the model produces results.
Analysis methods include arithmetic, analysis, and simulation.
Arithmetic is a low-level form of analysis based on parameter values (back-of-the-envelope analysis).
- A useful first step and sanity check.
- Is the inter-arrival rate less than the service rate? Queue overflow!
- The queue never overflows? At least one of the rates is wrong.

Hybrid Analysis

Hybrid analysis combines analytic and simulation methods.
- Analytic methods may be well defined for some of the subsystems.
  - But require stronger assumptions.
- Analytic methods may smooth out sizeable disparities in the system.
  - Instruction level CPU simulation with I-O.
Analytic methods can be used to derive parameter values from distributions.

Verification

Verification determines if the model is accurately implemented.
Verification can be either static or dynamic.
Static verification does not run the model implementation.
- Code walk-through, double checking derivations, and so on.

Dynamic Verification

Dynamic verification runs the model implementation to produce results.
- The results are compared to common sense, the collected data, or separate analytic results.
  - Comparisons require a goodness-of-fit criterion.
Appropriate changes in model behavior can also be used for verification.
- Increasing service times with unchanging arrival rates leads to growing queues.

Validation

Validation determines if the system is accurately implemented.
Implementation validation is the second major validation done.
- The first was on the model abstracted from the system.
Validation is easier if the system exists, although it's possible if the system doesn't exist.
- For existing systems, validation compares performance data derived from the system and the implementation.
- Static validation techniques apply for non-existing systems.

Validation vs. Verification

The difference between validation and verification can be a pain.
- Understand how other people define them.
- Define them when you use them.
It doesn't matter. The important questions are:
1. Do the results produced bear some resemblance to reality? (validation)
2. Are the results produced by something with a resemblance to reality? (verification)
Sometimes verification is less important than validation.
- Black-box simulation for answers.

Debugging

If either verification or validation fail, it's time to debug.
- Also, the implementation may just be broken.
Given the amount of data or the length of the runs, simulation debugging can be a real problem.
- Unfortunately, debugging support is poor (that is, it's the usual).
Debugging support should be built-in to the model and the implementation.
Post-hoc debugging tools are perhaps the most useful approach.
- Write programs to debug programs.

Points to Remember

Data collection defines, among other things, workload and system parameters.
Analysis methods include arithmetic, mathematics, and simulation.
Debugging's around when verification and validation fail.

This page last modified on 23 February 2005.