A GPU Implementation of the Correlation Technique for Real-time Fourier Domain Pulsar Acceleration Searches

Sofia Dimoudi, Karel Adámek, T. Prabu, S. M. Ransom, A. Karastergiou, Wesley ArmourThe Astrophysical Journal Supplement Series 2018 · DOI

TL;DR

This paper presents a GPU-accelerated implementation of the Fourier Domain Acceleration Search (FDAS) algorithm, crucial for detecting pulsars in binary systems. By optimizing the computationally intensive correlation technique using GPUs, they achieve significant speedups, enabling real-time analysis of data from future radio telescopes like the SKA.

What Problem Does This Paper Address?

Detecting pulsars, especially those in binary systems, is vital for testing fundamental physics like general relativity. However, the orbital motion of a pulsar in a binary system causes its observed spin frequency to drift. This "Doppler effect" spreads the pulsar's signal across multiple frequency bins, drastically reducing the sensitivity of standard periodicity searches. "Acceleration searches" are designed to counteract this effect by accounting for the pulsar's orbital acceleration.

The challenge is that these acceleration searches are computationally very expensive. With upcoming instruments like the Square Kilometre Array (SKA) generating unprecedented volumes of data, performing these searches in real-time is essential. Existing methods, while effective, struggle to meet these demands, necessitating the use of high-performance computing (HPC) platforms. This paper tackles the problem of making these crucial acceleration searches computationally feasible for real-time analysis on modern HPC hardware.

Methods

The core of this work is the implementation of the Fourier Domain Acceleration Search (FDAS) algorithm on Graphics Processing Units (GPUs). FDAS works by performing a convolution in the Fourier domain using multiple Finite Impulse Response (FIR) filters, each representing a different trial acceleration. This convolution is computationally intensive.

The authors explored two main GPU implementation strategies:

  1. cuFFT-based Approach: This method leverages NVIDIA's highly optimized cuFFT library for performing Fast Fourier Transforms (FFTs) on the GPU. Custom CUDA kernels were developed for the correlation and power spectrum calculations.
  2. Custom FFT on Shared Memory: This approach involves developing a custom FFT implementation that runs entirely within the GPU's fast on-chip shared memory. The goal is to minimize data transfers between global memory and the processing units, aiming for maximum efficiency.

Both approaches utilize the "overlap and save" method for efficient convolution and incorporate "interbinning" to mitigate signal loss due to frequency binning.

Datasets

Not discussed in the paper. The authors generated simulated pulsar signals using the "fake" program from the SIGPROC pulsar processing package for their evaluations.

Key Insights and Ideas

  • GPU Acceleration is Crucial for Real-time Pulsar Searches: The sheer computational demands of acceleration searches, especially for future instruments like the SKA, make GPUs a necessity for real-time processing.
  • Custom Shared Memory FFT Outperforms Libraries: Implementing FFTs directly in GPU shared memory can yield significant performance gains over using optimized libraries like cuFFT, especially when carefully tuned. This highlights the benefit of deep hardware-specific optimization.
  • Interbinning Trade-offs: While interbinning improves signal detection by mitigating "scalloping loss," its precise impact on SNR and the optimal implementation strategy require further investigation.
  • Architecture Matters: Performance gains are strongly influenced by GPU architecture, with newer architectures (Maxwell, Pascal) showing particular benefits due to improved shared memory capabilities.

Key Results

The custom FFT implementation on GPU shared memory demonstrated superior performance:

  • Speedup: The custom FFT implementation was 1.5 to 3.2 times faster than the cuFFT-based approach for smaller, sufficient filter sizes.
  • Comparison to Existing Software: It achieved a speedup of 4 to 6 times compared to existing GPU and OpenMP implementations of FDAS (specifically, PRESTO and PRESTO-GPU).
  • Real-time Capability: The optimized FDAS implementation, when tested on a Tesla P100 GPU with SKA-like sampling rates, could process over 6500 independent time series per second, indicating its suitability for real-time streaming pipelines.
  • Signal Recovery: The custom FFT algorithm achieved signal recovery performance comparable to PRESTO, demonstrating its effectiveness in detecting simulated pulsars.

Limitations and Future Work

  • Interbinning Characterization: The paper acknowledges that the precise impact of interbinning on SNR and detection accuracy is not fully understood and requires further investigation.
  • SNR Calculation: The current implementation does not include methods for calculating signal significance (SNR), which is a crucial step in actual pulsar detection pipelines. Future work should focus on developing and integrating these methods.
  • Harmonic Summing and Candidate Selection: The current GPU implementation focuses on the matched filtering and power spectrum calculation. Future work aims to incorporate computationally intensive steps like harmonic summing, search, and candidate selection onto the GPU to achieve end-to-end real-time processing.
  • Memory Limitations: The cuFFT-based approach faced memory limitations for larger signal sizes and template counts, which is expected to be less of an issue with evolving GPU memory capacities.
  • Template Size Limitation: The custom FFT implementation is currently limited to a template size of 1024 points due to shared memory constraints.

Summary updated

Abstract

Abstract The study of binary pulsars enables tests of general relativity. Orbital motion in binary systems causes the apparent pulsar spin frequency to drift, reducing the sensitivity of periodicity searches. Acceleration searches are methods that account for the effect of orbital acceleration. Existing methods are currently computationally expensive, and the vast amount of data that will be produced by next-generation instruments such as the Square Kilometre Array necessitates real-time acceleration searches, which in turn requires the use of high-performance computing (HPC) platforms. We present our implementation of the correlation technique for the Fourier Domain Acceleration Search (FDAS) algorithm on Graphics Processor Units (GPUs). The correlation technique is applied as a convolution with multiple finite impulse response (FIR) filters in the Fourier domain. Two approaches are compared: the first uses the NVIDIA cuFFT library for applying Fast Fourier transforms (FFTs) on the GPU, and the second contains a custom FFT implementation in GPU shared memory. We find that the FFT shared-memory implementation performs between 1.5 and 3.2 times faster than our cuFFT-based application for smaller but sufficient filter sizes. It is also 4–6 times faster than the existing GPU and OpenMP implementations of FDAS. This work is part of the AstroAccelerate project, a many-core accelerated time-domain signal-processing library for radio astronomy.
BibTeX
@article{dimoudi2018gpu,
  author = {Sofia Dimoudi and Karel Adámek and T. Prabu and S. M. Ransom and A. Karastergiou and Wesley Armour},
  title = {{A GPU Implementation of the Correlation Technique for Real-time Fourier Domain Pulsar Acceleration Searches}},
  journal = {The Astrophysical Journal Supplement Series},
  year = {2018},
  doi = {10.3847/1538-4365/aabe88},
}
Figure