Transposing the rows and columns of a matrix is an important problem in signal processing and scientific

Question:

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:

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;

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.

Row 0 Row 1 dst array Col. 0 m Col. 1 Rowo Row 1 src array Col. 0 m Col. 1

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

Fantastic news! We've Found the answer you've been seeking!

Step by Step Answer:

Related Book For  book-img-for-question

Computer Systems A Programmers Perspective

ISBN: 9781292101767

3rd Global Edition

Authors: Randal E. Bryant, David R. O'Hallaron

Question Posted: