Overview / Usage

快速傅里叶变换(Fast Fourier Transformation，FFT)是一种利用计算机计算离散傅里叶变换(DFT)的高效、快速计算方法，能够在时间复杂度为O(nlogn)的时间内将多项式的系数表示法转换成点值表示法，从而能够极大提升傅里叶变换算法的运行速度。具体而言，快速傅氏变换是根据离散傅氏变换的奇、偶、虚、实等特性，对离散傅立叶变换的算法进行改进获得的，所以它对傅氏变换的理论并没有新的发现，但是对于在计算机系统或者说数字系统中应用离散傅立叶变换具有非常大的意义。比如所，FFT可以快速将一个信号从时域变换到频域，从而快速进行频谱特征分析。因此，我们现代生活中的很多科技，比如无线通讯和GPS，甚至于任何和信号处理有关的算法，都依赖于FFT的高效性。 本项目计划将FFT时间抽取算法进行MPI并行实现。

Methodology / Approach

FFT的基本思想是把原始的N点序列，依次分解成一系列的短序列。充分利用DFT计算式中指数因子所具有的对称性质和周期性质，进而求出这些短序列相应的DFT并进行适当组合，达到删除重复计算、减少乘法运算和简化结构的目的。计算离散傅里叶变换的快速方法，有按时间抽取的FFT算法和按频率抽取的FFT算法。前者是将时域信号序列按偶奇分排，后者是将频域信号序列按偶奇分排。

如果采用传统的基于并行模型的算法进行上述蝶形迭代运算，虽然在任务执行的前一部分处理核心之间没有数据交换，可以实现完全的并行，但在任务执行的后半阶段，相应的处理核之间需要数据的交换，当数据量N的规模较大时，必然会出现大量的拥塞，拥塞现象将大幅度影响硬件的利用率，对算法性能造成较大影响。为了提高性能，本工作采用了一种叫Six-step FFT的算法，以提高并行算法的性能。

Technologies Used

我们使用了intel平台的oneApi技术来实现FFT的并行化计算。

Repository

https://github.com/lss-1138/oneapi-fft

Collaborators