4
$\begingroup$

I know when we access elements in rows it will be much faster than if it is accessed column wise. In matrix multiplication one of the matrices must be accessed column wise. In GPUs with CUDA/OpenCL I could resolve this issue by explicitly copying both matrices row-wise into user-managed shared(cache)-memory (or local memory in OpenCL), and then can access data for matrix multiplication in anyway- no penalty for column access.

My question is how do I avoid such column access if I am implementing Matrix-multiplication on CPU, where I do not have any access to such shared memory as in GPU?

$\endgroup$
2
$\begingroup$

I'm assuming you don't want to store a copy of the second matrix in column-wise order and then multiply. In this case maybe the best way is to take the most advantage of cache hierarchy in modern CPUs. There are many complexity results for such setting.

For matrix multiplication there is a cache-oblivious algorithm based on Strassen's algorithm. Here you can find it in details. Notice that their aim is to optimize I/O access, so it may not fully match your requirement.

$\endgroup$
0
$\begingroup$

You can transpose one matrix first. Then iterating that matrix can be done "in-sync" with the other.

Of course, now you have to find a nice transposition algorithm that avoids jumping around memory, but even if you don't, it will probably save you a lot of cache misses, when compared regular matrix multiplication.

For a square matrix, you can find a cache-aware matrix-transpose algorithm, as well as a cache-oblivious algorithm on the wikipedia page for in-place matrix transposition. See Cache-oblivious algorithms (Frigo et al., 1999) for more info.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.