GSOC 2010 Project - FFTW / NEON Optimizations

GoogleGroups
1

Dear group,

I'm interested in applying for the GSOC 2010 for the fftw / neon
optimization project and am in my final year of a 2-year msc program
(the end of my studies is officially sept 30, 2010).

This fftw optimization project is still a 'raw idea' and needs to be
'fleshed out', so I was hoping that a potential member on the list
could dialog with me about this topic.

I already have a beagleboard (rev B5), a fairly plethorous amount of
embedded / arm linux experience (including asm, oe, android, gentoo,
etc), and some experience with the gnuradio codebase (i rewrote
libusrp2 in c for my university, eliminating most of the extraneous
library dependencies).

Naturally, I also have been using the beagleboard for other projects
for some time.

I would be happy to submit my resume for the mentors to review. Also,
I would consider the following other topics if they are more likely to
be approved:

Utilize Open Embedded to build Android
DSP libraries for Android

Regards,

Christopher

2

I thought I should also respond and say that I'm fluent in english,
german, (and my french is reasonable as well).

3

How would you use OE to build Android and what would be your goal? I have some interest, but just getting it to build and run under OE sounds like an overly simple task. I can dream up some reasons to do this and additional tasks, but I want to hear your vision.

4

Hi Jason,

How would you use OE to build Android and what would be your goal? I have some interest, but just getting it to build and run under OE sounds like an overly simple task. I can dream up some reasons to do this and additional tasks, but I want to hear your vision.

I had to give some thought to what you were talking about before
replying, but you're very correct; its quite easy to use OE to simply
_build_ an Android image and add the TI proprietary binaries. That
would be too simple for a GSOC project.

Considering the Android build system, I honestly have very few gripes
with it. It's reasonably fast (considering the amount of code that it
compiles) and it has a high degree of consistence with a simple-to-use
Android.mk syntax and variable cleaning.

However, having 'ported' a few libraries over to the Android build
system myself, compiling / linking against bionic, I found that such
an endeavor usually requires just a few patches against the official
(external) project release, which is something that could easily be
pulled together into a git repository (on gitorious for example). A
good example of this is my psqldroid port (I haven't yet put this up
on gitorious, but you can find it on google code).

Where this gets interesting is in the repo internals. I haven't yet
gotten deeply into repo itself yet, but there is some indication that
a sort of 'overlay' concept is possible through the .repo/manifest.xml
file. For example, there is a <default> tag, which contains the
default revision and remote repository. But then it might be possible
to patch that manifest with additional <remote> tags and then specify
additional projects pulling from repositories other than the default
kernel.org (e.g. gitorious).

Leveraging OE as the patch-and-run-make system, and a sort of
directory of pre-ported libraries / patch files, this could
potentially aid the community tremendously by collecting several
options for common "external/" projects (and the patches required to
make them compile) in a single place.

So if, for example, several different platforms (not even necessarily
OMAP) want to make use of a certain library (e.g. postgresql), then
they could just specify something like

TARGET_OS:="android"
ANDROID_EXTRA="postgresql lame x264"

in the Bitbake local.conf file, and an OE module for Android could
automatically apply the required manfest.xml entries, apply any
necessary patches, and then build the Android image automatically
(alongside the Angstrom image). This would be quite useful for
community projects that use the same SoC - e.g. BeagleBoard, AI TB,
OpenPandora (... an Android gaming system?!).

Having the Android build system contained within OE would allow
maximum re-use of components without needing to 'shop around'.
Everything would be right there at the developer's fingertips in the
OE build system.

So implementing something like that would require a fair amount of
work in OE itself, possibly some in the repo source code, and then
getting 1 or 2 proof-of-concept builds working would be the final
step.

That's just an example of the potential I see ... did you have
something else in mind?

Cheers,

Chris

5

I don't know who proposed it (Phil Balister?), but it looks more
interesting to me than build scripts (sorry Jason :wink: if you have the
skills and interest, which you appear to.

Unfortunately I don't know much about fftw other than that I'm using
it in a project currently (nothing to do with beagleboard), and I've
read a bit of the documentation on how it works (which is quite
fascinating in itself).

Given that it is a widely used library and that it would be quite a
self-contained project I still think you should consider it if you're
still interested.

It might be worth finding out if anybody else is looking at NEON or
even just ARM optimisations for FFTW (i found this with a quick
search: http://uppermeadow.com/pipermail/mep-dev/2009-October/000292.html).
If FFTW is such that NEON isn't terribly difficult/or it's already
been done, the project could shift to using the DSP as well - given
that the CELL BE version already has a heterogeneous implementation,
the framework is perhaps already there for it and it could provider a
meatier challenge.

Michael

6

Take a look at the fftw source. There is a directory called simd,
which is a pretty good place to start inserting NEON code. Also, the
CELL BE code may give you a starting point for sending work to the
DSP.

I'd love to see this happen.

Philip

7

Hi Michael,

Unfortunately I don't know much about fftw other than that I'm using
it in a project currently (nothing to do with beagleboard), and I've
read a bit of the documentation on how it works (which is quite
fascinating in itself).

FFTW is (in particular) used by Matlab(R) (and GNU Octave) - which
makes it very highly used by a lot of people. Considering that
Mathworks(TM) also has no ARM port, Octave will become a very
attractive alternative for the next generation of ARM-powered netbooks
/ smartbooks. I actually have already been working on an Octave port
for Android as well.

Given that it is a widely used library and that it would be quite a
self-contained project I still think you should consider it if you're
still interested.

It is the main project I'm interested in.

Should I put together an application to GSOC then?

Cheers,

Chris

8

Hi Michael,

Unfortunately I don't know much about fftw other than that I'm using
it in a project currently (nothing to do with beagleboard), and I've
read a bit of the documentation on how it works (which is quite
fascinating in itself).

FFTW is (in particular) used by Matlab(R) (and GNU Octave) - which
makes it very highly used by a lot of people. Considering that
Mathworks(TM) also has no ARM port, Octave will become a very
attractive alternative for the next generation of ARM-powered netbooks
/ smartbooks. I actually have already been working on an Octave port
for Android as well.

GNU Radio uses it also, which is my primary interest.

Given that it is a widely used library and that it would be quite a
self-contained project I still think you should consider it if you're
still interested.

It is the main project I'm interested in.

Should I put together an application to GSOC then?

YES!

Philip

9

Hi Michael,

Unfortunately I don't know much about fftw other than that I'm using
it in a project currently (nothing to do with beagleboard), and I've
read a bit of the documentation on how it works (which is quite
fascinating in itself).

FFTW is (in particular) used by Matlab(R) (and GNU Octave) - which
makes it very highly used by a lot of people. Considering that
Mathworks(TM) also has no ARM port, Octave will become a very
attractive alternative for the next generation of ARM-powered netbooks
/ smartbooks. I actually have already been working on an Octave port
for Android as well.

Given that it is a widely used library and that it would be quite a
self-contained project I still think you should consider it if you're
still interested.

It is the main project I'm interested in.

Should I put together an application to GSOC then?

Yes!

10

Philip Balister <philip.balister@gmail.com> writes:

11

Good point - there were some neon enhancments for ffmpeg not too long ago.

12

I still think you should check if the FFmpeg FFT does what you need.

Good point - there were some neon enhancments for ffmpeg not too long ago.

It will be easier to add NEON to fftw, than modify all the software
that uses fftw to use ffmpeg. Also, I believe Mans told me ffmpeg only
handles the power of 2 sized fft's. fftw works out the best approach
for arbitrary sized fft's.

Philip

13

Philip Balister <philip.balister@gmail.com> writes:

I still think you should check if the FFmpeg FFT does what you need.

Good point - there were some neon enhancments for ffmpeg not too long ago.

It will be easier to add NEON to fftw, than modify all the software
that uses fftw to use ffmpeg. Also, I believe Mans told me ffmpeg only
handles the power of 2 sized fft's. fftw works out the best approach
for arbitrary sized fft's.

That's why I said you should check if powers of two are good enough.
If the FFmpeg FFT solves your problem, it should be faster than fftw.
It uses a better algorithm.

Converting gnuradio to ffmpeg fft is, if possible, probably less
effort than optimising fftw, and the only talk about fftw on this list
and #beagle has been about gnuradio.

Optimising fftw is of course also a nice thing to do, but it may not
be what _you_ would benefit most from.