一、Radix2的傅里叶变换的缺陷
首先,我们解释一下什么是Radix2,Radix4,Radix8等的傅里叶变换。在上一篇中,我们得出我们可以将N的傅里叶变换的输入拆为奇数和偶数,然后奇数和偶数分别进行傅里叶变换,再通过蝶形变换组合为N的傅里叶变换的结果。简单的公式形式化描述如下
$$
DFT(N) = DFT_1(\frac N 2) \oplus DFT_2(\frac N 2), \oplus表示蝶形变换
$$
我们可以知道,一次蝶形变换中所做的计算非常少,每一轮GPU派发很多任务,然后每个任务仅执行一次2个数据的蝶形变换,然后就结束写回Buffer了。这样我们的瓶颈往往会卡在DrawCall上。