Slashdot Mirror
High performance FFT on GPUs
A reader writes: "The UNC GAMMA group has recently released a high performance FFT library which can handle large 1-D FFTs. According to their webpage, the FFT library is able to achieve 4x higher computational performance on a $500 NVIDIA 7900 GPU than optimized Intel Math Kernel FFT routines running on high-end Intel and AMD CPUs costing $1500-$2000. The library is supported for both Linux and Windows platforms and is tested to work on many programmable GPUs. There is also a link to download the library freely for non-commerical use."
Why use a GPU for Final Fantasy Tactics? Couldn't you just use the GBA?
Note to mods: I'm probably being sarcastic.
if you're only considering 32-bit floating point numbers and don't need full IEEE-754 compliance.
Fast Fourier Transform
""The UNC GAMMA group has recently released a high performance FFT library which can handle large 1-D FFTs. According to their webpage, the FFT library is able to achieve 4x higher computational performance on a $500 NVIDIA 7900 GPU than optimized Intel Math Kernel FFT routines running on high-end Intel and AMD CPUs costing $1500-$2000. "
GPUs are nice, but there's the little matter of getting data and results on and off the chip.
Well, seeing as how the V.P. is such a V.I.P., shouldn't we keep the P.C. on the Q.T.? 'Cause if it leaks to the V.C. he could end up M.I.A., and then we'd all be put out in K.P.
While interesting, I need IEEE 64 bit double precision for my scientific applications. Are there any 64-bit floating point GPU's out there?
FFT; Fast Fourier Transform - a specific algorithm, but used to indicate any algorithm attempting to determine the power versus frequency graph for a signal Dag-nadit
I have mod points and I am not afraid to use them.
FFT:
Some calculation which can be heavily optimized to simple but fast processing. Hence a [relatively] cheap part that does a few simple tasks very fast can out perform a more expensive part that can do a vastly greater range of tasks with more efficiency across that general range but less in a specific area when performing that optimized calculation.
By capitalizing on this incredibly basic rule of computer science (the an optimized simple thing going fast is faster than a more powerful general thing that is only being used for one of its many potentials), attention grabbing headlines can be garnered.
Isn't that what SETI@home uses for the bulk of its signal analysis? Would be kind of neat to leverage the millions of idle GPU's out there.
If you don't know where you are going, you will wind up somewhere else.
I have an uncle who's a professor who's been using GPUs for scientific computation for years. Apparently he has systems with four GPUs running simulations.
One more reason to buy an overpriced video card instead of an overpriced CPU?
I don't know if it's exactly newsworthy, but it's kind of cute (and interesting) that the amount of specialisation that's going on in graphics cards leads to situations where one can persuade the graphics card to do one's (not graphics-related) work faster than one would be using the general purpose CPU for the same task. It's more amusement than anything else (although for those who want to do the computation, it's also useful).
For every problem, there is at least one solution that is simple, neat, and wrong.
I sense a little bias here; the fastest Intel and AMD processors are actually $1,000.
There's a somewhat non-obvious mathematical result that any continuous periodic function can be decomposed as the sum of a series of sine functions of different frequencies. This series of sine waves is referred to as the fourier series of the function. The FFT (fast fourier transform) is an efficient numeric algorithm to derive the coefficients of the fourier series for any function.
...
One useful way to think of the FFT is as transform of signal data from the time domain (raw samples) to the frequency domain (the constituent sine waves). This is useful for all sorts of purposes such as being the first step in speech recognition, the basis of JPEG/MPEG compression,
This is probably making a lot of developers, myself included, very very happy people. FFT's are where the proverbial magic happens for a lot of signals and systems analysis, as well as for the multiplication of very large integers. So anyone involved in gaming that includes digital signal processing (voice chat in UT, karaoke-karaoke-revolution type games, analog user input, etc.) is going to be happy, and anyone who's involved in multiplying huge integers (crypto anyone?) may very well have wet themselves.
If this is true, to be able to make the same computations in a fourth of the time is a pretty nice thing, and using a little more of a GPU is likely to be acceptable in a decent number of applications.
"My heart is in the work." - Andrew Carnegie
Thirty years later, a $500 GPU, weighing less than 1 pound, can produce 6 gigaflops. People complain about its power and cooling needs, but they are rather below 200 kW! We sometimes forget just how amazing the developments in computing have been over the last three decades.
an FFT is a transform that turns a signal (like an audio file) into its frequency components (like a spectrograph). It's used for MP3 compression, sound EQs, jpeg compression, mpeg4 compression, and a number of other things (I use FFTW for tuning my guitar).
FFTW is the 'Fastest Fourier Transform in the West', a cute name for the work of a number of graduate students who use several techniques to turn the FFT from 'Numerical Recipes in C' into a freaking speed daemon.
GPUFFTW is much the same thing, but ported to your video card's GPU - which is generally more optimized for doing the 'apply a floating point matrix to an array' thing - thus speedin the FFTW up even more while relieving the main processor from doing the work.
If you don't have a high-powered video card, this means nothing for you. If you do, it means the above operations (compression, spectrum analysis, etc) can be done faster and without eating up processes.
110100 1101000 1101000 1100110 0 1101111 1101000 1100011 1
AGP was not very useful for bidirectional data flow, but PCIe is. GPU's are pretty sophisticated these days, so they've got the logic to handle moving stuff in and out of it's memory and over the bus to the CPU and the rest of the system.
Or in the form of a concrete example ... The little spectrum analysers in iTunes are a good example of taking some time domain data, analysing it, and displaying the low through high frequencies.
As an example of how far we've come, I implemented the Cooley-Tukey FFT in assembler on an Amiga, and it was just barely out of real-time. You had to capture some audio data, then wait while it was analysed. Nowadays, you can write the same thing in Objective-C on a G4, using the standard audio capture library, and have the FFT's computed between redraw events.
-- "It's not stalking if you're married!" My Wife.
The limit is the floating-point precision of the GPU.
Most GPU can do max up to 32-bit floating point operations (depending on the brand and the model), where as most scientific applications use 64-bit and higher (the old FP unit could do 80bit FP math, SSE registers in recent processors can do 128-bits FP math).
So some user will be happy, like for sound processing (GPU have already been used to process reverberation to create realistic sound environnement - too lazy to do the search for the slashdot reference)
But other application (cryptography maybe) will probably need more FP precision.
Not to mention that most scientific applications run mostly under *nix like Linux or BSD, for which GFX driver support isn't always incredible, specially for recent models, (website mentions performance hit).
(And also remember that soon Vista will have an interface that'll completly clog the GPU and leave less free cycles to do general purpose calculation).
"Sufficiently advanced satire is indistinguishable from reality." - [Tips: 1DrYakQDKCQ6y52z6QbnkxHXAocMZJE61o ]
FFT is a data compression and encryption standard used by a wide variety of extraterrestrial civilizations. Seti@home spends most of its time running FFT code to look for signals. If we managed to communicate with any of these aliens we could ask them what it stands for.
Doesn't it make you feel good to know that our freedoms are protected by politicans, lawyers and journalists.
on this page here they almost compare to a program called libgpufft (which is an open source BSD version of the same library here ) I wonder how they do compared to the BSD licensed version---
The interesting question will be :
Is the 32-bit precision enough for SETI@Home application ?
Or does the project needs the higher precisions (64bit to 128bit) that can (for now) only be provided by the CPU ?
IMHO, maybe this could be useful. They're trying to find which chunk contains candidate data. If there's some fast low-precision algorithm that can quickly mark chunks as interesting / recheck with higher precision / un-interesting, it'll be helpful to quickly tell appart interseting chunk, even if data need to be post-processed later at higher precision.
"Sufficiently advanced satire is indistinguishable from reality." - [Tips: 1DrYakQDKCQ6y52z6QbnkxHXAocMZJE61o ]
The Video RAM will determine the maximum array length that can be sorted on the GPU. A rough guideline for performing FFT on 32-bit floats is: Maximum array length in millions = Video RAM in MB / 32
Max array length equals video RAM in megabytes divided by 32... bits? Correct me if i'm dumb but shouldn't it rather be "Video RAM in MB / 4"?
You just got troll'd!
Graphics Processing Units have always been better for FFTs and signal processing than general CPUs. I've read a journal article where machine vision was implemented on a GeForce 5200 at a 3x speedup over an AMD Athlon 3200+. The reason? This is what a GPU is made for; the small dedicated instruction set makes a GPU much more adept at signal processing than the 686's have ever been.
Karma: Good, or bust!
Apparently nobody knows what an FFT is. Here's the best description I can give without descending into math too much.
The Fast Fourier Transform is an algorithm to turn a set of data (as amplitude vs. time) into a set of waves (as amplitude vs. frequency). Say that I have a recording of a piano playing an A at 440 Hz. If I plot the actual data that the sound card records, it'll come out something like this picture. There's a large fading-out, then the 440 Hz wave, then a couple of overtones at multiples of 440 Hz. The Fourier series will have a strong spike at 440 Hz, then smaller spikes at higher frequencies: something like this plot. (Of course, that's not at 440, but you get the idea.)
The reason we like Fourier transforms is that once you have that second plot, it's extremely easy to tell what the frequency of the wave is, for example - just look for the biggest spike. It's a much more efficient way to store musical data, and it allows for, e.g., pitch transformations (compute the FFT, add your pitch change to the result, and compute the inverse FFT which uses almost the same formula). It's good for data compression because it can tell us which frequencies are important and which are imperceptible - and it's much smaller to say "Play 440 Hz, plus half an 880 Hz, plus..." than to specify each height at each sampling interval.
The FFT is a very mathematics-heavy algorithm, which makes it well suited for a GPU (a math-oriented device, because it performs a lot of vector and floating-point calculations for graphics rendering) as opposed to a general-purpose CPU (which is more suited for data transfer and processing, memory access, logic structures, integer calculations, etc.) We're starting to see a lot of use of the GPU as the modern equivalent of the old math coprocessor.
If you're looking for more information, Wikipedia's FFT article is a good technical description of the algorithm itself. This article has some good diagrams and examples, but his explanation is a little non-traditional.
Awesome, this is really good news for audio people.
I want to see how I can take advantage of this... I hope the license isn't too restrictive.
It might be a good example of how to use the GPU for general purpose (vector-based) computation, something I've been wanting to explore.
Just curious, how does the use of the GPU for this kind of thing affect the graphics display?
Are you unable to draw on the screen while it's running, or something?
Crypto = Number theory = integer math.
No need for floating point.
Finally I have a good excuse to give the IT department why I need to upgrade my video card. I need to do FFTs faster (it has nothing at all to do with Doom3).
Support Right To Repair Legislation.
not so custom really if you go with the right integrator.
SRC computers puts out FPGA based systems that has a nice
32bit floating point fft library already in their development
environment. Most customers using the fft are for radar image
processing where the best PC solution is 50 times slower
then the fpga based solution. Think UAVs with smart
tracking off their radar.
http://www.srccomputers.com/
If I could walk that way I wouldnt need cologne.
The one thing that I haven't seen mentioned is that the benchmarks only show "compute timings" and not actual setup and retreval times. If the benchmarks showed the amount of time to get the data to the GPU and especially the time to get the result back to a place where a program could actually use it then it would be blown out of the water by the CPU. Future cards/drivers could speed up the process of retrieving the data, but for now there will always be lame benchmarks like this that are unfairly biased toward the GPU and only tell half the story. I mean what's the point of doing an FFT so quickly if it takes forever to actually be able to get to the data.
Note that you can only use the 2xx Opterons in 1 or 2 CPU (2 or 4 core) motherboards. If you want to have 4 CPUs with 8 cores you need to use the 8 series Opterons. The Opteron 880 dual core currently starts at over USD 1,600.00 each, which makes your configuration start at about 7,500 just for the MB and CPUs. Then add the registered RAM, server case, big juicy power supply, drives, video, monitor, a UPS to protect all of that... It sounds sexy but realistically its going to be close to $10K if you build it yourself.
And as you tread the halls of sanity, You feel so glad to be, Unable to go beyond. I have a message, From another time..
Right then. So how long before they just include some weak general-purpose instructions in the GPU, add SATA and ethernet to the cards, and call it a budget PC?
Kid-proof tablet..
For both MP3, JPEG, and MPEG4 the transformation used is not a Fourier transform (not even TDFT/FFT), but DCT/IDCT ([inverse]discrete cosine transform). The reason for using DCT instead of the FFT (equivalent to the time Discrete Fourier Transform) is because the DCT is computationally cheaper than the FFT (about one half, in the fundamentals is really a mutilated DFT/FFT), and it provides enough information for the band discarding approaches used in lossy data compression.
The sizes of transforms they are using for comparison here are of lengths of the order of 1 million points. This is huge for an FFT, and truncation error will definitely come into play here using only 32-bit precision. It all depends on what you are doing whether this will be adequate or not. Also, it's not at all clear what they did on the other platforms. There are some tricks to doing very long sequences; essentially using a 2D transform to perform a long 1D transform. It's not trivial, and requires some extra work, but generally a lot more efficient than taking a 1D transform and shoving a 4 million element transform into it. The inner loops of a 1D transform will eventually trash the cache for such a large transform, so using a blocked 2D transform avoids this, with some overhead of course. It's hard to tell what they are doing from the performance curves, since they report seconds, and it needs to be scaled by n log n to really see what's going on. It's cool they tried this, though. I was looking at using a GPU to do FFTs and linear algebra kernels a couple of years ago, but decided not to go there as I didn't think it would pay off; mostly because of the 32-bit precision.
Knowing how to hook up a composite video input is irrelevant. The civilised world uses SCART. You can't screw up hooking up SCART.
And just you wait, France will develop a European alternative to that Fourier nonsense as well!
USE HOT GRITS WITH STATUE OF NATALIE PORTMAN (NAKED AND PETRIFIED)
And just you wait, France will develop a European alternative to that Fourier nonsense as well!
Read ... And notice the country....
Mod the guy up.. He might be a troll, but he is funny :-D
Ahhh...the great dumpster continuum. Many a free computer will be found there. -- sowth (748135)
I'm wondering whether or not the DSP latency of these libraries is sufficient to use with real-time audio processing...if folks were to write RTAS/AU/VST plugins using the library, how they would compare to other hardware-assisted DSP solutions such as the PowerCore and Pro Tools farm cards. Then again, if you have to spend $500 on a card to get this goodness, it's hardly a bargain (albeit cheaper than the above products...)
Sorry, the FFT of a time-domain signal does **NOT** indicate how the power (or energy) of the signal is distributed.
For the latter, you need a PSD (power spectral density) plot, which is obtained by finding the square of the magnitude of the freq-domain FFT (complex) outputs.
And the term "FFT" usually describes a specific class of algorithms that finds a Discrete Fourier Transform of a signal in much less than O(N^2) time, where N is the number of elements/samples considered.
However, the FFT is also useful to perform fast polynomial multiplication (and even fast multiplication of very very very long numbers). This application has nothing to do with power or frequencies in a signal.
djbfft apparently had an edge at some point, but now has not been updated for more than 5 years. meanwhile FFTW has incremented the major version number to 3, undergone a complete rewrite, added simd, multiprocessor, 64bit and a slew of other things (its obviously not a stagnant project). not to mention its the basis of the 'fft' function in matlab and thereby probably the most used fft implementation in the world. assuming their benchmarks (which now include accuracy as well as speed) are valid, Intel Performance Suite is probably their closest competitor.
In floating-point arithmetic, the algorithm was proved in 1966 to have an upper bound for the error that grows only as O(log N), and the mean (rms) error grows only as O(log N). (See this page for more info.) (Errors in fixed-point arithmetic are worse, going as N.)
Even in single precision, the errors for their FFT sizes are probably quite reasonable, assuming they haven't done something silly like use an unstable trigonometric recurrence.
If a thing is not diminished by being shared, it is not rightly owned if it is only owned & not shared. S. Augustine
That should be O(sqrt(log N)) for the rms error and O(sqrt(N)) for fixed point. (My sqrt symbols didn't post properly somehow)
If a thing is not diminished by being shared, it is not rightly owned if it is only owned & not shared. S. Augustine
You're right, they give them no credit. From TFA:
We are not porting FFTW to GPUs and our project is not related to FFTW. FFTW is a more general library designed mainly for CPUs. GPUFFTW uses some cache optimizations to obtain maximum memory performance on GPUs.
What is newsworthy is that this is a shameless attempt to secularize mathematics. It's right in the name -- Fast Fourier Transformation. That's idolatry. What can a man know about signals that God hasn't already made clear in the Word? Come to our website, and you can learn all about Intelligent Factoring, which is on much sounder mathematical grounds because it develops entirely from biblical principles.