Cache Simulations

The following code fragment simulates a direct-mapped cache with 8 lines of 1 word.

#include "stdio.h"

int tag[8];

int main( )
{
    int addr;
    int i, j, t;
    int hits, accesses;
    FILE *fp;

    fp = fopen("trace.txt", "r");
    hits = 0;
    accesses = 0;
    while (fscanf(fp, "%x", &addr) > 0) {
        /* simulate a direct-mapped cache with 8 words */
        accesses += 1;
        printf("%3d: 0x%08x ", accesses, addr);
        i = (addr >> 2) & 7;
        t = addr | 0x1f;
        if (tag[i] == t) {
            hits += 1;
            printf("Hit%d ", i);
        } else {
            /* allocate entry */
            printf("Miss ");
            tag[i] = t;
        }
        for (i = 0; i < 8; i++)
            printf("0x%08x ", tag[i]);
        printf("\n");
    }
    printf("Hits = %d, Accesses = %d, Hit ratio = %f\n", hits, accesses, ((float)hits)/accesses);
    close(fp);
}

The structure of the code is as follows. First, the trace file is opened and each address is read from it (i.e. the fscanf() function call) into the variable addr. The index and tag parts of the address are extracted into the variables i and t respectively. The part of the address associated with the tag, t, is then compared to the tag at the specified index. If they match, a hit is recorded. On a miss the tag is updated to reflect the replaced cache entry. This cache simulator outputs a line for every memory access. When the end of the trace file is reached a summary is printed out.

Checkoff #1: What function does the line i = (addr >> 2) & 7; serve in the simulation?

Write your explanation here.

Checkoff #2: Compile and execute the direct-mapped cache simulator given above. Report the final number of hits and accesses output by the code. Also, based on the pattern of cache hits, estimate the hit rate of the given miniMIPS code fragment in the steady state (once the compulsory misses are accounted for).

Report your findings and estimates here.

Checkoff #3: Our implementation of a simple, direct-mapped cache simulator only uses and maintains the tags in its simulation. Why is this enough to get a working example of cache behavior?

Write your explanation here.

Part 2: A fully-associative cache

The next program simulates a fully associative cache with 8 lines each of 1 word.

#include "stdio.h"

int tag[8];
int mru[8] = {7,6,5,4,3,2,1,0};

void mruUpdate(int index)
{
    int i;
    // find index in mru
    for (i = 0; i < 8; i++)
        if (mru[i] == index)
            break;
    // move earlier refs one later
    while (i > 0) {
        mru[i] = mru[i-1];
        i--;
    }
    mru[0] = index;
}

int main( )
{
    int addr;
    int i, j, t;
    int hits, accesses;
    FILE *fp;
    
    fp = fopen("trace.txt", "r");
    hits = 0;
    accesses = 0;
    while (fscanf(fp, "%x", &addr) > 0) {
        /* simulate fully associative cache with 8 words */
        accesses += 1;
        printf("%3d: 0x%08x ", accesses, addr);
        for (i = 0; i < 8; i++) {
            if (tag[i] == addr) {
                hits += 1;
                printf("Hit%d ", i);
                mruUpdate(i);
                break;
            }
        }
        if (i == 8) {
            /* allocate entry */
            printf("Miss ");
            i = mru[7];
            tag[i] = addr;
            mruUpdate(i);
        }
        for (i = 0; i < 8; i++)
            printf("0x%08x ", tag[i]);
        for (i = 0; i < 8; i++)
            printf("%d ", mru[i]);
        printf("\n");
    }
    printf("Hits = %d, Accesses = %d, Hit ratio = %f\n", hits, accesses, ((float)hits)/accesses);
    close(fp);
}

This program maintains an array with 8 tags and the most-recently-used ordering of the lines in the array mru[]. When each address is read from the trace file, it is compared to all of the tags in the cache in the first for loop. If the tag is found, a hit is recorded, and the mru[] array is updated using the mruUpdate() function, and the loop is exited via the break statement. A miss is detected when no matches are found after searching all 8 tags. In this case the loop index, i, will be set to 8. On a miss the least recently-used tag, which should be the last element in mru[], is chosen for replacement, the tag is updated, and the mru[] array is updated.

As before, the cache simulator outputs a line for every memory access. When the end of the trace file is reached a summary is printed out.

Checkoff #4: Explain the newly-added function mruUpdate(), briefly outlining its purpose, how it works, and why we would want or need such a function in our fully-associative cache simulator.

Write your explanation here.

Checkoff #5: Compile and execute the fully-associative cache simulator provided above. Report the final number of hits and accesses output by the code. Based on the pattern of cache hits, estimate the hit rate of the given miniMIPS code fragment in the steady state (once the compulsory misses are accounted for).

Report your findings and estimates here.