寻求最快速的矩阵乘实现

G-Spider · 发表于 2010-10-29 20:15:02

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 · 发表于 2010-10-30 07:52:54

11# G-Spider

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

G-Spider · 发表于 2010-10-30 22:38:20

简单的小结:
由于之前也没有关于矩阵乘实现的经历，也很难找到一些有用的提速资料，
所以上面和以后的所有文字仅仅是个人的体会，既不规范也存在错误和误导，勿怪^_^，只作为参考（没有实用价值或认为很没有的直接忽略...），上课的时候无形中感觉有些不对劲，主要有以下几个方面：

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 · 发表于 2010-10-31 19:21:07

13# G-Spider
有很好的参考价值。

这样说，G-Spider的矩阵乘已超过了matlab，可喜可贺！

另外，这个速度大约是前面Forcal代码（代表了纯C/C++代码的速度吧）的几倍？需要在一台机器上测试才有意义，麻烦G-Spider测试一下；或者将你生成的exe文件发给我，我试一下？谢谢！

G-Spider · 发表于 2010-10-31 21:11:48

14# forcal

Forcal兄过奖了，现在还不能说超过matlab(因为还没真正成形)，要真正超过它，还要提高Cache命中率，这也是我能想到的一个主要问题，在真正解决了这个问题之后，我会发给你的。

我想matlab(矩阵实验室)，以矩阵发家，以矩阵的视角处理问题，长达25年的历史变迁，从几m到几百m到几个G的文件，要在几天内超过其最核心的模块谈何容易，不过应该快了，至少在一定的平台下，呵呵....

liangbch · 发表于 2010-10-31 21:50:57

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

liangbch · 发表于 2010-10-31 21:51:27

楼上测试程序的显卡是GT240

G-Spider · 发表于 2010-10-31 22:34:48

16# liangbch

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

litaoye · 发表于 2010-11-2 15:39:26

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

无心人 · 发表于 2010-11-2 16:17:38

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

所以，很多数学软件内置的算法都是极端复杂的

账号		自动登录	找回密码
密码			欢迎注册

[擂台] 寻求最快速的矩阵乘实现