JuliaCon 2022 (Times are UTC)

Fast, Faster, Julia: High Performance Implementation of the NFFT
07-28, 12:30–13:00 (UTC), Green

In this talk, we present the architecture of the NFFT.jl package, which implements the non-equidistant fast Fourier trans-form (NFFT). The NFFT is commonly implemented in C/C++ and requires sophisticated performance optimizations to exploit the full potential of the underlying algorithm. We demonstrate how Julia enables a high-performance, generic, and dimension-agnostic implementation with only a fraction of the code required for established C/C++ NFFT implementations.

The non-equidistant fast Fourier transform (NFFT) is an extension of the well-known fast Fourier transform (FFT) in which the sample points in one domain can be non-equidistant. The NFFT is an approximate algorithm and allows the approximation error to be controlled to achieve machine precision while keeping the algorithmic complexity in the same order of magnitude as a regular FFT. The NFFT plays an important role in many signal processing applications and has been intensively studied from both theoretical and computational perspectives. The fastest NFFT libraries are implemented in the low-level programming languages C and C++ and require a trade-off between generic code, code readability, and code efficiency.

In this talk, we show that Julia provides new ways to optimize these three conflicting goals. We outline the architecture and implementation of the NFFT.jl package, which has recently been refactored to match the performance of the modern C++ implementation FINUFFT. NFFT.jl is fully generic, dimension-independent, and has a flexible architecture that allows parts of the algorithm to be exchanged through different code paths. This is crucial for the realization of different precomputation strategies tailored to optimize either the computation time or the required main memory. NFFT.jl makes intensive use of the Cartesian macros in Julia Base, allowing for zero-overhead and dimension-agnostic implementation. In contrast, the two modern C (NFFT3) and C++ (FINUFFT) libraries use dedicated 1D, 2D and 3D code paths to achieve maximum performance. The generic Julia implementation thus avoids code duplication and requires 3-4 times less code than its C/C++ counterparts. NFFT.jl is multi-threaded and uses a cache-aware blocking technique to achieve decent speedups.

Package being presented:
- https://github.com/JuliaMath/NFFT.jl

Tobias Knopp received his Diplom degree in computer science in 2007 and his PhD in 2010, both from the University of Lübeck with highest distinction. For his PhD on the tomographic imaging method Magnetic Particle Imaging (MPI) he was awarded with the Klee award from the DGBMT (VDE) in 2011. From 2010 until 2011 he led the MAPIT project at the University of Lübeck and published the first scientific book on MPI. In 2011 he joined Bruker Biospin to work on the first commercially available MPI system. From 2012 until 2014 he worked at Thorlabs in the field of Optical Coherence Tomography (OCT) as a software developer. Since 2014, Tobias Knopp is a professor for Biomedical Imaging at the University Medical Center Hamburg-Eppendorf and the Hamburg University of Technology in Hamburg, Germany. Beside his work as a researcher in the field of tomographic imaging method Tobias Knopp is an open-source developer and part of the Julia community since 2012.