Improved Acceleration of the GPU Fourier Domain Acceleration Search Algorithm

Karel Adámek, Sofia Dimoudi, Michael B. Giles, Wesley ArmourarXiv 2017 · DOI · arXiv

Abstract

We present an enhanced implementation of the Correlation Technique for the Fourier Domain Acceleration Search (FDAS) algorithm on Graphics Processing Units (GPUs). By replacing standard NVIDIA cuFFT libraries with custom-built GPU kernels optimized for shared memory and warp-level primitives, we achieved a convolution code that is 2.5 to 3.9 times faster than cuFFT-based versions on an NVIDIA P100. These optimizations result in a 44% overall performance increase for FDAS compared to previous best implementations and an 8-fold speedup over the industry-standard PRESTO GPU implementation.

Introduction

The search for binary pulsars is a cornerstone of modern radio astronomy, providing unique laboratories for testing general relativity. However, the orbital motion of a pulsar in a binary system induces a time-varying Doppler shift, "smearing" its signal in the frequency domain. The Fourier Domain Acceleration Search (FDAS) algorithm mitigates this by applying matched filtering (convolutions) to "de-smear" the data. Given the massive computational requirements of processing high-resolution survey data, accelerating FDAS is critical for real-time analysis in projects like the Square Kilometre Array (SKA).

Optimization Strategies

The primary bottleneck in FDAS is the execution of numerous Fast Fourier Transforms (FFTs). While NVIDIA’s cuFFT library is highly optimized for general use, it often relies on global memory access, which limits performance for specific signal processing pipelines. Our approach, integrated into the AstroAccelerate library, focuses on keeping data within the GPU's high-speed shared memory.

Key optimizations include:

  • Custom Shared Memory Kernels: By performing the entire FFT-Multiplication-Inverse FFT sequence within shared memory, we avoid costly round-trips to global memory.
  • Warp-Level Primitives: We utilize GPU "shuffle" instructions to allow direct data exchange between threads in a warp, reducing synchronization overhead.
  • Increased Work per Thread: We evaluated different configurations for the number of FFT elements processed per thread to maximize data reuse and instruction efficiency.
Table 2: Execution times (ms) for various FFT kernel variants on P100 and TITAN X (p) GPUs. The 4-element per thread variant shows the best performance on the P100.

As shown in the table above, the 4-element per thread variant achieved the lowest execution time (1.80 ms) on the P100, significantly outperforming the global-memory-limited cuFFT baseline (3.05 ms).

Performance Results

The custom convolution kernels demonstrate substantial speedups across various filter lengths. On the NVIDIA P100, the speedup factor relative to a cuFFT-based implementation ranges from 2.45x to 3.89x, depending on the filter size.

Table 1: Speedup of the custom convolution code compared to cuFFT-based implementations for different filter lengths. Values in brackets represent speedup over the previous custom version.

These kernel-level improvements translate to a 44% overall performance boost for the FDAS algorithm. When compared to the widely used PRESTO GPU implementation, our optimized FDAS is approximately 8 times faster, enabling much more efficient pulsar searches.

Conclusion

By tailoring GPU kernels to the specific mathematical structure and memory access patterns of the FDAS algorithm, we have achieved significant performance gains over general-purpose libraries. This work ensures that the AstroAccelerate library remains capable of meeting the extreme data processing demands of next-generation radio telescopes like the SKA. Future work will explore further register optimizations to push the boundaries of real-time pulsar discovery.

Summary updated

Abstract

We present an improvement of our implementation of the Correlation Technique for the Fourier Domain Acceleration Search (FDAS) algorithm on Graphics Processor Units (GPUs) (Dimoudi & Armour 2015; Dimoudi et al. 2017). Our new improved convolution code which uses our custom GPU FFT code is between 2.5 and 3.9 times faster the than our cuFFT-based implementation (on an NVIDIA P100) and allows for a wider range of filter sizes then our previous version. By using this new version of our convolution code in FDAS we have achieved 44% performance increase over our previous best implementation. It is also approximately 8 times faster than the existing PRESTO GPU implementation of FDAS (Luo 2013). This work is part of the AstroAccelerate project (Armour et al. 2002), a many-core accelerated time-domain signal processing library for radio astronomy.
BibTeX
@misc{adamek2017improved,
  author = {Karel Adámek and Sofia Dimoudi and Michael B. Giles and Wesley Armour},
  title = {{Improved Acceleration of the GPU Fourier Domain Acceleration Search Algorithm}},
  year = {2017},
  eprint = {1711.10855},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1711.10855},
}
Figure