Lune

SC2025Top-tier venue

Automatic Generation of Mappings for Distributed Fourier Operations

Doru-Thom Popovici, Botao Wu, John Shalf, Martin Kong

Abstract

The Fourier transform is an ubiquitous mathematical operation used in a multitude of scientific applications. Most distributed Fourier transform libraries provide rigid implementations that force developers of high performance applications to mold their code around the Fourier computation, omitting opportunities for minimizing communication across the Fourier transforms and the surrounding computation. In this work, we introduce a new automatic approach to generate distributed mappings for multi-dimensional Fourier operations, offering a solution to this problem. Our approach decides how to decompose, map, and schedule the computation as smaller and lower-dimensional parallel operations. We design and implement a novel non-linear iterative formulation that optimizes across Fourier and linear algebra operations. Our scheme leverages the Z3 SMT solver to minimize the number of communication steps across key MPI collectives, while selecting the grid shape. We evaluate the effectiveness of our new scheme and demonstrate 2 × -31 × speedups over coupled heFFTe and COSMA solutions.

Ask Lune

Know where this paper stands in minutes, not an afternoon.

Lune can read the top-tier papers that cite it and the ones closest to it, and tells you what it claims, what came after and where it falls short, each point cited to the paper it comes from. No skimming, no AI slop.

Questions to start from

Lune can draw on

its abstract · related work

Get the answer

Free to start. No credit card required.

Related papers

  1. Deinsum: Practically I/O Optimal Multi-Linear AlgebraAlexandros Nikolaos Ziogas, Grzegorz Kwasniewski, Tal Ben-Nun, Timo Schneider et al.SC 2022 · 2 citations
  2. Optimizing Quantum Fourier Transformation (QFT) Kernels for Modern NISQ and FT ArchitecturesYuwei Jin, Xiangyu Gao, Minghao Guo, Henry Chen et al.SC 2024 · 3 citations
  3. Bind the gap: compiling real software to hardware FFT acceleratorsJackson Woodruff, Jordi Armengol-Estapé, Sam Ainsworth, Michael F. P. O'BoylePLDI 2022 · 14 citations
  4. Automated Mapping of Task-Based Programs onto Distributed and Heterogeneous MachinesThiago S. F. X. Teixeira, Alexandra Henzinger, Rohan Yadav, Alex AikenSC 2023 · 5 citations
  5. Automatic Generation of Distributed-Memory Mappings for Tensor ComputationsMartin Kong, Raneem Abu Yosef, Atanas Rountev, P. SadayappanSC 2023 · 9 citations
Dusk over the sea between two cliffs drawn in fine vertical lines