On the Communication Complexity of 3D FFTs and Its Implications for Exascale

This paper revisits the communication complexity of large-scale 3D Fast Fourier Transforms (FFTs) and asks what impact trends in current architectures will have on FFT performance at exascale. The authors analyze both memory hierarchy traffic and network communication to derive suitable analytical models, which they calibrate against current software implementations; they then evaluate models to make predictions about potential scaling outcomes at exascale, based on extrapolating current technology trends. Of particular interest is the performance impact of choosing high-density processors, typified today by graphics co-processors (GPUs), as the base processor for an exascale system.