[QUOTE=ldesnogu;264485]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? [/QUOTE]

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 ...

Would the "ulong" data type (a 64-bit unsigned integer) help?

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;

[QUOTE=Bdot;264505]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 ...[/QUOTE]
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);
[/code]where bitsize is the number of bits of a, b and res. Again that could be slower than your original code.

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);
[/code]I'm looking for something simpler for the evaluation of the new carry. Something like
[code]
carry = (res >= a) || carry;
[/code](Yes, I know this one is not correct)

We have available all logical operators, +, -, and the [URL="http://www.khronos.org/registry/cl/sdk/1.1/docs/man/xhtml/integerFunctions.html"]OpenCL Integer Functions[/URL]. 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 ;-)

[QUOTE=Bdot;264555]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 ;-)[/QUOTE]
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 :smile:

[QUOTE=Bdot;263174]

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.

[/QUOTE]

I have HD 4550, Windows 2008 R2 x64. Would that work?

Andriy

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?

I played around with this a little ...

[QUOTE=ldesnogu;264544]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
[/QUOTE]

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 :smile:

[QUOTE=ldesnogu;264544]
- 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);
[/code]where bitsize is the number of bits of a, b and res. Again that could be slower than your original code.[/QUOTE]

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
Radeon HD 5870 135 M Threads\Sec
Radeon HD 6970 118 M Threads\Sec
Radeon HD 6870 100 M Threads\Sec
Radeon HD 5770 68 M Threads\Sec
Radeon HD 4890 66 M Threads\Sec
Radeon HD 4870 58 M Threads\Sec
FireStream 9270 58 M Threads\Sec
FireStream 9250 48 M Threads\Sec
Radeon HD 4770 46 M Threads\Sec
Radeon HD 6670 38 M Threads\Sec
Radeon HD 4670 35 M Threads\Sec
Radeon HD 5670 23 M Threads\Sec
Radeon HD 6450 10 M Threads\Sec
Radeon HD 4550 7 M Threads\Sec
Radeon HD 5450 6 M Threads\Sec
[/code]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.

[QUOTE=Ken_g6;265320]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?[/QUOTE]
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.

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.