为什么我的Strassen矩阵乘法器这么快? [英] Why is my Strassen Matrix multiplier so fast?

问题描述

作为一个实验，我实现了Strassen矩阵乘法算法，以查看是否确实导致了较大n的更快代码.

As an experiment I implemented the Strassen Matrix Multiplication Algorithm to see if truly lead to faster code for large n.

https://github.com/wcochran/strassen_multiplier/blob/master /mm.c

令我惊讶的是，大n的速度前进.例如，n = 1024的情况 使用传统方法花费了17.20秒，而仅花费了1.13秒 使用Strassen方法(2x2.66 GHz Xeon).什么-15倍加速！?它应该只稍微快一点.实际上，即使对于较小的32x32矩阵，它似乎也同样有用！?

To my surprise it was way faster for large n. For example, the n=1024 case took 17.20 seconds using the conventional method whereas it only took 1.13 seconds using the Strassen method (2x2.66 GHz Xeon). What -- a 15x speedup!? It should only be marginally faster. In fact, it seemed to be as good for even small 32x32 matrices!?

我能解释这么多加速的唯一方法是我的算法对缓存更友好-即，它专注于矩阵的小块，因此数据更加本地化.可能的话，也许我应该做所有的矩阵算术运算.

The only way I can explain this much of a speed-up is that my algorithm is more cache-friendly -- i.e., it focuses on small pieces of the matrices and thus the data is more localized. Maybe I should be doing all my matrix arithmetic piecemeal when possible.

还有其他关于为什么这么快的理论吗?

Any other theories on why this is so fast?

推荐答案

Strassen的递归性质具有更好的内存局部性， 因此这可能是图片的一部分.递归规则 矩阵乘法也许是合理的事情 比较.

The recursive nature of Strassen has better memory locality, so that may be a part of the picture. A recursive regular matrix multiplication is perhaps a reasonable thing to compare to.

这篇关于为什么我的Strassen矩阵乘法器这么快?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！