The Design And Implementation Of High-dimension Parallel FFT Vector Coding Algorithm

Since the Cooley-Tukey found FFT (Fast Fourier Transform) algorithm, FFT rapidly spread to all fields of science. It gives our lives an enormous impact. More and more people start to research FFT algorithms, the hope of finding better ways to increase the speed of FFT. With the development of modern parallel computer, a number of parallel FFT algorithm emerged. Most algorithms is based on a specific parallel computer structure, that is to say, these kind of algorithms only maximize the effectiveness when they are used on the special computer. These algorithms are not universal.Vector coding algorithm is a new kind of FFT algorithm. Comparing with the row-column of algorithms, it not only has the less computation, but also has a better solution to the code reverse order, the site operator and the butterfly operator. This article is based on the FFT vector coding algorithm, and transforms the FFT into a three steps. These three steps, the first two relatively independent, can be better to completely compute in parallel. And the third step, if the number of processors is less, can be in full accordance with the operator to add and subtract.In this article, the author uses the storage-style shared memory parallel computer to test the high-dimensional FFT algorithm for vector coding with the MPI parallel library to develop this algorithm, several tests showed that less than ideal speedup. Study found that shared memory based on the OpenMP parallel language model than message passing based on MPI is more suitable. It is more efficient to test in this parallel machine. The result is that the maximum speedup is 3.2 when we computer the two-dimensional data.