用户
 找回密码
 立即注册
quanzhang100 该用户已被删除
发表于 2013-11-16 11:18:10
71812
大家好!我对double型的cufft二维FFT执行效率做了一个测试,结果如下
二维矩阵大小(R x L)           执行时间
  • 32 x 32                            0.018ms
  • 64 x 64                            0.020ms
  • 128 x 128                        0.029ms
  • 256 x 256                        0.092ms
  • 512 x 512                        0.402ms
  • 1024 x 1024                    1.468ms

好像FFT的时间复杂度是Nlog2N,如果是二维的计算复杂度是不是R*L*log2L+ L*R*log2R(其中R表示行,L表示列,因为二维FFT是先对行做FFT然后再对列做FFT)因为我的R=L所以R*L* log2L+ L*R*log2R = 2L2*log2L用上面相邻两行的计算时间的比值应该是N/4(N+1)   (这里的N是行或者列的2的幂指数,如果行为32那么N就是5)
(1)如果相邻两行的时间比值接近N/4(N+1)那么说明GPU是充分利用了,如果大于这个比值说明GPU资源有空闲呢?
(2)从上面的数据显示,可不可以这样理解1,2,3的执行时间很接近说明GPU没有充分利用,从3到4数据量扩大了4倍数执行时间扩大为大约3.2倍,从4到5数据量扩大4倍数时间扩大4.3倍,但是从5到6数据扩大4倍数时间扩大3.6倍,这是为什么?
(3)以上的分析是否合理,如果不合理能否给出更加合理的分析?
使用道具 举报 回复
发表于 2013-11-16 15:09:07
LZ您好:

cufft是一个闭源实现的库,对于用户来说,是一个黑箱实现,因此很难就结论做一些直接的评价,除非是做过非常全面的测试,或者是得到具体的实现细节。

对于cufft的时间复杂度,根据手册可知总是NlogN级别,但是对于不同的长度具体快慢是不同的,对于可以分解为小素数乘积的点数是特别优化过的,也是最快的。
以及,cufft具体执行情况如何,这个和硬件架构有关,内部在执行的时候,可能会根据不同的架构特点选择不同的执行路径,以及在建立plan的时候,还会做一些profiling,以确定如何优选参数,因此cufft的执行情况也是和具体硬件有关的。但是具体的参数选择方法对于用户是未知的。

具体到您的问题:
1:我觉得这个并不能说明此时GPU已经充分利用了,因为这个只是GPU充分利用的必要条件,而非充分条件。逻辑上讲,只需要两次对比的情况下,GPU利用率保持一致即可,并不要求都是100%或者接近100%占用。所以要判断是否充分利用,可能还需要其他进一步的研究和观察。

2:1,2,3这样的时间对比,显然是没有充分利用。但是之后的情况难以判明,因为不知道具体的执行情况。以及您提供的测试时间也并非和您推导的比值很好地吻合,这说明应该还有一些和您设想不一致的地方。

3:暂无其他分析建议,本人非研究fft算法方向,仅能简要分析至此,请熟悉cufft实现的NV内部人士补充(如果可以的话),或请其他专门研究fft算法的人继续讨论。

欢迎您莅临论坛,祝您好运~
使用道具 举报 回复 支持 反对
发表于 2013-11-17 09:36:12
1, 算法复杂度只能分析个大概,对于小点数应该减去一个内核spawn的开销,然后再做比例分析,这样更准点,大点数还好些。
2,实现包括内存,共享内存和计算三者间的overlap,一种机制不能对所有点都特别优化,有一定的起伏。
使用道具 举报 回复 支持 反对
发新帖
您需要登录后才可以回帖 登录 | 立即注册