A scheduling policy to save 10% of communication time in parallel fast Fourier transform
Samar A. Aseeri, Anando Gopal Chatterjee, Mahendra Kumar Verma, David Elliot Keyes · Concurrency and Computation Practice and Experience · 2021
Summary The fast Fourier transform (FFT) has applications in almost every frequency related study, for example, in image and signal processing, and radio astronomy. It is also used as a Poisson operator inversion kernel in partial differential equations in fluid flows, in density functional theory, many‐body theory, and others. The three‐dimensional FFT has large time complexity . Hence, parallelization is used to compute such FFTs. Popular libraries perform slab division or pencil decomposition of data. None of the existing libraries achieve perfect inverse scaling of time with cores because FFT requires all‐to‐all communication and clusters hitherto do not have physical all‐to‐all connections. Dragonfly, one of the popular topologies for the interconnect, supports hierarchical connections among the components. We show that if we align the all‐to‐all communication of FFT with the physical connections of Dragonfly topology we will achieve a better scaling and reduce communication time.