## Featured Story Corner## Highly Scalable Parallel Three-dimensional Fast Fourier Transforms## —Dmitry PekurovskyFast Fourier Transforms (FFT) is a very commonly used numerical technique in computational physics, engineering, chemistry, geosciences, and other areas of high performance computing. Since this is a mature subject of research, there are many excellent FFT libraries available. Some of those libraries are optimized for a particular architecture while others are generic; some are proprietary, while others, such as the Fastest Fourier Transform in the West (FFTW) are open source. FFT libraries typically provide several types of one dimensional FFT transforms, and some libraries provide two and three dimensional (3D) transform capability. However, not all of the libraries provide parallel implementations of FFTs. Those that do provide the parallel capability are subject to an important constraint that we will discuss below, leading to limited scalability. The subject of this article is parallelizing 3D FFT in a highly scalable fashion. Consider a parallel implementation of a 3D FFT of a 3D array of complex numbers. Somehow, this array needs to be decomposed among P processors. One easy way to do it is to divide the volume of data into slabs, each consisting of one or several planes. If each processor gets such a slab to hold in its memory, this scheme is called
An alternative approach was used to overcome the scalability limitation in the SAC project on DNS turbulence mentioned above. Here the data volume is divided into columns, which is called The execution speed (number of steps per second of execution), normalized by the problem size, is plotted on the Y-axis. In summary, 2D decomposition increases scaling capability of codes making intensive use of 3D FFT. Implementing 2D decomposition requires a somewhat more elaborate communication module than 1D decomposition. As an outcome of the SAC project mentioned above, we created a standalone 3D FFT module, which can be incorporated into other applications relying on 3D FFT usage.This module, dubbed P3DFFT, provides 3D FFT utilities in an optimized fashion and hopefully will be of benefit to our users who are in the process of gearing their software for petascale computing. See the SDSC User Services Applications section for a downloadable beta version and user guide. We would appreciate hearing from users about the degree of interest in such a utility, as well as any feedback about using the beta version, for example bugs and suggested features. Please contact Dmitry Pekurovsky with your comments. |