寻求最快速的矩阵乘实现

G-Spider

9# forcal 8# litaoye 看来要使用一些高级的算法才能降低时间复杂度. 看一下乘法的计算次数： 普通：0(n^3)......1024^3=1 073 741 824次乘运算 Strassen分治：0(n^2.81)............1024^2.81= 287 701 988次算运算 Don Coppersmith and Shmuel Wmograd改进：0(n^2.367).........1024^2.367= 13 346 887次算运算 ........ 当然在实现上的难度会越来越大............ 最新的矩阵乘算法动态，可参考： Fast and stable matrix multiplication

forcal

11# G-Spider 感谢G-Spider的资料！原来有这么多高级的矩阵算法。

G-Spider

简单的小结: 由于之前也没有关于矩阵乘实现的经历，也很难找到一些有用的提速资料， 所以上面和以后的所有文字仅仅是个人的体会，既不规范也存在错误和误导，勿怪^_^，只作为参考（没有实用价值或认为很没有的直接忽略...），上课的时候无形中感觉有些不对劲，主要有以下几个方面： 1.矩阵乘法的代价或者说瓶颈果真是乘的次数吗？对于这一思考我作了一个简单测试（可能不太规范），就是将算核中的大半的乘 运算指令换成了加法指令，你猜结果会怎样呢？...几乎没有什么效率的提升。 2.理论上的诸如Strassen分治，Don Coppersmith and Shmuel Wmograd算法果真能得到实现上的高效吗？数学理论上的最优不代表 实现上的高效，今天抽了点时间看了一下<矩阵计算>这本书中关于矩阵乘法的Strassen分治介绍，整个过程用递归实现，我想对于 小矩阵可能在脑子里算算感觉乐在其中，大量的递归还能否高效？提到了这，也是为什么像单纯形法之类看似不起眼的算法应用仍 然广泛... 3.本身个人时间不太多，需要大家一同出点子，才会有更好的发展，呵呵....第一轮的期末考试来临.... 对于1，能说明一点：当前的指令执行速度已经不再是20世纪末的糟糕情形，也就是说瓶颈应该不在乘法的次数(n^3与n^2.81已经 没有明显的区别，不会超过1ms)，所以你拼了命，那恭喜你赢得了1ms的性能。瓶颈应该在取数...不合理的数据存储导致严重的抖 动现象，乘法指令的执行等待，大量的等待导致时间片过，这也是为什么经常测得的时间数据不准的原因之一吧。合理的优化存储 ，深刻理解Cache技术或许才有大的飞跃，又作了简单测试（不算合理，但能反映问题），将A*B改成A*A这样数据块相对集中，性 能是一个量级的差别，在我这个400元掀不出去的机子上测试matlab A*B(1024,1024) Elapsed time is 1.344000 seconds.我的 A*B用时稍好一点1.28000s ，A*A 486ms左右.... 对于2,我的体会是先放弃这类“高级”算法，虽然0(n^3)听起来有点吓人，哈哈....也许在问题1解决了之后在考虑2才合理，理由 很简单：“乘法指令说，我想运算，我要数据，你快快传给我！！移动指令说，对不起，我习惯了等待...”. 娱乐。。。见笑..............(编译出来的程序说什么病毒，哎360....)

forcal

13# G-Spider 有很好的参考价值。 这样说，G-Spider的矩阵乘已超过了matlab，可喜可贺！ 另外，这个速度大约是前面Forcal代码（代表了纯C/C++代码的速度吧）的几倍？需要在一台机器上测试才有意义，麻烦G-Spider测试一下；或者将你生成的exe文件发给我，我试一下？谢谢！

G-Spider

14# forcal Forcal兄过奖了，现在还不能说超过matlab(因为还没真正成形)，要真正超过它，还要提高Cache命中率，这也是我能想到的一个主要问题，在真正解决了这个问题之后，我会发给你的。 我想matlab(矩阵实验室)，以矩阵发家，以矩阵的视角处理问题，长达25年的历史变迁，从几m到几百m到几个G的文件，要在几天内超过其最核心的模块谈何容易，不过应该快了，至少在一定的平台下，呵呵....

liangbch

我直接使用 CUDA sdk 的测试代码NVIDIA Corporation\NVIDIA GPU Computing SDK\C\src\matrixMulDrv，计算2个1024*1024矩阵的乘积（单精度），运算时间为32-37ms，而参考代码，直接计算则需要12秒多。

liangbch

楼上测试程序的显卡是GT240

G-Spider

16# liangbch GOD JOB 非常好的结果，NVIDIA CUDA编程指南中也有对矩阵乘的详细介绍，从某种意义来讲是处理阵上的实现，对于计算密集性的程序通常可以提高量级的倍数，其代价是要有支持CUDA架构的英伟达显卡和NVIDIA drivers 所以进行适当的侦测，性能明显提高，不知道matlab有没有之方面的考虑. 以前也有人作了些测试： A realtime Mandelbrot zoomer in SSE assembly and CUDA

litaoye

并不是慢在了乘法指令上了，而是慢在复杂度上了。n^3同n^2.81比较，当n=1000时，能够相差3-4倍，如果使用n^2.367，那就快多了，几十倍有了。

无心人

数学运算软件为追求最大效率，一般都按照每种具体形式，写很多特殊算法 不惜加大软件复杂度 所以，很多数学软件内置的算法都是极端复杂的