3 ms·

Fast Fourier Transform in Rust

55 points by logicalguess 3y ago

logicalguess 3y ago
For those who are interested, there is a strong connection between FFT and quantum gates. Applying a gate to a target qubit in a quantum system follows the same computing pattern as one stage in FFT. Consequently, any quantum simulator contains an FFT implementation, and an efficient FFT implementation can be ported to a quantum simulator implementation. To see how quantum gates work, take a look at Spinoza: https://github.com/QuState/spinoza https://github.com/QuState/spinoza, a sister project for PhastFT, and Hume, a simpler, but lower performing, Python version: https://github.com/learnqc/code/tree/main/src/hume https://github.com/learnqc/code/tree/main/src/hume.
deleted 3y ago
[deleted]
amelius 3y ago
When will Rust be available for the GPU, and will this code work then?
- littlestymaar 3y ago
  Rust is already available for GPU, kind of: https://github.com/EmbarkStudios/rust-gpu https://github.com/EmbarkStudios/rust-gpu I don't think it's production ready though and I have no idea if this library should work on this.
  - cchance 3y ago
    How does this differ from outputting wgpu from rust?
    - bendn 3y ago
      wgpu uses WGSL as its shader language, not rust..?
    - littlestymaar 3y ago
      I have no idea, I just saw this pop up on reddit again yesterday in a thread[1], I had seen it before and forgotten its existence. [1]: https://www.reddit.com/r/rust/comments/1cho244/luminal_compiling_fast_gpu_kernels_in_rust/ https://www.reddit.com/r/rust/comments/1cho244/luminal_compi...
eru 3y ago
Btw, Rust is big in 'crypto', and for eg Zero Knowledge Proofs we do a lot of Fourier transforms, too. And there's a few implementations in Rust for that. See https://en.wikipedia.org/wiki/Discrete_Fourier_transform_over_a_ring https://en.wikipedia.org/wiki/Discrete_Fourier_transform_ove...
deleted 3y ago
[deleted]
gct 3y ago
This isn't really apples-to-apples comparing with FFTW. 1. It's been my experience that distros don't configure AVX properly for it, and 2. PhastFT takes its inputs de-interleaved in separate real/imaginary arrays which is generally not how complex data is provided, so that overhead doesn't appear in PhastFT.
- O3marchnative 3y ago
  Hi, One of the authors of PhastFT here. Thank you for your interest. We went out of our way to configure FFTW for AVX-512. The Rust bindings don't do it, but the FFTW itself in the benchmark does. It's worth noting that with FFTW you have to choose between building it for your CPU and making it non-portable, or targeting the lowest common denominator of CPU features so that it runs everywhere but much slower. Meanwhile PhastFT detects the available CPU features at runtime, and will utilize the fastest CPU features without sacrificing portability. Lastly, we are currently working on support for interleaved format [1]. That should ship in the next release. [1] https://github.com/QuState/PhastFT/pull/27 https://github.com/QuState/PhastFT/pull/27
  - gct 3y ago
    FFTW will definitely query cpuid at runtime too, since it's piecing together kernels anyways it's not much more work for it to choose to ignore AVX, etc. If you use the [guru interface](https://www.fftw.org/fftw3_doc/Guru-vector-and-transform-sizes.html https://www.fftw.org/fftw3_doc/Guru-vector-and-transform-siz...) to configure it to work with split arrays (and maybe use FFTW_MEASURE when planning) I think the benchmarks will be a lot more 1:1

55 points by logicalguess 3y ago

For those who are interested, there is a strong connection between FFT and quantum gates. Applying a gate to a target qubit in a quantum system follows the same computing pattern as one stage in FFT. Consequently, any quantum simulator contains an FFT implementation, and an efficient FFT implementation can be ported to a quantum simulator implementation. To see how quantum gates work, take a look at Spinoza: https://github.com/QuState/spinoza https://github.com/QuState/spinoza, a sister project for PhastFT, and Hume, a simpler, but lower performing, Python version: https://github.com/learnqc/code/tree/main/src/hume https://github.com/learnqc/code/tree/main/src/hume.

deleted 3y ago

[deleted]

amelius 3y ago

When will Rust be available for the GPU, and will this code work then?

littlestymaar 3y ago
Rust is already available for GPU, kind of: https://github.com/EmbarkStudios/rust-gpu https://github.com/EmbarkStudios/rust-gpu I don't think it's production ready though and I have no idea if this library should work on this.
- cchance 3y ago
  How does this differ from outputting wgpu from rust?
  - bendn 3y ago
    wgpu uses WGSL as its shader language, not rust..?
  - littlestymaar 3y ago
    I have no idea, I just saw this pop up on reddit again yesterday in a thread[1], I had seen it before and forgotten its existence. [1]: https://www.reddit.com/r/rust/comments/1cho244/luminal_compiling_fast_gpu_kernels_in_rust/ https://www.reddit.com/r/rust/comments/1cho244/luminal_compi...

eru 3y ago

Btw, Rust is big in 'crypto', and for eg Zero Knowledge Proofs we do a lot of Fourier transforms, too. And there's a few implementations in Rust for that. See https://en.wikipedia.org/wiki/Discrete_Fourier_transform_over_a_ring https://en.wikipedia.org/wiki/Discrete_Fourier_transform_ove...

deleted 3y ago

[deleted]

gct 3y ago

This isn't really apples-to-apples comparing with FFTW. 1. It's been my experience that distros don't configure AVX properly for it, and 2. PhastFT takes its inputs de-interleaved in separate real/imaginary arrays which is generally not how complex data is provided, so that overhead doesn't appear in PhastFT.

O3marchnative 3y ago
Hi, One of the authors of PhastFT here. Thank you for your interest. We went out of our way to configure FFTW for AVX-512. The Rust bindings don't do it, but the FFTW itself in the benchmark does. It's worth noting that with FFTW you have to choose between building it for your CPU and making it non-portable, or targeting the lowest common denominator of CPU features so that it runs everywhere but much slower. Meanwhile PhastFT detects the available CPU features at runtime, and will utilize the fastest CPU features without sacrificing portability. Lastly, we are currently working on support for interleaved format [1]. That should ship in the next release. [1] https://github.com/QuState/PhastFT/pull/27 https://github.com/QuState/PhastFT/pull/27
- gct 3y ago
  FFTW will definitely query cpuid at runtime too, since it's piecing together kernels anyways it's not much more work for it to choose to ignore AVX, etc. If you use the [guru interface](https://www.fftw.org/fftw3_doc/Guru-vector-and-transform-sizes.html https://www.fftw.org/fftw3_doc/Guru-vector-and-transform-siz...) to configure it to work with split arrays (and maybe use FFTW_MEASURE when planning) I think the benchmarks will be a lot more 1:1