4 ms·

If you can't keep 3 rows of the input matrix in cache, why would you be able to keep 3 rows of the output matrix in cache? If the matrices are large enough that

• fluffything 6y ago
  > If you can't keep 3 rows of the input matrix in cache, why would you be able to keep 3 rows of the output matrix in cache? If the matrices are large enough that they don't fit in cache, shouldn't they be processed in squareish blocks recursively to maximize cache reuse (not in rows)? Your cache size is fixed by the computer and you can't change it. If you are doing a convolution, you want "(N+1)xN = cache size" to determine the size of the "blocks" (NxN matrix, and an 1xN row) of the convolution you process. Those blocks are also matrices, so by decomposing your matrix into smaller matrices you don't avoid this problem. So sure, you could also decompose your problem by doing "(N+3)xN = cache-size", but that means that the size of the "square blocks" that you can now properly fit in cache is smaller, and need to decompose your original problem into more sub-problems to get it done. You could also do: "2Nx2N = cache size", and just load a whole input block and an output block into cache. In both cases, you are bringing memory into cache that you only touch once, yet continue occupying cache space after you don't need them anymore. You could have used that space to process larger matrices instead, and have to decompose your problem into fewer blocks.