What is the cache bandwidth for optimal matrix transformation?

Question

If I have an M x N matrix and L1 cache of size K, then what cache bandwidth has the optimal matrix transposition. Obviously, I'm looking for something that is a function of M and N (and possibly K , although it might be too complicated), and not a specific number.

I ask, because I have a lot of matrix data that needs to be processed in both directions, and I would like the rule of thumb to know when to store both the original data and transpose it in memory.

Answer 1

You did not say anything about the type of cache that you have, is it directly mapped? N-shaped associative set? Suppose an associative N-shaped set is associative (and yes, you need all of the cache details depending on your specific processor architecture) and assuming one specific matrix ordering, for example. column major, then you will have mostly cold misses, mostly M * N / C, where C is the size of the cache line (which depends on the processor, but usually 8 doubles :)).

Then you will have alternating access on the target matrix, and if the matrix is ​​not small enough to fit completely into L1, you can assume the worst-case M * N miss scenario, for example. L1 is 32kB in size, you can accommodate 4000 doubles, i.e. matrix size ~ 63 * 63.

Therefore, we will look at the worst (M * N / C + M * N) total miss L1 for transposition.

One idea would be to do the trick with flipping matrix ordering, for example. from a major column to a row-row, instead of physically moving it, access it as transposed . This is a zero-cost operation if you have the correct matrix implementation, where you can flip the matrix ordering over the same data.

The real expensive prefects, although they are never located on L1, but on the LLC (last level cache), even if you get L1 passes, this is still a cheap miss because it will be loaded from L2. In conclusion, it is very difficult to calculate if you do not have all the small details of your target processor architecture.