Michael Pippig: PFFT - An Extension of FFTW to Massively Parallel Architectures

Author(s):

Michael Pippig

Title:

Michael Pippig: PFFT - An Extension of FFTW to Massively Parallel Architectures

Electronic source:

application/pdf

Preprint series:

Technische Universität Chemnitz, Fakultät für Mathematik (Germany). Preprint 06, 2012

Mathematics Subject Classification:

65T50	[Discrete and fast Fourier transforms]
65Y05	[Parallel computation]

Abstract:

We present a MPI based software library for computing the fast Fourier transforms on massively parallel, distributed memory architectures. Similar to established transpose FFT algorithms, we propose a parallel FFT framework that is based on a combination of local FFTs, local data permutations and global data transpositions. This framework can be generalized to arbitrary multi-dimensional data and process meshes. All performance relevant building blocks can be implemented with the help of the FFTW software library. Therefore, our library offers great flexibility and portable performance. Likewise FFTW, we are able to compute FFTs of complex data, real data and even- or odd-symmetric real data. All the transforms can be performed completely in place. Furthermore, we propose an algorithm to calculate pruned FFTs more efficiently on distributed memory architectures. For example, we provide performance measurements of FFTs of size $512^3$ and $1024^3$ up to $262144$ cores on a BlueGene/P architecture.

Keywords:

parallel fast Fourier transform, FFT

Language:

English

Publication time:

05/2012