Question

Consider the following matrix transpose routines:

typedef int array[4][4];

void transpose (array dst, array src) {

    int i, j;

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

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

          dst[i][j] = src[i][j];

   }

    }

}

void transpose2 (array dst, array src) {

    int i, j;

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

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

          dst[j][i] = src[j][i];

   }

    }

}

Assume this code runs on a machine with the following properties:

sizeof(int) = 4

The src array starts at address 0x0 and the dst array starts at address 0x40

There is a single L1 data cache that is direct-mapped, write-through, writeallocate, with a block size of 16 bytes.

The cache has a total size of 32 data bytes and the cache is initially empty.

Accesses to the ser and dst arrays are the only sources of read and write misses, respectively

For each row and col, indicate whether the access to src[row][col] and dst[row][col] is a hit (h) or a miss (m). For example. Reading src[0][0] is a miss and writing dst[0][0] is also a miss.

A. Transpose:

dst	Col 0	Col 1	Col 2	Col 3		src	Col 0	Col 1	Col 2	Col 3
Row 0	m					Row 0	m
Row 1						Row 1
Row 2						Row 2
Row 3						Row 3

B. Transpose 2:

dst	Col 0	Col 1	Col 2	Col 3		src	Col 0	Col 1	Col 2	Col 3
Row 0	m					Row 0	m
Row 1						Row 1
Row 2						Row 2
Row 3						Row 3

C. What is the cache miss rate for each transpose function? Are they different, Why or why not?