The transpose of a matrix interchanges its rows and columns; this is illustrated below:

$\backslash$left$[\backslash$begin$\{$matrix$\}$A$11$&A$12$&A$13$&A$14\backslash \backslash$A$21$&A$22$&A$23$&A$24\backslash \backslash$A$31$&A$32$&A$33$&A$34\backslash \backslash$A$41$&A$42$&A$43$&A$44\backslash \backslash \backslash$end$\{$matrix$\}\backslash$right$]\backslash$Longrightarrow$\backslash$left$[\backslash$begin$\{$matrix$\}$A$11$&A$21$&A$31$&A$41\backslash \backslash$A$12$&A$22$&A$32$&A$42\backslash \backslash$A$13$&A$23$&A$33$&A$43\backslash \backslash$A$14$&A$24$&A$34$&A$44\backslash \backslash \backslash$end$\{$matrix$\}\backslash$right$]$

Here is a simple C loop to show the transpose:

for $($i $=0$; $1<3$; i$++)\{$

for $($j $=0$; j $<3$; j$++)\{$

output$[$j$][$i$]=$ input$[$i$][$j$]$;

$\}$

$\}$

Assume that both the input and output matrices are stored in the row major order $($row major order means that the row index changes fastest$).$

Assume that you are executing a $256$ x $256$ double$-$precision transpose on a processor with a $16$ KB fully associative $($don$\text{'}$t worry about cache conflicts; cache just has $1$ set$)$ least recently used $($LRU$)$ replacement L$1$ data cache with $64$ byte blocks.

Assume that the L$1$ cache misses or prefetches require $16$ cycles and always hit in the L$2$ cache, and that the L$2$ cache can process a request every two processor cycles.

Assume that each iteration of the inner loop above requires four cycles if the data are present in the L$1$ cache.

Assume that the cache has a write$-$allocate fetch$-$on$-$write policy for write misses.

Unrealistically, assume that writing back dirty cache blocks requires $0$ cycles.

For the simple implementation given above, this execution order would be nonideal for the input matrix; however, applying a loop interchange optimization would create a nonideal order for the output matrix. Because loop interchange is not sufficient to improve its performance, it must be blocked instead.

What should be the minimum size of the cache to take advantage of blocked execution?