How to know which element replaces which for a cache

ccachemips

If I assume that the first element of the matrix that is fetched to the D-cache is a[0][0], for associativity 4, please tell me which element in which matrix that will write over a[0][0] in the D-cache. Since the formula for set associativity is

In a set-associative cache, the set containing a memory block is given
by (Block number) modulo (Number of sets in the cache)

How can I know from this code, compiled and run as MIPS assembly in a MIPS simulator, which element that will write over a[0][0]?

/* matris.c */
#include <stdio.h>
#include <idt_entrypt.h>

#define MATRIXSIZE 16
#define MATRIXSIZE_ROWS 16
#define MATRIXSIZE_COLS 16

/*
 * addera two matriser
 */
void matrisadd( int res[MATRIXSIZE_ROWS][MATRIXSIZE_COLS],
                int   a[MATRIXSIZE_ROWS][MATRIXSIZE_COLS],
                int   b[MATRIXSIZE_ROWS][MATRIXSIZE_COLS] )
{
  int i,j;

  for(i=0; i < MATRIXSIZE; ++i) /* variera rad-index */
    for(j=0; j < MATRIXSIZE; ++j) /* variera kolumn-index */
      res[i][j] = a[i][j] + b[i][j];
}

int main()
{
  static int   a[MATRIXSIZE_ROWS][MATRIXSIZE_COLS];
  static int   b[MATRIXSIZE_ROWS][MATRIXSIZE_COLS];
  static int res[MATRIXSIZE_ROWS][MATRIXSIZE_COLS];
  int i,j, Time;

  /*
   * initiera matris a och b
   */
  for( i=0; i<MATRIXSIZE; ++i)
    for( j=0; j<MATRIXSIZE; ++j)
    {
      a[i][j] = i+j;
      b[i][j] = i-j;
    }

  flush_cache();              /* toem cachen */
  timer_start();              /* nollstall tidmatning */

  matrisadd( res, a, b);

  Time = timer_stop();                /* las av tiden */
  printf("Time: %d\n",Time);
}

Best Answer

I think ANSI C dictates that multi-dimensional arrays are allocated to memory in row-major order. That means elements in a row are contiguous in memory, which is to say a[0][0] is adjacent to a[0][1] in memory.

The way associative caches work is that some of the address bits tell you which line of the cache the item is on, and some other bits of the address tell you which set the item goes in. You need to know the line-width to know how many bytes are on a line, and you need to know how many lines each set contains.

Lets say you didn't have an associative cache (i.e. you had associativity = 1). Lets also say you had 32 bytes per line, and 16 lines. So your total cache size would be 16 * 32 = 512 bytes. If your a[0][0] was allocated to memory such that it was on a cache line boundary (i.e. it's address was divisible by 32), then the line it brought in would contain a[0][0] through a[0][31] assuming the cardinality of the second dimension was that big. If on the other hand the cardinality of the second dimension was say 16, the a[0][0] row would contain a[0][0] ... a[0][15], a[1][0] ... a[1][15]. And so on.

However your array is dimensinoed, after 512 bytes, you're going to be full and the 513th byte offset from a[0][0] is going to blow away the row containing a[0][0]. Unless your cache is associative. In that case, your 513th entry is going to go into the next set, and that's going to keep happening for as many ways associative your cache is. Only after exhausting the sets will you wrap back around and blow away a[0][0]. Now, obviously for the same size cache, increasing associativity will effectively reduce the number of lines per set. So the access pattern determines whether it's helpful or not. Mileage may vary.

Related Topic