4 ms·

>The first thing that we need to do to accelerate our program is to improve the memory utilization of matrix B. Why not put matrix B in column-major order?

costrouc 8y ago
Matrix multiplication involves moving across one matrix in column order and the other matrix in row order. So it turns out that both row or column ordering make no difference. I think that matrix multiplication is one of the best examples of a deceptivly simple problem. It shows how far ALL code is from peak performance. We can only strive to be within an order or two from peak performance.
- fdej 8y ago
  This trick does work. If the matrices are in row-major order, you transpose B in memory and then compute A * (B^T)^T. This multiplication reads both matrices in row order. However, while this does improve performance over the naive algorithm, it's still not as good as a tiling algorithm.
  - shaklee3 8y ago
    I've found where that causes problems is when on of the matrix dimensions is not a multiple of the cache line size. It's common on gpus to use more elements then there are in the dimension. Nvidia calls this the leading dimension, and it must be greater than or equal to the Matrix dimension. If this is the case, the transpose trick doesn't quite work anymore.
- hedora 8y ago
  I took a different lesson from learning to implement matrix multiply: you can get a small amount of code within a few percent of peak performance if you try. So, the trick is to keep the 99% of the code that does 10% of the work within an order of magnitude of peak performance, and then get the rest within a factor of two. That gets the system within a factor of three, which is still embarrassing, but that’s what profiling tools are for. :-)
yvdriess 8y ago
That works only in limited cases, viz. where B matrix can stay in column-major format afterwards, ponder A * B * C.
- adrianratnapala 8y ago
  But it is a reason why the matrix is not always a great abstraction. That is, the internal layout of a matrix interacts with the use case enough that (sometimes) users will want explicit control that layout.

costrouc 8y ago

Matrix multiplication involves moving across one matrix in column order and the other matrix in row order. So it turns out that both row or column ordering make no difference. I think that matrix multiplication is one of the best examples of a deceptivly simple problem. It shows how far ALL code is from peak performance. We can only strive to be within an order or two from peak performance.

fdej 8y ago
This trick does work. If the matrices are in row-major order, you transpose B in memory and then compute A * (B^T)^T. This multiplication reads both matrices in row order. However, while this does improve performance over the naive algorithm, it's still not as good as a tiling algorithm.
- shaklee3 8y ago
  I've found where that causes problems is when on of the matrix dimensions is not a multiple of the cache line size. It's common on gpus to use more elements then there are in the dimension. Nvidia calls this the leading dimension, and it must be greater than or equal to the Matrix dimension. If this is the case, the transpose trick doesn't quite work anymore.
hedora 8y ago
I took a different lesson from learning to implement matrix multiply: you can get a small amount of code within a few percent of peak performance if you try. So, the trick is to keep the 99% of the code that does 10% of the work within an order of magnitude of peak performance, and then get the rest within a factor of two. That gets the system within a factor of three, which is still embarrassing, but that’s what profiling tools are for. :-)

yvdriess 8y ago

That works only in limited cases, viz. where B matrix can stay in column-major format afterwards, ponder A * B * C.

adrianratnapala 8y ago
But it is a reason why the matrix is not always a great abstraction. That is, the internal layout of a matrix interacts with the use case enough that (sometimes) users will want explicit control that layout.