Early Trials with OpenCL (Barrett's Modulus)

[diep]

Originally Posted by chrisjp

Hey all, Sorry for the long long delay. Lots of changes in life, but here is the barebones opencl code. Currently not usable unless you're quite dedicated :)

It has lots of debug stuff and old code, but you can get the jist of the algorithm.

It currently runs around 93M primes / second with everything precalculated and ready to go on the CPU side on an HD 6870 @ 1Ghz.

I'll try to incorporate it into a .exe sometime this or next week.

Chris

I assume you mean a 6870 @ 900Mhz. The RAM is clocked 1.05Ghz yet the PE's are clocked 900Mhz. Except when you overclock it but i guess that's not recommended for number crunching :)

http://www.amd.com/us/products/deskt...verview.aspx#2

Maybe i should ask you at which bitlevel you are trying FC's, as i was counting at the 880Mhz @ 1536 streamcores i have here (radeon hd 6970), to reach speeds of nearly a billion per second or more this at up to 63 bits, maybe 64 bits.

93M/s is very disappointing i'd argue.

Vincent

[chrisjp]

No I mean the 6870 at 1000 Mhz, overclocking hasn't produced any errors but you may do what you wish :).

The code is constant up to 71-bits... I and many others would be interested to see code that can work at 1B/second with these factors :)

Chris

Originally Posted by diep

I assume you mean a 6870 @ 900Mhz. The RAM is clocked 1.05Ghz yet the PE's are clocked 900Mhz. Except when you overclock it but i guess that's not recommended for number crunching :)

http://www.amd.com/us/products/deskt...verview.aspx#2

Maybe i should ask you at which bitlevel you are trying FC's, as i was counting at the 880Mhz @ 1536 streamcores i have here (radeon hd 6970), to reach speeds of nearly a billion per second or more this at up to 63 bits, maybe 64 bits.

93M/s is very disappointing i'd argue.

Vincent

[chrisjp]

Right, but 24-bit instructions get issued in 4-lanes, wheres 32-bits go in one lane. 4 times the throughput.. basic stuff here. It's easy to see the difference if you profile code with 32-bit versus 24-bit multiplies. Fermi can do 32-bit at full-speed, whereas ATI cannot. The code already uses the high and low instructions in other places.

Originally Posted by diep

24 bits????

older nvidia's could only do 24 bits (fermi can do 32 now as well). AMD always could do 32 x 32 bits multiplications since the 4000 series AFAIK. One instruction gives top 32 bits another instruction lower 32 bits. I already wanted to post how to get those in openCL, but maybe you want to post this :)

[diep]

Originally Posted by chrisjp

Right, but 24-bit instructions get issued in 4-lanes, wheres 32-bits go in one lane. 4 times the throughput.. basic stuff here. It's easy to see the difference if you profile code with 32-bit versus 24-bit multiplies. Fermi can do 32-bit at full-speed, whereas ATI cannot. The code already uses the high and low instructions in other places.

Right, except that the 6000 series is supposed to have more than doubled that capacity; from 1 in 5 PE's now 2 out of 4 can execute it and you're not issuing multiplication most of the time, there is other instructions as well.

Besides the crucial first 64 bits you cover with 2 units using 2 x 32 bits,
versus 3 x 32 bits for the 24 bits equivalent.

But of course we agree that one should test it all very well, as that'll decide what and how :)

Realize with wagstaff we're still trial factoring around the 10M bits sizes, so getting to 64 bits is already quite something, as default it's 61 bits now.

thanks to the hard work here of the gpu's doing TF for mersenne, did i read it correct that for GIMPS things get TF'ed now at the current range to 69 bits isn't it?

Thanks,
Vincent

[diep]

Originally Posted by chrisjp

No I mean the 6870 at 1000 Mhz, overclocking hasn't produced any errors but you may do what you wish :).

The code is constant up to 71-bits... I and many others would be interested to see code that can work at 1B/second with these factors :)

Chris

I calculated with 64 bits of course, as my goal is to Trial Factor to 64 bits of course, where 61 bits got accomplished by my 16 core AMD @ 16 cores, as that's about what you need to run TF to keep Jeff Gilchrist' fed enough exponents to test; maybe it's cold during winters in Canada!

[diep]

Originally Posted by chrisjp

No I mean the 6870 at 1000 Mhz, overclocking hasn't produced any errors but you may do what you wish :).

The code is constant up to 71-bits... I and many others would be interested to see code that can work at 1B/second with these factors :)

Chris

Didn't know you were in the league of overclockers :)

As serious note on the 1B/s. Let's consider i've got 1536 cores @ 880Mhz.
Now let's skip silly definitions of AMD/Nvidia (both multiply their gpu's with a phantom factor to determine number of gflops, in case of AMD that's in the manual explained as well) and look realistic.

The ideal throughput is 1.0 per PE. To reach 1B/s we can throw effectively a tad less, in my case as i'm intending doing the sieving in another wavefront, than 1536 * 0.88 cycles per FC into battle.

That's 1351 cycles for a 64 bits FC.

On a cpu, 1351 cycles is hell of a lot. Within 1351 cycles you can calculate for example what distance it takes to travel around the planet. Even a small bathroom stop is allowed in fact.

I'm testing numbers of around 10-12M now, which all already have been processed to 61 bits.

Let's take a 10M number.

That's 24 bits deep. So to see whether a 64 bits number divides this, let's say roughly we need roughly 37 squares and 37 modulo's. Using barrett (note i remember one day i had reinvented barrett myself - see GMP mailing list - it beated for big numbers the default modulo at the time) that means extension of this 128 bits number to 192 bits. So another multiplication.

Let's assume now stupid schoolboy algorithm, which for GPU's usually is not such a bad idea (huh?).

Let's calculate everything in units for 1 step:

First we have 2 units that we get to 4. That's say 4 multiplications.
Then we have 4 units times 2, that's 8 multiplications.
So 12 multiplications in total.

37 * 12 = 444 multiplications, and of course a lot of extra work, but all the extra work should go at full PE speed.

I wrote things down in a naive manner here, without further indepth research yet, but i hope you see what i was guessing that would be theoretical possible.

Now i also know the theoretist problem - paper supports everything

But what's your estimate on what is possible?

Realize so far i didn't count the sieve yet and that thing isn't exactly 'free' either.

Regards,
Vincent

[chrisjp]

My code currently runs (on the 6870 not 6970) in 2334 clock cycles. Roughly 1/10th of that is in the squaring and the remainder in the modulus calculation.

In terms of what could be done at only 64-bits, I believe you could get 400M if you refined my code. The main limitations are going to be the carry steps (lots of serial dependencies that limit your ALU packing) and subtraction steps (no integrated carry registers in the alu's that are exposed to opencl.)

You would also run into problems solely relying on 64-bit(2X32) multiplies as you need guard bits for the carries (no carry register in opencl). So for 61-or-62 bit factors 400M might be possible with a 6970 fairly easily.

But again, then you have to worry about precalculating the mu (like mkafct) on the GPU side to really get good CPU thoroughput.

In short 400M I think I could do at 64 exclusive, but it's hard to know!

Originally Posted by diep

Didn't know you were in the league of overclockers :)

As serious note on the 1B/s. Let's consider i've got 1536 cores @ 880Mhz.
Now let's skip silly definitions of AMD/Nvidia (both multiply their gpu's with a phantom factor to determine number of gflops, in case of AMD that's in the manual explained as well) and look realistic.

The ideal throughput is 1.0 per PE. To reach 1B/s we can throw effectively a tad less, in my case as i'm intending doing the sieving in another wavefront, than 1536 * 0.88 cycles per FC into battle.

That's 1351 cycles for a 64 bits FC.

On a cpu, 1351 cycles is hell of a lot. Within 1351 cycles you can calculate for example what distance it takes to travel around the planet. Even a small bathroom stop is allowed in fact.

I'm testing numbers of around 10-12M now, which all already have been processed to 61 bits.

Let's take a 10M number.

That's 24 bits deep. So to see whether a 64 bits number divides this, let's say roughly we need roughly 37 squares and 37 modulo's. Using barrett (note i remember one day i had reinvented barrett myself - see GMP mailing list - it beated for big numbers the default modulo at the time) that means extension of this 128 bits number to 192 bits. So another multiplication.

Let's assume now stupid schoolboy algorithm, which for GPU's usually is not such a bad idea (huh?).

Let's calculate everything in units for 1 step:

First we have 2 units that we get to 4. That's say 4 multiplications.
Then we have 4 units times 2, that's 8 multiplications.
So 12 multiplications in total.

37 * 12 = 444 multiplications, and of course a lot of extra work, but all the extra work should go at full PE speed.

I wrote things down in a naive manner here, without further indepth research yet, but i hope you see what i was guessing that would be theoretical possible.

Now i also know the theoretist problem - paper supports everything

But what's your estimate on what is possible?

Realize so far i didn't count the sieve yet and that thing isn't exactly 'free' either.

Regards,
Vincent

[diep]

Originally Posted by chrisjp

My code currently runs (on the 6870 not 6970) in 2334 clock cycles. Roughly 1/10th of that is in the squaring and the remainder in the modulus calculation.

...snip

Some sooner here you posted: "It currently runs around 93M primes / second with everything precalculated and ready to go on the CPU side on an HD 6870 @ 1Ghz."

2334 clockcycles @ 1120 PE's ==> 480M /s

Yet you report 93M/s which actually is in number of cycles per FC:

1120G / 93M = 1120k / 93 = 12k cycles per FC.

In terms of what could be done at only 64-bits, I believe you could get 400M if you refined my code. The main limitations are going to be the carry steps (lots of serial dependencies that limit your ALU packing) and subtraction steps (no integrated carry registers in the alu's that are exposed to opencl.)

You would also run into problems solely relying on 64-bit(2X32) multiplies as you need guard bits for the carries (no carry register in opencl). So for 61-or-62 bit factors 400M might be possible with a 6970 fairly easily.

But again, then you have to worry about precalculating the mu (like mkafct) on the GPU side to really get good CPU thoroughput.

In short 400M I think I could do at 64 exclusive, but it's hard to know!

No carry possibilities in opencl, if AMD gpu's do allow using it, would be severe problem for gpgpu in opencl at AMD gpu's as it throws away a lot of performance.

[diep]

Originally Posted by chrisjp

[snip]
In terms of what could be done at only 64-bits, I believe you could get 400M if you refined my code. The main limitations are going to be the carry steps (lots of serial dependencies that limit your ALU packing) and subtraction steps (no integrated carry registers in the alu's that are exposed to opencl.)

You would also run into problems solely relying on 64-bit(2X32) multiplies as you need guard bits for the carries (no carry register in opencl). So for 61-or-62 bit factors 400M might be possible with a 6970 fairly easily.

Let's skip the discussion on what refining is, as probably it means starting from scratch :)

Reality is that being the first writing something always is toughest.

REFINING

As i'm after 64 bits initially, i'll have to start from scratch anyway.

It's not needed to have guard bits at all of course, just it's a lot more expensive than just adding the carry.

Much depends upon the throughput independant instructions at the gpu's.

When writing a special implementation for 61-63 bits or so, so something less than 64, you will need to shiftright top bits in order to add them.

That might not be so fast.

It might be a problem for 2 reasons, but of course it would require alternatives to be there. These gpu's have fast CMOV capabilities i hope.

The instructionset of amd already for years shows at gpu level that they have really a lot of different instructions for that.

Now what i don't know is how many PE's actually can execute it.

Manual carry:

adding A and B:

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

Till so far for now.

[xilman]

Originally Posted by diep

Manual carry:

adding A and B:

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

You don't give declarations for the types of A and B but I'm going to assume that they are word-sized unsigned integers. If so, a standard and usually efficient way of computing the carry uses fewer lines of code and fewer operations on the variables than your sample above. A C function runs something like:

/* add with carry-out function.
  Result of addition is stored where the first argument points.
  Carry_out is returned as the value of the function.
*/
unsigned adc (unsigned *sum, unsigned a, unsigned b)
{
   *sum = a+b;
   return *sum < a;   /* sum is unsigned less than a if the addition overflowed */
}

Paul

[diep]

Originally Posted by xilman

You don't give declarations for the types of A and B but I'm going to assume that they are word-sized unsigned integers. If so, a standard and usually efficient way of computing the carry uses fewer lines of code and fewer operations on the variables than your sample above. A C function runs something like:

/* add with carry-out function.
  Result of addition is stored where the first argument points.
  Carry_out is returned as the value of the function.
*/
unsigned adc (unsigned *sum, unsigned a, unsigned b)
{
   *sum = a+b;
   return *sum < a;   /* sum is unsigned less than a if the addition overflowed */
}

Paul

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