Assigned: 2 November 2004

Due: 16 November 2004

The goal of this assignment is to give you a more concrete idea about caching. You will write your own data Cache Simulator and observe its behavior. Your results will be summarized in a written report, which you will turn in with your Simulator.

Cache Simulator Specifications

The input will be a series of decimal addresses that your cache will interpret as READS at that address. For simplicity, assume memory is word addressable and your cache blocks are 1 word each. A word in our system is 4 bytes. The size of your cache will be specified in words.

The input file can be downloaded from here or from blackboard.

In a real system, meaningful data would exist in memory. For this project, assume that each memory address requested contains one word, the address at which it is located. So, for example, address 100 would have the data 100 stored at it. Please follow this convention for testing. What does this mean as far as your source code? When you get a cache miss you should store the address requested in the appropriate location in the cache.

Your cache will run under two configurations:

  1. Direct mapped
  2. 2-Way set associative, LRU replacement scheme

You will run each configuration on 4 different sizes, for a total of 8 different cache simulations on the input. The sizes you run will depend on the last 2 digits of your PID as indicated in the table below:

last 2 PID digits Cache sizes
00–24 64, 256, 512, 8k
25–49 32, 128, 1k, 16k
50–74 128, 256, 2k, 32k
75–99 256, 512, 4k, 16k

The output of your program should be (under each configuration and size combination):

  1. The number of cache hits, the number of cache misses, and the miss ratio.
  2. The contents of the first 20 blocks of your cache (first 10 from each set for the set-associative cache). This will be an easy way for the TA to verify the correctness of your results.

Your program should be invoked with a line like the following:

cache trc.txt 1 1024

which would run your cache on trc.txt input with configuration 1 (direct mapped) and a cache of total size 1024 words.

Your Cache Simulator will be written in C, C++, or Java. It will not be graded unless it builds cleanly.

Turn-in Instructions

You will email with your source files and a Word or PDF file describing your results.

Your written report should include:

  1. A graph or table showing the miss ratio results for each of the 8 tests you ran. Clearly label these.
  2. A discussion of the results for #1. Were these as you expected? Why? If not, explain what you would have expected. Do not doctor your results to match what you expect. Simply discuss your findings and show a clear thought process.
  3. A table showing the first 20 blocks of your cache at the end of each test run. This doesn’t have to be well formatted.. just attach it at the end and label it well.

You should be able to convey your ideas (#1 and #2) in less than a page. A program turned in without a written report will receive very little partial credit, so please write up a discussion of any results you have before submitting your work.