Objectives

Implement a memory cache ADT using a double-linked list in Java

Read data from files

Create a test program for verifying the operation of your cache

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:

1. When a data request is made, a search for the data is made in the cache first.

a.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.

b. 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.

2. 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

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

b. 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:

a. 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.

b. 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.

c. 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.

a. For a L1 cache, the hit ratio (HR₁) is the number of L1 cache hits (NH₁) divided by the total number of L1 cache accesses (NA₁).

If there is only a one-level cache, the overall cache hit rate (HR) is the same as the L1 hit rate (HR₁)

b. For a L2 cache, the hit ratio (HR₂) is the number of L2 cache hits (NH₂) divided by the total number of L2 cache accesses (NA₂).

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 (NH₁ and NH₂), and the overall number of cache accesses (NA₁), we can determine the overall hit rate (HR) of a two-level cache, using this formula:

Tasks

1. Create a Java class called Cache.

a. Your class should use double-linked list implementation that holds generic objects.

b. include a default constructor that creates an empty cache of capacity 100, another constructor with a given capacity as a parameter, and any other methods necessary for the operation of your cache.

2. Create is a tester class.

a. Driver class should be called Test.

b. It should include 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.

c. 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.

d. 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.

e. Program should print out the results on the console. See below for the format of the output.

Program Execution

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

java Test [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 Test 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 Test 2 1000 5000 myFile.txt

In this case, there are L1 and 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%

HR, NH, = NAI