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:
1. 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.
2. 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.