GPU-FFT

A Rust library for GPU-accelerated FFT and IFFT built on CubeCL.

Table of Contents

• Features
• Requirements
• Installation
• Usage
• Benchmarks
• License

Features

• Cooley-Tukey radix-2 DIT FFT/IFFT — O(N log₂ N), runs log₂ N butterfly-stage kernel dispatches of N/2 threads each instead of a single O(N²) DFT pass
• Automatic zero-padding — non-power-of-two inputs are padded to the next power of two
• Power Spectral Density — one-sided PSD with correct 1/N normalisation
• Dominant frequency detection — local-peak search above a threshold
• wgpu and CUDA backends via CubeCL feature flags

Roadmap

• GPU kernel (CubeCL / wgpu)
• Precomputed twiddle factors (WIP branch)
• Cooley-Tukey radix-2 FFT — O(N log N)
• Shared-memory tiling — inner stages fused into one launch; 10 → 1 dispatch for N ≤ 1 024
• Batched FFT (multiple signals in one kernel launch)
• Mixed-radix / radix-4 — halve the outer-stage count for large N

Requirements

• Rust 1.84 or later
• A Vulkan, Metal, or DX12 GPU (wgpu backend) or an NVIDIA GPU (CUDA backend)

Installation

cargo add gpu_fft -F wgpu

Usage

cargo run --example simple -F wgpu

The example generates a 15 Hz sine wave, runs FFT, identifies the dominant frequency in the one-sided spectrum, then reconstructs the signal with IFFT and reports the round-trip error.

Example Output

Input
  samples    : 1000  (zero-padded to 1024 for FFT)
  sample rate: 200 Hz
  frequency  : 15 Hz
  first 5    : [0.0000, 0.4540, 0.8090, 0.9877, 0.9511]

FFT  completed in 5.21ms
Dominant frequencies (0 … 100 Hz):
     15.04 Hz  power       243.16

IFFT completed in 1.84ms
Round-trip max error : 3.58e-6  (limit 5·log₂N·ε = 5.96e-6)  ✓

The first run includes GPU shader compilation (~50 ms one-time cost per kernel variant). Subsequent calls reuse the compiled shaders.

Benchmarks

Performance

Charts and the table below are regenerated automatically by ./scripts/bench.sh. Shaded bands show the Criterion 95 % confidence interval.

Full results (95 % CI, std dev, raw Criterion output) → bench-results/latest.md

Running benchmarks

# Run everything, generate charts, save report
./scripts/bench.sh

# Single size
cargo bench --features wgpu --bench fft_bench -- fft/65536

# Save a named Criterion baseline, then compare after changes
./scripts/bench.sh -- --save-baseline before
./scripts/bench.sh -- --baseline before

Results are saved to bench-results/latest.md and archived under bench-results/archive/.

Algorithm

FFT

1. Bit-reverse permute the input on the CPU (O(N), negligible).
2. Upload to GPU.
3. Inner stages (where half_stride < TILE_SIZE/2 = 512) — fused into a single kernel launch using workgroup shared memory. Each workgroup of 512 threads loads 1 024 elements into SharedMemory<f32>, runs all ≤ 10 butterfly stages with sync_cube() barriers between stages, then writes back. This eliminates ~10 × 65 µs of kernel-launch overhead per call.
4. Outer stages — one kernel launch each, reading/writing global memory.

   W  = exp(-jπ · k / half_stride)     (forward; positive for inverse)
   out[i] = in[i] + W · in[j]
   out[j] = in[i] − W · in[j]
   

5. Read back.

Total launches per transform:

Each unique (tile, stages, direction) / (N, half_stride, direction) triple compiles to a separate specialised kernel cached by CubeCL after the first run.

IFFT

Same butterfly with positive twiddle factors, followed by a CPU-side 1/N divide.

License

This project is licensed under the MIT License. See the LICENSE file for details.

Copyright

© 2025-2026, Eugene Hauptmann