CS 5513 Fall 2011, Homework 4
This homework is due at 11:59pm, Monday, October 10, 2011
Cache Simulator
Modify the xocolatl emulator to include a cache simulator.
- Download the
xocolatl-cache
emulator for the MC6809 processor. Unpack it into your home directory
on one of the UTCS machines with tar -xvzf xocolatl.tar.gz .
Note that this is a new version of the emulator that has been augmented
with hooks for a cache simulator.
- Modify the file xocolatl/src/projects/cache.java to
simulate a cache as described below.
- Compile xocolatl with your modifications and run it on the benchmarks
in the main xocolatl directory. Use the cache configurations specified below.
- Turn in your code as well as a writeup of observations and experiences including two bar graphs:
- One that shows the miss rate for each benchmark for each cache configuration, as well as the arithmetic mean over all benchmarks for each configuration.
- One that shows the CPI for each benchmark for each cache configuration, as well as the geometric mean over all benchmarks for each configuration.
In your writeup, write about your observations of the effect of different
cache parameters on miss rate and performance.
Your code should produce no output; it should only simulate the
cache.
around in memory and do computation. If you like to have debug output,
please disable it in the code you use to turn in your assignment.
Programming Interface and What to Simulate
You should modify xocolatl/projects/cache.java to simulate a cache
and accurately report the number of misses.
The file xocolatl/projects/cache.java has the following methods
defined:
- cache (int, int, int, int); This constructor accepts four
integer arguments: the size of one cache block in bytes, the number of
blocks per set, the number of sets in the cache, and the replacement
policy where 0 means none, 1 means random, 2 means least-recently-used
(LRU), and 3 means first-in-first-out (FIFO).
- void load (int); This method is called by the simulator
every time a byte is loaded from memory. The single parameter is the
address of the load in memory. Addresses are 19 bits.
- void store(int); This method is called every time there is
a store to memory. Again, the single parameter is a 19-bit address.
- long report_misses(); This method returns the number of
cache misses that have occurred.
The command-line arguments of the xoco program have been augmented
to accept a -cache option followed by three integers and one string
specifying the simulated cache's block size, associativity (i.e. number
blocks per set), number of sets, and replacement policy (one of "lru",
"fifo", "random", or "none" for direct-mapped). The emulator automatically
calls the constructor with these parameters and translates the name of a
replacement policy to a number from 0 to 3 so all you have to do is write
the simulator code in cache.java.
Hints for writing a precise simulator
Pay attention to these hints so your simulator will compute the exact
number of misses for each benchmark and configuration:
- Initially (i.e. implement this in the constructor), all cache blocks
are invalid. A cache block becomes valid the first time something is placed
into it from memory. Each block should have a "valid" bit associated with
it that is true if the block is valid, false otherwise.
- For every replacement policy, an invalid block should be replaced
before any valid block. That is, before you begin using the replacement
policy to decide which block to replace, you should see if there is an
invalid block that can be used first.
- Notice that the load and store instructions don't
indicate what the actual value being loaded or stored is. It doesn't matter;
all the simulator is concerned with is statistics about the number of misses,
so the actual values stored in the cache don't need to be represented by
the program.
- "Least recently used" means the one block out of all the blocks in
a set that was loaded from or stored to the longest time ago. How you
implement this policy is up to you; there is more than one right way to
do it but they all result in the same number of misses.
- "First-in-first-out" means the one block out of all the blocks in a
set that was replaced the longest time ago. Again, how you implement this
is up to you but there is only one right answer for the number of misses.
- You will need to keep a count of the number of misses encountered
by your simulator. Make sure this count is a long, since it is
possible that the number of memory accesses could exceed the capacity of
an int.
- You will find that your simulations will be time-consuming. Be patient
and try to code efficiently. You might want to parallel-process, i.e., log
onto more than one machine and run different benchmarks or configurations
simultaneously.
- It should really go without saying, but for goodness' sake don't use
String operations to extract bit fields from machine addresses.
That's super-inefficient. Use shifts and masks on integers.
Compiling and running xocolatl
As in Homework 2,
to compile xocolatl together with the code you have written
in xocolatl/src/projects/cache.java, change to the directory
xocolatl/src and type make.
There are 5 benchmarks:
- compiler - A BASIC compiler compiling itself.
- interpreter - A BASIC interpreter running a BASIC compiler on a sorting program.
- linker - An assembler/linker program assembling and linking the output of the BASIC compiler with the BASIC runtime.
- lisp - A LISP interpreter computing the 12th Fibonacci number with an inefficient recursive function.
- sort - A sorting program doing a bubble sort on pseudo-random numbers.
You can run the benchmarks with the simulator using the run-benchmark
script located in the xocolatl directory. The first argument to run-benchmark should be the name of the benchmark, and the second argument
should be, in quotes, a command-line argument to the simulator to pass
the cache configuration. For example, to run the sort benchmark
with a 2-way set associative cache that has 8-byte blocks, 16 sets,
and an LRU replacement policy, you would type the following from
the xocolatl directory:
./run-benchmark sort "-cache 8 2 16 lru"
(The quotes are necessary so that command-line option to the emulator
won't be parsed by the run-benchmark shell script. Note also that the
replacement policy e.g. "lru" should be in lowercase.)
Each benchmark will run for a while, periodically printing output related
to the running simulated program, and then the simulator will finish with
statistic related to the cache simulation. In the case of running sort with the above configuration, the last few lines of output look like this:
executed 27569591 instructions
9915309 misses
116242901 accesses
8.530% miss rate
1019100491 estimated cycles
36.965 estimated CPI
As you can see, the emulator reports the number of instructions executed,
the number of simulated cache misses, the number of memory accesses,
the simulated cache miss rate, an estimated number of cycles, and an
estimated CPI. The estimated number of cycles and CPI are based on a
machine model where every instruction takes one cycle and every cache miss
has a penalty of 100 cycles (this is computed automatically by the emulator
so your code doesn't need to do anything special about cycles or CPI).
Configurations
In your writeup, report the results of running all 5 benchmarks with
the following configurations:
- 1KB cache, 8 byte blocks, 8-way set associativity, LRU replacement.
- 768 byte cache, 8 byte blocks, 6-way set associativity, LRU replacement.
- 1KB cache, 8 byte blocks, 4-way set associativity, LRU replacement.
- 1KB cache, 8 byte blocks, 2-way set associativity, LRU replacement.
- 1KB cache, 8 byte blocks, 4-way set associativity, random replacement.
- 1KB cache, 8 byte blocks, 2-way set associativity, random replacement.
- 1KB cache, 8 byte blocks, 4-way set associativity, fifo replacement.
- 1KB cache, 8 byte blocks, 2-way set associativity, fifo replacement.
- 1KB cache, 4 byte blocks, 4-way set associativity, LRU replacement.
- 1KB cache, 1 byte blocks, 4-way set associativity, LRU replacement
- 1KB cache, 8 byte blocks, direct-mapped
- 2KB cache, 8 byte blocks, direct-mapped
- 1KB cache, 4 byte blocks, direct-mapped
- 1KB cache, 8 byte blocks, fully associative, random replacement
Clearly, you will have to do some arithmetic to translate the configurations
as specified above into the parameters expected by the simulation.
Examples
These examples will help you develop your simulator. These are only
examples; you should turn in results for all of the benchmarks for all of
the configurations above.
- 2KB cache, 8 byte blocks, 2-way set associativity, LRU replacement.
2KB is 2048 bytes, 2048 / 8 = 256 blocks, 256 / 2 = 128 sets, so to
run the compiler benchmark we would type
./run-benchmark compiler "-cache 8 2 128 lru"
When the simulation finished, the last few lines should look like this:
executed 62815127 instructions
4702985 misses
222067984 accesses
2.118% miss rate
533113627 estimated cycles
8.487 estimated CPI
- 1KB cache, 8 byte blocks, direct-mapped. There are 1024 / 8 = 128 blocks,
so for compiler we run:
./run-benchmark compiler "-cache 8 1 128 none"
and the last few lines of output are:
executed 62815127 instructions
11121057 misses
222067984 accesses
5.008% miss rate
1174920827 estimated cycles
18.704 estimated CPI
Note that the second parameter for the "-cache" option is 1, i.e., 1 block per set, since it is a direct-mapped cache.
- 4KB cache, 16-byte blocks, 8-way set-associative, random replacement.
There are 4096 / 16 = 256 blocks, 256 / 8 = 32 sets, so for sort we
run
./run-benchmark sort "-cache 16 8 32 random"
and the last few lines of output are:
executed 27569591 instructions
3755 misses
116242901 accesses
0.003% miss rate
27945091 estimated cycles
1.014 estimated CPI
- The same example as above, but FIFO replacement on the lisp
benchmark:
./run-benchmark lisp "-cache 16 8 32 fifo"
...
executed 34373897 instructions
273094 misses
112687694 accesses
0.242% miss rate
61683297 estimated cycles
1.794 estimated CPI
- 768 byte cache, 16-byte blocks, 6-way set associative, fifo replacement:
./run-benchmark lisp "-cache 16 6 8 fifo"
...
executed 34373897 instructions
3387548 misses
112687694 accesses
3.006% miss rate
373128697 estimated cycles
10.855 estimated CPI
- 2KB cache, 16-byte blocks, fully associative, LRU replacement.
A 2KB cache with 16 byte blocks has 128 blocks. We can simulate a
fully-associative cache as having one big set with associativity equal to
the number of blocks. So:
./run-benchmark linker "-cache 16 128 1 lru"
...
executed 113214151 instructions
5497880 misses
426017473 accesses
1.291% miss rate
663002151 estimated cycles
5.856 estimated CPI
Note that, for these examples with lru, direct-mapped, and fifo replacement,
your simulator should match exactly the number of misses.
With random replacement, your result should be close, but depending on
your implementation of randomness might be slightly different.
Note: If you are running the emulator after having logged in
remotely, you might need to set your DISPLAY environment variable
to ":0.0" to fool the JVM into believing it has a screen before it can run.
See the README file in xocolatl/ for information about
using the video display option.
You may not work together on this assignment with other classmates or
receive assistance from any person other than your professor or teaching
assistant. Do not use code that isn't your own work for this assignment.
Do not allow other classmates access to your code. Do not allow anyone
access to a computer where your assignment is stored.
Your assignment should be nicely typed or word-processed. You must
your writeup through email to our teaching assistant. You must turn in
your Java and C code electronically by emailing your cache.java
file to the teaching assistant before
midnight on Monday, October 10, 2011. The files you email should
be sufficient to run your programs, so do not email any other files.
Your Java and C code will be graded not only for whether or not it works,
but also for clarity and documentation.
This homework, including the Java code and writeup, is due by 11:59pm on Monday, October 10, 2011.
Late assignments will not be accepted.