Call for volunteers: RSA896 - Page 4

frmky · 2012-12-06, 05:35

Quote:

Originally Posted by jasonp

the more effective root sieve developed by Shi Bai

Steal it and put it in msieve?

frmky · 2012-12-11, 22:07

From my 1.3 million stage 1 hits, so far I've gotten a

# norm 4.371817e-20 alpha -11.383344 e 2.347e-19 rroots 4

The run continues...

jasonp · 2012-12-12, 01:49

I sent a batch of hits computed with a cutoff of 5e33 instead of the previous 1e33, and apparently the polynomials generated with the looser cutoff are similar in quality. So if you use 5e33 for the stage1_norm you'll generate hits about 5x faster.

pinhodecarlos · 2012-12-12, 09:17

Quote:

Originally Posted by jasonp

and then run

msieve -v -np1 "stage1_norm=5e33 X,Y"

where X and Y is a range of numbers with magnitude 10^12 to 10^15.

So it's better to update first post.

bai · 2012-12-13, 23:52

Quote:

Originally Posted by poily

Here's my slightly better (according to msieve) polynomial

Code:

SKEW 28338177.70                                                                                                    
R0 -3626941552197564826492128852700460060642852                                                                     
R1 48957407582916194761589                                                                                          
A0 -26101732745933806144485280988037796254029367990700826499285                                                     
A1 -2408464141902741608017790242140644715688145388490381                                                            
A2 -174314770228113076791419006080421369720970639                                                                   
A3 28697722660097589508721192118263624637                                                                           
A4 1036456362256909021188219944324                                                                                  
A5 -21292410351587764080336                                                                                         
A6 181000001476800 
skew 28338177.70, size 4.381e-20, alpha -12.189, combined = 2.348e-19 rroots = 2

jasonp, what score does CADO show for your or my polynomial?

Hi poily, in cado, it's

Code:

Y1: 48957407582916194761589
Y0: -3626941552197564826492128852700460060642852
c6: 181000001476800
c5: -21292410351587764080336
c4: 1036456362256909021188219944324
c3: 28697722660097589508721192118263624637
c2: -174314770228113076791419006080421369720970639
c1: -2408464141902741608017790242140644715688145388490381
c0: -26101732745933806144485280988037796254029367990700826499285
skew: 20504576.000
# lognorm: 83.45, alpha: -12.19 (proj: -3.18), E: 71.26, nr: 2
# MurphyE(Bf=10000000,Bg=5000000,area=1.00e+16)=3.39e-19

jasonp · 2012-12-14, 01:30

Msieve computes an E-value of 2.339e-19 when using the skew computed by CADO. Would it be worthwhile to find out what causes such big differences?

poily · 2012-12-14, 09:31

Ok, here are about 1.8M hits for the new bound 5e33. It seems the tighter bound was better: with 1e33 as a bound on stage 1 after size optimizations I saw norms of about Xe32 whereas the new bound gives only Xe33 and worse. The best e for this pack was about 2.2e-19.

Bai, I used E.sage from the public CADO repository and got almost the same Murphy e values as msieve shows. Do you compute it somehow different now?

Dubslow · 2012-12-14, 16:13

Quote:

Originally Posted by jasonp

Would it be worthwhile to find out what causes such big differences?

As a bystander who has no knowledge of either how to go about such finding out or how much work it might be, I would be very interested in the results.

(poily's post directly above this makes it all the more interesting!)

debrouxl · 2012-12-14, 16:26

For the purposes of generating several hits with CPUs (as I can't currently use my GPU...) more quickly, I resurrected poily's MPI polsel patch, from http://www.mersenneforum.org/showpos...39&postcount=9 .
Mainline msieve changed somewhat since then (e.g. separation of the size optimization and the root sieve), so I started by upgrading and expanding the additions to the code; I also changed whitespace to follow the coding convention of the surrounding code more closely

That allowed the computer to produce a number of hits with:
$ mpirun -n 6 msieve -np1 "stage1_norm=2e33 1100000000000,1100010000000" -v

I think it would be great to see the MPI polsel patch integrated to mainline msieve. This way, every user of multi-threaded polsel (even on a single computer) would benefit without having to apply (and upgrade) an out of tree patch

However, AFAICS, the patch requires improvements before this can happen. Indeed, I noticed that when a child process has finished working ("polynomial selection complete"), it sticks its core to 100% usage. One of the processes found no suitable leading coefficient in its range and gave up on polsel immediately; after ~2h47 of CPU time wasted by that one, soon after another process had exhausted its range as well, I tried to kill one of the inactive processes... which killed all of its siblings, as I should have expected...
293 stage 1 hits generated in ~10h40 CPU time on Xeon E3-1230 @ 3.2 GHz.

I have zero MPI experience, and therefore, no clue how to make finished jobs not waste significant CPU power

jasonp · 2012-12-14, 18:01

The patch makes all the MPI processes wait at a barrier when poly selection is finishing, and my experience with OpenMPI is that this is a computationally expensive operation. I suspect that's what is burning up 100% CPU.

Unfortunately there's no real way around that, if you wanted processes to stop waiting on each other then you wouldn't be using barrier synchronization; put another way, MPI is a poor substitute for a distributed client-server architecture :)

firejuggler · 2012-12-14, 20:22

ran a 15 min 'search' on a 560, got 227 hit, best poly

Code:

Fri Dec 14 21:18:19 2012  Msieve v. 1.51 (SVN 766)
Fri Dec 14 21:18:19 2012  random seeds: ccf343ec 7dcd68de
Fri Dec 14 21:18:19 2012  factoring 412023436986659543855531365332575948179811699844327982845455626433876445565248426198098870423161841879261420247188869492560931776375033421130982397485150944909106910269861031862704114880866970564902903653658867433731720813104105190864254793282601391257624033946373269391 (270 digits)
Fri Dec 14 21:18:21 2012  no P-1/P+1/ECM available, skipping
Fri Dec 14 21:18:21 2012  commencing number field sieve (270-digit input)
Fri Dec 14 21:18:21 2012  commencing number field sieve polynomial selection
Fri Dec 14 21:18:21 2012  polynomial degree: 6
Fri Dec 14 21:18:21 2012  max stage 1 norm: 1.08e+035
Fri Dec 14 21:18:21 2012  max stage 2 norm: 1.05e+035
Fri Dec 14 21:18:21 2012  min E-value: 0.00e+000
Fri Dec 14 21:18:21 2012  poly select deadline: 1079999
Fri Dec 14 21:20:02 2012  polynomial selection complete
Fri Dec 14 21:20:02 2012  R0: -3334009071282816277832905784211277620964254
Fri Dec 14 21:20:02 2012  R1: 100281358245707420758237
Fri Dec 14 21:20:02 2012  A0: 372828901627475347894334652824133151170797461276260673
Fri Dec 14 21:20:02 2012  A1: 77826863799406908305447316219479205604506482315
Fri Dec 14 21:20:02 2012  A2: -8440449792077225990613216882014698768493181
Fri Dec 14 21:20:02 2012  A3: -434343399475320970345769932599595433
Fri Dec 14 21:20:02 2012  A4: 27102576369602076901509411656588
Fri Dec 14 21:20:02 2012  A5: 139702468047107462100798
Fri Dec 14 21:20:02 2012  A6: 300000002082000
Fri Dec 14 21:20:02 2012  skew 1498026.43, size 1.811e-020, alpha -8.436, combined = 1.092e-019 rroots = 4

(yeah I know, score is pretty bad, but thats a 15 min run)
and the msieve.dat.m file to be run in cado

2012-12-14, 09:31	#40
poily Nov 2010 50₁₀ Posts	Ok, here are about 1.8M hits for the new bound 5e33. It seems the tighter bound was better: with 1e33 as a bound on stage 1 after size optimizations I saw norms of about Xe32 whereas the new bound gives only Xe33 and worse. The best e for this pack was about 2.2e-19. Bai, I used E.sage from the public CADO repository and got almost the same Murphy e values as msieve shows. Do you compute it somehow different now? Last fiddled with by poily on 2012-12-14 at 09:35

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Volunteers needed	axn	GPU Computing	28	2012-05-28 12:05
call for volunteers: RSA768 polynomial selection	jasonp	Operation Kibibit	200	2011-11-05 21:31
Call for help	Wacky	NFSNET Discussion	13	2005-07-14 00:25
Volunteers needed!	Xyzzy	Hardware	23	2003-04-18 23:27
We need two volunteers...	Xyzzy	PrimeNet	8	2003-02-27 02:26

2012-12-11, 22:07	#35
frmky Jul 2003 So Cal 3·5·137 Posts	From my 1.3 million stage 1 hits, so far I've gotten a # norm 4.371817e-20 alpha -11.383344 e 2.347e-19 rroots 4 The run continues...

2012-12-12, 01:49	#36
jasonp Tribal Bullet Oct 2004 2×3×19×31 Posts	I sent a batch of hits computed with a cutoff of 5e33 instead of the previous 1e33, and apparently the polynomials generated with the looser cutoff are similar in quality. So if you use 5e33 for the stage1_norm you'll generate hits about 5x faster.

2012-12-14, 01:30	#39
jasonp Tribal Bullet Oct 2004 2×3×19×31 Posts	Msieve computes an E-value of 2.339e-19 when using the skew computed by CADO. Would it be worthwhile to find out what causes such big differences?

2012-12-14, 18:01	#43
jasonp Tribal Bullet Oct 2004 2×3×19×31 Posts	The patch makes all the MPI processes wait at a barrier when poly selection is finishing, and my experience with OpenMPI is that this is a computationally expensive operation. I suspect that's what is burning up 100% CPU. Unfortunately there's no real way around that, if you wanted processes to stop waiting on each other then you wouldn't be using barrier synchronization; put another way, MPI is a poor substitute for a distributed client-server architecture :)