An Optimized Parallel FFT Algorithm on Multiprocessors with Cache Technology in Linux

Multiprocessor system is commonly used nowadays, and will be a trend in the next few years. In this paper, we propose a high-performance parallel Fast Fourier Transform (FFT) algorithm for a shared memory symmetric multiprocessor (SMP) system. Due to its intrinsic property of parallelism, the serial FFT algorithm can be altered to parallel algorithm, which improves the performance of FFT through distributed computations of every processor in the system. In addition, cache plays an important role in modern computer architectures. We analyze the feature of cache and make full use of it to increase the computation speed. Finally, we implement the parallel FFT algorithm in Linux. The experimental result shows that the performance of our implementation is much better than that of the traditional way using DSP.