Msieve 1.53 feedback - Page 5

jasonp · 2015-05-06, 13:20

Can someone verify whether changing the above to use '-march=native' works now with Apple's gcc? Last time I checked (2009), it didn't.

jyb · 2015-05-20, 22:17

Quote:

Originally Posted by jasonp

Can someone verify whether changing the above to use '-march=native' works now with Apple's gcc? Last time I checked (2009), it didn't.

I can verify that it successfully compiles with that change. I haven't tried any timing tests yet.

jyb · 2015-05-20, 22:22

There's some code in the murphy score calculator that causes writes off the end of an array if the algebraic polynomial has degree 8. On my machines this causes a crash due to the stack being smashed.

This patch fixes it:

Code:

Index: gnfs/poly/size_score.c
===================================================================
--- gnfs/poly/size_score.c	(revision 984)
+++ gnfs/poly/size_score.c	(working copy)
@@ -381,8 +381,8 @@
 	uint32 i, j, k;
 	uint32 deg = poly->degree;
 	double *coeff = poly->coeff;
-	double xbinom[MAX_POLY_DEGREE][MAX_POLY_DEGREE+1];
-	double ybinom[MAX_POLY_DEGREE][MAX_POLY_DEGREE+1];
+	double xbinom[MAX_POLY_DEGREE+1][MAX_POLY_DEGREE+1];
+	double ybinom[MAX_POLY_DEGREE+1][MAX_POLY_DEGREE+1];
 	double sum[MAX_POLY_DEGREE+1];
 	double *xrow, *yrow;
 	double res;

I can give more details if needed.

ChristianB · 2015-06-05, 07:58

Hi, I monitored my GPU utilization while msieve polynomial selection was running and there was almost no utilization at all. I suspected that it is not working but the log file tells me otherwise. So my question is how to determine if msieve actually uses the GPU?

During plynomial selection msieve only uses one of my 4 cores. GPU processing (with CUDA) in general works fine with the Einstein@home BOINC project.

Code:

Fri Jun 05 09:23:15 2015 -> factmsieve.py (v0.76)
Fri Jun 05 09:23:15 2015 -> This is client 1 of 1
Fri Jun 05 09:23:15 2015 -> Running on 4 Cores with 1 hyper-thread per Core
Fri Jun 05 09:23:15 2015 -> Working with NAME = test
Fri Jun 05 09:23:15 2015 -> Running polynomial selection ...
Fri Jun  5 09:23:15 2015  
Fri Jun  5 09:23:15 2015  
Fri Jun  5 09:23:15 2015  Msieve v. 1.53 (SVN 984)
Fri Jun  5 09:23:15 2015  random seeds: f70e728d 3365454f
Fri Jun  5 09:23:15 2015  factoring 98650581114479552852343603025318895159272210247065459576715937633611628188885221127215976582022103 (98 digits)
Fri Jun  5 09:23:15 2015  commencing number field sieve (98-digit input)
Fri Jun  5 09:23:15 2015  commencing number field sieve polynomial selection
Fri Jun  5 09:23:15 2015  polynomial degree: 4
Fri Jun  5 09:23:15 2015  max stage 1 norm: 7.28e+16
Fri Jun  5 09:23:15 2015  max stage 2 norm: 2.29e+15
Fri Jun  5 09:23:15 2015  min E-value: 1.05e-08
Fri Jun  5 09:23:15 2015  poly select deadline: 1162
Fri Jun  5 09:23:15 2015  time limit set to 0.32 CPU-hours
Fri Jun  5 09:23:15 2015  expecting poly E from 1.76e-08 to > 2.03e-08
Fri Jun  5 09:23:15 2015  searching leading coefficients from 1 to 48871280
Fri Jun  5 09:23:15 2015  using GPU 0 (GeForce GTX 750 Ti)
Fri Jun  5 09:23:15 2015  selected card has CUDA arch 5.0
Fri Jun  5 09:44:48 2015  polynomial selection complete
Fri Jun  5 09:44:48 2015  R0: -653773818955430513706546
Fri Jun  5 09:44:48 2015  R1: 1215460131941
Fri Jun  5 09:44:48 2015  A0: 3556417201381026586634823091
Fri Jun  5 09:44:48 2015  A1: 6760589081435238349864
Fri Jun  5 09:44:48 2015  A2: -9264578801542487
Fri Jun  5 09:44:48 2015  A3: -2816454360
Fri Jun  5 09:44:48 2015  A4: 540
Fri Jun  5 09:44:48 2015  skew 2499815.11, size 1.548e-13, alpha -5.014, combined = 1.474e-08 rroots = 4
Fri Jun  5 09:44:48 2015  elapsed time 00:21:33

fivemack · 2015-06-05, 09:02

This is a parameterisation issue; with the default parameters, the -np1 pass on the GPU produces candidates much more quickly than the CPU-dependent passes can deal with them, so, whilst the GPU is being used, it is often idle.

When doing large runs, I run -np1 with a stage-1 norm picked so I'm getting a reasonable rate of candidate production (I look for somewhere between 10 and 100 candidates per second; IIRC doubling stage1_norm gets you about ten times as many candidates in about five times the runtime, but it's worth checking that empirically) and then aim to cut down wildly in post-processing - I run -nps on a 0.1% sample of the -np1 output file and pick the second-highest observed norm as the target stage2_norm for the main run. The output file from -np1 can be cut into as many chunks as you want and have -nps/-npr run on each chunk in parallel.

Note that, even when I had GPUs available, I generally didn't bother using GPU polynomial selection on numbers less than 512 bits; but I have quite a wide queue and quite a lot of CPUs, so leaving one of 48 cores running msieve for ten days was a perfectly effective lazy way to proceed.

If people are using factmsieve.py on actually-large numbers I should probably consider implementing an automatic version of the calibration process.

firejuggler · 2015-06-27, 16:32

1.51 had a gpu version. is there a 1.53 gpu version ( windows?)

henryzz · 2015-06-27, 21:21

Quote:

Originally Posted by firejuggler

1.51 had a gpu version. is there a 1.53 gpu version ( windows?)

I could also do with a version which runs on a core 2.

jasonp · 2015-07-01, 13:34

Nothing in the poly selection code is different between 1.52 and 1.53. Also, the latest CUDA toolkit does not want the ancient MSVC2008 express version I had been using to keep it happy, so I need the time to install the 2013Visual Studio compiler.

chris2be8 · 2015-07-27, 15:54

Hello,

One job I've run has a segmentation fault during -nc1. The log contains:

Code:

Mon Jul 27 04:43:38 2015 =>nice -n 19  "/home/chris/ggnfs/trunk/bin/msieve" -s m42463_37.dat -l m42463_37.log -i m42463_37.ini -v -nf m42463_37.fb -t 3 -nc1
Mon Jul 27 04:43:38 2015
Mon Jul 27 04:43:38 2015
Mon Jul 27 04:43:38 2015  Msieve v. 1.52 (SVN 956)
Mon Jul 27 04:43:38 2015  random seeds: fff24941 348eb9cb
Mon Jul 27 04:43:38 2015  factoring 4058770369178367583462936689816080729092492803658359213413005553936582466283493371442095770487282083639 0933543547593306131570956988156579323512106138663303453675152961 (167 digits)
Mon Jul 27 04:43:39 2015  searching for 15-digit factors
Mon Jul 27 04:43:40 2015  commencing number field sieve (167-digit input)
Mon Jul 27 04:43:40 2015  R0: 5862246044108162244450441409
Mon Jul 27 04:43:40 2015  R1: -1
Mon Jul 27 04:43:40 2015  A0: -1
Mon Jul 27 04:43:40 2015  A1: 0
Mon Jul 27 04:43:40 2015  A2: 0
Mon Jul 27 04:43:40 2015  A3: 0
Mon Jul 27 04:43:40 2015  A4: 0
Mon Jul 27 04:43:40 2015  A5: 0
Mon Jul 27 04:43:40 2015  A6: 42463
Mon Jul 27 04:43:40 2015  skew 0.17, size 1.006e-08, alpha -0.524, combined = 7.621e-11 rroots = 2
Mon Jul 27 04:43:40 2015
Mon Jul 27 04:43:40 2015  commencing relation filtering
Mon Jul 27 04:43:40 2015  estimated available RAM is 15941.3 MB
Mon Jul 27 04:43:40 2015  commencing duplicate removal, pass 1
Mon Jul 27 04:45:10 2015  found 1971050 hash collisions in 19106144 relations
Mon Jul 27 04:45:23 2015  added 1204588 free relations
Mon Jul 27 04:45:23 2015  commencing duplicate removal, pass 2
Mon Jul 27 04:45:28 2015  found 1560729 duplicates and 18750003 unique relations
Mon Jul 27 04:45:28 2015  memory use: 69.3 MB
Mon Jul 27 04:45:28 2015  reading ideals above 720000
Mon Jul 27 04:45:28 2015  commencing singleton removal, initial pass
Mon Jul 27 04:47:33 2015  memory use: 689.0 MB
Mon Jul 27 04:47:33 2015  reading all ideals from disk
Mon Jul 27 04:47:33 2015  memory use: 568.5 MB
Mon Jul 27 04:47:34 2015  keeping 22365672 ideals with weight <= 200, target excess is 116358
Mon Jul 27 04:47:35 2015  commencing in-memory singleton removal
Mon Jul 27 04:47:36 2015  begin with 18750003 relations and 22365672 unique ideals
Mon Jul 27 04:47:47 2015  reduce to 5953192 relations and 5741810 ideals in 23 passes
Mon Jul 27 04:47:47 2015  max relations containing the same ideal: 93
Mon Jul 27 04:47:49 2015  removing 556781 relations and 518578 ideals in 38203 cliques
Mon Jul 27 04:47:49 2015  commencing in-memory singleton removal
Mon Jul 27 04:47:49 2015  begin with 5396411 relations and 5741810 unique ideals
Mon Jul 27 04:47:53 2015  reduce to 5339057 relations and 5165302 ideals in 11 passes
Mon Jul 27 04:47:53 2015  max relations containing the same ideal: 82
Mon Jul 27 04:47:55 2015  removing 399720 relations and 361517 ideals in 38203 cliques
Mon Jul 27 04:47:55 2015  commencing in-memory singleton removal
Mon Jul 27 04:47:55 2015  begin with 4939337 relations and 5165302 unique ideals
Mon Jul 27 04:47:58 2015  reduce to 4908790 relations and 4772966 ideals in 10 passes
Mon Jul 27 04:47:58 2015  max relations containing the same ideal: 78
Mon Jul 27 04:48:00 2015  relations with 0 large ideals: 4884
Mon Jul 27 04:48:00 2015  relations with 1 large ideals: 1799
Mon Jul 27 04:48:00 2015  relations with 2 large ideals: 29891
Mon Jul 27 04:48:00 2015  relations with 3 large ideals: 195675
Mon Jul 27 04:48:00 2015  relations with 4 large ideals: 668761
Mon Jul 27 04:48:00 2015  relations with 5 large ideals: 1288188
Mon Jul 27 04:48:00 2015  relations with 6 large ideals: 1402209
Mon Jul 27 04:48:00 2015  relations with 7+ large ideals: 1317383
Mon Jul 27 04:48:00 2015  commencing 2-way merge
Mon Jul 27 04:48:03 2015  reduce to 2698840 relation sets and 2563029 unique ideals
Mon Jul 27 04:48:03 2015  ignored 13 oversize relation sets
Mon Jul 27 04:48:03 2015  commencing full merge
Mon Jul 27 04:48:34 2015  memory use: 286.9 MB
Mon Jul 27 04:48:34 2015  found 1344643 cycles, need 1331229
Mon Jul 27 04:48:34 2015  weight of 1331229 cycles is about 93401364 (70.16/cycle)
Mon Jul 27 04:48:34 2015  distribution of cycle lengths:
Mon Jul 27 04:48:34 2015  1 relations: 182702
Mon Jul 27 04:48:34 2015  2 relations: 163540
Mon Jul 27 04:48:34 2015  3 relations: 157040
Mon Jul 27 04:48:34 2015  4 relations: 137550
Mon Jul 27 04:48:34 2015  5 relations: 116115
Mon Jul 27 04:48:34 2015  6 relations: 99717
Mon Jul 27 04:48:34 2015  7 relations: 84097
Mon Jul 27 04:48:34 2015  8 relations: 69249
Mon Jul 27 04:48:34 2015  9 relations: 57787
Mon Jul 27 04:48:34 2015  10+ relations: 263432
Mon Jul 27 04:48:34 2015  heaviest cycle: 26 relations
Mon Jul 27 04:48:34 2015  commencing cycle optimization
Mon Jul 27 04:48:36 2015  start with 7991296 relations
Mon Jul 27 04:48:44 2015 Return value 35584. Terminating...

I re-ran with the latest version I had installed, with very similar results. Then I tried:

Code:

chris@4core ~/ggnfs/trunk/tests/3core/m42463_37 $ sort -ur m42463_37.dat > m42463_37.sorted
chris@4core ~/ggnfs/trunk/tests/3core/m42463_37 $ mv m42463_37.dat m42463_37.dat.orig
chris@4core ~/ggnfs/trunk/tests/3core/m42463_37 $ mv m42463_37.sorted m42463_37.dat

And a re-run (with -nc instead of -nc1) worked:

Code:

Mon Jul 27 13:57:26 2015  Msieve v. 1.53 (SVN 967M)
Mon Jul 27 13:57:26 2015  random seeds: 04386fe3 73e98872
Mon Jul 27 13:57:26 2015  factoring 4058770369178367583462936689816080729092492803658359213413005553936582466283493371442095770487282083639 0933543547593306131570956988156579323512106138663303453675152961 (167 digits)
Mon Jul 27 13:57:26 2015  no P-1/P+1/ECM available, skipping
Mon Jul 27 13:57:26 2015  commencing number field sieve (167-digit input)
Mon Jul 27 13:57:26 2015  R0: 5862246044108162244450441409
Mon Jul 27 13:57:26 2015  R1: -1
Mon Jul 27 13:57:26 2015  A0: -1
Mon Jul 27 13:57:26 2015  A1: 0
Mon Jul 27 13:57:26 2015  A2: 0
Mon Jul 27 13:57:26 2015  A3: 0
Mon Jul 27 13:57:26 2015  A4: 0
Mon Jul 27 13:57:26 2015  A5: 0
Mon Jul 27 13:57:26 2015  A6: 42463
Mon Jul 27 13:57:26 2015  skew 0.17, size 1.006e-08, alpha -0.524, combined = 7.621e-11 rroots = 2
Mon Jul 27 13:57:26 2015
Mon Jul 27 13:57:26 2015  commencing relation filtering
Mon Jul 27 13:57:26 2015  estimated available RAM is 15941.3 MB
Mon Jul 27 13:57:26 2015  commencing duplicate removal, pass 1
Mon Jul 27 13:59:53 2015  found 2528105 hash collisions in 20310731 relations
Mon Jul 27 14:00:03 2015  commencing duplicate removal, pass 2
Mon Jul 27 14:00:08 2015  found 1560728 duplicates and 18750003 unique relations
Mon Jul 27 14:00:08 2015  memory use: 82.6 MB
Mon Jul 27 14:00:08 2015  reading ideals above 720000
Mon Jul 27 14:00:08 2015  commencing singleton removal, initial pass
Mon Jul 27 14:02:19 2015  memory use: 689.0 MB
Mon Jul 27 14:02:19 2015  reading all ideals from disk
Mon Jul 27 14:02:19 2015  memory use: 568.5 MB
Mon Jul 27 14:02:20 2015  keeping 22365672 ideals with weight <= 200, target excess is 116358
Mon Jul 27 14:02:21 2015  commencing in-memory singleton removal
Mon Jul 27 14:02:22 2015  begin with 18750003 relations and 22365672 unique ideals
Mon Jul 27 14:02:34 2015  reduce to 5953192 relations and 5741810 ideals in 23 passes
Mon Jul 27 14:02:34 2015  max relations containing the same ideal: 93
Mon Jul 27 14:02:36 2015  removing 556781 relations and 518578 ideals in 38203 cliques
Mon Jul 27 14:02:36 2015  commencing in-memory singleton removal
Mon Jul 27 14:02:36 2015  begin with 5396411 relations and 5741810 unique ideals
Mon Jul 27 14:02:40 2015  reduce to 5339057 relations and 5165302 ideals in 10 passes
Mon Jul 27 14:02:40 2015  max relations containing the same ideal: 82
Mon Jul 27 14:02:42 2015  removing 399720 relations and 361517 ideals in 38203 cliques
Mon Jul 27 14:02:42 2015  commencing in-memory singleton removal
Mon Jul 27 14:02:42 2015  begin with 4939337 relations and 5165302 unique ideals
Mon Jul 27 14:02:46 2015  reduce to 4908790 relations and 4772966 ideals in 10 passes
Mon Jul 27 14:02:46 2015  max relations containing the same ideal: 78
Mon Jul 27 14:02:48 2015  relations with 0 large ideals: 4884
Mon Jul 27 14:02:48 2015  relations with 1 large ideals: 1799
Mon Jul 27 14:02:48 2015  relations with 2 large ideals: 29891
Mon Jul 27 14:02:48 2015  relations with 3 large ideals: 195675
Mon Jul 27 14:02:48 2015  relations with 4 large ideals: 668761
Mon Jul 27 14:02:48 2015  relations with 5 large ideals: 1288188
Mon Jul 27 14:02:48 2015  relations with 6 large ideals: 1402209
Mon Jul 27 14:02:48 2015  relations with 7+ large ideals: 1317383
Mon Jul 27 14:02:48 2015  commencing 2-way merge
Mon Jul 27 14:02:51 2015  reduce to 2698840 relation sets and 2563029 unique ideals
Mon Jul 27 14:02:51 2015  ignored 13 oversize relation sets
Mon Jul 27 14:02:51 2015  commencing full merge
Mon Jul 27 14:03:26 2015  memory use: 286.9 MB
Mon Jul 27 14:03:26 2015  found 1344567 cycles, need 1331229
Mon Jul 27 14:03:27 2015  weight of 1331229 cycles is about 93395168 (70.16/cycle)
Mon Jul 27 14:03:27 2015  distribution of cycle lengths:
Mon Jul 27 14:03:27 2015  1 relations: 182674
Mon Jul 27 14:03:27 2015  2 relations: 163909
Mon Jul 27 14:03:27 2015  3 relations: 156863
Mon Jul 27 14:03:27 2015  4 relations: 138016
Mon Jul 27 14:03:27 2015  5 relations: 116158
Mon Jul 27 14:03:27 2015  6 relations: 99335
Mon Jul 27 14:03:27 2015  7 relations: 84021
Mon Jul 27 14:03:27 2015  8 relations: 69146
Mon Jul 27 14:03:27 2015  9 relations: 57674
Mon Jul 27 14:03:27 2015  10+ relations: 263433
Mon Jul 27 14:03:27 2015  heaviest cycle: 26 relations
Mon Jul 27 14:03:27 2015  commencing cycle optimization
Mon Jul 27 14:03:29 2015  start with 7991107 relations
Mon Jul 27 14:03:38 2015  pruned 142768 relations
Mon Jul 27 14:03:38 2015  memory use: 275.0 MB
Mon Jul 27 14:03:38 2015  distribution of cycle lengths:
Mon Jul 27 14:03:38 2015  1 relations: 182674
Mon Jul 27 14:03:38 2015  2 relations: 166908
Mon Jul 27 14:03:38 2015  3 relations: 161235
Mon Jul 27 14:03:38 2015  4 relations: 139964
Mon Jul 27 14:03:38 2015  5 relations: 117960
Mon Jul 27 14:03:38 2015  6 relations: 99770
Mon Jul 27 14:03:38 2015  7 relations: 84070
Mon Jul 27 14:03:38 2015  8 relations: 68673
Mon Jul 27 14:03:38 2015  9 relations: 56834
Mon Jul 27 14:03:38 2015  10+ relations: 253141
Mon Jul 27 14:03:38 2015  heaviest cycle: 25 relations
Mon Jul 27 14:03:40 2015  RelProcTime: 374
Mon Jul 27 14:03:40 2015
Mon Jul 27 14:03:40 2015  commencing linear algebra
Mon Jul 27 14:03:40 2015  read 1331229 cycles
Mon Jul 27 14:03:42 2015  cycles contain 4704458 unique relations
Mon Jul 27 14:04:05 2015  read 4704458 relations
Mon Jul 27 14:04:10 2015  using 20 quadratic characters above 268434392
Mon Jul 27 14:04:27 2015  building initial matrix
Mon Jul 27 14:05:01 2015  memory use: 560.8 MB
Mon Jul 27 14:05:01 2015  read 1331229 cycles
Mon Jul 27 14:05:01 2015  matrix is 1359115 x 1331229 (401.4 MB) with weight 118060741 (88.69/col)
Mon Jul 27 14:05:01 2015  sparse part has weight 90573219 (68.04/col)
Mon Jul 27 14:05:13 2015  filtering completed in 2 passes
Mon Jul 27 14:05:13 2015  matrix is 1330029 x 1315564 (396.9 MB) with weight 116701662 (88.71/col)
Mon Jul 27 14:05:13 2015  sparse part has weight 89569488 (68.08/col)
Mon Jul 27 14:05:19 2015  matrix starts at (0, 0)
Mon Jul 27 14:05:19 2015  matrix is 1330029 x 1315564 (396.9 MB) with weight 116701662 (88.71/col)
Mon Jul 27 14:05:19 2015  sparse part has weight 89569488 (68.08/col)
Mon Jul 27 14:05:19 2015  matrix needs more columns than rows; try adding 2-3% more relations

I'll sieve a few more relations and re-try msieve in a few days.

I have a backup of all file in the directory from after the first run failed. Would it help debugging?

Chris

jasonp · 2015-07-31, 02:16

Yes, this looks like the large dataset bug, on a dataset that is not very large.

henryzz · 2015-07-31, 13:52

Quote:

Originally Posted by jasonp

Yes, this looks like the large dataset bug, on a dataset that is not very large.

Presumably a good test set then.

2015-06-05, 09:02	#49
fivemack (loop (#_fork)) Feb 2006 Cambridge, England 7²·131 Posts	This is a parameterisation issue; with the default parameters, the -np1 pass on the GPU produces candidates much more quickly than the CPU-dependent passes can deal with them, so, whilst the GPU is being used, it is often idle. When doing large runs, I run -np1 with a stage-1 norm picked so I'm getting a reasonable rate of candidate production (I look for somewhere between 10 and 100 candidates per second; IIRC doubling stage1_norm gets you about ten times as many candidates in about five times the runtime, but it's worth checking that empirically) and then aim to cut down wildly in post-processing - I run -nps on a 0.1% sample of the -np1 output file and pick the second-highest observed norm as the target stage2_norm for the main run. The output file from -np1 can be cut into as many chunks as you want and have -nps/-npr run on each chunk in parallel. Note that, even when I had GPUs available, I generally didn't bother using GPU polynomial selection on numbers less than 512 bits; but I have quite a wide queue and quite a lot of CPUs, so leaving one of 48 cores running msieve for ten days was a perfectly effective lazy way to proceed. If people are using factmsieve.py on actually-large numbers I should probably consider implementing an automatic version of the calibration process. Last fiddled with by fivemack on 2015-06-05 at 09:04

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Msieve 1.50 feedback	firejuggler	Msieve	99	2013-02-17 11:53
Msieve v1.48 feedback	Jeff Gilchrist	Msieve	48	2011-06-10 18:18
Msieve 1.43 feedback	Jeff Gilchrist	Msieve	47	2009-11-24 15:53
Msieve 1.42 feedback	Andi47	Msieve	167	2009-10-18 19:37
Msieve 1.41 Feedback	Batalov	Msieve	130	2009-06-09 16:01

2015-05-06, 13:20	#45
jasonp Tribal Bullet Oct 2004 3,541 Posts	Can someone verify whether changing the above to use '-march=native' works now with Apple's gcc? Last time I checked (2009), it didn't.

2015-06-27, 16:32	#50
firejuggler Apr 2010 Over the rainbow 101000101000₂ Posts	1.51 had a gpu version. is there a 1.53 gpu version ( windows?)

2015-07-01, 13:34	#52
jasonp Tribal Bullet Oct 2004 6725₈ Posts	Nothing in the poly selection code is different between 1.52 and 1.53. Also, the latest CUDA toolkit does not want the ancient MSVC2008 express version I had been using to keep it happy, so I need the time to install the 2013Visual Studio compiler.

2015-07-31, 02:16	#54
jasonp Tribal Bullet Oct 2004 3,541 Posts	Yes, this looks like the large dataset bug, on a dataset that is not very large.