PadhaikoAll subjects

Simulation of Computer Systems

Simulation and Modeling (ENCT 353)

Open in the Padhaiko app

10.1 Simulation tools

Simulating computer hardware, operating systems, and networks is essential because fabricating silicon prototypes or deploying physical network testbeds is prohibitively expensive and slow.

Definition

Three Paradigms of Computer System Simulators

  1. Trace-Driven Simulation: Records a real sequence of events (e.g., memory addresses, instruction PCs, or packet arrival timestamps) from an existing system into a trace file and replays it through a model of proposed hardware. Fast and realistic, though traces cannot adapt to feedback-dependent execution paths.
  2. Execution-Driven (Functional / Full-System) Simulation: Actually executes compiled application or OS binaries instruction by instruction on a virtualized CPU model, capturing branch mispredictions, speculative execution, and OS interrupts dynamically.
  3. Distribution-Driven (Analytical / Stochastic) Simulation: Generates synthetic workloads from fitted probability distributions (e.g., Poisson packet arrivals, Zipf cache popularity) to explore broad parameter sweeps quickly.
Representative Computer-System Simulation Tools
ToolDomainSimulation ParadigmTypical Usage
gem5CPU, cache, full-system SoCExecution-driven (functional & cycle-accurate)Pipeline IPC, branch prediction, coherence protocols
Dinero IV / CachegrindCache & memory hierarchyTrace-drivenCache hit/miss rates across associativity and block sizes
QEMU / SimicsFull computer systemFast binary-translating functional simulationBooting OS kernels, firmware/driver testing
NS-3 / OMNeT++Computer & wireless networksPacket-level discrete-event simulationTCP congestion control, routing, 5G/Wi-Fi MAC evaluation
CloudSimCloud data centersDiscrete-event resource & VM simulationVM scheduling, server consolidation, energy modeling

10.2 High level computer: System simulation

High-level (system-level) computer simulation models the interactions among major subsystems—CPU cores, cache hierarchy, system bus/interconnect, main memory, DMA controllers, and I/O devices—under realistic workloads such as SPEC or TPC benchmarks.


10.3 CPU simulation

CPU simulators span a strict speed-versus-accuracy spectrum:

AspectFunctional CPU SimulatorCycle-Accurate Timing Simulator
What It ModelsArchitectural state (registers, memory, ISA semantics)Microarchitectural details (pipeline stages, ROB, reservation stations, caches)
Simulation SpeedVery fast ( instructions/s)Slow ( instructions/s)
Primary PurposeSoftware bring-up, ISA verification, functional correctnessMeasuring exact , stall cycles, and microarchitectural design tradeoffs

Modeling Pipeline Performance

In a pipelined CPU simulator, each instruction ideally retires in cycles (typically for a scalar pipeline), but hazards add stall cycles:

where:


10.4 Memory simulation

Memory hierarchy simulation evaluates cache organizations, write policies, replacement algorithms, and virtual memory (TLB and page-fault behavior) against real address traces.

Definition

Cache Address Mapping & Replacement

A memory address of bits accessing a cache with block size bytes and sets is split into three fields:

Cache Miss Classification (3 Cs) and AMAT

Memory simulators categorize misses into the Three Cs—Compulsory (cold start), Capacity (cache too small for working set), and Conflict (multiple blocks colliding on the same set)—and compute the Average Memory Access Time (AMAT):

Similarly, virtual memory simulators replay page-reference strings through frame-allocation algorithms (LRU, FIFO, Optimal/Belady, Clock) to measure page-fault rates and detect thrashing.


10.5 Simulation of computer networks

Computer network simulation models packet generation, queuing inside router buffers, link transmission/propagation, MAC contention, routing protocols, and end-to-end transport dynamics (such as TCP congestion control) using packet-level discrete-event simulation.

Core Delay Components in Packet Simulation

For a packet of length bits crossing a link of bandwidth bps and physical distance with propagation speed (typically in fiber/copper):

Nodal Delay Components in Network Simulation
Delay ComponentFormulaPhysical Cause
Transmission Delay ()Time to push all bits of the packet onto the link
Propagation Delay ()Time for one electromagnetic bit to travel distance
Processing Delay ()Fixed or distribution per routerHeader checksum check, routing table lookup
Queuing Delay ()Random (simulated via or )Time spent waiting in the router output buffer behind prior packets

Worked Out Examples

Example 1

1

A cycle-accurate CPU simulator runs a -instruction trace on a scalar processor with . Simulation counters record:

Calculate:

  1. Effective .
  2. Simulated execution time (in milliseconds) and throughput in .

Computing branch and memory stall cycles per instruction:

Computing execution time and MIPS: Clock period is .

Answer:
  1. Execution time , throughput .
Example 2

2

A trace-driven memory simulator replays the block-address sequence

into a -block cache (hit time , miss penalty ). Simulate and compare the hit rate and for:

  1. A direct-mapped cache ( sets, index ).
  2. A -way set-associative cache ( sets, index ) using LRU replacement.

Trace simulation for the Direct-Mapped Cache (index ):

Direct-Mapped Cache Trace (4 Sets)
AccessBlock AddrSet ()OutcomeCache Sets [0, 1, 2, 3] After Access
Miss[0, -, -, -]
Miss (Conflict)[4, -, -, -]
Miss (Conflict)[0, -, -, -]
Miss (Conflict)[4, -, -, -]
Miss[4, 1, -, -]
Miss (Conflict)[4, 5, -, -]
Miss (Conflict)[0, 5, -, -]

Hits , Misses Hit Rate , Miss Rate :

Trace simulation for the -Way Set-Associative Cache with LRU (index ):

2-Way Set-Associative Cache Trace (LRU)
AccessBlock AddrSet ()OutcomeSet 0 [LRU..MRU]Set 1 [LRU..MRU]
Miss[0][]
Miss[0, 4][]
Hit[4, 0][]
Hit[0, 4][]
Miss[0, 4][1]
Miss[0, 4][1, 5]
Hit[4, 0][1, 5]

Hits , Misses Hit Rate , Miss Rate :

Answer:
  1. Direct-mapped: hits, misses ( hit rate), due to conflict thrashing.
  2. -way set-associative (LRU): hits, misses ( hit rate), .
Example 3

3

In a discrete-event network simulation, packets of size travel across a fiber link (propagation speed ) at bandwidth . Mean router processing plus queuing delay is .

  1. Calculate the transmission delay , propagation delay , and total one-way packet delay (in ms).
  2. Calculate the propagation bandwidth–delay product ( where ) in bits and in packets.

Computing transmission, propagation, and total one-way delay:

Computing the Bandwidth–Delay Product ():

Answer:
  1. , , .
  2. ( full packet of ).

Exercises

Practice Exercises — Simulation of Computer Systems

Question 1

Compare trace-driven, execution-driven, and distribution-driven computer system simulators, giving one advantage and one limitation of each.

Comparing the Three Simulator Types:

  • Trace-Driven: Replays captured instruction/address/packet traces. Advantage: Realistic real-application access patterns and fast replay. Limitation: Static trace cannot react when a design change alters execution timing or branch paths, and traces consume huge storage.
  • Execution-Driven: Runs full binaries dynamically. Advantage: Captures speculative execution, OS interrupts, and timing feedback accurately. Limitation: Much slower simulation speed and complex setup.
  • Distribution-Driven: Uses synthetic random variates (e.g., Poisson arrivals). Advantage: Easy to sweep workload intensity () and generate unlimited trials. Limitation: May miss real-world burstiness or spatial locality unless carefully modeled.
Answer:

Trace-driven simulators replay recorded workloads rapidly but lack timing feedback; execution-driven simulators execute real binaries accurately at slower speed; distribution-driven simulators sweep synthetic workloads easily but depend on distribution fidelity.

Question 2

Distinguish between a functional CPU simulator and a cycle-accurate CPU simulator, and explain how Amdahl’s Law guides subsystem bottleneck analysis in high-level computer simulation.

Functional vs. Cycle-Accurate CPU Simulators: A functional simulator accurately reproduces instruction semantics and architectural register/memory values at high speed (used for software debugging and ISA bring-up), whereas a cycle-accurate simulator models internal pipeline stages, hazard stalls, branch predictors, and caches cycle by cycle to predict execution time ().

Role of Amdahl’s Law: High-level system simulation quantifies what fraction of total execution time is spent in a subsystem (e.g., disk I/O or memory stalls). By , speeding up a component responsible for only of time can yield at most overall speedup even if made infinitely fast, directing engineers toward the true bottleneck.

Answer:

Functional simulators model ISA correctness quickly while cycle-accurate simulators model microarchitectural timing stalls. Amdahl's Law uses simulated time-breakdown fractions to bound maximum system speedup and identify primary bottlenecks.

Question 3

A simulated CPU has . In a benchmark trace, of instructions are branches (with misprediction rate and -cycle penalty) and are memory instructions (with cache miss rate and -cycle penalty).

  1. Find the effective .
  2. What speedup would be achieved if a perfect cache reduced memory misses to ?

Computing with both penalties:

Computing speedup with a perfect cache ():

Answer:
  1. Effective .
  2. Eliminating memory stalls reduces to , yielding a speedup of .
Question 4

A trace-driven memory simulator tests two cache designs, both with hit time and miss penalty:

Calculate the Average Memory Access Time () for each design and the percentage reduction in achieved by Design B.

Computing for Design A and Design B:

Percentage reduction in :

Answer:

, , giving a reduction in average memory access time.

Question 5

In a packet-level network simulation, -byte frames traverse a optical link () at , encountering combined processing and queuing delay. Compute , , and the total one-way packet delay in milliseconds.

Computing transmission and propagation delays:

Summing total one-way packet delay:

Answer:

, , and total one-way packet delay is .

← Simulation software