矩阵乘法的优化

1. 矩阵乘法计算的优化方法小记

之前逛知乎的时候经常看到有人对julia，numpy(python)，ndarray(rust), openblas,blas,lapack的矩阵乘法速度或者其它矩阵操作的速度进行比较，因此就非常好奇，为什么会存在这种差异呢？

https://zhuanlan.zhihu.com/p/546901963

https://zhuanlan.zhihu.com/p/368870275

经过搜索发现，其实不管怎么变，我们在代码层面看到的计算复杂度并没有变，但是在编译后执行层面上会有不同。

不同的写法会影响cpu读取内存中的数据的位置(比如在缓存中读取数据就比在堆中读取要快很多，在寄存器中读取数据比在缓存中要快很多)；读取数据的方式(比如未经优化的代码需要计算数据存储的位置进行指针的跳转，而经过优化后，只需要将指针按顺序移动一位即可，在空间上是连续的)；此外还可以充分应用CPU中的向量化指令，对矩阵进行分块再转至缓存计算；对矩阵计算进行预热，提前存储各个矩阵分块的指针；最后还可以直接调用CPU架构对应的汇编语言，针对硬件进行优化。更高级一点对于多核CPU(多线程)或者显卡，可以引入并行计算对矩阵乘法进行加速。

总而言之，想要充分发挥CPU(or GPU)的计算效率，我们的算法需要针对硬件，针对电脑读取和计算数据的方式进行优化，这比我们最初预想要解决问题的计算方式要困难许多。

PS：

当然对于矩阵的计算除了三重循环，还有strassen算法，有一些算法是针对超大型矩阵进行设计的(在小矩阵上没有优势)，他们的预计的计算复杂度能够做到\(O(N^3)\)到\(O(N^2)\)之间。

可能理想很丰满，现实很骨感，这些算法也许由于适用的范围和前面提到的与计算机交互时硬件水平上面临的问题，并不能被广泛应用吧。