A framework for low-communication 1-D FFT

Issue title: Selected Papers from Super Computing 2012

Article type: Research Article

Authors: Tang, Ping Tak Peter^; | Park, Jongsoo | Kim, Daehyun | Petrov, Vladimir

Affiliations: Intel Corporation, Santa Clara, CA, USA

Note: [] Corresponding author. E-mail: [email protected]

Abstract: In high-performance computing on distributed-memory systems, communication often represents a significant part of the overall execution time. The relative cost of communication will certainly continue to rise as compute-density growth follows the current technology and industry trends. Design of lower-communication alternatives to fundamental computational algorithms has become an important field of research. For distributed 1-D FFT, communication cost has hitherto remained high as all industry-standard implementations perform three all-to-all internode data exchanges (also called global transposes). These communication steps indeed dominate execution time. In this paper, we present a mathematical framework from which many single-all-to-all and easy-to-implement 1-D FFT algorithms can be derived. For large-scale problems, our implementation can be twice as fast as leading FFT libraries on state-of-the-art computer clusters. Moreover, our framework allows tradeoff between accuracy and performance, further boosting performance if reduced accuracy is acceptable.

Keywords: FFT, low communication, hybrid convolution theorem, Poisson summation formula

DOI: 10.3233/SPR-130373

Journal: Scientific Programming, vol. 21, no. 3-4, pp. 181-195, 2013