CS 321: Homework

Memory Cache
(60 points)

"Time moves in one direction, memory in another."
--William Gibson

Objectives

Background

Memory cache, or just cache, is a hardware or software component in a computer that stores data so future requests for that data can be served faster. If there's copy of the data in cache, this data can read directly from the cache, instead of accessing it from main memory, which takes a lot more time. The data might be stored in a cache as the result of an earlier computation, or as the result of the duplication of data stored elsewhere.

  1. Cache Algorithms

    A number of cache replacement algorithms have developed for managing the data stored in a cache. These algorithms determine how the data should be organized and which pieces of data should be replaced, when the cache is full. One commonly used cache algorithm is called the Most Recently Used (MRU) algorithm.

    The MRU algorithm works as follows:

    • When a data request is made, a search for the data is made in the cache first.
      • If the data is found, which is called a cache hit, the cache returns the data. That data is then moved to the first position in the cache.
      • If the data is not found, which is called a cache miss, the data is first read from main memory. Then that data is added to the first position of the cache.

        Note: If the cache is full, the last entry (least recently used data) in the cache is removed before the new entry is added.

    • When a request is made to write data, that data is moved to the first position in the cache. But it's not an add operation. The data must already be in the cache.

  2. Types of Caches

    • One-Level Cache(L1): A single cache, which works as described above, if it is using the MRU algorithm.

    • Two-level Cache(L2): In addition to a L1 cache, there's a second, usually much larger, level of cache. It is located between the L1 cache and main memory.

      In general, all data in the L1 cache is also in the L2 cache. This is called the multi-level inclusion property. However, because L2 cache is much larger, there will be data in the L2 cache that is not in L1.

      The two-level cache works as follows:
      • If there's a L1 cache hit, both caches have the data. Even though the access and hit only count for the L1 cache, that data is moved to the top of both caches.
      • If there's a L1 cache miss but a L2 cache hit, the data is not in L1 cache but is in L2. The access counts against both caches, but only the L2 receives a hit. The data is added to the top of the L1 cache and is moved to the top of the L2 cache.
      • If there's a L1 and L2 cache miss, the data is in neither cache. This counts as an access against both caches, but neither gets a hit. The data is retrieved from main memory and added to the top of both caches.

  3. Cache Performance

    A common measure of cache performance is its hit rate: the number of cache hits relative to the total number of cache accesses, expressed as a percentage.

    • For a L1 cache, the hit ratio (HR1) is the number of L1 cache hits (NH1) divided by the total number of L1 cache accesses (NA1).
    • HR 1 = NH 1 NA 1
      If there is only a one-level cache, the overall cache hit rate (HR) is the same as the L1 hit rate (HR1)
    • For a L2 cache, the hit ratio (HR2) is the number of L2 cache hits (NH2) divided by the total number of L2 cache accesses (NA2).
    • HR 2 = NH 2 NA 2

    Another useful measure of cache performance is its miss rate: the number of cache misses relative to the total number of cache accesses, expressed as a percentage. It can be calculated by subtracting the hit rate from 1.

    Miss Rate = 1 - Hit Rate

    Given the number of hits for both caches (NH1 and NH2), and the overall number of cache accesses (NA1), we can determine the overall hit rate (HR) of a two-level cache, using this formula:

    HR = NH 1 + NH 2 NA 1

Tasks

  1. Create a Java class called Cache.

    • Your Cache class should be implemented using a double-linked list that holds generic objects.
      • Do not use the Java LinkedList class in your implementation.
      • Do not use your double-linked list implementation of the IndexedUnsortedList that you created in CS 221. This is a cache ADT, not a indexed-unsorted list ADT.
      • You should use the double-linked list node class called DLLNode that is provided in the zip file.

    • The class should implement the ICache interface, which defines a cache ADT.

    • In addition to the methods required by this interface, include:
      • a default constructor that creates an empty cache of capacity 100.
      • another constructor with a given capacity as a parameter.
      • any other methods necessary for the operation of your cache.

  2. To test the functionality of your Cache class, use the provided TestNG test classes. Before running the tests, be sure you completed Homework 0.
    • To test your Cache class in Eclipse:
      1. Import all of the test files and the cache XML file into your project.
      2. Right-click the XML file in the Package Explorer window.
      3. Your class should pass all 117 tests with no skips.

    • To test your Cache class on Onyx:
      1. Download the test files and the cache XML file into your project folder.
      2. Compile all of the test files.
      3. Use the following command to run the tests:
        java org.testng.TestNG cache.xml
      4. Your class should pass all 117 tests with no skips.

  3. Create driver class called CacheSimulator, that uses your Cache to simulate L1 and L2 caches.
    • Your class should include your main method and it should read in command-line arguments.
      • The tests run on your program won't verify input data, but it's a best practice to run some basic checks on the command-line arguments.
    • Your program should then instantiate two Cache objects, one for each level of cache. Be sure that the L2 cache is at least as large as the L1 cache.
    • Your program should read data from the input file, and keep track of the hit rate for your L1 cache and for your L2 cache, if it's a two-level cache.
    • Your program should print out the results on the console. See below for the format of the output.

  4. Test CacheSimulator with the given example files. The expected results of several runs with each example are provided.

In this zip file you will find the ICache interface, TestNG test files, and some example files to run the simulator. These provided files are just examples. You shouldn't assume that your program will be run only with these files.

Note:

To run simulations using Encyclopedia.txt on Onyx, you can first create a link to the file using this command:

    ln -s ~MhThomas/cs321/projects/files/Encyclopedia.txt

This file is quite large, so you probably don't want to copy to your own directory. After creating this link, you can refer to this file by its name without the directory information.

Program Execution

To operate correctly, CacheSimulator should run using the following command-line statement:

    java CacheSimulator [1 | 2] [L1 cache size] [ | L2 cache size] [filename]

where the 1 flag indicates that your program is just using a L1 cache, and the 2 flag indicates that your program is using both L1 and L2 caches. If your program is just using a L1 cache, you only have to include the size of that cache. If you're using both, then you have to include the size of both caches. For all cases, the last argument should be the name of the file you're running the program on.

For instance, if you're using just a L1 cache of size 1,000 on a file called myFile.txt, you would use the following command-line syntax:

    java CacheSimulator 1 1000 myFile.txt

Since there's only a L1 cache, the L1 hit rate and the overall hit rate will be the same. Assuming there were 100 cache accesses, 96 cache hits, your output should look like this:

    L1 cache with 1000 entries created
    ...
    Number of L1 cache hits: 96
    L1 cache hit rate: 96.00%

    Total number of accesses: 100
    Total number of cache hits: 96
    Overall hit rate: 96.00%

Your output should include exactly two decimal places of precision and the percentage symbol.

If you're using a L1 cache of size 1,000 and a L2 cache of size 5,000 on that same file, you would use the following command-line syntax:

    java CacheSimulator 2 1000 5000 myFile.txt

In this case, there are L1 and L2 caches, so the overall hit rate will have to be calculated. Assuming your L1 has an 90% hit rate and your L2 cache has a hit rate of 98%, your output should look like this:

    L1 cache with 1000 entries created
    L2 cache with 5000 entries created
    ...
    Number of L1 cache hits: 900
    L1 cache hit rate: 90.00%

    Number of L2 cache hits: 98
    L2 cache hit rate: 98.00%

    Total number of accesses: 1000
    Total number of cache hits: 998
    Overall hit rate: 99.80%

Grading

Points will be awarded according to the following breakdown:

Tasks

Points

Includes README file, comments

10

Correctly executes command-line arguments

10

CacheSimulator functionality

20

Cache class functionality

20

Required Files

To receive full credit, all the submitted files should be well documented, and should include program and method headers that use common Javadoc notation, as well as appropriate in-line comments.

Submit only the following files:

Submission

Submit this assignment electronically using the following command:

   submit MhThomas cs321 cache

Submit all files from the same directory. Do not include any unnecessary files.