Thread: D-Cache/I Cache Simulator

Hello,

I need to modify this code to allow me to obtain input from the user for how many sets, bytes, associativity, and block size for a cache. I need to simulate based on a d-cache and then an I-cache. However i need to incorporate it with the trace viewer I already have built. Can anyone give me any insight of what to do with the skeleton to get me in the right direction?

Here is the cache skeleton, and I've added a few items to it however:

Code:

struct cache_blk_t {
  unsigned long tag;
  char valid;
  char dirty;

  cache_blk_t *way_next;
  cache_blk_t *way_prev;
};

struct cache_set_t {
  cache_blk_t *way_head;
  cache_blk_t *way_tail;

  unsigned int FIFO_counter;
};

enum cache_policy {
  LRU,
  Random,
  FIFO
};

struct cache_t
{
  int nsets;		// # sets
  int bsize;		// block size
  int assoc;		// associativity


  enum cache_policy policy;

  // statistics
  unsigned long accesses;
  unsigned long hits;
  unsigned long misses;
  unsigned long replacements;
  unsigned long writebacks;

  struct cache_set_t *sets;
};

int assocInput;
int bsizeInput;
int nsetsInput;

void
cache_create(int assoc, int bsize, int nsets, enum cache_policy policy)
{
  //create cache based on A, B, and C
  //allocate sets
  //allocate blocks in each set
  //remember the replacement policy setting
  //initialize statistics data
  cache_char2policy(char c);
};

int
cache_access(struct cache_t *cp, unsigned long address, char access_type)
{
  //based on address determine the set to access in cp
  //examine blocks in the set to check hit/miss
  //if miss, determine the victim in the set to replace
  //if LRU is used, update the block list
};

Basically also, I need to decifer between d-cache and i-cache in the simulator...the program already takes three(3) arguments, for the trace file, and if the viewer is on or off.

Here is my code i need to incorporate with:

Code:

#include <stdio.h>
#include <string.h>
// You can include the trace item structure and type by including a header file
#include "mytrace.h"

#define TRACE_BUFSIZE 1024*1024
#include <stdint.h>
#include <stdlib.h>
#define N 50
double A[N][N];
int i,j;
static FILE *trace_fd;
static int trace_buf_ptr;
static int trace_buf_end;
static struct trace_item *trace_buf;

void trace_init()
{
  trace_buf = (trace_item*)malloc(sizeof(struct trace_item) * TRACE_BUFSIZE);

  if (!trace_buf) {
    fprintf(stdout, "** trace_buf not allocated\n");
    exit(-1);
  }

  trace_buf_ptr = 0;
  trace_buf_end = 0;
}

void trace_uninit()
{
  free(trace_buf);
  fclose(trace_fd);
}





int trace_get_item(struct trace_item **item)
{
  int n_items;

  if (trace_buf_ptr == trace_buf_end) {
    // get new data
    n_items = fread(trace_buf, sizeof(struct trace_item), TRACE_BUFSIZE, trace_fd);
    if (!n_items) return 0;

    trace_buf_ptr = 0;
    trace_buf_end = n_items;
  }

  *item = &trace_buf[trace_buf_ptr];
  trace_buf_ptr++;

  return 1;
}

int main(int argc, char **argv)
{
  struct trace_item *tr_entry;
  size_t size;
  char *trace_file_name;
  int trace_view_on = 0;

  unsigned char t_type = 0;
  unsigned char t_sReg_a= 0;
  unsigned char t_sReg_b= 0;
  unsigned char t_dReg= 0;
  unsigned int t_PC = 0;
  unsigned int t_Addr = 0;

  unsigned int n_items = 0;
  unsigned int n_nop = 0;
  unsigned int n_rtype = 0;
  unsigned int n_itype = 0;
  unsigned int n_load = 0;
  unsigned int n_store = 0;
  unsigned int n_branch = 0;
  unsigned int n_jtype = 0;
  unsigned int n_jrtype = 0;
  unsigned int n_special = 0;
  unsigned int n_unknown = 0;
  unsigned int n_mem_inst = 0;
  unsigned int n_cont_inst = 0;
  unsigned int n_branchTake = 0;

  if (argc == 1) {
    fprintf(stdout, "\nUSAGE: tv <trace_file> <switch - any character>\n");
    fprintf(stdout, "\n(switch) to turn on or off individual item view.\n\n");
    exit(0);
  }

  trace_file_name = argv[1];
  trace_view_on = (argc == 3);

  fprintf(stdout, "\n ** opening file %s\n", trace_file_name);

  trace_fd = fopen(trace_file_name, "rb");

  if (!trace_fd) {
    fprintf(stdout, "\ntrace file %s not opened.\n\n", trace_file_name);
    exit(0);
  }

  trace_init();

  while(1) {
    size = trace_get_item(&tr_entry);

    if (!size) {
      printf("+ total # items : %u\n", n_items);
      printf("+ # nop: %u\n", n_nop);
      printf("+ # rtype: %u\n", n_rtype);
      printf("+ # itype: %u\n", n_itype);
      printf("+ # load: %u\n", n_load);
      printf("+ # store: %u\n", n_store);
      printf("+ # branch: %u\n", n_branch);
      printf("+ # taken Branch: %u\n", n_branchTake);
      printf("+ # jtype: %u\n", n_jtype);
      printf("+ # jrtype: %u\n", n_jrtype);
      printf("+ # special: %u\n", n_special);
      printf("+ # unknown: %u\n", n_unknown);
      printf("+ # Avg mem instr: %4.2f\n", (double)n_mem_inst/(double)n_items);
      printf("+ # Avg control instr: %4.2f\n", (double)n_cont_inst/(double)n_items);
      break;
    }
    else{
      n_items++;
      t_type = tr_entry->type;
      t_sReg_a = tr_entry->sReg_a;
      t_sReg_b = tr_entry->sReg_b;
      t_dReg = tr_entry->dReg;
      t_PC = tr_entry->PC;
      t_Addr = tr_entry->Addr;
    }
    int bflag;
    int clkcntr;
    int temp;
    int distance;
    if (bflag)
    {
        if (tr_entry->PC == temp)
            //commented out fields to print distance

            //printf("%d\n",distance);

            ++n_branchTake;
        bflag = 1;
    }


    switch(tr_entry->type)
    {



      case ti_NOP:
      {
        if (trace_view_on){
          printf("[item %d] [entry NOP:] [(PC: %x)] [(sReg_a: %d)] [(sReg_b: %d)] [(dReg: %d)] [(addr: %x)]\n", n_items, tr_entry->PC, tr_entry->sReg_a, tr_entry->sReg_b, tr_entry->dReg, tr_entry->Addr);
        }

        n_nop++;
        break;
      }
      case ti_RTYPE:
      {
        if (trace_view_on){
          printf("[item %d] [entry RTYPE:] [(PC: %x)] [(sReg_a: %d)] [(sReg_b: %d)] [(dReg: %d)] [(addr: %x)]\n", n_items, tr_entry->PC, tr_entry->sReg_a, tr_entry->sReg_b, tr_entry->dReg, tr_entry->Addr);
        }

        n_rtype++;
        break;
      }
     case ti_ITYPE:
     {
        if (trace_view_on){
          printf("[item %d] [entry ITYPE:] [(PC: %x)] [(sReg_a: %d)] [(sReg_b: %d)] [(dReg: %d)] [(addr: %x)]\n", n_items, tr_entry->PC, tr_entry->sReg_a, tr_entry->sReg_b, tr_entry->dReg, tr_entry->Addr);
        }

        n_itype++;
        break;
     }
     case ti_LOAD:
     {
        if (trace_view_on){
          printf("[item %d] [entry LOAD:] [(PC: %x)] [(sReg_a: %d)] [(sReg_b: %d)] [(dReg: %d)] [(addr: %x)]\n", n_items,  tr_entry->PC, tr_entry->sReg_a, tr_entry->sReg_b, tr_entry->dReg, tr_entry->Addr);
        }
        clkcntr+=4;
        n_load++; n_mem_inst++;
        break;

     }

     case ti_STORE:
     {
        if (trace_view_on){
          printf("[item %d] [entry STORE:] [(PC: %x)] [(sReg_a: %d)] [(sReg_b: %d)] [(dReg: %d)] [(addr: %x)]\n", n_items, tr_entry->PC, tr_entry->sReg_a, tr_entry->sReg_b, tr_entry->dReg, tr_entry->Addr);
        }

        n_store++; n_mem_inst++;
        break;
     }
     case ti_BRANCH:
    {

        if (trace_view_on){
          printf("[item %d] [entry BRANCH:] [(PC: %x)] [(sReg_a: %d)] [(sReg_b: %d)] [(dReg: %d)] [(addr: %x)]\n", n_items, tr_entry->PC, tr_entry->sReg_a, tr_entry->sReg_b, tr_entry->dReg, tr_entry->Addr);
        }

        n_branch++; n_cont_inst++;
        temp = tr_entry->Addr;
        distance=temp>>2;
        ++bflag;
        break;
    }
     case ti_JTYPE:
     {
        if (trace_view_on){
          printf("[item %d] [entry JTYPE:] [(PC: %x)] [(sReg_a: %d)] [(sReg_b: %d)] [(dReg: %d)] [(addr: %x)]\n", n_items, tr_entry->PC, tr_entry->sReg_a, tr_entry->sReg_b, tr_entry->dReg, tr_entry->Addr);
        }

        n_jtype++; n_cont_inst++;
        break;
     }
     case ti_SPECIAL:
     {
        if (trace_view_on){
          printf("[item %d] [entry SPECIAL:] [(PC: %x)] [(sReg_a: %d)] [(sReg_b: %d)] [(dReg: %d)] [(addr: %x)]\n", n_items, tr_entry->PC, tr_entry->sReg_a, tr_entry->sReg_b, tr_entry->dReg, tr_entry->Addr);
        }

        n_special++; n_cont_inst++;
        break;
     }
     case ti_JRTYPE:
     {
        if (trace_view_on){
          printf("[item %d] [entry JRTYPE:] [(PC: %x)] [(sReg_a: %d)] [(sReg_b: %d)] [(dReg: %d)] [(addr: %x)]\n", n_items, tr_entry->PC, tr_entry->sReg_a, tr_entry->sReg_b, tr_entry->dReg, tr_entry->Addr);
        }

        n_jrtype++; n_cont_inst++;
        break;
     }
      default:
	n_unknown++;
	break;




    }
  }


  trace_uninit();

  exit(0);
}

Suggest you focus on the simpler I-cache first as the D-cache structure is a lot more complex.
Build a simple one-way set associative cache and later add complexity to it i.e. n-way set associative cache.
In cache_create() prompt the user for three things - no. of sets, no. of entries in each set, and its associativity.

Here is what I have now:

Code:

unsigned char byte_t;
void
cache_create(char name, int assoc, int bsize, int nsets, int usize, int balloc, unsigned int hit_latency, enum cache_policy policy)
{
    struct cache_t *cp;
    struct cache_blk_t *blk;
    int i, j, bindex;

    printf("Please enter the number of sets: ");
    scanf("%d, nsets");
    printf("Please enter the size:");
    scanf("%d, bsize");
    printf("Please enter the associativity:");
    scanf("%d, assoc");

  //create cache based on A, B, and C
  //allocate sets
  cp = (struct cache_t *)
  calloc(1, sizeof(struct cache_t) + (nsets-1)*sizeof(struct cache_set_t));

    cp->name = name;
    cp->nsets = nsets;
    cp->bsize = bsize;
    cp->balloc = balloc;
    cp->usize = usize;
    cp->assoc = assoc;
    cp->policy = policy;
    cp->hit_latency = hit_latency;
  //allocate blocks in each set
   cp->data = (byte_t *);
   calloc(nsets * assoc, sizeof(struct cache_blk_t) + (cp->balloc ? (bsize*sizeof(byte_t)) : 0));

  //remember the replacement policy setting
   cp->blk_access_fn = blk_access_fn;

  //initialize statistics data
    cp->hits = 0;
    cp->misses = 0;
    cp->replacements = 0;
    cp->writebacks = 0;
    cp->accesses=0;

};

int
cache_access(struct cache_t *cp, unsigned long address, char access_type)
{
  //based on address determine the set to access in cp
  //examine blocks in the set to check hit/miss
  //if miss, determine the victim in the set to replace
  //if LRU is used, update the block list
};

Originally Posted by husslela2

Code:

calloc(1, sizeof(struct cache_t) + (nsets-1)*sizeof(struct cache_set_t));

Why are you creating one less than the number of cache sets required (in red above).
And what's the use of allocating storage for sizeof(struct cache_t)? Not required IMO.

Code:

unsigned char byte_t;
void
cache_create(char name, int assoc, int bsize, int nsets, int usize, int balloc, unsigned int hit_latency, enum cache_policy policy)
{
    struct cache_t *cp;
    struct cache_blk_t *blk;
    int i, j, bindex;

    printf("Please enter the number of sets: ");
    scanf("%d, nsets");
    printf("Please enter the size:");
    scanf("%d, bsize");
    printf("Please enter the associativity:");
    scanf("%d, assoc");

  //create cache based on A, B, and C
  //allocate sets
  cp = (struct cache_t *)
  balloc= (nsets)*sizeof(struct cache_set_t));

    cp->name = name;
    cp->nsets = nsets;
    cp->bsize = bsize;
    cp->balloc = balloc;
    cp->usize = usize;
    cp->assoc = assoc;
    cp->policy = policy;
    cp->hit_latency = hit_latency;
  //allocate blocks in each set
   cp->data = (byte_t *);
   calloc(nsets * assoc, sizeof(struct cache_blk_t) + (cp->balloc ? (bsize*sizeof(byte_t)) : 0));

  //remember the replacement policy setting
   cp->blk_access_fn = blk_access_fn;

  //initialize statistics data
    cp->hits = 0;
    cp->misses = 0;
    cp->replacements = 0;
    cp->writebacks = 0;
    cp->accesses=0;

};

int
cache_access(struct cache_t *cp, unsigned long address, char access_type)
{
#define cache_double(cp, cmd, addr, p, now, udata)      \
  cache_access(cp, cmd, addr, p, sizeof(double), now, udata)
#define cache_float(cp, cmd, addr, p, now, udata)       \
   cache_access(cp, cmd, addr, p, sizeof(float), now, udata)
#define cache_dword(cp, cmd, addr, p, now, udata)       \
   cache_access(cp, cmd, addr, p, sizeof(long long), now, udata)
#define cache_word(cp, cmd, addr, p, now, udata)        \
   cache_access(cp, cmd, addr, p, sizeof(int), now, udata)
#define cache_half(cp, cmd, addr, p, now, udata)        \
   cache_access(cp, cmd, addr, p, sizeof(short), now, udata)
#define cache_byte(cp, cmd, addr, p, now, udata)        \
   cache_access(cp, cmd, addr, p, sizeof(char), now, udata)
register md_addr_t addr;
  //based on address determine the set to access in cp
  int                                     /* non-zero if access would hit */
 cache_probe(struct cache_t *cp,         /* cache instance to probe */
    md_addr_t addr);            /* address of block to probe */

  //examine blocks in the set to check hit/miss
  //if miss, determine the victim in the set to replace
  //if LRU is used, update the block list
};

ok i made the change, what do you suggest next to implement that i-cache?

Before diving into the coding part - think about how the cache is organized. Perhaps read some material on cache organization i.e. how they are organized and used. I'm saying so because the data structures you're using seem incomplete or have information that's not needed. Then again perhaps I'm wrong, so do clarify.

Code:

/*
 Is the below struct for a cache line?
 If so, it's missing room for cache contents
 */
struct cache_blk_t {
  unsigned long tag;
  char valid;
  char dirty;

  long cached_instr[2]; 

  cache_blk_t *way_next;
  cache_blk_t *way_prev;
};

/* what about this struct - is it supposed to represent the cache set? */
struct cache_set_t {
  cache_blk_t *way_head;
  cache_blk_t *way_tail;

  unsigned int FIFO_counter;  /* what is this being used for? */
};

/* if this struct stores cache statistics, what is the use of the items in red? */
struct cache_t
{
  int nsets;		// # sets
  int bsize;		// block size
  int assoc;		// associativity


  enum cache_policy policy;

  // statistics
  unsigned long accesses;
  unsigned long hits;
  unsigned long misses;
  unsigned long replacements;
  unsigned long writebacks;

  struct cache_set_t *sets;
};

Here's a simple structure that can be used for caching 64 instructions at a time (assuming each instruction takes up 32 bits).

Code:

enum cachepolicy {LRU, Random, FIFO};

typedef struct cachestats
{
    unsigned long hits;
    unsigned long misses;
    unsigned long accesses;
    unsigned long writebacks;
    unsigned long replacements;
} stats;

typedef struct icache
{
    int policy;
    int valid;
    unsigned long tag;
    unsigned long instr;
} icache;

icache index[64];

and then a data cache does reads and stores...

so I would have to create a structure for the d-cache

which could maybe be:

Code:

typedef struct dcache
{

     int policy;
     int valid;
     int read;
     int write;

}dcache;


dcache index[];