The Fast Fourier Transform is a well-known algorithm used in many high-performance applications, ranging from signal processing to convolutional neural networks.

In this paper, we encode FFTs by building high-level abstractions based on a set of functional parallel patterns in the Lift language. Abstractions are derived from and closely resemble mathematical definitions for FFTs. We leverage the Lift performance-portable code generator to generate high performing GPU code for FFTs. No FFT-specific patterns are required for this, showing the expressive power of the generic parallel patterns used in Lift.

Our experimental results show that our approach achieves performance close to or better than AMD’s OpenCL implementation clFFT on two different models of GPU, but that Nvidia’s highly optimized cuFFT implementation still performs better on their GPUs.