DaggerFFT: A Distributed FFT Framework Using Task Scheduling in Julia
Preprint
Abstract
The Fast Fourier Transform (FFT) is a fundamental numerical technique with widespread application in a range of scientific problems. As scientific simulations attempt to exploit exascale systems, there has been a growing demand for distributed FFT algorithms that can effectively utilize modern heterogeneous high-performance computing (HPC) systems. Conventional FFT algorithms commonly encounter performance bottlenecks, especially when run on heterogeneous platforms. Most distributed FFT approaches rely on static task distribution and require synchronization barriers, limiting scalability and impacting overall resource utilization. In this paper we present DaggerFFT, a distributed FFT framework, developed in Julia, that treats highly parallel FFT computations as a dynamically scheduled task graph. Each FFT stage operates on a separately defined distributed array. FFT operations are expressed as DTasks operating on pencil or slab partitioned DArrays. Each FFT stage owns its own DArray, and the runtime assigns DTasks across devices using Dagger's dynamic scheduler that uses work stealing. We demonstrate how DaggerFFT's dynamic scheduler can outperform state-of-the-art distributed FFT libraries on both CPU and GPU backends, achieving up to a 2.6x speedup on CPU clusters and up to a 1.35x speedup on GPU clusters. We have integrated DaggerFFT into Oceananigans.jl, a geophysical fluid dynamics framework, demonstrating that high-level, task-based runtimes can deliver both superior performance and modularity in large-scale, real-world simulations.Keywords
All Related Versions
This publication has 9 references indexed in Scilit:
- OpenFFT-SME: An Efficient Outer Product Pattern FFT Library on ARM SME CPUs2024
- GFFT: a Task Graph Based Fast Fourier Transform Optimization Framework2023
- OpenFFT: An Adaptive Tuning Framework for 3D FFT on ARM Multicore CPUs2023
- An effective 3-D fast fourier transform framework for multi-GPU accelerated distributed-memory systemsThe Journal of Supercomputing, 2022
- Performance Analysis of Parallel FFT on Large Multi-GPU Systems2022
- GeophysicalFlows.jl: Solvers for geophysical fluid dynamics problems in periodic domains on CPUs GPUsJournal of Open Source Software, 2021
- Oceananigans.jl: Fast and friendly geophysical fluid dynamics on GPUsJournal of Open Source Software, 2020
- Fast Parallel Algorithms for Short-Range Molecular DynamicsJournal of Computational Physics, 1995
- LogP: towards a realistic model of parallel computation1993