Musings of someone learning

[Prime95]

Try

http://processors.wiki.ti.com/index...._of_Real_Input
https://www.dsprelated.com/showarticle/97.php
http://www.engineeringproductivityto...T0001/PT10.HTM

or even this odd collection:

http://www.jjj.de/fft/fftpage.html

[airsquirrels]

Originally Posted by Prime95

Try

http://processors.wiki.ti.com/index...._of_Real_Input
https://www.dsprelated.com/showarticle/97.php
http://www.engineeringproductivityto...T0001/PT10.HTM

or even this odd collection:

http://www.jjj.de/fft/fftpage.html

Thanks! Reading and gaining understanding is great, coming to know what you don't know you don't know and finding where to learn it is the challenge of the self-taught.

[airsquirrels]

Good work is being done! I now have a full understanding of the whole process from a math stand point and am in the process of benchmarking various implementation trade offs for doing LL on the GPU vs those used on the CPU. The biggest unintuitive trade off not utilized in current GPU LL code is the understanding of just how slow (latency, not bandwidth) memory access is on a GPU vs a CPU. It is often 2-40x faster to compute twiddle factors, weight signal values, etc. on the fly vs. reading from precomputed tables. Additionally, separating the squaring, normalizing, and carry kernels means writing large amounts of data out to memory just to load it back up, perform 3 multiplications and some adds, write it all out again, and then load it all up again. On an architecture without large caches this is sucking up quite a bit of performance. Especially when all the weight signals and precomputed factors are also coming in from memory to pollute the cache.

The one area where I am struggling with creating parallel code is the variable word carry/adder. I'm currently shuttling off to the CPU and doing that sequentially so I can work on other areas while still maintaining correct residues.

Is the parallel prefix research route the one I should be taking? I see that applying for most of the carries, however I'm not sure how to adapt it to the cyclical nature of the carries with the IBDWT. gpuLucas seems to just make assumptions about the maximum length of a carry chain and limit the number of passes based on that. It seems there may be circumstances with lots of 1 bits where that could fall down. Does mLucas or prime95 effectively parallel the carry work with multiple threads per worker?

[Prime95]

Originally Posted by airsquirrels

gpuLucas seems to just make assumptions about the maximum length of a carry chain and limit the number of passes based on that. It seems there may be circumstances with lots of 1 bits where that could fall down. Does mLucas or prime95 effectively parallel the carry work with multiple threads per worker?

Perfect carry code is not required. Say you get a 53-bit result and are storing 20-bits per word. You'll have a 33-bit carry into the next word, a 13-bit carry into the word after that, and -1,0,+1 into the third word. Do not worry about whether +/-1 could cause another carry.

As far as I know, mlucas, prime95, and cudaLucas all do parallel carry work with multiple threads.

[airsquirrels]

Originally Posted by Prime95

Perfect carry code is not required. Say you get a 53-bit result and are storing 20-bits per word. You'll have a 33-bit carry into the next word, a 13-bit carry into the word after that, and -1,0,+1 into the third word. Do not worry about whether +/-1 could cause another carry.

As far as I know, mlucas, prime95, and cudaLucas all do parallel carry work with multiple threads.

Does the potential extra carry just get absorbed into the math, and we have enough precision to restore a value even if the word size is 1 bit longer than it should have been?

Take the small example with word sizes {10,9,9,9}

After squaring, IFFT, inverse weighting, and rounding say we are left with:

787356, 938236, 393292, and 837234.

Base -> Carry : Carry1 -> Carry 2
924 -> 768 : 256 -> 1
253 -> 1832 : 296 -> 3
76 -> 768 : 256 -> 1
114 -> 1635 : 99 -> 3

adding the first round carry results in parallel of carry gives us

924 + 99 + 1 = 1024 -> 1 bit carry
252 + 256 + 3 = 511 -> 0
76 + 296 + 1 = 373 -> 0
114 + 256 + 3 = 373 -> 0

Are you saying we can ignore the 1 bit carry and leave 1024 as the first word for the next round?

If we can't, the next round looks like

0 -> 0
512 -> 1
373 -> 0
373 -> 0

Which again needs a another round to get our words back to size of
0 -> 0
0 -> 0
374 -> 0
373 -> 0

The above represents "perfect carry code" - Which of the above steps is unnecessary? Note that I am using unbalanced representations for simplicity, but I can contrive similar values for balanced representations.

[GP2]

Fascinating stuff, though I'm only vaguely following along.

GPUs will surely see a lot more technological advancement than Intel CPUs in the coming years, since they're key to things like deep learning which is rapidly advancing now. It seems almost inevitable that the GPU-based programs will supersede mprime at some point, though probably not for some years yet.

Just a request, this thread should probably be renamed to something less vague, for the sake of posterity, since the information being revealed here has lasting value.

[Prime95]

Originally Posted by airsquirrels

The above represents "perfect carry code" - Which of the above steps is unnecessary?

All of them :)

You can leave the 6 digit numbers as is and do another FFT multiply. Of course, now you'll have 12-digit numbers to deal with. The thing to understand about carry propagation is that it does not change the math -- each representation is equally valid. The reason we do carry propagation is to keep the numbers a manageable size in order to reduce round off error. As far as round off error is concerned it makes little difference if each FFT word is between 0 and 511 vs. 0 and 512.

[airsquirrels]

Originally Posted by Prime95

All of them :)

You can leave the 6 digit numbers as is and do another FFT multiply. Of course, now you'll have 12-digit numbers to deal with. The thing to understand about carry propagation is that it does not change the math -- each representation is equally valid. The reason we do carry propagation is to keep the numbers a manageable size in order to reduce round off error. As far as round off error is concerned it makes little difference if each FFT word is between 0 and 511 vs. 0 and 512.

That means I can make my carry code significantly faster than I was expecting.

Back to the workshop with me...

[airsquirrels]

Originally Posted by airsquirrels

That means I can make my carry code significantly faster than I was expecting.

Back to the workshop with me...

For a quick little update, turns out with enough wavefronts all of that memory latency for accessing precomputed buffers nearly disappears, so my in-line computation gains did not scale up. Storing all our twiddle dees and twiddle dums as precomputed constant arrays compiled in let's the compiler optimize everything for strides, access, etc.

On the positive side my implementation of LL in OpenCL currently validates all the small mersenne primes, as well as 74207281. Sadly its current manifestation clocks in at ~4ms/iteration at 4096k on a Fury X, just slightly above clLucas. Unsurprisingly msft did a lot of good successful optimizing already.

I'm investigating more math tricks now. I'm wondering whether it is critical for each word in the FFT to be in order. I've also thought about whether you could do some hybrid approach, using a larger Single Precision FFT on the input side and possibly doing some fancy match to switch to double precision only around the squaring and reconstruction.

[kriesel]

Originally Posted by airsquirrels

For a quick little update, turns out with enough wavefronts all of that memory latency for accessing precomputed buffers nearly disappears, so my in-line computation gains did not scale up. Storing all our twiddle dees and twiddle dums as precomputed constant arrays compiled in let's the compiler optimize everything for strides, access, etc.

On the positive side my implementation of LL in OpenCL currently validates all the small mersenne primes, as well as 74207281. Sadly its current manifestation clocks in at ~4ms/iteration at 4096k on a Fury X, just slightly above clLucas. Unsurprisingly msft did a lot of good successful optimizing already.

I'm investigating more math tricks now. I'm wondering whether it is critical for each word in the FFT to be in order. I've also thought about whether you could do some hybrid approach, using a larger Single Precision FFT on the input side and possibly doing some fancy match to switch to double precision only around the squaring and reconstruction.

Very interesting thread. Is there anything further to report?