提高标准矩阵乘法算法的效率？

Question

如何提高标准矩阵乘法算法的效率？

参与这种方法的主要操作是：C[i][j]+=A[i][p]*B[p][j]

什么可以做，以提高算法的效率？

Answer 1

你可能想看看使用BLAS（基本线性代数子程序）库，特别是英特尔提供他们的MKL here，AMD有自己的ACML here，也有在（开源）转到BLAS here。

（密集）矩阵 - 矩阵乘内核将调用?GEMM，其中?指示浮点类型。例如，DGEMM将调用double例程。

除非你非常自信，你知道你在做什么低级别的优化，这些库可能会提供比你手动编写的东西更好的性能。

如果你想有在编码这个自己一展身手，那么你可能要考虑以下几点：

1. 使用“矢量”的说明。 SSE, SSE2..4指令得到广泛支持，一些较新的CPU的指令也将支持AVX指令。
2. 嵌套循环展开以最大化浮点操作与加载/存储操作的比率。
3. 确保有效缓存使用的分块算法。
4. 多线程。

这种提法可能给你的东西的当前状态的一个想法：

级别3 BLAS的高性能实现 - K转到。

希望这会有所帮助。

Answer 2

我建议阅读Golub and Van Loan的第1章，它解决了这个确切的问题。

Answer 3

1. 缓存拦截 - 确保你正确使用和高速缓存中重用值
2. 更好的算法 - “按定义”的方式来繁殖矩阵是不是最优的，看看Strassen's algorithm
3. 并行 - 如果你的机器有一个以上的核心和/或处理器，可以分而治之
4. SIMD - 利用SSE向量指令在现代CPU架构
5. GPGPU - 现代GPU进行优化，以做到这这种事情。看看CUDA和OpenCL。

请注意，使用这些方法不能保证更好的性能。需要进行大量的调整才能实现显着的加速。研究如何迅速增加矩阵的方法有很多钱，因此不存在有关该主题的期刊文章短缺。

Answer 4

如果问题涉及多个矩阵乘法 - M1 x M2 x ... x Mn - 那么还有另一种基于动态规划的优化技术，这是另一种球类游戏。请注意，这不适用于提高两个矩阵相乘的效率;但是，如果您以成对方式乘以三个或更多矩阵，则可以在更高的水平上进行优化。只是以为我会把这个答案放在堆上来完成信息。

Answer 5

那么有Strassen's Algorithm，这取决于矩阵的大小，比你列出的标准算法稍快。当然有even faster algorithms，但它们不是很容易实现。

标准算法是O（N^3）， Strassen重的算法中为O（N^2.8）， 和铜匠-的Winograd是O（N^2.3）