DTolm

Hello, I am the author of VkFFT, Tolmachev Dmitrii.

I remember VkFFT got a lot of initial traction thanks to Hacker News three years ago. Back then VkFFT was a simple collection of pre-made shaders for powers of two FFTs.

Nowadays it is based on the runtime code generation and optimization platform that supports all the mentioned backends, has a wide range of implemented algorithms (some of which are not even present in other codes) to cover all system sizes and can do things no other GPU FFT library can so far (like real to real transforms, arbitrary dimensional transforms, zero-padding, convolutions and more).

If you have some questions about the library, design choices, functionality or anything else - I will be happy to answer them!

The white paper of VkFFT is out. It can be interesting to people who want to know more about performant GPU algorithms in HPC and how VkFFT is designed.

VkFFT is an efficient GPU-accelerated multidimensional Fast Fourier Transform library for Vulkan/CUDA/HIP/OpenCL/Level Zero and Metal projects. VkFFT aims to provide the community with a cross-platform open-source alternative to vendor-specific solutions while achieving comparable or better performance.

In VkFFT FFT is done as a part of the so called compute queue. There is no need to transfer data through PCI to show it on screen - there is a graphics queue that has this as its main purpose. You can use compute queue results in it and do all necessary calculations directly on the GPU. This type of task can benifit greatly from doing FFT on GPU. VkFFT can be append FFT to the user command buffer (list of commands), which can be then followed by additional user commands, like scaling, correcting, etc.

AFAIK, virtualization software right now has no or very limited access to the GPU, so no extensive graphics can be done through it.

Big 1D FFTs also take a lot of memory by themselves (i.e. 2^28 takes 2GB just to store complex data). Multiple smaller batches can be used in ML applications for example for big kernel convolutions. All learning can actually be done without transferring data to CPU. In computational physics iterative processes or PDE integrators can do their algorithms independently of the CPU.

About using simple time per iteration as a benchmark. I used to have this type of benchmark before the last update (see: https://raw.githubusercontent.com/DTolm/VkFFT/f7c8c45717006c...). As you can see, it is not really that informative, as you can't really compare smaller times to big ones here. The layout I use now doesn't make any assumptions about algorithm yet still provides very informative scaling - just by looking at it it is possible to jusge wether techinques like register overutilization actually work. Another important thing is that it can clearly prove that the problem is bandwidth bound and compare at which size VkFFT/cuFFT swwitch from 1 to 2 and then to 3 stage FFT algorithm. It also allows to detect wether algorithm deviates from predicted result.

There are surely many different ways to get the job done. VkFFT.h file by itself desn't do any computations btw - it is more like a configurator that launches shaders (sth similar to kernels in CUDA). Having only one header also makes it easier to distribute the library as a code.

I just like the switches as in glsl(shaders) compiler can optimize and unroll them, if the key is provided as a constant. This can provide a non-negligible algorithm speed increase. So over the course of development I came to the point that it is not hard to follow the switches logic for me.

1k FFT size in single precision is 1024 x 2 x sizeof(float) = 8KB. If we don't think that it won't utilize full GPU (not even one compute unit) and assume that it scales similarly to big systems then: 1)165GB/s is an algorithmic bandwidth of benchmark, including consecutive FFT+iFFT. Both of them take one upload and one download from chip - total 4 memory transfers. The real bandwidth for this value will be 4*165=660GB/s. 2)one FFT is 2 transfers - upload and download. Total 16KB. 3)660GB/s / 16KB = 43M iterations per second. Similar to your number, but your number didn't account that benchmark has 4 uploads instead of 2.

These benchmarks don't include transfers to and from GPU, as those are done with PCI-E bandwidth (30GB/s) which is really slow compared to VRAM-chip bandwidth (>500GB/s). This is why it is important to have enough VRAM and avoid CPU communications as much as possible.

FFT is an extremely bandwidth limited problem, so if most time is taken by one upload by both algorithms, the overall time will be similar. More in-depth analysis of how VkFFT and cuFFT scales with memory clocks and bandwidth can be found here: https://www.reddit.com/r/nvidia/comments/jxlbjs/rtx_3090_ove...

I don't know exactly what cuFFT does differently, but I am fairly certain they use very similar memory layout and algorithms behind their code (judging by execution times only).

What should be the main take from this is that Vulkan allows for similar in performance low-level memory control, while being cross platform and open source. I don't think that SPIR-V is more expressive - bet Nvidia wouldn't allow this. But it doesn't prohibit it from still being good.

The library only includes vkFFT.h file (in C) and a set of shaders (C-like language compiled to SPIR-V). Vulkan_FFT.cpp is only an example that shows how VkFFT can be used. It also contains the benchmark in it, but it is not a part of the library.

Actually, it is still best to aim at zero transfers between GPU and CPU during the execution. The GPU is limited by VRAM-chip bandwidth which is much bigger than the PCI-E bandwidth. And it should not be affected by SAM.

Yes, this is indeed something I would like to add in the future. While adding different radix kernels support for small prime factors is not that hard, writing efficient scheduler is a much more challenging task (each sequence, even for power of 2 now is split differently targeting different architectures to optimize performance).

The Bluestein's algorithm typically used for arbitrary prime sizes requires both zero-padding and convolutions support which are already efficiently implemented, so it is also not completely out of reach.

It is a great open-source license for library projects. For example, Eigen uses it: https://eigen.tuxfamily.org/index.php?title=News:Relicensing...!

Hello! Since the last post VkFFT has experienced a number of huge improvements and optimizations. Namely:

-It now supports sequences up to 2^32 in all dimensions (algorithmically, in reality limited to allocatable memory size, switch to 64-bit addressing scheme is planned for future release)

-configurations optimized for bigger range of systems and vendors

-benchmarked Radeon VII and RTX 3080, shows that FFT is extremely bandwidth limited on modern GPUs

-VkFFT is able to match and outperform cuFFT on the whole tested range from 2^7 to 2^28 in single precision

-added double and half precision support and precision tests against FFTW on CPU

-improved native zeropadding - up to 3x performance boost

-switched license to MPL 2.0

Thanks for your attention! I am happy to answer any questions.

Hello, I am the creator of VkFFT library(https://github.com/DTolm/VkFFT). I was recently invited to be a speaker at the EUROfusion Webinar #5 about Vulkan Compute. I would like to share the recording of it with the community: https://www.youtube.com/watch?v=YD_QO5Ilz2U. I have discussed the following topics there:

-Compute and memory-bound problems. Importance of proper memory management and why it is important to have coalesced global memory accesses and avoid shared memory bank conflicts.

-VkFFT, Vulkan Spirit and memory layout optimizations implemented there

-There was a coding session in the end where I showed a simple out-of-place transposition routine in Vulkan. It was launched on Nvidia GTX 1660Ti, Intel UHD 610 and AMD Radeon Vega RX 10 to illustrate the differences in bandwidth and memory coalescing of the different architectures. Full code with comments can be found here: https://github.com/DTolm/VulkanComputeSamples-Transposition

Hope this can be interesting to people willing to try Vulkan for computations!

P.S. I have added double and half precision support (with precision verification) to VkFFT and a choice to perform FFTs using lookup tables. VkFFT now also has a command line interface and it is possible to build cuFFT benchmark and launch it right after VkFFT one.

If you happen to need any assistance in refining VkFFT for your use case, feel free to contact me.

Well, most likely I won't be able to help explaining the fluctuation easily then, as you have spent a lot of time on it already. It would be cool to try VkFFT in this usage scenario at some pont in the future though - it also can do 1D FFTs of grouped in matrix sequences.

I have some of these routines like Reduce and Scan in my other project https://github.com/DTolm/spirit. It also has implementations of linear algebra solvers like CG, VP, Runge-Kutta and some others. These routines have to be inlined in users shaders in some way to have a good performance. Releasing them as a standalone library will require some thinking due to the fact that some routines have multiple shader dispatches.

Small FFTs like 2048 only utilize one SM and the way they are given to the GPU may produce some fluctuations. It also depends on the way your code works. Synchronizations are also more impactful in this case. Do you launch a big grid that consists of multiple samples combined in a matrix or you launch each sample separately?

He is not wrong, convolutions between an image and a small kernel can be done faster by direct multiplication than by padding the kernel and performing FFT + iFFT. This is what tensor cores are aiming to do really fast. However, doing a convolution betwen an image and a kernel with the similar size is the general use case for the convolution theorem and is the thing that is currently implemented in VkFFT.

I use the averaged data of 1000 merged launches and then average the end result over a number of runs. Merging FFT calls is actually the way how I use VkFFT in Vulkan Spirit (with some other shaders between), so this benchmark is fairly close to the real life application use case. My benchmark most likely averages out multimodal distribution effects by design.

GPU is a very consistent device, so the purpose of such big sample sizes and multiple launches with averaging is to reduce all the deviations almost to zero. The error is <1% in this case and showing it on the plot will not really change it. The values, however, change when I update the code and improve it, so this is by no means the final way the benchmark will look like. I will think on how to adress this better in the future, but for now I think the best solution if you doubt the results is to launch VkFFT and see what it outputs for yourself.

The FFT and iFFT are performed consecutively up to 1000 times and then each run is done 5 more times. The total result is averaged both for VkFFT and cuFFT and stays roughly the same between launches. The minor performance gains (5-20%) are noticeable. If you have a better testing technique, I am open to the suggestions.

I have tested VkFFT on Intel UHD620 GPU and the performance scaled on the same rate as most benchmarks do. There are a couple of parameters that can be modified for different GPUs (like the amount of memory coalesced, which is 32bits on Nvidia GPUs after Pascal and is 64bits for Intel). I have no access to an AMD machine, otherwise I would have refined the lauch configuration parameters for it too. I have not tested other libraries than cuFFT yet.

I have used VkFFT to create GPU version of a magnetic simulation software Spirit (https://github.com/DTolm/spirit). Except for FFT it also has a lot of general linear algebra routines, like efficient GPU reduce/scan and system solvers, like CG, LBFGS, VP, Runge-Kutta and Depondt. This version of Spirit is faster than CUDA based software that has been out and updated for ~6 years due to the fact that I have full control over all the code I use. You might want to check the discussions on reddit for this project: https://www.reddit.com/r/MachineLearning/comments/ilcw2f/p_v... and https://www.reddit.com/r/programming/comments/il9sar/vulkan_...

Currently, I hit the limit of maximum workgroups amount for one submit dispatch (this is why y and z axis are lower than x one for now). It can be removed by adding multiple dispatches to the code, which I will do in one of the next updates. To go past 2^24 I need to polish the four stage FFT algorithm to allow for >2 data transfers, which I have implemented, but not yet tested. There will also be a single precision limit in this range, as the twiddle factors values will be close to 1e-8 which will be close to a machine error.

No, the 1D case will mostly save on the fact that it transfers 2x times less data from the vram to the chip. The up to 2x times increase in performance was mainly related to 2D and 3D cases, where only 1/4 or 1/8 of the data is nonzero. In 2D, when doing 1D FFTs over x-axis, we omit sequences after Ny/2 because we know they are full of 0 and thus their result will be 0. So we do 0.5Ny x-axis ffts and full Nx y-axis ffts. For a square system this will mean a drop from 2N to 1.5N sequences. In 3D the drop will be even bigger, from 3N^2 to (1/4+1/2+1)=1.75N^2 sequences (almost 2x).

That is almost the correct answer. To go even further, there are sequences that are completely full of zeros in the padded case of multidimensional FFTs and we can omit their FFTs entirely.

Hello, I am the author of VkFFT. When I made VkFFT I wanted license to be like this: your project doesn't have to be open-source, but please share your modifications to VkFFT. I think about switching it to MPL 2.0, is this one better for everybody?

This was indeed what I was thinking in the first place, when I made VkFFT - your project doesn't have to be open-source, but please share your modifications to VkFFT. I think about switching it to MPL 2.0, is this one better for everybody?