并行计算环境下的快速傅立叶变换算法分析

为了提高并行环境下的傅立叶算法的运行速度,深入研究在不同并行计算模型下的傅立叶算法性能特点,分析输出结果序列关系和递归层数的确定方法,对SIMD-MCC模型、SIMD-BF模型、SIMD-CC模型下的傅立叶算法计算步骤和算法复杂度进行研究。结果表明,SIMD-CC模型更适合傅立叶算法的运算,其计算时间复杂度可达到O(lbn),并且使用的处理器个数也较SIMD-MCC模型少。

Analysis on Fast Fournier Transformation Algorithm under Parallel Computing Environment

In order to enhance the running rate of Fourier algorithm under the parallel environment the performance characteristics of Fourier algorithm with the different parallel computing model are thoroughly studied, and the output result sequence relations and the recursion layer definite method also analyzed. Then, the computing steps and algorithm complexity of Fourier algorithm under the SIMD-MCC model, the SIMI）-BF model and SIMD-CC model are discussed in detail. The experimental results show that SIMD-CC model is more suitable for Fourier algorithm operation, its computing-time complexity could reach O（ln）, and compared with SIMD-MCC mode, less processors are used.