CS 505, Spring 2005, HW3

Out: 3/30/05

In: 4/13/05

Write a program that simulates caches. In the linked file, you will find traces that represent the memory behavior of a program as it runs. Each trace is a single row of ASCII text with two fields, separated by a space. The first field contains either the letter R, meaning a read, or the letter W, meaning a write. The second field is the hexadecimal address of the accessed memory. For example, a few traces look like this:

W 3f9fa74
R 3f9f9e8
R 3f9f9e4
R 3f9fa3c

Write a program that reads these traces as input and determines the read miss rate for the following cache configurations:

• A 64KB direct mapped cache with 4-byte blocks.
• A 64KB direct mapped cache with 32-byte blocks.
• A 64KB direct mapped cache with 64-byte blocks.
• A 32KB 2-way set associative cache with 64-byte blocks and random replacement.
• A 4KB fully associative cache with 64-byte blocks and LRU replacement.

Turn in the following items, prepared as a single printed word-processed document:

• Your program code. Your code should be well documented, well formatted, and easy to read.
• A separate description of how you went about writing the program. Include your experiences with bugs you found or other difficulties.
• A table showing the miss rates for each configuration.
• Explain the differences in miss rates.

To hand-in, tar and gzipped everything and email it to me before class on 4/13/05.

Note: Define the read miss rate as the number of reads that miss in the cache divided by the total number of reads. Make sure that writes update the cache, but don't count them as reads for the miss rate. Assume that each read or write moves four bytes of data. Assume that the cache is initially empty, i.e., there is no valid data in the cache.

Extra Credit: For extra credit, search the design space for 64KB caches to find the cache configuration that minimizes the read miss rate for this data. Explore the following parameters: block sizes from 4 to 128 bytes, levels of associativity from 1 to 8, random, FIFO, and LRU replacement policies. Feel free to investigate other replacement policies as well as other variations on cache design. Write up your findings, giving your methodology and results. The extra points will be proportional to the extra effort as perceived by the grader(s) as well as soundness of the methdology.