The purpose of this lab is to give you some experience programming in C and also to reinforce what you learned in ECE 232 about cache organization.

In this lab, you will write a simulator in C for set-associative caches under the LRU replacement strategy. The inputs to the simulator will be the line length, lines per set, and the cache size. The number of sets will be computed from these inputs.

By clicking here, you will get a trace of memory references. This may seem to be a large file, but it is extremely small compared to the traces that you would use in an actual design process. Each line in the trace consists of two fields. The first field is a number from 0 to 4, and the second is the address of the trace in hex.

The first field specifies the access type of the reference:

0 = read data
1 = write data
2 = instruction fetch
3 = unknown access type
4 = causes a flushing of the cache, i.e., all the lines in the cache are invalidated. If the cache is writeback, everything is written back.

The address space is 32 bits long (or 8 hex positions). If fewer than 8 positions are specified, the leading positions are 0. Thus, for example, an address of abcd is to be read as the hex address 0x0000abcd.

Determine the miss rate for each of the following cases under LRU.

C stands for the total cache size in bytes, L for the line size in bytes, and K for the set associativity (number of lines per set). FA means fully associative (i.e., the entire cache is one set). To begin with, assume there is just a single cache that holds both instructions and data.

[a] C = 1 KByte, K = 1 line per set, L = 4, 8, 16, 32 bytes.

[b] K = 4 lines per set, L = 16 bytes, C = 16, 32, 64, 128 KBytes.

[c] C = 16 KBytes, L = 16 bytes, K = 1, 2, 4 lines per set.

[d] Now, assume you have separate instruction and data caches. These are each of size 16 kBytes. Determine the instruction and data miss rates, assuming that K=1 line per set and L=16 bytes. (In simulating these caches, filter out accesses of unknown access type).

Hand in the source code as well, fully documented. Also, discuss any trends you see in the results. The results must be properly tabulated for easy review. In other words, group your results in a table to ensure that any trends that exist can be seen at a glance. The grading criteria for your lab report include (a) correctness of the numerical results, (b) code correctness, organization and documentation, and (c) quality of presentation of the data and discussion of results.

You will be asked to demonstrate the operation of your simulator. Also, there will be a closed-book quiz (held during regular class hours on October 23rd) that tests your knowledge of set associative caches and basic C programming.

If you use the ECS Unix machines, you will gain some exposure to working in a Unix environment: Unix (or one of its many variants, the best known of which is Linux) is widely used in the real world. To access an ECS Unix machine from the Duda Hall lab, use WinSCP; from one of the ECS computer labs, use ssh to connect to barney.ecs.umass.edu. If your machine does not have ssh, you can download SecureCRT from here. Log in and enter your program using any Unix editor you want (probably the simplest such text editor is vi) and compile it using the command