Cache Simulator

Lesha Published at Dev

Lesha

I am writing a cache simulator. The idea is to given an input file with commands, trace the results of that input simulating cache functions so that we can keep track of cache hits and misses. I have written the following code but seem to be having trouble getting the proper output. I am posting my whole code because I dont want to make assumptions about where the problem may lie. Can anyone tell where I am making a mistake?

#include <stdlib.h>
#include <stdio.h>
#include <getopt.h>
#include <strings.h>

#include "cachelab.h"

/* Always use a 64-bit variable to hold memory addresses*/
typedef unsigned long long int mem_addr_t;

/* a struct that groups cache parameters together */
typedef struct {
    int s; /* 2**s cache sets */
    int b; /* cacheline block size 2**b bytes */
    int E; /* number of cachelines per set */
    int S; /* number of sets, derived from S = 2**s */
    int B; /* cacheline block size (bytes), derived from B = 2**b */
} cache_param_t;

int verbosity;

/*
 * printUsage - Print usage info
 */
void printUsage(char* argv[])
{
    printf("Usage: %s [-hv] -s <num> -E <num> -b <num> -t <file>\n", argv[0]);
    printf("Options:\n");
    printf("  -h         Print this help message.\n");
    printf("  -v         Optional verbose flag.\n");
    printf("  -s <num>   Number of set index bits.\n");
    printf("  -E <num>   Number of lines per set.\n");
    printf("  -b <num>   Number of block offset bits.\n");
    printf("  -t <file>  Trace file.\n");
    printf("\nExamples:\n");
    printf("  %s -s 4 -E 1 -b 4 -t traces/yi.trace\n", argv[0]);
    printf("  %s -v -s 8 -E 2 -b 4 -t traces/yi.trace\n", argv[0]);
    exit(0);
}

int main(int argc, char **argv)
{

    cache_param_t par;
    bzero(&par, sizeof(par));

    char *trace_file;
    char c;
    while( (c=getopt(argc,argv,"s:E:b:t:vh")) != -1){
        switch(c){
        case 's':
            par.s = atoi(optarg);
            break;
        case 'E':
            par.E = atoi(optarg);
            break;
        case 'b':
            par.b = atoi(optarg);
            break;
        case 't':
            trace_file = optarg;
            break;
        case 'v':
            verbosity = 1;
            break;
        case 'h':
            printUsage(argv);
            exit(0);
        default:
            printUsage(argv);
            exit(1);
        }
    }

    if (par.s == 0 || par.E == 0 || par.b == 0 || trace_file == NULL) {
        printf("%s: Missing required command line argument\n", argv[0]);
        printUsage(argv);
        exit(1);
    }

    /* TODO: Compute S and B based on information passed in */

    //Compute S and B, 2^s and 2^b respectively
    par.S = (1 << par.s);
    par.B = (1 << par.b);

    /* TODO: Initialize a cache */

    //Structure for a line
    typedef struct {
      int valid;
      mem_addr_t tag;
      int timestamp;
    } line_st;

    //Structure for a set; a pointer to an array of lines
    typedef struct {
      line_st *lines;
    } cache_set;

    //Structure for a cache; a pointer to an array of sets
    typedef struct {
      cache_set *sets;
    } cache_t;

    //allocate space for sets and for lines
    cache_t cache;
    cache.sets = malloc(par.S * sizeof(cache_set));
    for (int i = 0; i < par.S; i++) {
      cache.sets[i].lines = malloc(sizeof(line_st) * par.E);
    }

    //counters
    int hit_count = 0;
    int miss_count = 0;
    int eviction_count = 0;

    /* TODO: Run the trace simulation */

    char act; //L,S,M
    int size; //size read in from file
    int TSTAMP = 0; //value for LRU
    int empty = -1; //index of empty space
    int H = 0; //is there a hit
    int E = 0; //is there an eviction
    int toEvict = 0; //keeps track of what to evict
    mem_addr_t addr;

    //open the file and read it in
    FILE * traceFile = fopen(trace_file, "r");
    if (traceFile != NULL) {

      //keep going while we have additional lines
      //while(feof(traceFile) == 0) {
        while(fscanf(traceFile, " %c %llx,%d", &act, &addr, &size) == 3){
        if (act != 'I') {
        //read the next line and look for string formated as " %c %llx,%d"

        //sscanf(traceFile, " %c %llx,%d", &act, &addr, &size);
        //fscanf(traceFile, " %c %llx,%d", &act, &addr, &size);

        //calculate address tag and set index
        mem_addr_t addr_tag = addr >> (par.s + par.b);
        int tag_size = (64 - (par.s + par.b));
        unsigned long long temp = addr << (tag_size);
        unsigned long long setid = temp >> (tag_size + par.b);

        //unsigned long long setid = ((addr >> par.b) & (par.S - 1));
        cache_set set = cache.sets[setid];
        int low = par.E + 1;
        for(int e = 0; e < par.E; e++) {
          if (set.lines[e].valid == 0) {
        empty = e;
          }
          else if (set.lines[e].valid == 1){
        if (TSTAMP < low) {
          low = TSTAMP;
          toEvict = e;
        }
        if (set.lines[e].tag == addr_tag) {
          hit_count++;
          H = 1;
          set.lines[e].timestamp = TSTAMP;
          TSTAMP++;
        }
          }
        }
        //if we have a miss
        if (H != 1){
          miss_count++;
          //if we have an empty line
          if (empty > -1) {
        set.lines[empty].valid = 1;
        set.lines[empty].tag = addr_tag;
        set.lines[empty].timestamp = TSTAMP;
        TSTAMP++;
          }
          //if the set is full we need to evict
          else if (empty < 0) {
        E = 1;
        set.lines[toEvict].tag = addr_tag;
        set.lines[toEvict].timestamp = TSTAMP;
        eviction_count++;
          }
        }
        //if the instruction is M, we will always get a hit
        if (act == 'M') {
          hit_count++;
        }
        //if the -v flag is set print out all debug information
        if (verbosity == 1) {
          printf("%c ", act);
          //printf("%llx,%d ", addr_tag, setid);
          printf("%llx,%d ", addr, size);
          if (H == 1) {
        printf("Hit ");
          }
          else if (H != 1) {
        printf("Miss ");
          }
          if (E == 1) {
        printf("Eviction ");
          }
          if (act == 'M') {
        printf("Hit ");
          }
          printf("\n");
        }
        empty = -1;
        H = 0;
        E = 0;
      }
      }
    }

    /* TODO: Clean up cache resources */

    /* TODO: Print out real results */
    printSummary(hit_count, miss_count, eviction_count);
    return 0;
}

I am running my code with the following sample input:

 S 00600aa0,1
 S 7ff000384,4
 L 7ff000384,4
 L 7ff000384,4
 L 00600a20,4
 L 7ff000384,4

My code produces the following result:

./ -v -s 2 -E 2 -b 3 -t traces/test.trace
S 600aa0,1 Miss 
S 7ff000384,4 Miss 
L 7ff000384,4 Hit 
L 7ff000384,4 Hit 
L 600a20,4 Miss Eviction 
L 7ff000384,4 Miss Eviction 
hits:2 misses:4 evictions:2

but this is what it should be producing:

./ -v -s 2 -E 2 -b 3 -t traces/test.trace
S 600aa0,1 miss 
S 7ff000384,4 miss 
L 7ff000384,4 hit 
L 7ff000384,4 hit 
L 600a20,4 miss eviction 
L 7ff000384,4 hit 
hits:3 misses:3 evictions:1

Can anyone tell what I am doing wrong?

EDIT:

Second test file:

 S 00600aa0,1
I  004005b6,5
I  004005bb,5
I  004005c0,5
 S 7ff000398,8
I  0040051e,1
 S 7ff000390,8
I  0040051f,3
I  00400522,4
 S 7ff000378,8
I  00400526,4
 S 7ff000370,8
I  0040052a,7
 S 7ff000384,4
I  00400531,2
I  00400581,4
 L 7ff000384,4
I  00400585,2
I  00400533,7
 S 7ff000388,4
I  0040053a,2
I  00400577,4
 L 7ff000388,4
I  0040057b,2
I  0040053c,3
 L 7ff000384,4
I  0040053f,2
I  00400541,4
I  00400545,3
I  00400548,4
 L 7ff000378,8
I  0040054c,3
 L 7ff000388,4
I  0040054f,2
I  00400551,3
 L 00600a20,4
I  00400554,3
 S 7ff00038c,4
I  00400557,3
 L 7ff000388,4
I  0040055a,2
I  0040055c,4
I  00400560,3
I  00400563,4
 L 7ff000370,8
I  00400567,3
 L 7ff000384,4
I  0040056a,3
I  0040056d,3
 L 7ff00038c,4
I  00400570,3
 S 00600a60,4
I  00400573,4
 M 7ff000388,4
I  00400577,4
 L 7ff000388,4
I  0040057b,2
I  0040053c,3
 L 7ff000384,4
I  0040053f,2
I  00400541,4
I  00400545,3
I  00400548,4
 L 7ff000378,8
I  0040054c,3
 L 7ff000388,4
I  0040054f,2
I  00400551,3
 L 00600a24,4
I  00400554,3
 S 7ff00038c,4
I  00400557,3
 L 7ff000388,4
I  0040055a,2
I  0040055c,4
I  00400560,3
I  00400563,4
 L 7ff000370,8
I  00400567,3
 L 7ff000384,4
I  0040056a,3
I  0040056d,3
 L 7ff00038c,4
I  00400570,3
 S 00600a70,4
I  00400573,4
 M 7ff000388,4
I  00400577,4
 L 7ff000388,4
I  0040057b,2
I  0040053c,3
 L 7ff000384,4
I  0040053f,2
I  00400541,4
I  00400545,3
I  00400548,4
 L 7ff000378,8
I  0040054c,3
 L 7ff000388,4
I  0040054f,2
I  00400551,3
 L 00600a28,4
I  00400554,3
 S 7ff00038c,4
I  00400557,3
 L 7ff000388,4
I  0040055a,2
I  0040055c,4
I  00400560,3
I  00400563,4
 L 7ff000370,8
I  00400567,3
 L 7ff000384,4
I  0040056a,3
I  0040056d,3
 L 7ff00038c,4
I  00400570,3
 S 00600a80,4
I  00400573,4
 M 7ff000388,4
I  00400577,4
 L 7ff000388,4
I  0040057b,2
I  0040053c,3
 L 7ff000384,4
I  0040053f,2
I  00400541,4
I  00400545,3
I  00400548,4
 L 7ff000378,8
I  0040054c,3
 L 7ff000388,4
I  0040054f,2
I  00400551,3
 L 00600a2c,4
I  00400554,3
 S 7ff00038c,4
I  00400557,3
 L 7ff000388,4
I  0040055a,2
I  0040055c,4
I  00400560,3
I  00400563,4
 L 7ff000370,8
I  00400567,3
 L 7ff000384,4
I  0040056a,3
I  0040056d,3
 L 7ff00038c,4
I  00400570,3
 S 00600a90,4
I  00400573,4
 M 7ff000388,4
I  00400577,4
 L 7ff000388,4
I  0040057b,2
I  0040057d,4
 M 7ff000384,4
I  00400581,4
 L 7ff000384,4
I  00400585,2
I  00400533,7
 S 7ff000388,4
I  0040053a,2
I  00400577,4
 L 7ff000388,4
I  0040057b,2
I  0040053c,3
 L 7ff000384,4
I  0040053f,2
I  00400541,4
I  00400545,3
I  00400548,4
 L 7ff000378,8
I  0040054c,3
 L 7ff000388,4
I  0040054f,2
I  00400551,3
 L 00600a30,4
I  00400554,3
 S 7ff00038c,4
I  00400557,3
 L 7ff000388,4
I  0040055a,2
I  0040055c,4
I  00400560,3
I  00400563,4
 L 7ff000370,8
I  00400567,3
 L 7ff000384,4
I  0040056a,3
I  0040056d,3
 L 7ff00038c,4
I  00400570,3
 S 00600a64,4
I  00400573,4
 M 7ff000388,4
I  00400577,4
 L 7ff000388,4
I  0040057b,2
I  0040053c,3
 L 7ff000384,4
I  0040053f,2
I  00400541,4
I  00400545,3
I  00400548,4
 L 7ff000378,8
I  0040054c,3
 L 7ff000388,4
I  0040054f,2
I  00400551,3
 L 00600a34,4
I  00400554,3
 S 7ff00038c,4
I  00400557,3
 L 7ff000388,4
I  0040055a,2
I  0040055c,4
I  00400560,3
I  00400563,4
 L 7ff000370,8
I  00400567,3
 L 7ff000384,4
I  0040056a,3
I  0040056d,3
 L 7ff00038c,4
I  00400570,3
 S 00600a74,4
I  00400573,4
 M 7ff000388,4
I  00400577,4
 L 7ff000388,4
I  0040057b,2
I  0040053c,3
 L 7ff000384,4
I  0040053f,2
I  00400541,4
I  00400545,3
I  00400548,4
 L 7ff000378,8
I  0040054c,3
 L 7ff000388,4
I  0040054f,2
I  00400551,3
 L 00600a38,4
I  00400554,3
 S 7ff00038c,4
I  00400557,3
 L 7ff000388,4
I  0040055a,2
I  0040055c,4
I  00400560,3
I  00400563,4
 L 7ff000370,8
I  00400567,3
 L 7ff000384,4
I  0040056a,3
I  0040056d,3
 L 7ff00038c,4
I  00400570,3
 S 00600a84,4
I  00400573,4
 M 7ff000388,4
I  00400577,4
 L 7ff000388,4
I  0040057b,2
I  0040053c,3
 L 7ff000384,4
I  0040053f,2
I  00400541,4
I  00400545,3
I  00400548,4
 L 7ff000378,8
I  0040054c,3
 L 7ff000388,4
I  0040054f,2
I  00400551,3
 L 00600a3c,4
I  00400554,3
 S 7ff00038c,4
I  00400557,3
 L 7ff000388,4
I  0040055a,2
I  0040055c,4
I  00400560,3
I  00400563,4
 L 7ff000370,8
I  00400567,3
 L 7ff000384,4
I  0040056a,3
I  0040056d,3
 L 7ff00038c,4
I  00400570,3
 S 00600a94,4
I  00400573,4
 M 7ff000388,4
I  00400577,4
 L 7ff000388,4
I  0040057b,2
I  0040057d,4
 M 7ff000384,4
I  00400581,4
 L 7ff000384,4
I  00400585,2
I  00400533,7
 S 7ff000388,4
I  0040053a,2
I  00400577,4
 L 7ff000388,4
I  0040057b,2
I  0040053c,3
 L 7ff000384,4
I  0040053f,2
I  00400541,4
I  00400545,3
I  00400548,4
 L 7ff000378,8
I  0040054c,3
 L 7ff000388,4
I  0040054f,2
I  00400551,3
 L 00600a40,4
I  00400554,3
 S 7ff00038c,4
I  00400557,3
 L 7ff000388,4
I  0040055a,2
I  0040055c,4
I  00400560,3
I  00400563,4
 L 7ff000370,8
I  00400567,3
 L 7ff000384,4
I  0040056a,3
I  0040056d,3
 L 7ff00038c,4
I  00400570,3
 S 00600a68,4
I  00400573,4
 M 7ff000388,4
I  00400577,4
 L 7ff000388,4
I  0040057b,2
I  0040053c,3
 L 7ff000384,4
I  0040053f,2
I  00400541,4
I  00400545,3
I  00400548,4
 L 7ff000378,8
I  0040054c,3
 L 7ff000388,4
I  0040054f,2
I  00400551,3
 L 00600a44,4
I  00400554,3
 S 7ff00038c,4
I  00400557,3
 L 7ff000388,4
I  0040055a,2
I  0040055c,4
I  00400560,3
I  00400563,4
 L 7ff000370,8
I  00400567,3
 L 7ff000384,4
I  0040056a,3
I  0040056d,3
 L 7ff00038c,4
I  00400570,3
 S 00600a78,4
I  00400573,4
 M 7ff000388,4
I  00400577,4
 L 7ff000388,4
I  0040057b,2
I  0040053c,3
 L 7ff000384,4
I  0040053f,2
I  00400541,4
I  00400545,3
I  00400548,4
 L 7ff000378,8
I  0040054c,3
 L 7ff000388,4
I  0040054f,2
I  00400551,3
 L 00600a48,4
I  00400554,3
 S 7ff00038c,4
I  00400557,3
 L 7ff000388,4
I  0040055a,2
I  0040055c,4
I  00400560,3
I  00400563,4
 L 7ff000370,8
I  00400567,3
 L 7ff000384,4
I  0040056a,3
I  0040056d,3
 L 7ff00038c,4
I  00400570,3
 S 00600a88,4
I  00400573,4
 M 7ff000388,4
I  00400577,4
 L 7ff000388,4
I  0040057b,2
I  0040053c,3
 L 7ff000384,4
I  0040053f,2
I  00400541,4
I  00400545,3
I  00400548,4
 L 7ff000378,8
I  0040054c,3
 L 7ff000388,4
I  0040054f,2
I  00400551,3
 L 00600a4c,4
I  00400554,3
 S 7ff00038c,4
I  00400557,3
 L 7ff000388,4
I  0040055a,2
I  0040055c,4
I  00400560,3
I  00400563,4
 L 7ff000370,8
I  00400567,3
 L 7ff000384,4
I  0040056a,3
I  0040056d,3
 L 7ff00038c,4
I  00400570,3
 S 00600a98,4
I  00400573,4
 M 7ff000388,4
I  00400577,4
 L 7ff000388,4
I  0040057b,2
I  0040057d,4
 M 7ff000384,4
I  00400581,4
 L 7ff000384,4
I  00400585,2
I  00400533,7
 S 7ff000388,4
I  0040053a,2
I  00400577,4
 L 7ff000388,4
I  0040057b,2
I  0040053c,3
 L 7ff000384,4
I  0040053f,2
I  00400541,4
I  00400545,3
I  00400548,4
 L 7ff000378,8
I  0040054c,3
 L 7ff000388,4
I  0040054f,2
I  00400551,3
 L 00600a50,4
I  00400554,3
 S 7ff00038c,4
I  00400557,3
 L 7ff000388,4
I  0040055a,2
I  0040055c,4
I  00400560,3
I  00400563,4
 L 7ff000370,8
I  00400567,3
 L 7ff000384,4
I  0040056a,3
I  0040056d,3
 L 7ff00038c,4
I  00400570,3
 S 00600a6c,4
I  00400573,4
 M 7ff000388,4
I  00400577,4
 L 7ff000388,4
I  0040057b,2
I  0040053c,3
 L 7ff000384,4
I  0040053f,2
I  00400541,4
I  00400545,3
I  00400548,4
 L 7ff000378,8
I  0040054c,3
 L 7ff000388,4
I  0040054f,2
I  00400551,3
 L 00600a54,4
I  00400554,3
 S 7ff00038c,4
I  00400557,3
 L 7ff000388,4
I  0040055a,2
I  0040055c,4
I  00400560,3
I  00400563,4
 L 7ff000370,8
I  00400567,3
 L 7ff000384,4
I  0040056a,3
I  0040056d,3
 L 7ff00038c,4
I  00400570,3
 S 00600a7c,4
I  00400573,4
 M 7ff000388,4
I  00400577,4
 L 7ff000388,4
I  0040057b,2
I  0040053c,3
 L 7ff000384,4
I  0040053f,2
I  00400541,4
I  00400545,3
I  00400548,4
 L 7ff000378,8
I  0040054c,3
 L 7ff000388,4
I  0040054f,2
I  00400551,3
 L 00600a58,4
I  00400554,3
 S 7ff00038c,4
I  00400557,3
 L 7ff000388,4
I  0040055a,2
I  0040055c,4
I  00400560,3
I  00400563,4
 L 7ff000370,8
I  00400567,3
 L 7ff000384,4
I  0040056a,3
I  0040056d,3
 L 7ff00038c,4
I  00400570,3
 S 00600a8c,4
I  00400573,4
 M 7ff000388,4
I  00400577,4
 L 7ff000388,4
I  0040057b,2
I  0040053c,3
 L 7ff000384,4
I  0040053f,2
I  00400541,4
I  00400545,3
I  00400548,4
 L 7ff000378,8
I  0040054c,3
 L 7ff000388,4
I  0040054f,2
I  00400551,3
 L 00600a5c,4
I  00400554,3
 S 7ff00038c,4
I  00400557,3
 L 7ff000388,4
I  0040055a,2
I  0040055c,4
I  00400560,3
I  00400563,4
 L 7ff000370,8
I  00400567,3
 L 7ff000384,4
I  0040056a,3
I  0040056d,3
 L 7ff00038c,4
I  00400570,3
 S 00600a9c,4
I  00400573,4
 M 7ff000388,4
I  00400577,4
 L 7ff000388,4
I  0040057b,2
I  0040057d,4
 M 7ff000384,4
I  00400581,4
 L 7ff000384,4
I  00400585,2
I  00400587,1
 L 7ff000390,8
I  00400588,1
 L 7ff000398,8
I  004005c5,7
 L 00600aa0,1

Expected Values:

              My simulator       Reference simulator
(s,E,b)    Hits  Misses  Evicts    Hits  Misses  Evicts
(2,2,3)     196      42      34     201      37      29  
(2,4,3)     208      30      14     212      26      10

JohnH

Tricky bug there. I changed the for-loop in the middle to only set empty if it is already -1, so it will use the first empty spot found, then it won't change it again once it has found an empty spot. I also modified the initialization of low to be INT_MAX and look for true least-recently used by changing the relevant else conditions. I also re-ordered the code to look for a match BEFORE looking for eviction candidates, since finding a match freshens the cache timestamp. You also had forgotten to increment TSTAMP in the case of a Miss Eviction.

#include <stdlib.h>
#include <stdio.h>
#include <getopt.h>
#include <strings.h>
#include <limits.h>

//#include "cachelab.h"

/* Always use a 64-bit variable to hold memory addresses*/
typedef unsigned long long int mem_addr_t;

/* a struct that groups cache parameters together */
typedef struct
{
   int s;                       /* 2**s cache sets */
   int b;                       /* cacheline block size 2**b bytes */
   int E;                       /* number of cachelines per set */
   int S;                       /* number of sets, derived from S = 2**s */
   int B;                       /* cacheline block size (bytes), derived from B = 2**b */
} cache_param_t;

int verbosity;

/* printUsage - Print usage info */
void printUsage( char *argv[] )
{
   printf( "Usage: %s [-hv] -s <num> -E <num> -b <num> -t <file>\n", argv[0] );
   printf( "Options:\n" );
   printf( "  -h         Print this help message.\n" );
   printf( "  -v         Optional verbose flag.\n" );
   printf( "  -s <num>   Number of set index bits.\n" );
   printf( "  -E <num>   Number of lines per set.\n" );
   printf( "  -b <num>   Number of block offset bits.\n" );
   printf( "  -t <file>  Trace file.\n" );
   printf( "\nExamples:\n" );
   printf( "  %s -s 4 -E 1 -b 4 -t traces/yi.trace\n", argv[0] );
   printf( "  %s -v -s 8 -E 2 -b 4 -t traces/yi.trace\n", argv[0] );
   exit( 0 );
}

void printSummary( int hit_count, int miss_count, int eviction_count )
{
   printf( "hits: %d   misses: %d   evictions: %d\n", hit_count, miss_count, eviction_count );
} 

int main( int argc, char **argv )
{
   cache_param_t par;

   bzero( &par, sizeof ( par ) );

   char *trace_file;
   char c;

   while ( ( c = getopt( argc, argv, "s:E:b:t:vh" ) ) != -1 )
   {
      switch ( c )
      {
         case 's':
            par.s = atoi( optarg );
            break;
         case 'E':
            par.E = atoi( optarg );
            break;
         case 'b':
            par.b = atoi( optarg );
            break;
         case 't':
            trace_file = optarg;
            break;
         case 'v':
            verbosity = 1;
            break;
         case 'h':
            printUsage( argv );
            exit( 0 );
         default:
            printUsage( argv );
            exit( 1 );
      }
   }

   if ( par.s == 0 || par.E == 0 || par.b == 0 || trace_file == NULL )
   {
      printf( "%s: Missing required command line argument\n", argv[0] );
      printUsage( argv );
      exit( 1 );
   }

   /* TODO: Compute S and B based on information passed in */

   //Compute S and B, 2^s and 2^b respectively
   par.S = ( 1 << par.s );
   par.B = ( 1 << par.b );

   /* TODO: Initialize a cache */

   //Structure for a line
   typedef struct
   {
      int valid;
      mem_addr_t tag;
      int timestamp;
   } line_st;

   //Structure for a set; a pointer to an array of lines
   typedef struct
   {
      line_st *lines;
   } cache_set;

   //Structure for a cache; a pointer to an array of sets
   typedef struct
   {
      cache_set *sets;
   } cache_t;

   //allocate space for sets and for lines
   cache_t cache;

   cache.sets = malloc( par.S * sizeof ( cache_set ) );
   for ( int i = 0; i < par.S; i++ )
   {
      cache.sets[i].lines = malloc( sizeof ( line_st ) * par.E );
   }

   //counters
   int hit_count = 0;
   int miss_count = 0;
   int eviction_count = 0;

   /* TODO: Run the trace simulation */

   char act;                    //L,S,M
   int size;                    //size read in from file
   int TSTAMP = 0;              //value for LRU
   int empty = -1;              //index of empty space
   int H = 0;                   //is there a hit
   int E = 0;                   //is there an eviction
   mem_addr_t addr;

   //open the file and read it in
   FILE *traceFile = fopen( trace_file, "r" );

   if ( traceFile != NULL )
   {
      while ( fscanf( traceFile, " %c %llx,%d", &act, &addr, &size ) == 3 )
      {
         int toEvict = 0;             //keeps track of what to evict
         if ( act != 'I' )
         {
            //calculate address tag and set index
            mem_addr_t addr_tag = addr >> ( par.s + par.b );
            int tag_size = ( 64 - ( par.s + par.b ) );
            unsigned long long temp = addr << ( tag_size );
            unsigned long long setid = temp >> ( tag_size + par.b );
            cache_set set = cache.sets[setid];
            int low = INT_MAX; // CHANGED, also added #include <limits.h>

            for ( int e = 0; e < par.E; e++ ) {
               if ( set.lines[e].valid == 1 ) {
                  // CHANGED ORDER: look for hit before eviction candidates
                  if ( set.lines[e].tag == addr_tag ) {
                     hit_count++;
                     H = 1;
                     set.lines[e].timestamp = TSTAMP;
                     TSTAMP++;
                  }
                  // CHANGED WHOLE ELSE: look for oldest for eviction.
                  else if ( set.lines[e].timestamp < low ) {
                     low = set.lines[e].timestamp;
                     toEvict = e;
                  }
               }
               // CHANGED: if we haven't yet found an empty, mark one that we found.
               else if( empty == -1 ) {
                  empty = e;
               }
            }

            //if we have a miss
            if ( H != 1 )
            {
               miss_count++;
               //if we have an empty line
               if ( empty > -1 )
               {
                  set.lines[empty].valid = 1;
                  set.lines[empty].tag = addr_tag;
                  set.lines[empty].timestamp = TSTAMP;
                  TSTAMP++; 
               }
               //if the set is full we need to evict
               else if ( empty < 0 )
               {
                  E = 1;
                  set.lines[toEvict].tag = addr_tag;
                  set.lines[toEvict].timestamp = TSTAMP;
                  TSTAMP++; // CHANGED: increment TSTAMP here too
                  eviction_count++;
               }
            }
            //if the instruction is M, we will always get a hit
            if ( act == 'M' )
            {
               hit_count++;
            }
            //if the -v flag is set print out all debug information
            if ( verbosity == 1 )
            {
               printf( "%c ", act );
               printf( "%llx,%d", addr, size );
               if ( H == 1 )
               {
                  printf( "Hit " );
               }
               else if ( H != 1 )
               {
                  printf( "Miss " );
               }
               if ( E == 1 )
               {
                  printf( "Eviction " );
               }
               // CHANGED: don't print Hit again since 'M' is always going to print Hit above.
               printf( "\n" );
            }
            empty = -1;
            H = 0;
            E = 0;
         }
      }
   }

   /* TODO: Clean up cache resources */

   /* TODO: Print out real results */
   printSummary( hit_count, miss_count, eviction_count );
   return 0;
}

My results:

$ ./ca2 -s 2 -E 2 -b 3 -t f2.trace
hits: 201   misses: 37   evictions: 29
$ ./ca2 -s 2 -E 4 -b 3 -t f2.trace
hits: 212   misses: 26   evictions: 10

Collected from the Internet

Please contact [email protected] to delete if infringement.

edited at2021-02-7

Comments

0 comments

From Dev

Related Related

Article

Cache Simulator

Cache Simulator

Cache simulator in C errors

How to clear IOS simulator memory cache

imageWithcontentsOfFile failing to load saved image from simulator cache dir

Restkit creates duplicates (error: "Managed object cache returned 2 objects") only on device, not in simulator

Restkit creates duplicates (error: "Managed object cache returned 2 objects") only on device, not in simulator

Birth simulator

Is there a simulator for tvOS?

'atm' simulator

Running Watch Simulator and iOS Simulator

Sensor simulator's NetworkOnMainThreadException

Uninstall Apps on tvOS Simulator

Is there an iPhone 5 simulator?

This Browser is not supported in iOS simulator

iOS Simulator not updating location

Simulator or Emulator? What is the difference?

Black screen in iOS simulator

Take screenshots in the iOS simulator

Using GCController with tvOS Simulator

Network Simulator for Ubuntu 12.04

iOS Simulator too big

Unable to run app in simulator

Simulating CoreMotion iOS Simulator

Simulator build for Apple Watch

Document folder iOS Simulator

iPad simulator and external screen

Is there a simulator/emulator of Xeon Phi?

Generate simulator build

App not showing in "Apps" in simulator

Lightweight VHDL simulator in Windows