大点数FFT的多DSPs并行处理算法及实现

Algorithm and Implementation of a Large-Point FFT Under the Master-Slave Parallel Multi-Processor Architecture

在FFT变体的基础上 ,提出一种新的并行算法 :先将数据在几片DSPs上并行地进行前几级蝶型运算 ,然后将结果汇总到另一片DSPs进行后几级蝶型运算 ,以实现大点数的FFT。该算法便于流水处理 ,只有一次简单的数据通讯 ,而且旋转因子规律简单易于将大点数FFT拆分成小点数FFT。应用该算法在多DSPs系统上 (5片TI公司的高速DSP芯片 :1片C6 2 0 2和 4片C6 70 1)实现 2 5 6K点复数FFT只需用 4 9ms,说明该算法有并行度高和易于实现的特点。

In this paper, a new parallel algorithm based on a modified FFT algorithm is presented, with which an N-point FFT for a large N is easy to implement under the multi-processor architecture. In this algorithm, the first several stages of butterfly merging operations are carried out on the parallel digital signal processors (DSPs) and the outputs are sent to another DSP to perform other butterfly merging operations, where only one data communication is needed. It is easy to implement this algorithm on pipeline processors and to divide an N-point FFT for a large N into some short ones because of an easy way to rotate the factors. An implementation on a multi-DSP system with a DSP of TI C6202 and four DSPs of TI C6701 shows that it takes only 49ms to perform a 256K-point FFT, which indicates that this algorithm is easy to implement and has a high parallelism.