Transposing the rows and columns of a matrix is an important problem in signal processing and scientific computing applications. It is also interesting from a locality point of view because its reference pattern is both row-wise and column-wise. For example, consider the following transpose routine:

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

. sizeof(int) = 4.

. The src array starts at address 0 and the dst array starts at address 16 (decimal).

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

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

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

A. 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.

B. Repeat the problem for a cache with 32 data bytes.

Transcribed Image Text:

1 2 3 4 5 6 7 8 9 typedef int array [2] [2]; void transpose1 (array dst, array src) { 10 11 12 } int i, j; for (i = 0; i < 2; i++) { } for (j = 0; j < 2; j++) { dst [j] [i] = src[i][j]; }