Bikeman
Posts: 65
Joined: Sun Nov 04, 2012 9:03 pm
Location: near Hannover, Germany

FFT libs

Wed May 15, 2013 12:02 pm

Dear all,

I know that some people here have been looking for efficient FFT libraries, and anyway for the records this might be intersting:

An FFT lib that has recently gained popularity in the Android world will now also compile on the Raspberry Pi: it is "FFTS : Fastest Fourier Transform from the South".

The git repo is here: https://github.com/anthonix/ffts
The author is Anthony Blake, this project is a spin-off from his PhD thesis (interesting read, btw) :

http://researchcommons.waikato.ac.nz/handle/10289/6417

Not much documentation yet (the author wants to have a full fledged web site for it up in a few weeks time).

NOTE: When compiling, it is important to configure for VFP, not NEON support , and you need to pass --with-float-abi=hard to configure as it otherwise defaults to the soft-float ABI (used by Android!) otherwise.

Other than this, FFTW ("Fastest Fourier Transform in the West" ) http://www.fftw.org/ works well, too. But FFTS claims to be faster than FFTW in many use cases, so it is worth to give FFTS a try, I guess.

Cheers
HB

User avatar
DaveDriesen
Posts: 113
Joined: Sun Mar 31, 2013 8:28 pm
Location: Top of the food chain
Contact: Website

Re: FFT libs

Thu May 16, 2013 2:45 pm

Thanks, that is interesting news indeed.

Have you implemented anything with it?

Dave Driesen
Linux dev and oldskool elite

Bikeman
Posts: 65
Joined: Sun Nov 04, 2012 9:03 pm
Location: near Hannover, Germany

Re: FFT libs

Thu May 16, 2013 3:49 pm

DaveDriesen wrote: Have you implemented anything with it?
Not yet, but soon :-). I'm working in an astrophysics context (as a software dev), we are running a distributed computing project mostly looking for pulsars, and FFT is usually the most timeconsuming part of it. We are using relatively long transforms, (say) 2^22 ... 2^24 , and I have yet to make tests that compare FFTS to FFTW. Stay tuned. Most people might have far shorter transforms in their applications, so even if our project won't see a benefit, others still might.

Cheers
HB

birdwes
Posts: 19
Joined: Wed Oct 10, 2012 11:59 pm

Re: FFT libs

Mon Nov 25, 2013 1:24 am

You might want to check out what I'm doing here:

http://www.basic4ppc.com/android/forum/ ... ost-204309

birdwes
Posts: 19
Joined: Wed Oct 10, 2012 11:59 pm

Re: FFT libs

Tue Nov 26, 2013 12:10 am

Getting about 100, 4096 point transforms per second on a 700MHz clock (including printf over ssh). I don't know how that compares? This code is limited to a sample window of 16384 though as it is a 16/32 fixed point int implementation though. 10ppm accuracy!

http://pulsar.webshaker.net/ccc/sample-07cef1a6 .

This will be freely available (BSD Style License) as a combined RasPi / B4A Android project for both platforms.

birdwes
Posts: 19
Joined: Wed Oct 10, 2012 11:59 pm

Re: FFT libs

Wed Nov 27, 2013 12:22 am

OK, I have a handle on benchmarks now.

http://pmeerw.dyndns.org/blog/2011/Sep

This fixed point int non-Neon version is nearly 80% as quick at 700Mhz on RasPi as the Beagle doing Neon at 900 MHz. The RasPi does not do Neon.

Real + Complex 10,000 x 256 FFT = 1.6 seconds (roughly) on ARMv6 RasPi (ARM assembler in GCC)

You'll get the source code soon instead of this:

http://pulsar.webshaker.net/ccc/sample-f91cc9a6

Which tells you how I've done it!

You have to remember that this is Platform specific speedup though!

birdwes
Posts: 19
Joined: Wed Oct 10, 2012 11:59 pm

Re: FFT libs

Fri Nov 29, 2013 1:19 am


birdwes
Posts: 19
Joined: Wed Oct 10, 2012 11:59 pm

Re: FFT libs

Fri Nov 29, 2013 2:15 am


fl4p
Posts: 1
Joined: Sat Nov 30, 2013 9:44 pm

Re: FFT libs

Sat Nov 30, 2013 10:43 pm

birdwes, I'm very interessting in your library, have been looking for an ARM-optimized FFT for some time. Do you have an est. release date for the low-level FFT functions?

I have struggled getting the CMSIS DSP Lib ( http://www.disca.upv.es/aperles/arm_cor ... /DSP/html/ ) working on the RPI, but the arm_cfft_f32 only outputs garbage (probably its because it's only for Cortex-m). Anyone got success with it?

birdwes
Posts: 19
Joined: Wed Oct 10, 2012 11:59 pm

Re: FFT libs

Thu Dec 12, 2013 1:00 am

Please email about this. I'm getting a Beagle Black too. I need to learn Neon for ARM as well..

dom
Raspberry Pi Engineer & Forum Moderator
Raspberry Pi Engineer & Forum Moderator
Posts: 5960
Joined: Wed Aug 17, 2011 7:41 pm
Location: Cambridge

Re: FFT libs

Thu Jan 30, 2014 1:35 pm


birdwes
Posts: 19
Joined: Wed Oct 10, 2012 11:59 pm

Re: FFT libs

Thu Feb 13, 2014 12:33 am

fl4p wrote:birdwes, I'm very interessting in your library, have been looking for an ARM-optimized FFT for some time. Do you have an est. release date for the low-level FFT functions?

I have struggled getting the CMSIS DSP Lib ( http://www.disca.upv.es/aperles/arm_cor ... /DSP/html/ ) working on the RPI, but the arm_cfft_f32 only outputs garbage (probably its because it's only for Cortex-m). Anyone got success with it?
If you can find my email on my address in this thread (http://sourceforge.net/p/raspbx/discuss ... 13/?page=1) I can send you a working pre-release for Pi only. Doesn't work with Android yet (as here: http://www.basic4ppc.com/android/forum/ ... 550/page-3 ) as I have a lot of work on at the moment. There will be a Neon BB Black version sometime soon too. RPi and BBB are great for simulating low end phones at assembler level before going to JNI.


ovadaflame
Posts: 42
Joined: Fri Feb 14, 2014 7:21 pm

Re: FFT libs

Mon Apr 07, 2014 7:30 pm

Having some trouble getting FFTS up and running on my pi! Here's what damage has been done so far:

./configure --enable-sse --enable-single --prefix=/usr/local --with-float-abi=hard

I have taken out all commands in the configure file that have to do w/ NEON.
automake 1.14 has been installed
the make command produces the following error:


cd . && automake-1.14 --foreign
/bin/bash: line4: automake-1.14: command not found
make: *** [Makefile.in] Error 1

Any suggestions would be greatly appreciated!

ovadaflame
Posts: 42
Joined: Fri Feb 14, 2014 7:21 pm

Re: FFT libs

Wed Apr 09, 2014 4:11 pm

Ok, I got it up and running, and now I can't find any documentation pertaining to calls or how FFTS wants the input data..

User avatar
jackokring
Posts: 818
Joined: Tue Jul 31, 2012 8:27 am
Location: London, UK
Contact: ICQ

Re: FFT libs

Wed Apr 09, 2014 4:14 pm

There is a videocore GPU FFT for the Pi. It was on the site news feed at one point.
Pi[NFA]=B256R0USB CL4SD8GB Raspbian Stock.
Pi[Work]=A+256 CL4SD8GB Raspbian Stock.
My favourite constant 1.65056745028

ovadaflame
Posts: 42
Joined: Fri Feb 14, 2014 7:21 pm

Re: FFT libs

Wed Apr 09, 2014 4:21 pm

Yes, I am working with FFTW, FFTS, and GPU_FFT. FFTW and GPU_FFT have enough info to run the programs, but it seems that I can't locate documentation pertaining to FFTS calls, options, and data input.

Return to “C/C++”