Simulation of Computer Systems
Open in the Padhaiko app10.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.
Three Paradigms of Computer System Simulators
- 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.
- 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.
- 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.
| Tool | Domain | Simulation Paradigm | Typical Usage |
|---|---|---|---|
| gem5 | CPU, cache, full-system SoC | Execution-driven (functional & cycle-accurate) | Pipeline IPC, branch prediction, coherence protocols |
| Dinero IV / Cachegrind | Cache & memory hierarchy | Trace-driven | Cache hit/miss rates across associativity and block sizes |
| QEMU / Simics | Full computer system | Fast binary-translating functional simulation | Booting OS kernels, firmware/driver testing |
| NS-3 / OMNeT++ | Computer & wireless networks | Packet-level discrete-event simulation | TCP congestion control, routing, 5G/Wi-Fi MAC evaluation |
| CloudSim | Cloud data centers | Discrete-event resource & VM simulation | VM 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.
- Key Architectural Bottlenecks Modeled: Bus arbitration delays, memory-controller queuing, disk/NVMe I/O service times, and multi-core synchronization contention.
- Primary System Performance Metrics:
- Execution Time: , where is instruction count.
- Throughput: Instructions or jobs completed per second ().
- Speedup (Amdahl’s Law): If a fraction of execution time is accelerated by factor :
10.3 CPU simulation
CPU simulators span a strict speed-versus-accuracy spectrum:
| Aspect | Functional CPU Simulator | Cycle-Accurate Timing Simulator |
|---|---|---|
| What It Models | Architectural state (registers, memory, ISA semantics) | Microarchitectural details (pipeline stages, ROB, reservation stations, caches) |
| Simulation Speed | Very fast ( instructions/s) | Slow ( instructions/s) |
| Primary Purpose | Software bring-up, ISA verification, functional correctness | Measuring 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:
- Branch-misprediction stalls: .
- Memory stalls: .
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.
Cache Address Mapping & Replacement
A memory address of bits accessing a cache with block size bytes and sets is split into three fields:
- Direct-Mapped (-way): Each memory block maps to a single line in set .
- -Way Set-Associative: Each set holds candidate lines; requires a replacement policy (LRU — Least Recently Used, FIFO, or Random) when a set is full.
- Fully Associative: set containing all cache lines ( index bits).
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):
| Delay Component | Formula | Physical 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 router | Header checksum check, routing table lookup |
| Queuing Delay () | Random (simulated via or ) | Time spent waiting in the router output buffer behind prior packets |
- Bandwidth–Delay Product (): measures how many bits can be "in flight" simultaneously in the network pipe—critical for sizing TCP receive/congestion windows in NS-3 or OMNeT++ experiments.
Worked Out Examples
1
A cycle-accurate CPU simulator runs a -instruction trace on a scalar processor with . Simulation counters record:
- of instructions are branches; of branches are mispredicted, causing a -cycle pipeline flush penalty.
- of instructions are loads/stores; the data cache miss rate is with a -cycle miss penalty.
Calculate:
- Effective .
- Simulated execution time (in milliseconds) and throughput in .
Computing branch and memory stall cycles per instruction:
Computing execution time and MIPS: Clock period is .
- Execution time , throughput .
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:
- A direct-mapped cache ( sets, index ).
- A -way set-associative cache ( sets, index ) using LRU replacement.
Trace simulation for the Direct-Mapped Cache (index ):
| Access | Block Addr | Set () | Outcome | Cache 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 ):
| Access | Block Addr | Set () | Outcome | Set 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 :
- Direct-mapped: hits, misses ( hit rate), due to conflict thrashing.
- -way set-associative (LRU): hits, misses ( hit rate), .
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 .
- Calculate the transmission delay , propagation delay , and total one-way packet delay (in ms).
- 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 ():
- , , .
- ( full packet of ).
Exercises
Practice Exercises — Simulation of Computer Systems
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.
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.
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.
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.
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).
- Find the effective .
- What speedup would be achieved if a perfect cache reduced memory misses to ?
Computing with both penalties:
Computing speedup with a perfect cache ():
- Effective .
- Eliminating memory stalls reduces to , yielding a speedup of .
A trace-driven memory simulator tests two cache designs, both with hit time and miss penalty:
- Design A (Direct-mapped): miss rate.
- Design B (-way set-associative): miss rate (same hit time).
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 :
, , giving a reduction in average memory access time.
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:
, , and total one-way packet delay is .