Objective For this programming assignment, you will design and implement a cache simulator. Your simulator will read a memory access trace from a file, determine whether each memory access is a hit or...

Objective

For this programming assignment, you will design and implement a cache simulator. Your simulator will read a memory access trace from a file, determine whether each memory access is a hit or a miss, and output the hit rate. You can use whatever programming language you choose to implement your simulator (e.g. C++, Java, Python).

You will then analyze the performance (hit rate) of three cache designs. You will do this in an analysis paper which should answer the following questions:

1. How does the performance of a cache change with its associativity? (e.g. direct mapped vs n-way associative vs fully associative)


2. How does the performance of a cache change with cache size?


3. How does the performance change with replacement policy?

Important Information

The format of the memory trace file is the following:

• The first field is “l” or “s” depending on whether the processor is loading from or storing to memory. You don't need to do anything differently for load or store.


• The second field is a 32-bit memory address.


• The third field is the number of bytes being requested.

You don't need to do anything with the number of bytes being requested. The only field you care about is the address. You may assume that each request will be contained in one block.

I have provided some sample trace files in the Canvas directory Files / Cache Analysis.

• The small files are for debugging. Your analysis should be based on the hit rates for the larger files.


• You can create your own using the valgrind lackey tool.

Sharing trace files and results is welcomed and encouraged.

Guidelines

Items to Examine

1. Parameters
   
   
   • Number of sets in the cache (a positive power of 2)
   
   
   • Number of blocks in each set (a positive power of 2)
   
   
   • Number of bytes in a block (a positive power of 2, must be at least 4)
   
   
   • 1 set of n blocks is fully associative
   
   
   • n sets of 1 block is direct mapped
   
   
   • n sets of m blocks is m-way set associative
   
   
   
   


2. Replacement policy (for caches that aren't direct mapped)
   
   
   
   
   • Least recently used (LRU)
   
   
   • First in, first out (FIFO)
   
   
   
   


3. Examine effect of changing cache type
   
   
   
   
   • Direct mapped vs. Set associative vs. Fully associative
   
   
   
   


4. Examine effect of replacement type
   
   


5. Examine effect of cache size
   
   

Analysis Paper

Objective

Write a paper with your analysis of cache designs.

Sections to Include

1. Introduction
   
   
   • Description of simulation
   
   
   
   


2. Description of Tests
   
   
   
   
   • What were the parameters for each test? Include the values of parameters. Give a table with the parameter values for each test.
   
   
   • Make sure to specify the associativity for set associative.
   
   
   • Make a table of parameter values for the tests.
   
   
   • Why did you choose these parameters?
   
   
   
   


3. Results
   
   
   • What were the hit rates for the different configurations?
   
   
   • Create plots to show your results.
     
     
     
     
     • Example: Line graph of hit rate vs cache size, with separate lines for FIFO and LRU
     
     
     • Make sure your plots are labeled on the x and y axes. y axis should be hit rate, x axis is independent variable. Give units on the independent variable (e.g. bytes)
     
     
     
     
   
   
   
   


4. Conclusions
   
   
   • What can you say about cache design (direct mapped/set associative/fully associative)?
   
   
   • What can you say about replacement policies?
   
   
   • What can you say about cache size?
   
   
   
   

There are lots of example problems in the material. Look at those examples and understand them before you start designing your solution.

Submission

You must submit the following:

1. Source code with a read me file with instructions for compiling and running.


2. A screen capture (movie/.mp4) showing your code being compiled and a sample run.


3. Your analysis paper.