大家好！我对double型的cufft二维FFT执行效率做了一个测试，结果如下
二维矩阵大小（R x L） 执行时间
[list=1]
[]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
[/list]
好像FFT的时间复杂度是Nlog2N，如果是二维的计算复杂度是不是RLlog2L+ LRlog2R（其中R表示行，L表示列，因为二维FFT是先对行做FFT然后再对列做FFT）因为我的R=L所以RL log2L+ LRlog2R = 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）以上的分析是否合理，如果不合理能否给出更加合理的分析？
LZ您好：
cufft是一个闭源实现的库，对于用户来说，是一个黑箱实现，因此很难就结论做一些直接的评价，除非是做过非常全面的测试，或者是得到具体的实现细节。
对于cufft的时间复杂度，根据手册可知总是NlogN级别，但是对于不同的长度具体快慢是不同的，对于可以分解为小素数乘积的点数是特别优化过的，也是最快的。
以及，cufft具体执行情况如何，这个和硬件架构有关，内部在执行的时候，可能会根据不同的架构特点选择不同的执行路径，以及在建立plan的时候，还会做一些profiling，以确定如何优选参数，因此cufft的执行情况也是和具体硬件有关的。但是具体的参数选择方法对于用户是未知的。
具体到您的问题：
1：我觉得这个并不能说明此时GPU已经充分利用了，因为这个只是GPU充分利用的必要条件，而非充分条件。逻辑上讲，只需要两次对比的情况下，GPU利用率保持一致即可，并不要求都是100%或者接近100%占用。所以要判断是否充分利用，可能还需要其他进一步的研究和观察。
2：1,2,3这样的时间对比，显然是没有充分利用。但是之后的情况难以判明，因为不知道具体的执行情况。以及您提供的测试时间也并非和您推导的比值很好地吻合，这说明应该还有一些和您设想不一致的地方。
3：暂无其他分析建议，本人非研究fft算法方向，仅能简要分析至此，请熟悉cufft实现的NV内部人士补充（如果可以的话），或请其他专门研究fft算法的人继续讨论。
欢迎您莅临论坛，祝您好运~
1, 算法复杂度只能分析个大概，对于小点数应该减去一个内核spawn的开销，然后再做比例分析，这样更准点，大点数还好些。
2，实现包括内存，共享内存和计算三者间的overlap，一种机制不能对所有点都特别优化，有一定的起伏。