Early Trials with OpenCL (Barrett's Modulus)

[diep]

So that makes the new adding of carry code, without opencl support for it:

carry = 0;
x       = A+B;
if( x < A ) carry = 1;

[xilman]

Originally Posted by diep

Very good comments that it can be done without the OR as you can already prove 'sum' has to be smaller than a.

Yet putting it in a seperated function i guess is a lot slower in opencl. i didn't really test it to the limit, but i'd expect some crap compiler/interpreter running it, so all sorts of modern features todays compilers have i wouldn't expect it to do very well :)

Putting it in a function was purely a way of giving you a self-contained example which will compile without any additional material. In production C it would be typical to put the code in-line and avoid a function call overhead (though a modern compiler would probably in-line it anyway).

Paul

[xilman]

Originally Posted by diep

So that makes the new adding of carry code, without opencl support for it:

carry = 0;
x       = A+B;
if( x < A ) carry = 1;

I don't write in opencl, but does the language not have if-then-else?

If so

x = A+B;
if (x<A) carry=1; else carry=0;

only assigns to carry once. Your code assigns it 1.5 times on average.


Paul

[Robert Holmes]

One can try to use 64-bit integers and hope the compiler is smart enough to use internal ADC:

x = (u64)A+B;
carry = x>>32;

[diep]

Originally Posted by Robert Holmes

One can try to use 64-bit integers and hope the compiler is smart enough to use internal ADC:

x = (u64)A+B;
carry = x>>32;

This might go wrong though, the hardware can at most shiftright 31 bits, so compiler might produce random results.

[diep]

Originally Posted by xilman

I don't write in opencl, but does the language not have if-then-else?

If so

x = A+B;
if (x<A) carry=1; else carry=0;

only assigns to carry once. Your code assigns it 1.5 times on average.


Paul

If then else is the slowest possible thing at GPU's, except if it produces a CMOV type instruction here. Same is true what i wrote; i assume both codes will produce the CMOV and therefore the exact same code.


Relevant is of course to test it all at the opencl compiler and see how fast it is compared to shifting 31 bits and compared to not doing it at all (thugh producing wrong result, it's about the speedwise compare).

Note that another big problem of GPU's is the hidden latencies.

If we have the next sequential thing in the code:

x = a+b;
instruction using 'x' here

So the code uses 'x' directly after it wrote to 'x'. This will give a huge penalty. Say 4 cycles or so.
A way to avoid that is to already have another wavefront started at the gpu that runs while it waits for
the result of 'x' here. Yet in prime number code it might be important to schedule the code such that we can avoid another thread from needing to run there; as then we lose registers which we all need to store the primebase for the sieve generating factor candidates - bigger primebase means we waste less system time on testing composites in the form 2 np + 1 with trial factoring.

p.s. not so real important in this context:

As for too many functions in languages, we see in C++ the problem of that. Also the modern compilers have big problems with deep layers of classes, which seemingly would be easy to 'inline'. Resulting C++ codes nearly always are factors slower than C code, which is weird if you realize semantically usually there is no difference between the constructs.

Very few coders on the planet manage to produce in C++ code that's equally fast to C code, meanwhile really looking like C++ code :)

pps this is also 1 explanation why some CUDA codes seem so fast compared to the C++ alternatives; imperative languages simply are faster practical; that is if the code can get managed by 1 person. Obviously for companies there is huge advantages in using C++ for their projects - that's not the discussion here

[Robert Holmes]

Originally Posted by diep

This might go wrong though, the hardware can at most shiftright 31 bits, so compiler might produce random results.

Yes, that's why the compiler must be smart about it and recognize what we're trying to do.

Another option is:

x = A+B;
carry = A>=(-B);

This one's more attractive, as carry and sum calculation become independent. It works because -B is equivalent to 2^32-B; A > 2^32-B => A+B > 2^32.

[diep]

Originally Posted by Robert Holmes

Yes, that's why the compiler must be smart about it and recognize what we're trying to do.

Another option is:

x = A+B;
carry = A>=(-B);

This one's more attractive, as carry and sum calculation become independent. It works because -B is equivalent to 2^32-B; A > 2^32-B => A+B > 2^32.

This is a rather good idea to be tried!

Vincent

p.s. checking whether it has an efficient negate instruction ;)

Note i also have to write out all cases to check whether it works correct, but that's because i didn't see this one before :)

[xilman]

Originally Posted by diep

If then else is the slowest possible thing at GPU's, except if it produces a CMOV type instruction here.

Fair enough. I did say that I don't speak opencl.

Paul

[diep]

Originally Posted by xilman

Fair enough. I did say that I don't speak opencl.

Paul

Well you adress a fundamental problem which is language independant: GPU's are very ugly with branches, to say polite. In the luckiest case you can have, they execute *all code* in both chains of the branches. So if a branch doesn't get taken:

if( randomnumberPEdependant&1 ) {
  bla bla;
}
else {
  yep;
}

It will here also suffer from bla bla and yep; Of course not execute the code, but you can be sure your delay is at least the same as the time it takes to execute blabla and yep together;

Of course this only if a branch gets taken by some PE's; if all of them do not take it, maybe it's ok (have to check - let's not count at it for now).

[chrisjp]

You are correct about if/else, usually for simple arithmetic like in my code it gets easily translated to a conditional move. This saves tons of gpu cycles, a simple if/else if around 80 cycles on the newest hardware just for flow control if it isn't compiled as CMOV.

The issue with implementing any of the carries this way for me, is we are currently using a 6-wide 24-bit integer multiplication (3X3) for the barrett and similar for the squaring. If you use 32-bits with the 1-bit carry you end up needing to ripple through the carry on each multiply, which is quite slow.

If you are only doing 64-bits this is less of a problem of course.