Transposing the rows and columns of a matrix is an importantproblem in signal processing and scientific computingapplications. It is also interesting from a locality point of viewbecause its reference pattern is both row-wise and columnwise.For example, consider the following transpose routine:1 typedef int array[2][2];23 void transpose1(array dst, array src)4 {5 int i, j;67 for (i = 0; i < 2; i++) {8 for (j = 0; j < 2; j++) {9 dst[j][i] = src[i][j];10 }11 }12 }Assume this code runs on a machine with the followingproperties:sizeof(int) = 4.The src array starts at address 0 and the dst array startsat address 16 (decimal).There is a single L1 data cache that is direct-mapped, writethrough,and write-allocate, with a block size of 8 bytes.The cache has a total size of 16 data bytes and the cache isinitially empty.Accesses to the src and dst arrays are the only sourcesof read and write misses, respectively.A. For each row and col , indicate whether the access tosrc[row][col] and dst[row][col] is a hit (h) or a miss(m). For example, reading src[0][0] is a miss andwriting dst[0][0] is also a miss.dst array src arrayCol. 0 Col. 1 Col. 0 Col. 1Row 0 m _____ Row0 m _____Row 1 _____ _____ Row 1 _____ _____B. Repeat the problem for a cache with 32 data bytes.
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 columnwise.
For example, consider the following transpose routine:
1 typedef int array[2][2];
2
3 void transpose1(array dst, array src)
4 {
5 int i, j;
6
7 for (i = 0; i < 2; i++) {
8 for (j = 0; j < 2; j++) {
9 dst[j][i] = src[i][j];
10 }
11 }
12 }
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, writethrough,
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.
dst array src array
Col. 0 Col. 1 Col. 0 Col. 1
Row 0 m _____ Row0 m _____
Row 1 _____ _____ Row 1 _____ _____
B. Repeat the problem for a cache with 32 data bytes.
Trending now
This is a popular solution!
Step by step
Solved in 2 steps with 2 images
