GPU polynomial selection, extreme edition - Page 3

debrouxl · 2012-09-01, 19:24

Quote:

Originally Posted by fivemack

In the medium range I can offer 8352:1755 C178; [...] at the moment I'd expect a Murphy score of around 9e-14 for a good polynomial, so it would be intriguing to learn what Murphy score two GF580-weeks can offer.

It would indeed be intriguing to learn what exactly two GTX580-weeks could yield on 8352:1755 C178... At least, 9e-14 can easily be reached:

Code:

polynomial selection complete
R0: -84709038622734764783888333466210357
R1: 29993976615204881
A0: -1362671526509665302077465943107518752134689798880
A1: 28205522589692077665645404022630276668224
A2: -22077238490521238377117794168222
A3: -15348854333995610268865
A4: 3847484049680
A5: 1032
skew 2174174647.61, size 1.601e-17, alpha -8.426, combined = 9.107e-14 rroots = 5

That was the result of ~8 minutes of msieve -npr on the < 20 unique polynomials with norm below 1e24 (as indicated in the .dat.ms file), extracted from the ~15000 lines (!) produced by msieve -np1 -nps faststage1 on my GT540M, in only ~3 hours of work.

debrouxl · 2012-09-02, 06:54

I killed msieve -np1 -nps on 8352:1755 C178 at 14:15:32 of wall clock time. Even at reduced CPU usage, the CPU in this laptop exceed 90°C when the GPU is running, so I don't run GPU-intensive tasks 24/7...
msieve produced 78002 hits, 75116 unique, for 17 MB of output, on the 1-11100 range for A5.

Result of msieve -npr on the 100 hits with norm between 1e+23 and 1e+24 (there's no norm below 1e+23):

Code:

polynomial selection complete
R0: -63406418205306376111523443102555350
R1: 1012340958851498807
A0: 22984253874154911049110236774173244305193591137
A1: 150912639726515479622718372705215149459
A2: -3473769829041710266842808172947
A3: 4774413931203308323289
A4: 16960276844550
A5: 4392
skew 457889463.66, size 2.288e-17, alpha -8.313, combined = 1.142e-13 rroots = 5
elapsed time 00:39:05

The best polynomial was produced from the following hit, with the third smallest norm in the .dat.ms file:

Code:

4392 10500857212230 -11380685199228030256231 -92896253230609116373787152 42964643107182367408296584400646534 104051051835187044509336149554366114391 1012340958851498807 -63406418503081196885 978118575818494 -1.54 2.904663e+23

The hit with the smallest norm didn't produce much; the hit with the second smallest norm produced polynomials with e=1.12e-13 and e=1.13e-13.

If you need more information, just tell me

debrouxl · 2012-09-03, 18:29

In order to provide another data point, after a C163 and a C178, I set my sights on the somewhat larger RSA-190

Summary: once again, only 1-2% of the size-optimized stage 1 hits are interesting for root optimization. I don't know precisely what changes need to be performed in the code of msieve in order to decrease the output by at least an order of magnitude, but I think that it needs to be done across the range of difficulties

GPU-based polsel is now so fast, even on a lower-end GPU, that it produces just too much output ^^

In 12:01:52 of wall clock time, msieve -np1 -nps on the GT540M produced 26510 stage 1 hits, 26021 unique, 6 MB of output.
The distribution of norms is as follows:

Code:

$ grep "e+24" RSA190.dat.ms | sort -k10 | uniq | wc -l
0
$ grep "e+25" RSA190.dat.ms | sort -k10 | uniq | wc -l
144
$ grep "e+26" RSA190.dat.ms | sort -k10 | uniq | wc -l
14956
$ grep "e+27" RSA190.dat.ms | sort -k10 | uniq | wc -l
10921

The best polynomials produced by less than 5 minutes of msieve -npr on the five hits with the smallest norms are:

Code:

R0: -14132188288577037956744568550190340393
R1: 25931477490931393997
A0: -94194368630853444832733554633587529878564076333000
A1: 116503894615880794280063642409376454877840
A2: 325943501823794356871804936015088
A3: -326134308620324842795221
A4: -174723038450282
A5: 3384
skew 1615089872.19, size 1.134e-18, alpha -8.211, combined = 1.769e-14 rroots = 5

R0: -12552932417874790049819504811028017599
R1: 102821570281985098621
A0: 6862503539205415099516630962479825435908216250520
A1: -89231911152040484329017673829821880164948
A2: 32741257147974489627725342347286
A3: 1160648824712340127438355
A4: 22366864450362
A5: 6120
skew 1018696792.65, size 1.138e-18, alpha -8.801, combined = 1.763e-14 rroots = 3

These polynomials rival the result of at least a CPU-year of polsel5, used for sieving RSA-190 ( http://mersenneforum.org/showpost.ph...14&postcount=1 ), with murphy_e = 1.740627e-14:

Code:

skew: 1.89723e+06
c5: 40208599020
c4: -1373979915646426
c3: -18783091380980602091391
c2: 32414999912320727344430346523
c1: -375830488267489810578184841744243639
c0: 348578818479643113591848726218653819076813
Y1: 127570152207571988302487
Y0: -543540225411856459303967064165519554

Xyzzy · 2012-09-03, 18:39

Quote:

Originally Posted by debrouxl

These polynomials rival the result of at least a CPU-year of polsel5…

Would a GPU-year (?) provide a better result or just a lot of more results similar to what you just received?

jrk · 2012-09-03, 19:46

Quote:

Originally Posted by debrouxl

These polynomials rival the result of at least a CPU-year of polsel5, used for sieving RSA-190 ( http://mersenneforum.org/showpost.ph...14&postcount=1 ), with murphy_e = 1.740627e-14:

For reference: months ago I ran rsa190 through msieve 1.50 (using old sorting code) for 2 days on a 570 GTX and this is the best I found:

Code:

# norm 1.412795e-18 alpha -7.807532 e 2.112e-14 rroots 3
skew: 167701282.72
c0: -33570956343141502617325007763517125021008776740
c1:  1623700481580372471756342190639612571562
c2: -13815892179630914285517442461740
c3: -330504122287166237468552
c4:  577776345010431
c5:  2476764
Y0: -3778492389925782385492108170292919447
Y1:  101979949414559359913

Quote:

Originally Posted by Xyzzy

Would a GPU-year (?) provide a better result or just a lot of more results similar to what you just received?

A GPU-year (with a decent GPU) using the latest code would be overkill for rsa-190, IMO. But, better polys than the ones posted here exist, undoubtedly.

jasonp · 2012-09-03, 19:50

It would provide a lot more results, a very few of which will be a lot better by random chance. Poly selection is like throwing darts, try a few million of them and you'll get two or three bullseyes.

PS: can you tell I suck at darts?

debrouxl · 2012-09-04, 05:38

jrk: I'm curious, how many hits does msieve faststage1 produce on the GTX570 in several hours (i.e., how much faster than the GT540M is the GTX570, and does polsel scale better or worse than what mersenne-aries shows for Mersenne TF) ?

fivemack · 2012-09-04, 11:19

I really think that now is also the right time to decouple the score-for-proceeding-at-stage-2 and the target-score-for-stage-2; certainly for these larger numbers I found that a target-score low enough to give good polynomials was so low that you proceeded with almost every stage-1 hit and stage-2 took forever.

Certainly with the new awesomely fast stage-1 I would be very inclined to cut back the stage-1 param to around one output a second, and then take only the fifty best stage-1 outputs through a vigorous stage-2.

Sorry I'm not playing with this more directly: I sold my GPU-equipped machine, I can't physically fit a GPU into the 48-core monster, and if I fit one into the fileserver the discs are likely to melt. I've vowed not to buy another whole computer until May 2014 because the 48-core monster was really quite expensive.

poily · 2012-09-05, 13:08

24 hours of RSA-210 polynomial selection on 1 Tesla X2070 gave me the best murphy_e 7.485e-16 with the faststage1 version and 8.48e-16 with the trunk version. I know the polsel algorithm is essentially a lottery but still do I have to launch msieve with special arguments like -np1 ... instead of just -np to see the difference?

jasonp · 2012-09-05, 16:34

-np will run stage 2, which will spend a lot of time optimizing polynomials that will not be very good. Try running with

-np1 -nps X,Y

to search leading coefficients between X and Y, then look at the scores
of the size-optimized polynomials in msieve.dat.ms (it's the last column)
and only run the root optimization (-npr) on the polynomials with the
best (lowest) scores.

firejuggler · 2012-09-05, 16:50

may i remind you of http://mersenneforum.org/showthread.php?t=11989 (2^877-1 poly selec) for a 'mid level" candidate, and to compare the poly?

2012-09-02, 06:54	#24
debrouxl Sep 2009 3D1₁₆ Posts	I killed msieve -np1 -nps on 8352:1755 C178 at 14:15:32 of wall clock time. Even at reduced CPU usage, the CPU in this laptop exceed 90°C when the GPU is running, so I don't run GPU-intensive tasks 24/7... msieve produced 78002 hits, 75116 unique, for 17 MB of output, on the 1-11100 range for A5. Result of msieve -npr on the 100 hits with norm between 1e+23 and 1e+24 (there's no norm below 1e+23): Code: polynomial selection complete R0: -63406418205306376111523443102555350 R1: 1012340958851498807 A0: 22984253874154911049110236774173244305193591137 A1: 150912639726515479622718372705215149459 A2: -3473769829041710266842808172947 A3: 4774413931203308323289 A4: 16960276844550 A5: 4392 skew 457889463.66, size 2.288e-17, alpha -8.313, combined = 1.142e-13 rroots = 5 elapsed time 00:39:05 The best polynomial was produced from the following hit, with the third smallest norm in the .dat.ms file: Code: 4392 10500857212230 -11380685199228030256231 -92896253230609116373787152 42964643107182367408296584400646534 104051051835187044509336149554366114391 1012340958851498807 -63406418503081196885 978118575818494 -1.54 2.904663e+23 The hit with the smallest norm didn't produce much; the hit with the second smallest norm produced polynomials with e=1.12e-13 and e=1.13e-13. If you need more information, just tell me

2012-09-03, 19:50	#28
jasonp Tribal Bullet Oct 2004 6725₈ Posts	It would provide a lot more results, a very few of which will be a lot better by random chance. Poly selection is like throwing darts, try a few million of them and you'll get two or three bullseyes. PS: can you tell I suck at darts? Last fiddled with by jasonp on 2012-09-03 at 19:52

2012-09-04, 11:19	#30
fivemack (loop (#_fork)) Feb 2006 Cambridge, England 14423₈ Posts	I really think that now is also the right time to decouple the score-for-proceeding-at-stage-2 and the target-score-for-stage-2; certainly for these larger numbers I found that a target-score low enough to give good polynomials was so low that you proceeded with almost every stage-1 hit and stage-2 took forever. Certainly with the new awesomely fast stage-1 I would be very inclined to cut back the stage-1 param to around one output a second, and then take only the fifty best stage-1 outputs through a vigorous stage-2. Sorry I'm not playing with this more directly: I sold my GPU-equipped machine, I can't physically fit a GPU into the 48-core monster, and if I fit one into the fileserver the discs are likely to melt. I've vowed not to buy another whole computer until May 2014 because the 48-core monster was really quite expensive. Last fiddled with by fivemack on 2012-09-04 at 11:26

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
2^877-1 polynomial selection	fivemack	Factoring	47	2009-06-16 00:24
Polynomial selection	CRGreathouse	Factoring	2	2009-05-25 07:55
Intel Core i7 Extreme Edition Q965 on the X58 MOBO	IronBits	Hardware	17	2008-11-13 18:07
Vista 64 Ultimate Extreme Remix Limited Edition	Timber Jockey	PrimeNet	4	2008-10-20 19:39
Northwood, Prescott Or Extreme Edition?	georgekh	Hardware	13	2005-03-17 06:31

2012-09-04, 05:38	#29
debrouxl Sep 2009 977 Posts	jrk: I'm curious, how many hits does msieve faststage1 produce on the GTX570 in several hours (i.e., how much faster than the GT540M is the GTX570, and does polsel scale better or worse than what mersenne-aries shows for Mersenne TF) ?

2012-09-05, 13:08	#31
poily Nov 2010 62₈ Posts	24 hours of RSA-210 polynomial selection on 1 Tesla X2070 gave me the best murphy_e 7.485e-16 with the faststage1 version and 8.48e-16 with the trunk version. I know the polsel algorithm is essentially a lottery but still do I have to launch msieve with special arguments like -np1 ... instead of just -np to see the difference?

2012-09-05, 16:34	#32
jasonp Tribal Bullet Oct 2004 3,541 Posts	-np will run stage 2, which will spend a lot of time optimizing polynomials that will not be very good. Try running with -np1 -nps X,Y to search leading coefficients between X and Y, then look at the scores of the size-optimized polynomials in msieve.dat.ms (it's the last column) and only run the root optimization (-npr) on the polynomials with the best (lowest) scores.

2012-09-05, 16:50	#33
firejuggler Apr 2010 Over the rainbow 2³×5²×13 Posts	may i remind you of http://mersenneforum.org/showthread.php?t=11989 (2^877-1 poly selec) for a 'mid level" candidate, and to compare the poly?