CSARCH2---Cache-Simulation

Demo Video

Test Cases Input

Sequential Sequence

# Simulates a sequential memory access sequence up to 2n cache block and repeats the sequence four times
    private void sequentialSequence(){
        int numCacheBlocks = cache.getNumBlocks();
        int sequenceLength = 2 * numCacheBlocks;
    
        for (int reps = 0; reps < 4; reps++){
            for (int i = 0; i < sequenceLength; i++)
                memory.toCache(cache, i);
        }
    }

When the cache is empty, it is represented by the value -1. Because 0%4 equals 0, we can write the value to set 0. Furthermore, if the stack is empty, the item will be stored at the lowest available cache block. It's worth noting that when the cache is full, we must replace an old value with the new value we want to save. To identify which cache index to employ, a replacement algorithm is required.

In case that the cache is full, we will use the random replacement algorithm.

 public void replace(int data, int randomIndex){
        blocks[randomIndex] = data;
    }

Based on the output of the random algorithm, the data value is placed in cache block 7, which belongs to the set of 32%4=0.

In instances where the replacement value generated at random fails to match the index of the cache hit, the corresponding block value remains unaltered. Instead, the system proceeds to execute a read operation from the cache memory.

This is the final output of the 8-way (Random Replacement algorithm) - Sequential Sequence

Then we also print out our final cache details:
Total Access Count = 256; Since our number of cache blocks is 32 and the Random sequence is 4x64 blocks.

Cache Hits = 45

Cache Misses = 211

Miss Penalty = 52ns; Since our block size was 5 words. And the formula is (1+(blocksize*10)+1)

Average Memory Access Time = 44.62ns

; We get this by first calculating our hit rate and our miss rate. Which is 45/256 and 211/256 respectively.
; cacheAccessTime is 10 and missPenalty is 52ns as calculated before.
; And then we use the formula: hitRate x cacheAccessTime + missRate x missPenalty
; ((45/256) x 10 + (211/256) x 52) = 44.62ns

Total Memory Access Time = 11422.0ns

; We use the formula: cacheHits x cacheAccessTime + cacheMisses x missPenalty
; cacheAccessTime is 10 and missPenalty is 52ns as calculated before.
; (45 x 10 + 211 x 52) = 5438.0ns

Random

#  Simulates a random memory access sequence containing 4n blocks
    private void randomSequence(){
        Random random = new Random();
        int numCacheBlocks = 4 * cache.getNumBlocks();
    
        for (int i = 0; i < 32 * 4; i++)
            memory.toCache(cache, random.nextInt(numCacheBlocks));
    }

After providing all the inputs, we end up with this screen with the details for our Random Sequence Test Case:

Since this test case has a random sequence containing 4*32 blocks, there is no telling what number comes next. Also, we will fill out the set first, before using our random replacement algorithm. Empty cache blocks are denoted by -1. For our first one here, we have (111), when we modulo it by 4, we get 3. So we put it at Set 3 and at cache block 0. Update the cache misses and the total memory access time.

Next we get (42), when we modulo it by 4, we get 2. So we put it at Set 2 and at cache block 0. Update the cache misses and the total memory access time.

So we keep doing this until the set where the next value is going to be placed is already full which will cause us to use our random replacement algorithm. In this next one, we encounter our first cache hit. We can see here that in Set 1, (125) is at cache block 1 1.

And our next value also happens to be (125). Since it is a cache hit, we do nothing and increment our cache hits and our total memory access time.

We then encounter our first instance wherein we will use our replacement algorithm. Our next data is (2), so we put it in Set 2. However, as you can see below, the entire set is already filled.

So we use the replacement algorithm, in which it returned 1. So we replaced (6) and put (2) now at cache block 1. Update the cache misses and the total memory access time.

We then reach a point where the replacement algorithm is now used every time since all the sets are always full. After doing all the necessary replacements, we now have our final sets of values.

Then we also print out our final cache details:
Total Access Count = 128; Since our number of cache blocks is 32 and the Random sequence is 4x32 blocks.

Cache Hits = 29

Cache Misses = 99

Miss Penalty = 52ns; Since our block size was 5 words. And the formula is (1+(blocksize*10)+1)

Average Memory Access Time = 42.48ns

; We get this by first calculating our hit rate and our miss rate. Which is 29/128 and 99/128 respectively.
; cacheAccessTime is 10 and missPenalty is 52ns as calculated before.
; And then we use the formula: hitRate x cacheAccessTime + missRate x missPenalty
; ((29/128) x 10 + (99/128) x 52) = 42.48ns

Total Memory Access Time = 5438.0ns

; We use the formula: cacheHits x cacheAccessTime + cacheMisses x missPenalty
; cacheAccessTime is 10 and missPenalty is 52ns as calculated before.
; (29 x 10 + 99 x 52) = 5438.0ns

Mid-Repeat

# Simulates a memory access sequence with mid-repeat blocks which starts at block 0,
# then repeat the sequence in the middle two times up to n-1 blocks,
# after which continue up to 2n
    private void midRepeatBlocks(){
        int numCacheBlocks = cache.getNumBlocks();
        for (int reps = 0; reps < 4; reps++){

            memory.toCache(cache, 0);

            for (int i = 0; i < 2; i++){
                for (int j = 1; j < numCacheBlocks; j++)
                    memory.toCache(cache, j);
            }
            
            for (int k = numCacheBlocks; k < numCacheBlocks*2; k++)
                memory.toCache(cache, k);
        }
    }

After providing the input for the test case, we then get this screen including the details for our Mid Repeat Test Cases:

For this test case, we will start at block 0, then it will repeat the sequence in the middle 2 times until n-1 blocks, which will continue on to 2n. This sequence will then be repeated for 4 times. We then proceed to fill up the first set, starting at (0). Modulo it by 4 which will give us 0. We will put this in Set 0 and in index 1. We then update the cache misses and total memory access time.

The sequence will continue from (0) to (31) where we modulo it again by 4 to determine its designated set which will get us 3 then we will put it in Set 3 and in Index 8. Update the Cache Miss and total memory access time.

Since this test case is a mid-repeat sequence, we will then go back to (1) to repeat the middle sequence for the second time until n-1 blocks. Modulo by 4 we get 1 so we will put it in Set 1 and since 1 exists in the Set, we will just update the Cache Hit and the total memory access time.

After repeating the sequence in the middle for the second time, we will then proceed to (32) until (63). We modulo (32) by 4 to get the set location and we will get 0. We now put it in Set 0 and we will replace 24 in index 7 with (32). We then update the Cache Miss and total memory access time.

Final Result of the Cache Memory View for Mid Repeat Test Case

After the replacement algorithm reaches 2n, the sequence will be repeated 4 times and it will come to a point where we will get the following final cache values:

The final cache details would be:

Total Access Count = 380

Cache Hits = 110

Cache Misses = 270

Miss Penalty = 52ns

Average Memory Access Time = 39.84ns

; We get this by first calculating our hit rate and our miss rate. Which is 110/380 and 270/380 respectively.
; cacheAccessTime is 10 and missPenalty is 52ns as calculated before.
; And then we use the formula: hitRate x cacheAccessTime + missRate x missPenalty
; ((110/380) x 10 + (270/380) x 52) = 39.84ns

Total Memory Access Time = 15140.0ns

; We use the formula: cacheHits x cacheAccessTime + cacheMisses x missPenalty
; cacheAccessTime is 10 and missPenalty is 52ns as calculated before.
; (110 x 10 + 270 x 52) = 15140.0ns