Parallel Design And Implementation Of FFT Algorithm Based On MPI And Linux Cluster Environment

In the digital era, the frequency domain processing in the digital signal is indispensable to almost all of the actual system. The fast Fourier transform is the core technology of digital signal processing, being the most commonly used requency domain processing method, along with the rapid development of the field of communications, which has been widely used. The amount of data using the FFT processing is growing and the use of large amounts of data serial FFT calculation takes too long time with the rapid development of communication domain, which has been unable to meet the practical requirements. Parallel computing is an effective way to deal with a very large amount of data and time-consuming operation, and the cluster system is the mainstream platform of parallel computing programming, then the research of achieving FFT parallel based on the platform of cluster system is of great significance.This thesis describes the research background, significance and the main work, then introduces the large and complex knowledge in parallel computing of parallel machine architecture and several typical parallel computer systems. In parallel machine system, we focuse on the current mainstream platform for fleet system, and then introduces the theory of parallel algorithms and analysis and compare several parallel programming model. Combined with the system institutions fleet, we choose programming model and messaging application which is selected as the broader MPI communication standard. Based on theoretical study, we rezlized the buliding of PC fleet based on the operation system environment of Linux and Windows using experiment room conditions. Then we study the principles of FFT algorithm and mainly study the structural characteristics of the butterfly computing FFT algorithm, while analyze the fat binary tree network topology, based on the similar structural characteristics between them. We proposed FFT parallelization idea based on fat binary tree logical structure. Then, we analyze the feasibility of this idea in detail and achieve programming based on MPI.In the experimental part, this thesis introduces the experimental environment firstly. Let parallel algorithms and parallel FFT algorithm programmed in serial dawn TC5000 cluster groups experience more numerous experimental tests, and compares a series of obtained experimental data in the different treatment parallel data amount about the difference of time on parallel FFT and serial FFT. According to the experimental results which were reflected the situation verify the feasibility of logic based on binary fat tree structure FFT parallelization implemented in the cluster environment, and gets some meaningful conclusions about parallel computing. Finally, we summarize the thesis in front of the work and present the FFT algorithmparallelism to further optimize the combination of the architectural features of the idea of cluster system will be finished in the future.