Question

Cache performance

The starting code would have:

struct position {

int x; int y; }

int N;

struct position grid[N][N];

int totalX=0;

int totalY=0;

int i, j;

//For X loop

for( i = 0; i < N; i ++){

for( j = 0; j < N; j++){

totalX += grid[i][j].x; } }

//For Y loop

for( j = 0; j < N; j++){

for( i = 0; i < N; i++){

totalY += grid[i][j].y; } }

Part I: This part does not require coding. Given that: N = 16, the cache is 1024-byte direct-mapped data cache with 16-byte blocks (B=16), sizeof(int) =4, grid begins at memory address 0, the cache is initially empty, The only memory accesses are to the entries of the array grid. Variables i, j, totalX, totalY are stored in registers.

1) Calculate the total number of reads in the X loop.

2) Calculate the total number of read that miss in the cache in the X loop.

Part II: Use the code above as a template. For each case N=1000, N=2000, N=5000, N=8000: Randomize the values of x and y for all the position object inside the grid struct. Then record the time it takes to finish X loop and Y loop. The time should be in milliseconds.

3) Compare these 2 time values and give me your thoughts on the difference.

Answer 1