CDA3101  Cache Simulation Solved

Description

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?

 

Video Describing the Project

M07_07_CacheAnalysisProject_CDA3101_f21_Resch_Accessible.pptx

Do yourself a favor: Look at course material to learn about caches.  You CANNOT get everything you need to know about how to do this project from just the video or project description.  Applicable slide decks from lectures are Module 7, Parts 3, 4 and 5.

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 bytes in the cache (a positive power of 2)
• Number of blocks in each set (associativity)
• 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

1. Replacement policy (for caches that aren’t direct mapped) 

• Least recently used (LRU)
• First in, first out (FIFO)

1. Examine effect of changing cache type 

• Direct mapped vs. Set associative vs. Fully associative

1. Examine effect of replacement type
2. 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

1. Description of Tests 

• What were the parameters for each test? Include the values of parameters: cache size, block size, associativity, replacement strategy.
• Make sure to specify the associativity for set associative.
• Why did you choose these parameters?

1. 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)

1. 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 (.mov or .mp4) showing your code being compiled and a sample run.  Your name should appear somewhere in the video. Sound is not necessary.
3. Your analysis paper.

You may zip up parts 1 and 2.  The analysis paper must be turned in separately so it will go through turnitin.

So you can submit a zip file with parts 1 and 2 AND the analysis paper, but not one zip file.

You must submit code.   Code with no paper = 20 points.  Paper with no code=0 points.  Code with paper = 20-100 points.

 Return to Module 8