FFT lib port for Epiphany

[theover]

Because of certain audio programs I'd want to run on the ARM/FPGA/Epiphany (Like Jconvolve and Jamin preferably using Jack), I was wondering if there is some form of 32 bit (preferably) Fast Fourier Transform library available or being prepared for the Parallella board?

I mean I could get the right versions of some bignum libs on my main I7/Fedora17/64 system, try to get the dekit to configure, and then compile, and try with the simulator if it is realistic to get FFTw3 type of computations running a the speed I prefer (can the simulator do this?), but maybe someone did that already, like with matrix computations?

Theo V.

[ysapir]

Theo,

What size of FFT do you need? When you mention 32-bit FFT, do you mean a fixed-point implementation?

In the past, we published a whitepaper and a demo code for freq. domain image filtering utilizing 2D FFT/IFFT. I have just recently migrated this demo to the ZedBoard platform. But, it was intended to demonstrate the operation of the Epiphany in a data-stream mode, where it is a block in something like an image enhancement pipe, w/o use of the external memory. Thus it is limited to 128x128 images (on E16). However, this can be a starting point for further development.

[theover]

[ysapir]

Theoretically, from 16-core 128-point 2D FFT, a 16-core Epiphany can handle a 2K FFT internally (no external memory required). However, the challenge would be to make it a parallel (or fragmented) FFT, to work on multiple cores. The demo 2D application uses a nice trick to eliminate this fragmentation, and each core calculates 8 single-thread 128-point 1D FFT's.

You are encouraged to make a 2K FFT based on that application, if you are familiar with the FFT theory. Note that one approach may be to implement the 2K FFT as a variation on 2D FFT, so the demo can be a starting point.

[notzed]

Well if absolute latency isn't an issue (although it often is), the parallelism could be achieved by just doing 16x stages concurrently, each calculating the next result. It'll still take 'longer'' to get the first result, but then you'll have 16 ready at the same time. Whether this is useful or desirable depends on the rest of the algorithm of course.

I'm interested in parallelising various algorithms on epiphany and fft is among the ones i'm interested in, although my previous experiments never got very far.

[theover]

I recall having looked into some of the literature as a student (the universities DSP teacher at the time was rather a mess, and didn't do anything relevant himself), and there are various considerations to think about when making an FFT implementation, like accuracy of the repeated butterfly, and the reordering being done right as in not to throw away required sub-computations. Of course reusing the results of the previous computations makes the computations complexity go from something like square of the size to size times log(size), which is possibly lost when going parallel without reusing results...

@Yaniv: It's just that I found it marvelous I could use my graphics card for in priciple "plug-ing" in the fftw3 library, which the Cuda makers claim to be available in the same form from their libs. I don't know how much I'd need it and didn't try out making "Jamin" with graphics card acceleration, even though some of the specs of my humble GT640 Kepler card are probably reason enough to use the power of it. It's a nice thing to built a powerful, working Linux system from parts, getting Fedora on it, and using the motherboard great 192/24 audio converters to get studio quality processing, but it's a big machine, and many in Open Source appear to want to play as much "divide and conquer" as say Microsoft.

The idea of using the low power Parallella for the same purpose of the whole 100W Linux machine (actually less because of the platinum plus fanless supply), AND having the FPGA connect to for instance custom converters, meters, mixer control etc, is appealing.

T.

[costa]

Hello,
i'm looking for a implementation of a generic and fast FFT algorithm on Parallela too. I gave a look to the FFTW webpage, there is a MPI version of that library, but i think there isn't a MPI version for Parallela, right? do you think the FFTW/MPI solution is the right approach to the problem? Are there any FFT open source libraries or source code for multi-core ARM?

Thanks!
Leo

[9600]

[ysapir]

Costa,

We already demonstrated in the past using MPI to cluster 8 ZedBards in a Beowolf configuration, and there's a blog post on that. I am not aware of a WFFT implementation for Parallella yet, but if you'd like to take the time porting the WFFT, then the MPI infrastructure is available (again, between multiple Parallella boards).

That said, I think that if you have only one board, you may want to look more into OpenMP for an Epiphany based WFFT, as MPI was originally designed for message passing between distributed memory machines.

[Gravis]