mersenneforum.org mfakto: an OpenCL program for Mersenne prefactoring
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

2011-06-23, 17:34   #45
Bdot

Nov 2010
Germany

3×199 Posts

Quote:
 Originally Posted by ldesnogu Warning: I don't know anything about OpenCL... Why do you use ||, && et ?: at all? Doesn't OpenCL say a comparison result is either 0 or 1?
For scalar data types that is true. I could have saved a conditional load, but I guess the compiler will optimize that out anyway.

I already have in my mind to use the same code for a vector of data (just replace all uint by uint4, for instance), and then the result of a comparison is 0 or -1 (all bits set).

What I was really hoping for is something that propagates the carry with a little less logic, as that will really slow down additions and subtractions ...

 2011-06-23, 22:15 #46 Ken_g6     Jan 2005 Caught in a sieve 2×197 Posts Would the "ulong" data type (a 64-bit unsigned integer) help?
 2011-06-24, 00:18 #47 bsquared     "Ben" Feb 2007 2·3·541 Posts If you cast the arguments to uint64 then the borrow can be computed by shifting... tmp = (uint64)a - (uint64)b; sub = (uint32)tmp; borrow = tmp >> 63;
2011-06-24, 08:41   #48
ldesnogu

Jan 2008
France

17×31 Posts

Quote:
 Originally Posted by Bdot What I was really hoping for is something that propagates the carry with a little less logic, as that will really slow down additions and subtractions ...
Two other random ideas (again sorry if it's not applicable...):

- do as many computations as you can without taking care of carries and do a specific pass for handling them; of course that could lead to a big slowdown if you have to reload values and memory is the limiting factor

- another way to compute carries is bit arithmetic; let's say you want the carry from a - b
Code:
res = a - b;
carry = ((b & ~a) | (res & ~a) | (b & res)) >> (bitsize-1);
where bitsize is the number of bits of a, b and res. Again that could be slower than your original code.

 2011-06-24, 16:27 #49 Bdot     Nov 2010 Germany 3×199 Posts Thanks for all your suggestions so far. I'll definitely try the (ulong) conversion and compare it to my current bunch of logic. I still welcome suggestions ;-) Here's the task again: Inputs: uint a, uint b, uint carry (which is the borrow of the previous (lower) 32 bits) Output: uint res=a-b, carry (which should be the borrow for the next (higher) 32 bits) currently this basically looks like Code:  res = a - b - carry; carry = (res > a) || ((res == a) && carry); I'm looking for something simpler for the evaluation of the new carry. Something like Code:  carry = (res >= a) || carry; (Yes, I know this one is not correct) We have available all logical operators, +, -, and the OpenCL Integer Functions. But maybe a total of 6 operations for one 32-bit subtraction with borrow is already the minimum for OpenCL? I did not quite understand how evaluating carries afterwards can save something. Access to the operands is no problem, it's all in registers. The bit-wise operations lead to a total of 10 instructions (?) for one subtraction ... less likely to be an acceleration ;-)
2011-06-24, 16:43   #50
ldesnogu

Jan 2008
France

17×31 Posts

Quote:
 Originally Posted by Bdot I did not quite understand how evaluating carries afterwards can save something. Access to the operands is no problem, it's all in registers. The bit-wise operations lead to a total of 10 instructions (?) for one subtraction ... less likely to be an acceleration ;-)
Well that all depends on two things: what your compiler is able to find depending on the form of your program and what your micro-architecture is able to do.

The post pass carry evaluation for instance is very useful for vector like architectures. And it might be possible on some micro-architectures that the result of a comparison blocks a pipeline while logical operations don't, thus making the logical variant faster even though it uses more operations.

But then again I don't know anything about your target and OpenGL, so I'm probably completely off track

2011-07-03, 15:42   #51
apsen

Jun 2011

131 Posts

Quote:
 Originally Posted by Bdot As I have only this one ATI GPU I wanted to see if anyone would be willing to help testing on different hardware. Current requirements: OpenCL 1.1 (i.e. only ATI GPUs), Windows 64-bit.
I have HD 4550, Windows 2008 R2 x64. Would that work?

Andriy

 2011-07-03, 18:52 #52 Ken_g6     Jan 2005 Caught in a sieve 1100010102 Posts Bdot, what did you wind up finding did the fastest math, 32-bit numbers or 24-bit numbers? And what form of math? Or are you still working on it?
2011-07-04, 11:35   #53
Bdot

Nov 2010
Germany

3×199 Posts

I played around with this a little ...

Quote:
 Originally Posted by ldesnogu Two other random ideas (again sorry if it's not applicable...): - do as many computations as you can without taking care of carries and do a specific pass for handling them; of course that could lead to a big slowdown if you have to reload values and memory is the limiting factor
I have at most 5-6 operations that I can do before checking the carries. The runtime stays exactly the same and the reason is that the compiler reorders the instructions anyway as it thinks fit better. Even a few repeated steps that were necessary for the carry ops did not influence runtime as they were optimized out

Quote:
 Originally Posted by ldesnogu - another way to compute carries is bit arithmetic; let's say you want the carry from a - b Code: res = a - b; carry = ((b & ~a) | (res & ~a) | (b & res)) >> (bitsize-1); where bitsize is the number of bits of a, b and res. Again that could be slower than your original code.
I was really surprised by that one. Even though this is way more operations than my original code, it runs the same speed! Not a bit faster, not a bit slower with the single-vector kernel. Comparing the assembly it turns out that many of the additional operations are "hidden" in otherwise unused slots. Following up with the vector-version of the kernel that has less unused slots, I really saw the kernel takes 3 cycles more - with a total number of ~700 cycles thats less than .5% ...

Here's the current performance analysis of the 79-bit barrett kernel:

Code:
Name                Throughput
FireStream 9270      58 M Threads\Sec
FireStream 9250      48 M Threads\Sec
Radeon HD 5450        6 M Threads\Sec
This is the peak performance of the kernel given enough CPU-power to feed the factor candidates fast enough. Empirical translation tells that 1M Threads/sec is good for 1.2 - 1.5 GHz-days/day.

Unfortunately I right now have a problem that some of the kernel's code is skipped unless I enable kernel tracing. I need that fixed before I can get you another version for testing.

2011-07-04, 12:54   #54
Bdot

Nov 2010
Germany

3·199 Posts

Quote:
 Originally Posted by Ken_g6 Bdot, what did you wind up finding did the fastest math, 32-bit numbers or 24-bit numbers? And what form of math? Or are you still working on it?
Currently the fastest kernel is a 24-bit based kernel working on a vector of 4 factor candidates at once. Here's the list of kernels I currently have, along with the performance on a HD5770:

76 M/s mfakto_cl_71_4: 3x24-bit, 4-vectored kernel
68 M/s mfakto_cl_barrett79: 2.5x32-bit unvectored barrett kernel
53 M/s mfakto_cl_barrett92: 3x32-bit unvectored barrett kernel
44 M/s mfakto_cl_71: 3x24-bit unvectored kernel

The barrett kernels currently need to use a nasty workaround for a bug of the compiler, costing ~ 3%. I'm still working on vectorizing the barretts, a similar speedup as for the 24-bit kernel can be expected, so that the 32-bit based kernels will be a lot faster than 24-bit.

A 24-bit based barrett kernel that was suggested on the forum runs at 75M/s, but as it is using vectors for the representation of the factors, it cannot (easily) be enhanced to run on a vector of candidates. If that were easily possible, then the 24-bit kernel might run for the crown again. But it will not be far ahead of the 32-bit kernel. And the 32-bit one has the advantage of running FCs up to 79 bit instead of 71 bit.

 2011-07-05, 08:12 #55 Bdot     Nov 2010 Germany 3×199 Posts Oh boy, I finally found why the barrett kernels sometimes behaved odd ... OpenCL does bit-shifts only up to the number of bits in the target, and for that it only evaluates the necessary amount of bits of the operand. So for a bit-shift a >> b with 32-bit-values, only the lowest 5 bits of b are used, the rest is ignored ... Therefore the code that used bit-shifts of 32 or more positions to implicitely zero the target did not deliver the expected result. The fix for that goes without performance-penalty ... a little more testing and version 0.06 will be ready.

 Similar Threads Thread Thread Starter Forum Replies Last Post preda GPU Computing 2277 2020-06-06 04:26 TheJudger GPU Computing 3271 2020-05-19 22:42 msft GPU Computing 433 2019-06-23 21:11 TObject GPU Computing 2 2013-10-12 21:09 Stargate38 Factoring 24 2011-11-03 00:34

All times are UTC. The time now is 04:49.

Sat Jun 6 04:49:11 UTC 2020 up 73 days, 2:22, 0 users, load averages: 1.51, 1.42, 1.35