FFT lib port for Epiphany

Forum for anything not suitable for the other forums.

FFT lib port for Epiphany

Postby theover » Wed May 08, 2013 4:39 pm

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.
theover
 
Posts: 181
Joined: Mon Dec 17, 2012 4:50 pm

Re: FFT lib port for Epiphany

Postby ysapir » Wed May 08, 2013 7:12 pm

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.
User avatar
ysapir
 
Posts: 393
Joined: Tue Dec 11, 2012 7:05 pm

Re: FFT lib port for Epiphany

Postby theover » Thu May 09, 2013 10:43 am

ysapir wrote: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.....


Hi Yaniv,

I come from (also) a computer graphics background, where I suppose I'd be interested in looking at 2D transforms, but in this case I was thinking primarily about being able to run "Jamin" a (predominantly Linux) FFT based audio equalizer/mastering effect.

I don't know by heart what the length of the transform is (maybe 2000?), except that it is based on the more or less known FFT-w3 library. I have a long audio chain of Ldspa/Jack processes, where this effect plays the essential role of detecting complicated FFT-based audio components from good recordings. I think it has considerable overlap, and I can run it on a I7-950 in stereo at 192,000 Hz audio rate, but I'd have to look into the exact specs.

Theo.
theover
 
Posts: 181
Joined: Mon Dec 17, 2012 4:50 pm

Re: FFT lib port for Epiphany

Postby ysapir » Thu May 09, 2013 2:30 pm

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.
User avatar
ysapir
 
Posts: 393
Joined: Tue Dec 11, 2012 7:05 pm

Re: FFT lib port for Epiphany

Postby notzed » Fri May 10, 2013 9:36 am

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.
notzed
 
Posts: 331
Joined: Mon Dec 17, 2012 12:28 am
Location: Australia

Re: FFT lib port for Epiphany

Postby theover » Fri May 10, 2013 12:18 pm

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.
theover
 
Posts: 181
Joined: Mon Dec 17, 2012 4:50 pm

Re: FFT lib port for Epiphany

Postby costa » Mon Jun 24, 2013 10:20 am

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
costa
 
Posts: 6
Joined: Mon Dec 17, 2012 3:23 am

Re: FFT lib port for Epiphany

Postby 9600 » Mon Jun 24, 2013 11:12 am

costa wrote: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?


simsciloki recently started work on MPI for Parallella, building on dar's earlier proof-of-concept. However, I'm guessing it may be some time before there is something available which is suitable for use in other projects.

Cheers,

Andrew
Andrew Back (a.k.a. 9600 / carrierdetect)
User avatar
9600
 
Posts: 997
Joined: Mon Dec 17, 2012 3:25 am

Re: FFT lib port for Epiphany

Postby ysapir » Mon Jun 24, 2013 4:14 pm

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.
User avatar
ysapir
 
Posts: 393
Joined: Tue Dec 11, 2012 7:05 pm

Re: FFT lib port for Epiphany

Postby Gravis » Sun Aug 11, 2013 9:35 am

i stumbled onto this thread and did some searching that may help someone. the searches themselves are included because there are other results but these are the best results i found.

google search for: fft manycore algorithm 2d
results:

google search for: Large FFT on the Cell Broadband Engine
result:
User avatar
Gravis
 
Posts: 445
Joined: Mon Dec 17, 2012 3:27 am
Location: East coast USA.


Return to General Discussion

Who is online

Users browsing this forum: No registered users and 18 guests

cron