Lab 12: Caching in Your Chips

Goals:

By the conclusion of this lab, you will have:

  1. Learned more about caches and how they work.
  2. Written code to help determine the (potential) effectiveness of a cache.

Background

    You have been asked to help ascertain whether or not a given cache system should be implemented as part of the Bonas2000 computer.  If a significant speedup is available, then the design team is willing to include the cache (i.e. it is not prohibitively expensive), but they don't know if the speedup will be great enough.  They currently believe that the following table gives the relative times for various operations.

Operation

Time Cost

Querying Cache Status (e.g. checking a tag)

2

Reading Data directly from Cache

5

Moving Data between Cache and Memory

18

Moving Data to/from Memory without Cache

16

It is possible that these estimates may change at some point in the future.  In this lab, you will develop a program to help investigate the desirability of including such a caching system.

 

Steps For This Lab

  1. Build a small C++ program to simulate a cache.  Your program should prompt the user for the size of the cache and the total amount of memory.  It should then accept a series of integers.  The integers will all be between 0 and the memory size - 1.  These represent the cells of memory to be read.

    Your program is to keep track of which cells are in the cache at any given moment.  If a cell is needed, but is not in the cache, it is assumed to be copied into the cache.  You are to keep track of the total time cost for all operations as well as the percentage of the time that a cache miss (or hit) occurs.  Once the user is done entering numbers, your program should print the appropriate statistics (i.e. total cost from each type of operation and the cache miss percentage.)

    Hint: The C++ idiom while (cin>>cellToReference) may be useful for reading the input.

    Hint: Since we are only naming the cells, you do not need to keep track of the actual data in the cell.  For simplicity purposes, you may wish to consider that cell I always holds the number I+2.  Then again, you may not want to worry about this.

    Hint: It probably pays to determine the cost of cache hits and misses BEFORE you begin coding.  Remember, though, that all operations in this step are READ operations.  In fact, you should really design a small test file BEFORE you begin coding.

    Hint: You might consider letting the user specify a file that contains the memory references rather than typing them in by hand.  This capability is likely to come in handy in Step 4, although you might want to add it later rather than right now.


  2. Now we change the interpretation of the data. If a number is negative, that means that we are "writing" to that memory cell.  This means that sometimes a cache miss will entail copying data in two directions not one.  You will need to implement some form of a "dirty" bit to handle this efficiently.


  3. When you are convinced that your simulation works and is well-coded, save it and print out a copy.



  4. Now design an experiment (or series of experiments) to determine whether or not the design team should implement this caching system for the Bonas2000 computer.  Write a short report describing your experiments - including how you chose the data, your conclusions, and your recommendation about the caching system.

    Hint: Based upon the data in the Background section, what must the cache hit percentage be in order to make it worthwhile to include the cache.  Does your data back up this conclusion?

To Hand In

  1. You are to hand in a copy of the listing from Step 3, the report from Step 4, and a cover page.

Extra Credit

  1. Repeat this exercise using a Set-Associative cache.  Note: while this is not trivial, neither is it as difficult as it might seem.



 

        Help Policy in Effect for This Assignment: Group Project With Limited Collaboration

       In particular, you may discuss the assignment and concepts related to the assignment with the following persons, in addition to an instructor in this course: any Computer Science instructor and any student enrolled in CS 231.

       You may use the following materials produced by other students: materials produced by member of your own group.