Source-linked AI summary
P3DFFT: a framework for parallel computations of Fourier transforms in three dimensions
Dmitry Pekurovsky
TL;DR
Three-dimensional FFTs are communication-intensive and difficult to scale on many processing elements. P3DFFT addresses this with two-dimensional decomposition, achieving 45% parallel efficiency from 128 to 65,536 cores while extending scalability beyond one-dimensional decomposition limits.
Problem
Three-dimensional FFTs are compute- and communication-intensive components of computational applications, while one-dimensional decompositions lose scalability when processor count exceeds the linear grid size.
Method
P3DFFT implements three-dimensional Fourier and related transforms using two-dimensional domain decomposition, with local one-dimensional FFTs and interprocessor data exchanges.
Results
45% parallel efficiency was achieved from 128 to 65,536 compute cores in weak scaling, and the two-dimensional version continued scaling beyond the one-dimensional decomposition limit.
Takeaways & Limitations
Two-dimensional decomposition significantly increases the range of scalable three-dimensional FFT computation compared with one-dimensional decomposition.
Takeaways & Limitations
The communication analysis focuses on network throughput and does not model network contention because P3DFFT uses portable MPI_Alltoall(v).
Abstract
from arXiv · showhide
Fourier and related transforms is a family of algorithms widely employed in diverse areas of computational science, notoriously difficult to scale on high-performance parallel computers with large number of processing elements (cores). This paper introduces a popular software package called P3DFFT implementing Fast Fourier Transforms (FFT) in three dimensions (3D) in a highly efficient and scalable way. It overcomes a well-known scalability bottleneck of 3D FFT implementations by using two-dimensional domain decomposition. Designed for portable performance, P3DFFT achieves excellent timings for a number of systems and problem sizes. On Cray XT5 system P3DFFT attains 45% efficiency in weak scaling from 128 to 65,536 computational cores. Library features include Fourier and Chebyshev transforms, Fortran and C interfaces, in- and out-of-place transforms, uneven data grids, single and double precision. P3DFFT is available as open source at http://code.google.com/p/p3dfft/. This paper discusses P3DFFT implementation and performance in a way that helps guide the user in making optimal choices for parameters of their runs.
1. Introduction
P3DFFT addresses the limited scalability and public availability of general-purpose 3D FFT implementations by combining two-dimensional decomposition with portable, open-source software. It targets computational-science applications requiring dimension-wise local access to three-dimensional data.
- 3D FFTs are compute- and communication-intensive components in applications including turbulence, molecular dynamics, tomography, and astrophysics.
- 1D slab decomposition scales only up to the linear grid size, limiting use on systems with more processing elements.
- Few general-purpose 2D-decomposed implementations were publicly available, while related studies often produced non-public codes.
- P3DFFT provides an open-source, easy-to-use 2D-decomposed implementation designed for portability, diverse applications, and performance.
- The framework presents a portable implementation and benchmark analysis intended to guide choices of run parameters.
2. Parallel Implementation of Fourier Transforms
P3DFFT distributes a three-dimensional array as pencils across a two-dimensional processor grid, enabling local one-dimensional FFTs interleaved with data transposes. This extends the theoretical task-count limit beyond slab decomposition and supports related third-dimension transforms.
- 1D slab decomposition assigns planes to tasks but loses scalability when task count P exceeds linear grid size N.
- 2D pencil decomposition arranges tasks in an M1 x M2 virtual grid, with M1M2 = P controlling each processor’s rectangular data column.
- With 2D decomposition, the algorithm theoretically scales up to N^2 tasks.
- The 3D transform performs local 1D FFTs in X, Y, and Z, using two parallel transposes to reorient pencils between stages.
- For problems with one non-homogeneous dimension, the third FFT can be replaced by a Chebyshev or other appropriate transform.
3. P3DFFT design and use
P3DFFT combines pencil-oriented interfaces, configurable local storage and FFT kernels, MPI-based subgroup transposes, and options for portability and load balance. Its design accommodates real/complex transforms and uneven local grids while exposing performance-related choices.
- 3.1 Library overview: R2C transforms accept X-pencils and produce Z-pencils, while C2R reverses these distributions to avoid an extra transpose.
- 3.1 Library overview: P3DFFT supports Fortran and C access, uses MPI communication, and defines XYZ storage with X as the fastest-varying dimension.
- 3.3 Implementation strategy: The STRIDE1 option can transpose noncontiguous local data into stride-1 format before calling FFTW or ESSL, with loop blocking for cache use.
- 3.3 Implementation strategy: X-to-Y and Y-to-Z pencil transposes use MPI_Alltoall or MPI_Alltoallv within row and column subcommunicators of the virtual processor grid.
- 3.4 Load balancing: Uneven local dimensions and R2C/C2R output shapes can introduce load imbalance even when the processor grid divides the input grid evenly.
- 3.4 Load balancing: When load imbalance is small, USEEVEN pads send buffers so MPI_Alltoall can outperform MPI_Alltoallv on some Cray XT systems.
4. Results and Discussion
The benchmark suite measures repeated forward and backward transforms across several large-scale systems, while configurable defaults and user settings target portable performance. The supplied passages describe the test procedure and evaluation platforms but do not report numerical results.
- The sample test initializes a 3D array, performs forward and backward FFTs, verifies the result up to a scale factor, and averages timings over iterations.
- Tests discussed in the paper use Jaguar, Kraken, and Ranger, which differ in processor, memory, interconnect, and compiler configurations.
- P3DFFT provides reasonable defaults for portable performance plus user-controlled STRIDE1, USEEVEN, and processor-grid aspect-ratio settings.
1. STRIDE1 option
The STRIDE1 option determines whether P3DFFT or the FFT sub-library performs the local memory transpose, with different cache and access-pattern trade-offs.
- STRIDE1 controls whether P3DFFT performs the local memory transpose or delegates it to the FFT sub-library.
- Delegating the transpose can let the FFT library optimize cache flow together with the FFT, but requires non-stride-1 access on both input and output.
- P3DFFT’s separate transpose uses non-stride-1 access on only one side of the FFT, at the cost of an extra memory write/read in cache-sized chunks.
- Neither transpose strategy is generally superior, so the choice depends on the platform and run characteristics.
2. USEEVEN option
USEEVEN lets P3DFFT use MPI_Alltoall with padded, equal-sized buffers instead of the default MPI_Alltoallv. Its benefit is especially pronounced on Cray XT systems.
- USEEVEN enables MPI_Alltoall for transposes with unequal task buffers by padding them, while MPI_Alltoallv remains the default.
- The option has a noticeable effect on Cray XT5 because MPI_Alltoall and MPI_Alltoallv perform abnormally differently there.
- P3DFFT strongly recommends USEEVEN on Cray XT systems, but does not require it on other platforms.
3. Processor grid dimensions and task placement
P3DFFT’s performance depends on processor-grid geometry, communication behavior, and task placement. Two-dimensional decomposition avoids 1D scalability limits, but optimal settings vary by architecture and problem size.
- Communication structure: Two all-to-all transposes form P3DFFT’s main performance bottleneck, exchanging data within ROW and COLUMN sub-communicators.The FFT computation is distributed across three local 1D stages with transposes between X-, Y-, and Z-oriented pencils.
- Processor-grid geometry: M1 << M2 can make the ROW transpose local to a node, reducing its cost relative to the COLUMN exchange.This strategy is advantageous when the network can inject the required messages without becoming the limiting factor.
- Processor-grid geometry: 2048^3 transforms on 1024 cores show that time rises when M1 exceeds the cores-per-node threshold, and the square 32x32 grid is not optimal.The reported thresholds are 12 cores per node on Kraken and 16 on Ranger.
- Architecture dependence: At high core counts on Cray XT5, performance favors more square-shaped processor grids, contrary to the low-M1 strategy observed in the 1024-core example.The paper offers a possible explanation involving limits on the number of messages handled by the SeaStar interconnect.
- Practical guidance: Optimal M1 x M2 dimensions are architecture- and problem-specific; choosing M1 near the cores per node is a starting point, followed by test runs above and below it.Task placement is also scope-limited: the study focuses on cubic grids with simple contiguous placement, although topology-aware placement improved non-cubic cases elsewhere.
- Scaling results: 45% parallel efficiency is achieved from 128 to 65,536 cores under the paper’s weak-scaling definition.The study uses grids from 1024^3 through 8192^3 and accounts for the FFT’s O(N^3 log(N)) computational intensity.
5. Conclusion and related work
P3DFFT presents a portable, high-performance framework for scalable 3D FFTs using two-dimensional decomposition, with performance analyzed through benchmarks and an asymptotic model. Its Cray XT5 results demonstrate substantial weak-scaling capability, while processor-grid choices remain architecture- and problem-dependent.
- Conclusion: P3DFFT uses two-dimensional decomposition to extend the scaling range of parallel 3D FFTs beyond many one-dimensional implementations.The design emphasizes both portability and performance, supported by extensive experiments.
- Conclusion: Benchmark data agree with an asymptotic model based on network bisection bandwidth and provide a realistic expectation of high-scale P3DFFT performance.The model analysis estimates 6% efficiency relative to an assumed peak bisection bandwidth, but the estimate is explicitly described as rough.
- Conclusion: 45% weak-scaling efficiency was achieved on a Cray XT5 when increasing from 128 to 65,536 compute cores.The paper attributes efficiency loss to difficulty maintaining scalable sustained bisection bandwidth at very large core counts.
- Related work: Hybrid MPI/OpenMP implementations may aggregate messages, but their decisive performance advantage over pure MPI remains unresolved.Potential benefits are weighed against OpenMP overhead, false sharing, and programming difficulty; the approach might be implemented in later P3DFFT versions.
- Conclusion: P3DFFT supports several third-dimension transform types, while increased array-layout flexibility and isolated transpose calls are identified as possible future extensions.These prospective features are intended to broaden the package’s applicability in scientific computing.