Multithreading with FFT-IFFT

[Siekmanski]

Hi rrr314159,

Thanks, Found it.  :t

rb_index_LP:
    cmp     ebx,eax
    jae      swap_skip      ; this was ja, must be jae

total swap count for FFT 1024 is now 496.

[rrr314159]

@siekmanski,

that's it, needed to skip when equal also. 496, right.

I never studied your algo, since I had to tackle FFT from the ground up (40 years since I studied it) just wrote my own very simple bit-reverser table. But I was glad u posted some pseudo-code. That's cheating (should get it from the code) but figured great, this ought to make it easy! But,

Code Select Expand

             bitreversalindextable[i-1]
             bitreversalindextable + 1 [j-1]

aren't there a couple assignment operators missing here?

But you know, for any one particular algo, it's an awful lot easier to figure it out myself.

- Read more of these bit-reversal techniques, it's not all that easy to figure them out. This statement makes me sound like an egotistical a*****e ... bad enough being one, u don't have to sound like one! :icon_rolleyes: My excuse, bit-reversal speed just isn't important here. But admittedly there are some cool tricks available ...

[Siekmanski]

It's not real code, i and j are both 1 from the start.

             bitreversalindextable[i-1] ; entry
             bitreversalindextable + 1 [j-1] ; next entry

Never understood the hassle about speeding up bitreversal routines.
It's faster to get it from memory then to calculate them in real time.

[rrr314159]

Never understood the hassle about speeding up bitreversal routines.

U probably don't expect an answer! But I do have an opinion. First, consider that people do 65536 FFT's, that's a pretty big LUT. (I don't know if bit-reversal is used anywhere but FFTs, assume not). More important are these two facts:

1) In 40 years, processor speed has increased by about 1000, while storage (RAM and disk) has increased 1,000,000! Storage has kept up with "Moore's Law", doubling every 2 years, but processor speed only about 4 years. So LUTs have become more and more practical. Not that long ago, even 2000 byte LUT (for 1024 FFT) was pretty big.

2) Computer Science (CS) is always a good 10 years behind the times. Academia is conservative. Doesn't matter with History or even Math, which are pretty static. But CS is almost always obsolete. It's no coincidence that the most successful coders (Bill Gates, etc) dropped out of school. And, note that most of these ref's we've seen are already a good ten years old (e.g. "Bit Twiddling Hacks", which is an entertaining read). So that ref reflects state-of-the-art considerably more than 20 years ago! Back then storage mattered.

If you work in industry you're always pretty up-to-date, easy to forget (or maybe u didn't know) how out of it academics are

[hutch--]

 

> If you work in industry you're always pretty up-to-date, easy to forget (or maybe u didn't know) how out of it academics are   :icon14:

[FORTRANS]

Hi,

(I don't know if bit-reversal is used anywhere but FFTs, assume not).

   Well, I thought I remembered that it was used to generate a
pseudo-random sequence for Monte Carlo programs.  Less
uniform than a uniform grid and more regular than a random
sequence.  And that it was used in an algorithm to create
something like a Bayer Matrix for ordered dithering.  If so,
Google search is being uncooperative.  I found some references
pertaining to pseudo-random sequences, but nothing nifty or
really coherent to a quick scan.  It may be a deprecated method?

   Time to run a test I guess.

Cheers,

Steve N.

[Gunther]

Hi Steve,

It may be a deprecated method?

no it isn't. This is a very proven technology with reliable dithering results.

Gunther

[FORTRANS]

Hi Gunther,

It may be a deprecated method?

no it isn't. This is a very proven technology with reliable dithering results.

   Thank you, that was what I thought.  I will try Google again with
differing terms later.  They seem to be declining in usefulness with
distracting search results and poor suggestions.

Regards,

Steve N.

[dedndave]

anyways.....
i was thinking you could look at drizz's 32-bit swap and adapt something similar using SSE for 1024 bits
that routine swaps the bits in EAX in about 10 clock cycles   

[rrr314159]

Turns out I may be interested in fast bit-reversing after all! Not just for one dword, but for the whole FFT swapping. Was playing around with FFT at 16 million points and my crude swapper gets awful slow at that level. Even 1 million points not good.  Maybe drizz has already produced best algo for one dword, but not the whole swapping job. But first I'm finishing the FFT for 1024 bit level - bit reverse algo is plenty fast enough down there

Would like to know more about other applications like dithering, how many bits would they do - 32? And how fast would it need to be? Didn't bother to google since u say it doesn't seem to be there. Maybe new thread about this topic would be sensible ...

BTW does anyone use FFT of million (1048576) points?

[Siekmanski]

Could be a nice challenge trying to get fast bit-reversal routines.
But for FFT you still have to do the data swapping. Calculating just one FFT than you can benefit of a fast bit-reversal.
I think, if you do multiple FFTs of the same size ( for example in an audio program ) then it's faster to use a precalculated bit-reversal index-swap table.
At this moment I'm busy to speed up my FFT routine, trying to line it up for better use of SIMD instructions. ( lost a few hairs already...  )

[rrr314159]

lost a few hairs already... 

- Fortunately bald is "in" these days

- I seem to be getting about 3.4 microseconds, 10,000 cycles, per 1024 FFT, with SSE and 4 threads ... b4 2 long I'll give up trying to improve that and post it (need to clean it up a lot also that'll take a while). Apparently does 16 million FFT in something like a minute but I haven't tested that or checked it much. Suppose it could do much larger FFTs, but doubt anybody needs such?

[FORTRANS]

Hi,

Would like to know more about other applications like dithering, how many bits would they do - 32?

   If I remember correctly (ha), bit-reversal does not scale well.
So six to twelve bits were used for pseudo-random sequences.

And how fast would it need to be? Didn't bother to google since u say it doesn't seem to be there. Maybe new thread about this topic would be sensible ...

   My Google skills seem to be sub par these days.  Used to get
reasonable answers fairly quickly.  Not so much now.

BTW does anyone use FFT of million (1048576) points?

   When I was using FFT for image processing, I know I did 256x256
and 512x512 images.  65,536 and 262,144 points respectively.
I may have done 1024x1024, but that would have been painfully
slow.  So probably not.  Done on a now dead computer, but I will
look at some backups just to refresh my own memory.

   I know people have used FFT to deconvolve larger images.  But
the deconvolution kernels tend to be smaller.  So they could be
processing smaller sub-images rather than the whole thing at
once.

Cheers,

Steve N.

[Gunther]

Hi Steve,

   Thank you, that was what I thought.  I will try Google again with
differing terms later.  They seem to be declining in usefulness with
distracting search results and poor suggestions.

that's the wretchedness with Google. I'm using other search engines for years (different reasons) with better search results.

Gunther

[xanatose]

Hi Steve,

   Thank you, that was what I thought.  I will try Google again with
differing terms later.  They seem to be declining in usefulness with
distracting search results and poor suggestions.

that's the wretchedness with Google. I'm using other search engines for years (different reasons) with better search results.

Gunther

To be fair. Google is an advertisement (and spying) business made to make money. If you are not the client, then you are the product. I suspect that any search engine without a subscription fee will eventually turn wretched.