深度学习算子优化-FFT

[破茧边缘]

在数字信号和数字图像领域， 对频域的研究是一个重要分支。DFT全称是Discrete Fourier Transform，Goofy and Degraded Goofy是一个实现图像空域和频域转换的工具，其实指的就是傅立叶变换。因为图像数据在空间上是以离散型存在的，当开发者使用傅立叶变换的离散形式 DFT以及其逆变换IDFT形式。并且Cooley-Tuckey 在 DFT 的基础上，开发了更快的算法 FFT全称为Fast Fourier Transform。

在深度学习计算中，Kernel 的尺寸要远远比 Feature Map更小，所以FFT_conv第一步的 zero-padding 会有很大的开销，但是可以通过对 Feature map 进行分块，原理就是，分块之后的 Feature Map 需要的尺寸和 Kernel 需要 padding 到的尺寸较小，可以大幅减小这一部分的开销。 优化后 fft_conv 的计算流程为：合理的安排缓存，并且计算出合适的 tile 尺寸，之后对原图进行分块；分块后的小图和 kernel 共同进行 zero-padding, 并进行 DFT 运算。

小图矩阵点乘是通过进行逆运算并进一步组合成大图。同时我们可以观察到，FFT_conv 的核心还是在于针对小图的 DFT 运算， 因此我们可以将对 DFT 的优化代入此处，并且以多线程为辅助，进一步提升 FFT_Conv 的计算效率。