CS 5513 Fall 2007, Homework 4

Due at the beginning of class, November 8, 2007.

Write a program that simulates caches. In the compressed file traces.txt.gz, you will find traces that represent the memory behavior of a program as it runs. (Note: Make sure to right-click on the link to avoid having your browser decompress this rather large file.) 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.

Handwritten assignments will not be accepted. Late assignments will not be accepted after 5:35pm on Thursday, November 8, 2007.

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. Your program must simulate writes in the cache, even though we are only measuring the read miss rate because writes affect the read miss rate.

You may assume that each read and write accesses a 4 byte object from the cache, and that all the reads and writes are aligned on a 4-byte boundary. Thus, you do not have to worry about a single read or write accessing more than one cache block because of an unaligned access.

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 as well as soundness of the methdology.