找回密码
 欢迎注册
查看: 22115|回复: 20

[擂台] 寻找最高效的矢量化算法

[复制链接]
发表于 2010-10-12 11:21:18 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有账号?欢迎注册

×
1、设a、b为数组指针,n为数组大小(n比较大,例如1000000):
  1. for(i=0;i<n;i++) a[i]=sin(b[i]);
复制代码
2、设a、b为数组指针,d为一个实数,n为数组大小(n比较大,例如1000000):
  1. for(i=0;i<n;i++) a[i]=b[i]+d;
复制代码
3、设a、b、c为数组指针,n为数组大小(n比较大,例如1000000):
  1. for(i=0;i<n;i++) a[i]=pow(b[i],c[i]);
复制代码
这样算效率肯定不是最高的,但如何提高效率呢?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-10-12 12:00:50 | 显示全部楼层
现在CPU可以让多条相同指令以SIMD并行提速,好的编译器会支持最新的CPU技术。
但楼主代码中含有sin、pow等高级函数,是否还能并行就不知道了。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2010-10-12 18:10:44 | 显示全部楼层
现在CPU可以让多条相同指令以SIMD并行提速,好的编译器会支持最新的CPU技术。
但楼主代码中含有sin、pow等高级函数,是否还能并行就不知道了。
gxqcn 发表于 2010-10-12 12:00

我对此类算法如何提速是一无所知,但我知道matlab的矢量化代码比以上代码约快20左右。
虽然这种提速意义不是很大,但也想知道是如何提速的。

该问题来源于以下csdn的帖子,但没有结果。
http://topic.csdn.net/u/20101006/21/2ed9e5c1-cc9f-4623-b1c0-ebd5d1b5a98a.html
http://topic.csdn.net/u/20101010/15/3bcf2fe0-0abd-4c29-b854-b1d007b16863.html
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2010-10-14 20:41:06 | 显示全部楼层
其他大牛呢?给点意见也好。

我只想知道有办法提高速度吗?有把握提速多少?

gxqcn 在大数计算方面据世界领先地位。难道其他方面我们不能尝试做得更好些?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-10-18 22:40:42 | 显示全部楼层
想知道的话,可以学一下汇编,了解一下优化,SSE系列指令集,指令预取技术等............
“但我知道matlab的矢量化代码比以上代码约快20左右。”
快与不快都是人做出来的,你没能得到高效的代码,只能说你不够精。。。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2010-10-21 20:40:22 | 显示全部楼层
想知道的话,可以学一下汇编,了解一下优化,SSE系列指令集,指令预取技术等............
“但我知道matlab的矢量化代码比以上代码约快20左右。”
快与不快都是人做出来的,你没能得到高效的代码,只能说你不够精。 ...
c12c12 发表于 2010-10-18 22:40

这些东西对我来说太难了。
但按这种说法,似乎熟悉这些东西的人实现这些功能不是太难,要的就是这个结果,果真如此么?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-10-21 23:22:37 | 显示全部楼层
回复之后,没有结果.....算了
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-10-22 09:46:17 | 显示全部楼层
SSE指令集支持16字节取数,也就是可能完成一条指令实现四个单精度的float运算,这些东西的出现不是摆设,“I was happy to see that it was almost 3 times faster than pure C”  ,当然也有对matlab的部分模拟的开源东东出现,比如FreeMat
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2010-10-22 23:49:54 | 显示全部楼层
原来c12c12 和我一样在等结果,哈哈。
感谢G-Spider 的指点。FreeMat第一次听说,也是个好东西。
FreeMat真比matlab快吗?应该是某些方面有优势吧?
matlab的矩阵速度似乎不好超越?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-10-23 12:07:48 | 显示全部楼层
就我个人理解,矢量这个东东无非是被封装在一个类中,在c中就是一个包含几个类型(通常是相同类型,这样方便并行处理)的结构体,比如游戏中常用的3D矢量,
union sse3D {
  __m128 m;<=采用这样了个共用体,为了保证下面的4个float ,16字节对齐(SSE某些指令中的要求)
  float f[4];
};
这样可以同时完成对四个float型变量的操作,这也就是SIMD的初衷,用到的技术叫作Swizzling Data
可以参考Intel&reg; 64 and IA-32 Architectures  Optimization Reference Manual 的CHAPTER 6
对于一些对精度要求不太高的环境下,比如游戏中,像sin(),cos() 之类的函数,用FSIN,FCOS是不明智的,因为其精度过高,也不快,所以通常采用近似(比如外推几项的Taylor展开),这样用加,减,乘即可,所以SSE有奏效了。
可以GOOGLE 这篇文章:Generating Fractals with SSE/SSE2
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-3-29 02:05 , Processed in 0.052514 second(s), 16 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表