c++ - Laderman 的 3x3 矩阵乘法只有 23 次乘法，值得吗？

Question

取两个 3x3 矩阵 A*B=C 的乘积。天真地，这需要使用 standard algorithm 进行 27 次乘法运算。 .如果你很聪明，你可以只用 23 次乘法来做到这一点，a result found in 1973 by Laderman .该技术涉及节省中间步骤并以正确的方式组合它们。

现在让我们修复一种语言和一种类型，比如带有 double 元素的 C++。如果 Laderman 算法是硬编码而不是简单的双循环，我们能否期望现代编译器的性能能够消除算法的差异？

关于这个问题的说明:这是一个编程网站，这个问题是在时间关键内循环的最佳实践的上下文中提出的；过早优化这不是。非常欢迎以评论的形式提供有关实现的提示。

Answer 1

关键是掌握平台上的指令集。这取决于您的平台。有几种技术，当您倾向于需要最大可能的性能时，您的编译器将附带分析工具，其中一些内置优化提示。对于最细粒度的操作，请查看汇编器输出，看看是否有任何改进也在那个水平。

同时指令多个数据命令对多个操作数并行执行相同的操作。这样你就可以拿了

double a,b,c,d;
double w = d + a; 
double x = a + b;
double y = b + c;
double z = c + d;

替换成

double256 dabc = pack256(d, a, b, c);
double256 abcd = pack256(a, b, c, d);
double256 wxyz = dabc + abcd;

因此，当值被加载到寄存器中时，它们会被加载到一个 256 位宽的寄存器中，用于某些具有 256 位宽寄存器的虚构平台。

浮点是一个重要的考虑因素，一些 DSP 可以显着加快对整数的运算速度。 GPU 在浮点方面往往表现出色，尽管有些 GPU 在单精度上的速度要快 2 倍。这个问题的 3x3 情况可以适合单个 CUDA 线程，因此您可以同时流式传输 256 个这些计算。

选择您的平台，阅读文档，实现几种不同的方法并对其进行分析。