CS 61C (Fall 2007)

Lab Assignment 12



Goals

This lab involves experiments with parameters of a simulated cache. We hope that the experiments will help you to be better able to predict the effect of a particular set of parameters on cache behavior.

Reading

Setup

Work with a partner on these exercises.

Copy the file cache.s from the directory ~cs61c/files/lab/12 to a suitable location in your home directory. The program has three parameters: the size of an array to step through, the step size (stepping every 4 bytes means processing every word in the array, stepping every 8 bytes means processing alternate words, and so on); and a repetition count. It implements the following pseudocode: 

for (k = 0; k < repcount; k++) {
	/* Step through the selected array segment with the given step size. */
	limit = arraysize - stepsize + 1;
	for (index = 0; index < limit; index = index + stepsize) {
		/* Right-hand side accesses the cache. */
		array[index/4] = array[index/4] + 1;
	}
}

Now run MARS and load the cache.s program. Also select the "Data Cache Simulator" from the Tools menu and click its "Connect to MIPS" button.

Exercise 1 (1 point)

First, draw a picture of the cache that will be simulated. Then, fill in the following values in cache.s: arraysize = 2048; stepsize = 4; and repcount = 1. Assemble and run the program. Consider single stepping, or using a breakpoint between the load and the store to help get a detailed view in the "Data Cache Simulator."  You will be using the default cache size and configuration: Direct Mapped, 8 blocks, 4 words per block.

  1. Observe that the hit rate is 87.5%, that is, 7 out of every 8 memory accesses. Using your diagram, identify which accesses are hits and which are misses. (Note that the program is performing a load, followed by a store into the same memory location. The store will always be a hit; thus the lowest hit rate is 50%.) You will need to click the "Reset" button between runs.

  2. Run the program twice more, first with stepsize = 8, then with stepsize = 16 (both still with arraysize = 2048). Explain the cache results.

  3. Finally, find a block size that, with an array size of 1024 and a step size of 4, produces a hit rate of 96.875% (31 hits out of 32 accesses).

Exercise 2 (1 point)

Using an array size of 1024, find a value for stepsize for which a 2-way set associative cache produces a better hit rate than a direct-mapped cache of the same size. Explain your solution. Also explain whether or not there is a step size for which a 2-way set associative cache produces a worse hit rate than a direct-mapped cache of the same size.

To successfully complete this exercise you will need to consider a simple case where a 2-way set associative cache will be able to keep certain words in cache, which would be replaced by something else in a direct mapped cache.  We recommend you think about the various things which might cause a block to be ejected from the cache.  P&H 7.5 talks about the 3 'C's of cache misses, which may give you a start.

Hint: remember to think about (or play with) all of the variables in cache.s

Exercise 3 (2 points)

Using a value of 4 for repcount, find the cache parameter values that produce the hit rates in the table below:

array size step size
  4 8 16 32 64 128 256
64 93.75% 87.5% 87.5% 87.5% 87.5%    
128 93.75% 87.5% 87.5% 87.5% 87.5% 87.5%  
256 93.75% 87.5% 87.5% 87.5% 87.5% 87.5% 87.5%
512 75% 50% 50% 50% 50% 87.5% 87.5%
1024 75% 50% 50% 50% 50% 50% 87.5%
2048 75% 50% 50% 50% 50% 50% 50%

We recommend that you approach this problem by attempting to determine each of the cache parameters separately.  In particular, you'll notice that there are a number of sudden changes in hit rate between adjacent cells in the above table.  By looking for patterns of such differences, you should be able to determine first one cache parameter and then another.

For example, there is a change in hit rate between the (64,4) and (64,8) hit rates.  What might cause this change?

Summary of checkoff requirements

Exercise 1

Exercise 2

Exercise 3