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, 64, 128 and 256 bytes.

[b] K = 4 lines per set, L = 16 bytes, C = 64, 128, 256, 512, 1024 bytes; 2K, 4K bytes.

[c] C = 256 Bytes, L = 16 bytes, K = 1, 2, 4, 8, and 16 lines per set.

[d] Now, assume you have separate instruction and data caches. These are each of size 1 kByte. 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).

[e] Use any uniform random number generator (RNG) for this part. For example, you can use the RNG rand() that is part of the stdlib standard utilities library. There are many alternatives readily available for download. (Warning: rand() is NOT a very good generator: it is convenient and good enough for our purposes, but it is not as good as others that are available in terms of the statistical properties of the random number stream that it generates. So, don't ever use it in "real life": there are many better ones available). Use this RNG to generate a trace of 10,000 read accesses randomly distributed over the entire address space. Run this trace on the cache configurations in part (b) above. Compare the miss rate you get with a random trace against that originally obtained in part (b).

[f] What is the miss rate you would get in each of the configurations in part (c) if the trace were purely sequential, i.e., if each access was to a word whose byte address was exactly 4 greater than that of the previous access? Construct such a trace, starting with an access to location 0 and 1,000 entries long. Use this as a check of the correctness of your simulator.

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 and answer questions related to caches at that time. During the demo, I may ask you to try out other cache configurations as well.

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

I have found the following quite accessible to inexperienced programmers:

Stephen G. Kochan, Programming in C, Sams Publishing, 2005.

A somewhat more basic book is

Greg Perry, Absolute Beginner's Guide to C, Sams Publishing, 1994.

The most famous C book of all is coauthored by people from Bell Labs who were responsible for the C language and the Unix operating system:

Brian W. Kernighan and Dennis M. Ritchie, The C Programming Language, Prentice Hall, 1988.

Kernighan and Ritchie's book is somewhat more terse than the others listed above and is not quite as accessible to the novice programmer. It is, however, very elegantly written and is deservedly a classic. If you plan to become a professional C programmer, you will find the K&R book a valuable possession.