Performance Analysis of Cache Replacement Policies
Version 0.1
October 2002
Aleksandar
Milenkovic, Milena Milenkovic
Department of Electrical and Computer Engineering
University of Alabama in Huntsville
Huntsville, AL 35899
milenka@ece.uah.edu
http://www.ece.uah.edu/~lacasa/crp02/crp.htm
On this web page, we present results of a study aimed to compare performance of different cache replacement policies such as Random, Round-Robin, LRU (Least Recently Used) and PLRU (Pseudo-LRU). As a measure of performance we use functional cache miss ratios and related statistics. Data are collected using a modified version of the SimpleScalar toolset (http://www.simplescalar.org/) driven by selected benchmarks from the SPEC CPU2000 (http://www.spec.org/osg/cpu2000/) and MiBench (http://www.eecs.umich.edu/mibench/) suites.
Methodology
All data have been collected with simulators sim-cache and sim-cheetah from
the Alpha version of the Simplescalar toolset, version 3.0b. We have implemented
the following changes in the simulators. An additional command option allows
printing various statistics every N executed instructions, where N is the user
specified number of instructions (-logfile stats.txt –perinst N). We have
adapted command options to allow user to specify the number of instructions to
be skipped in simulation (-fastfwd 500M) and the number of instructions to be
simulated (–max:inst 500M). Finally, the sim-cache simulator has been modified
to support pseudo-LRU replacement policies, tree-based PLRU, PLRU-T, and
MRU-based PLRU, PLRU-M, as well as other sub-optimal techniques. In all
simulations we skipped first 500 million instructions and simulated the
execution of the next 500 million instructions.
Data are collected for first level data cache memory (L1D) and second level
unified cache memory (L2U). In our simulations we have used reference input set
for all SPEC CPU2000 benchmarks and large input set for MiBench benchmarks. All
L1D and L2U cache configurations has 32B blocks.
We have collected data for selected benchmarks from SPEC CPU2000 and MiBench suits. The following tables give the list of all applications from the SPEC CPU2000 and MiBench suits and whether we have simulated them or not (on October 10).
SPEC CPU2000
|
Benchmark |
Language |
Type |
Category |
L1D |
L2U |
|
|
|
|
|
|
|
|
C |
Integer |
Compression |
No |
No |
|
|
C |
Integer |
FPGA Circuit Placement and Routing |
Yes |
Yes |
|
|
C |
Integer |
C Compiler |
Yes |
Yes |
|
|
C |
Integer |
Combinatorial Optimization |
No |
No |
|
|
C |
Integer |
Game Playing: Chess |
Yes |
No |
|
|
C |
Integer |
Word processing |
Yes |
Yes |
|
|
C++ |
Integer |
Computer Visualization |
Yes |
Yes |
|
|
C |
Integer |
PERL Programming Language |
Yes |
Yes |
|
|
C |
Integer |
Group Theory, Interpreter |
No |
No |
|
|
C |
Integer |
Object-oriented Database |
Yes |
Yes |
|
|
C |
Integer |
Compression |
No |
No |
|
|
C |
Integer |
Place and Route Simulator (CAE) |
Yes |
Yes |
|
|
|
|
|
|
|
|
|
Fortran77 |
Floating-Point |
Physics, Quantum Chromodynamics |
No |
No |
|
|
Fortran77 |
Floating-Point |
Shallow Water Modeling |
No |
No |
|
|
Fortran77 |
Floating-Point |
Multi-grid Solver: 3D Potential Field |
Yes |
Yes |
|
|
Fortran77 |
Floating-Point |
Parabolic/Elliptic Partial Diff. Eqns |
No |
No |
|
|
C |
Floating-Point |
3-D Graphics Library |
No |
No |
|
|
Fortran90 |
Floating-Point |
Computational Fluid Dynamics |
No |
No |
|
|
C |
Floating-Point |
Image Recognition / Neural Nets |
Yes |
No |
|
|
C |
Floating-Point |
Seismic Wave Propagation |
Yes |
No |
|
|
Fortran90 |
Floating-Point |
Image Processing: Face Recognition |
No |
No |
|
|
C |
Floating-Point |
Computational Chemistry |
Yes |
No |
|
|
Fortran90 |
Floating-Point |
Number Theory / Primality Testing |
No |
No |
|
|
Fortran90 |
Floating-Point |
Finite-Element Crash Simulation |
Yes |
No |
|
|
Fortran77 |
Floating-Point |
High Energy Nuclear Physics Accelerator Design |
No |
Yes |
|
|
Fortran77 |
Floating-Point |
Meteorology: Pollutant Distribution |
Yes |
Yes |
MiBench
|
Benchmark |
Language |
Type |
Category |
L1D |
Automotive |
|
|
|
|
|
basicmath |
C |
Integer |
Simple Math calculations |
|
|
bitcount |
C |
Integer |
Bit manipulation |
|
|
qsort |
C |
Integer |
Quick sort of strings |
|
|
susan |
C |
Integer |
Image recognition |
|
Consumer |
|
|
|
|
|
jpeg enc. |
C |
Integer |
Image compression |
|
|
jpeg dec. |
C |
Integer |
Image decompression |
|
|
lame |
C |
Integer |
MP3 encoder |
|
|
mad |
C |
Integer |
MPEG audio decoder |
|
|
tiff2bw |
C |
Integer |
Convert a color TIFF to black-white image |
|
|
tiff2rgba |
C |
Integer |
Convert a color TIFF to RGB color image |
|
|
|
|
|
|
|
Office |
|
|
|
|
|
ghostscript |
C |
Integer |
Postscript language interpreter |
|
|
ispell |
C |
Integer |
Spell checker |
|
|
rsynth |
C |
Integer |
Text-to-speech synthesis |
|
|
sphinx |
C |
Integer |
Speech decoder |
|
|
stringsearch |
C |
Integer |
Search words |
|
|
|
|
|
|
|
Network |
|
|
|
|
|
dijkstra |
C |
Integer |
Shortest path problem |
|
|
patricia |
C |
Integer |
Routing using reduced trees |
|
|
|
|
|
|
|
Security |
|
|
|
|
|
blowfish enc |
C |
Integer |
Block encryption |
|
|
blowfish dec |
C |
Integer |
Block decryption |
|
|
pgp |
C |
Integer |
PGP public key encryption |
|
|
rijandel |
C |
Integer |
Block encryption/decryption |
|
|
sha |
C |
Integer |
Exchange of cryptographic keys |
|
|
|
|
|
|
|
Telecomm |
|
|
|
|
|
CRC32 |
C |
Integer |
Cyclic Redundancy Check |
|
|
FFT |
C |
Integer |
Fast Fourier Transform |
|
|
IFFT |
C |
Integer |
Inverse FFT |
|
|
ADPCM enc. |
C |
Integer |
Adaptive Pulse Code Modulation encoder |
|
|
ADPCM dec. |
C |
Integer |
Adaptive Pulse Code Modulation decoder |
|
|
GSM enc. |
C |
Integer |
Voice Encoding |
|
|
GSM dec. |
C |
Integer |
Voice Decoding |
|
TBD
TBD
|
Benchmark |
Input |
Table |
|
|
|
|
|
|
||
|
scilab.c |
||
|
|
||
|
|
||
|
|
||
|
|
||
|
|
||
|
|
L1D Miss Ratio Tables for selected SPEC CPU2000 Floating-Point Benchmarks
|
Benchmark |
Input |
Table |
|
|
||
|
|
||
|
|
||
|
|
||
|
|
||
|
|
Publications
Data in this directory is correct to the best of our knowledge. However, we provide it, *AS IS* without an expressed or implied warranty, and we accept no responsibility for the consequences of the use or misuse of this data.
Last updated October 2002. Report any dead links or errors to milenka@ece.uah.edu.