1

I'm attempting to run the halide FFT implementation found here for benchmarking against FTTW. I'm able to run the implementation as is, but I've encountered some issues when digging a little deeper. The routine fails with errors for different values of H and W (the height and width of the random input image). For example, I get the following error with H=W=5:

Error at ./fft.cpp:603: Cannot vectorize dimension n0 of function v_S1_R5$6 because the function is scheduled inline. Aborted (core dumped)

I've been attempting to test on small image sizes (i.e. 5x5) to compare the results of the algorithms, but I can't get the algorithm to complete for any values less than 16, which even at that point makes checking the values a long task. The FFT also fails for values greater than 32, seemingly not working for all non-powers of 2.

Has anyone run into this issue before? Are there any other implementations of FFT in halide that work for different sized images?

For reference, I'm running the code on RHEL7 using gcc 4.8.3.

1 Answer 1

2

I think there are a few issues going on. First, there looks to be a bug for very small FFTs that only use one pass. I think that's what you hit in your first case.

The second issue is that W and H need to be a multiple of the vector size of your target, not necessarily that W and H need to be a power of 2. For example, W = 48, H = 32 seems to work for me. There's a further complication that for real FFTs, one dimension gets internally cut in half (this is how efficient real FFTs are implemented), so if you are on an AVX machine, that dimension must be a multiple of 16 (2x the vector width of 8 floats).

If you want to run on really small FFTs, you could remove the vectorize scheduling directives, then it should work, at least for learning purposes.

However, I would point out that running 5x5 won't be very interesting, because it will be done in just one radix 5 pass, i.e. just a plain old DFT (this also appears to be broken, as you've found). 4x4 (factored into 2 radix 2 passes) will be the smallest interesting FFT. When debugging it, I often used 8x8 FFTs (radix 4, radix 2).

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.