Msieve with GPU support - Page 4

henryzz · 2009-10-13, 06:16

Quote:

Originally Posted by Batalov

My card is an ancient 8600 GT, but I couldn't resist trying.

brilliant
you just made me realize that my 8600 GTS supports CUDA
i will try msieve tonight hopefully

10metreh · 2009-10-13, 07:18

Quote:

Originally Posted by henryzz

10 people viewing this thread currently including 3 supermods and 3 mods
how often does that happen?

Probably very rare except for when a new Mersenne prime is reaching the end of its doublecheck.

xilman · 2009-10-13, 07:19

Quote:

Originally Posted by jasonp

Henry, I don't know how even the GPU version of stage 1 compares to pol5 (the algorithm used in pol51m0b would be very difficult to port to a GPU). Stage 2 is much more powerful on msieve; pol51opt really cannot produce a polynomial with a skew larger than 1 million, whereas msieve's stage 2 can easily handle 100x that much.

I beg to differ.

A pol51opt run finished overnight. The best polynomial found has skewness 137977268.98 (almost 138 million). The second is just under 180 million. They are not the two most skewed polynomials.

Paul

bdodson · 2009-10-13, 10:29

Quote:

Originally Posted by henryzz

10 people viewing this thread currently including 3 supermods and 3 mods
how often does that happen?

Not to lower the level of the GPU discussion, but as long as
there's all this poly searching, Greg's c160 looks to be

Code:

160     11      275     -       229.1   0.698   /5q

from the Smaller-but-Needed with page 111. Another likely
prospect would be

Code:

160     7       721     L       261.1   0.612

and there's even a 4th hole at

Code:

161     5       391     -       273.2   0.589

Uhm, those were 11, 275- C160, 7, 721L C160 Sm-but-Needed and
5, 391- C161. All numbers worth clearing if someone finds a
suitable .poly. Should be no shortage of people to do sieving
and post-processing for the first GPU Cunningham, or even the
2nd or 3rd. -Bruce

jasonp · 2009-10-13, 13:36

Quote:

Originally Posted by xilman

A pol51opt run finished overnight. The best polynomial found has skewness 137977268.98 (almost 138 million). The second is just under 180 million. They are not the two most skewed polynomials.

I was insufficiently precise. pol51opt can find polynomials with very large skew, but the bounds used in the root sieve cannot exceed +-1M. So an initial polynomial from pol51m0b will look like

XXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXX
XXX
X

and then the size optimization will make it look like

XXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXX
XXXXXXX
X

because rotations can be chosen so that the first three coefficients are artificially small in size. When looking for good root properties, you can choose large rotations so that the polynomial will then become

XXXXXXXXXXXXXXXXXXXXYYYYYYYYYYY
XXXXXXXXXXXXXXXXXXXXYYYYY
XXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXX
XXXXXXX
X

but the root sieve in pol51opt might only get to

XXXXXXXXXXXXXXXXXXXXYYYYY
XXXXXXXXXXXXXXXXXXXXYY
XXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXX
XXXXXXX
X

The final size optimization can still make the last picture look like the picture before it, but most of the search space for good root properties (i.e. a primary reason for choosing very large skew) goes wasted. Look at some of the 170- or 180-digit polynomials that mersenneforum has sieved and they generally look like the latter picture.

Jeff Gilchrist · 2009-10-13, 14:27

Wow, nice, GPU support. I don't suppose once you get this all figured out in CUDA you would be willing to try out OpenCL so the rest of us with non-Nvidia graphics cards can play too?

fivemack · 2009-10-13, 15:07

I've just ordered a GTX275 (with 1.75G memory; nothing like enough for linalg but should be interesting for sieving) so I can do some playing with this; yes, it's not as rawly fast as ATI's equivalents, but the ATI software ecosystem is dire: ATI's OpenCL doesn't yet compile to GPU, the bug reports on their forum are really very uninspiring.

My not-terribly-informed opinion is that at the moment, efficient GPU work involves shaping the algorithm, let alone the code, sufficiently tightly to the underlying hardware enough that it doesn't make sense to pretend to be device-independent.

frmky · 2009-10-13, 18:32

Quote:

Originally Posted by frmky

Definitely seems to be working. For 11,275- (C160), it very quickly found

I ran 11,275- overnight again on all 4 GPUs by compiling 4 binaries, one for each GPU, and giving each a different range. The ten best were

Code:

all.p:# norm 9.231745e-16 alpha -6.916016 e 1.023e-12
all.p:# norm 9.210116e-16 alpha -6.805832 e 1.034e-12
all.p:# norm 9.289406e-16 alpha -7.277519 e 1.034e-12
all.p:# norm 9.269171e-16 alpha -6.400589 e 1.035e-12
all.p:# norm 9.313491e-16 alpha -7.706817 e 1.036e-12
all.p:# norm 9.369426e-16 alpha -7.442146 e 1.036e-12
all.p:# norm 9.371670e-16 alpha -6.449208 e 1.043e-12
all.p:# norm 9.477571e-16 alpha -7.980220 e 1.047e-12
all.p:# norm 9.549995e-16 alpha -8.057895 e 1.049e-12
all.p:# norm 9.896751e-16 alpha -7.232692 e 1.066e-12

with the two best polys

Code:

# norm 9.549995e-16 alpha -8.057895 e 1.049e-12
skew: 51018877.18
c0:  902279983224137484039338784561169683607200
c1: -249773548060743092821982704648059612
c2:  6773224049843781466534570936
c3:  189820877916105845643
c4: -280793577854 
c5:  11400
Y0: -15239548205919859860646057638229
Y1:  409668722066077021

# norm 9.896751e-16 alpha -7.232692 e 1.066e-12
skew: 17106039.87
c0: -14144188007100456071042671260511036216800
c1: -8770173721065438739467141198650180 
c2:  54805781884036304560654308  
c3:  216525056873144839851
c4: -916468293854 
c5:  11400
Y0: -15239552774622466061285418310177
Y1:  409668722066077021

How do these compare to typical polynomials for a C160 found by pol5?

fivemack · 2009-10-13, 18:47

They look pretty good in comparison to things I've run.

My data points are a C163 done with msieve, where the score was 0.725e-12 Murphies, and a C159 done with msieve with a score of 1.454e-12 Murphies.

My pol5 bracketting points are a C165 done some time ago, where the score was 0.674e-12, and a C155 done around the same time with a score of 2.06e-12.

Batalov · 2009-10-13, 18:57

For 2,1598M c160, long ago, with pol51, I had a 1.266e-12 poly (the units were different back then, so I re-gauged it with the latest binary).

P.S. My latest ad hoc fit suggests log₁₀ E₀ = -0.0667 * digits - 1.3333 for the cut-off. The actual values should be a bit larger. E.g. for 180-digits, cutoff 4.57e-14, with actual E for 5,421- 6.90e-14 and for 2,2254L, 6.15e-14 (so far, with pol51 and not with the GPU, of course).

P.P.S. ...can be regrouped into log₁₀ E₀ = -(digits+20)/15.0 (no calculator needed!)

bsquared · 2009-10-13, 19:14

Curve fits against data from 5,421- (C180), 2,877- (C178), 109!+1 (C179), 6,383+ (C165), and quite a few C150's and C140s, suggest a MurphyE of about 1.17e-12 is expected using pol51. Although I remember the poly search for 6,383+ took much longer than "overnight"

.

2009-10-13, 18:57	#43
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 10010100000101₂ Posts	For 2,1598M c160, long ago, with pol51, I had a 1.266e-12 poly (the units were different back then, so I re-gauged it with the latest binary). P.S. My latest ad hoc fit suggests log₁₀ E₀ = -0.0667 * digits - 1.3333 for the cut-off. The actual values should be a bit larger. E.g. for 180-digits, cutoff 4.57e-14, with actual E for 5,421- 6.90e-14 and for 2,2254L, 6.15e-14 (so far, with pol51 and not with the GPU, of course). P.P.S. ...can be regrouped into log₁₀ E₀ = -(digits+20)/15.0 (no calculator needed!) Last fiddled with by Batalov on 2009-10-13 at 19:21 Reason: ("the latest" was literal. fiddled just now)

2009-10-13, 19:14	#44
bsquared "Ben" Feb 2007 3×1,171 Posts	Curve fits against data from 5,421- (C180), 2,877- (C178), 109!+1 (C179), 6,383+ (C165), and quite a few C150's and C140s, suggest a MurphyE of about 1.17e-12 is expected using pol51. Although I remember the poly search for 6,383+ took much longer than "overnight" . Last fiddled with by bsquared on 2009-10-13 at 19:27 Reason: get sizes right

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Compiling Msieve with GPU support	LegionMammal978	Msieve	6	2017-02-09 04:28
5+ GPU support	TheMawn	GPU Computing	3	2014-07-13 02:31
Support AVX	Unregistered	Information & Answers	5	2011-07-05 17:12
Msieve with GNFS support	R.D. Silverman	Msieve	465	2010-01-11 20:59
Athlon64 support?	JuanTutors	Software	1	2004-06-04 02:46

2009-10-13, 14:27	#39
Jeff Gilchrist Jun 2003 Ottawa, Canada 3×17×23 Posts	Wow, nice, GPU support. I don't suppose once you get this all figured out in CUDA you would be willing to try out OpenCL so the rest of us with non-Nvidia graphics cards can play too?

2009-10-13, 15:07	#40
fivemack (loop (#_fork)) Feb 2006 Cambridge, England 1913₁₆ Posts	I've just ordered a GTX275 (with 1.75G memory; nothing like enough for linalg but should be interesting for sieving) so I can do some playing with this; yes, it's not as rawly fast as ATI's equivalents, but the ATI software ecosystem is dire: ATI's OpenCL doesn't yet compile to GPU, the bug reports on their forum are really very uninspiring. My not-terribly-informed opinion is that at the moment, efficient GPU work involves shaping the algorithm, let alone the code, sufficiently tightly to the underlying hardware enough that it doesn't make sense to pretend to be device-independent.

2009-10-13, 18:47	#42
fivemack (loop (#_fork)) Feb 2006 Cambridge, England 7²×131 Posts	They look pretty good in comparison to things I've run. My data points are a C163 done with msieve, where the score was 0.725e-12 Murphies, and a C159 done with msieve with a score of 1.454e-12 Murphies. My pol5 bracketting points are a C165 done some time ago, where the score was 0.674e-12, and a C155 done around the same time with a score of 2.06e-12.