mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > CADO-NFS

Reply
 
Thread Tools
Old 2021-05-17, 14:42   #23
charybdis
 
charybdis's Avatar
 
Apr 2020

72×11 Posts
Default

Quote:
Originally Posted by VBCurtis View Post
My previous GGNFS/msieve jobs around C165 have had matrices around 9M in size, so this job was rather strongly oversieved. We should cut rels_wanted to 210M for this file and see what matrix comes out.
Msieve always gives larger but sparser matrices though. Still possible this was oversieved, but probably not massively so.

My hunch is that raising tasks.sieve.mfb1 from 62 to 64 would be more effective than using 3LP here. That said, I've got a better idea of what to do with the other parameters than the last time I tried 3LP on a number of roughly this size (see post #2 in this thread). May give it a go in the near future.
charybdis is offline   Reply With Quote
Old 2021-05-18, 07:58   #24
bur
 
bur's Avatar
 
Aug 2020
79*6581e-4;3*2539e-3

3×139 Posts
Default

Thanks for the explanations, slowly I start to get more about what is going on. Interesting, that fundmental things like poly selection or q-range are so little understood that it makes an experimental attempt useful. From the little I could get from math papers, especially poly selection could probably be vastly optimized if we knew more about it.

Quote:
If you are interested in seeing the effect of the extra relations, zcat all your 220M relations out to a single file, and run msieve's filtering on the file to see what size matrix comes out. Then, restrict the number of relations msieve uses (via a filtering flag, see the -h option list for msieve) to 215, 210, 205 and let us know what size matrices pop out. I suggest a TD of 100 or so for msieve, but you might enjoy trying 100/110/120 on the full dataset to see how target_density affects matrix size.
So to just see the effect of fewer relations I'll set TD = 100?

And just to make 100% sure: more relations = faster matrix generation & higher matrix density = smaller matrix size = shorter LA times (not the newspaper, harhar)?
bur is offline   Reply With Quote
Old 2021-05-18, 14:43   #25
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

23×3×211 Posts
Default

No, there's a flag like filter_maxrels that lets you control the number of relations msieve uses.

TD 100 vs TD 110 shows you the effect of using higher target densities for a given set of relations- the difference is not very big. A higher density matrix is slightly tougher to solve than a lower-density matrix of the same size, but matrix size affects time-to-solve much more.

More relations -> smaller matrix.-> shorter LA time.

Higher TD -> makes sure you have enough relations for a reasonably small matrix.

When filtering with msieve, let's say you have 190M relations. TD = 90 might build a matrix 11M in size, while TD 110 fails and asks for more relations. If you use the full 220M relations, TD 90 might build a 7M matrix, while TD 110 builds a 6.5M matrix. The idea is that choosing TD = 110 makes sure you avoid the situation where a matrix barely builds and is quite large (e.g. 11M for this current factorization).
If you actually try these tests, let the matrix-solving step run for 1% completion, and note the ETA (ETA is pretty stable by the time 1% is done). The TD100 and TD110 ETAs won't be very different, I expect.
VBCurtis is offline   Reply With Quote
Old 2021-05-18, 15:00   #26
bur
 
bur's Avatar
 
Aug 2020
79*6581e-4;3*2539e-3

3×139 Posts
Default

What I meant was, if I only want to test various numbers of relations, which value for TD should I chose, 100? Or is there a default value?


Testing different target_densities was that just a proposal for me to see the effects, or are the results helpful to you similar to the various numbers of relations?
bur is offline   Reply With Quote
Old 2021-05-18, 16:27   #27
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

13C816 Posts
Default

Ah, I see- yes, I'd use TD 100 to test various relations counts, because higher TDs may not produce matrices. If TD 100 doesn't produce a matrix, that relations count is too low to be useful to us anyway (I think).

The TD 100 vs 110 is useful to us, but I agree it's more for your personal experience. I haven't done as many such tests as I should, so I am curious just how different the ETAs would be; my own limited testing showed the ETAs are similar enough that I rarely use TD 120 even on jobs I expect would easily build a matrix at that density, since the time spent when filtering fails feels greater than the time saved by using 120 instead of 110.
VBCurtis is offline   Reply With Quote
Old 2021-05-19, 07:02   #28
bur
 
bur's Avatar
 
Aug 2020
79*6581e-4;3*2539e-3

3·139 Posts
Default

I'm still running the tests, results so far show that 185M relations was too few. 190M still worked, LA took from around 14 h (190M) to 8:45 h (220M). Since sieving took 6 1/2 days, doing only 190M would have been quite a gain.

Would it be good to decrease rels_wanted to 190M generally or might this have been an exception? But even 2-3 additional filtering steps would still make the total time shorter.

I will post detailed results later this day.
bur is offline   Reply With Quote
Old 2021-05-19, 17:12   #29
bur
 
bur's Avatar
 
Aug 2020
79*6581e-4;3*2539e-3

6418 Posts
Default

I used this command line ./msieve -i c165.n -s rels.dat -nf c165.fb -t 10 -v -nc1 "filter_maxrels=200000000" afterwards the same with -nc2.

220M rels
Code:
matrix is 6441919 x 6442144 (2334.4 MB) with weight 618273835 (95.97/col)
sparse part has weight 547526160 (84.99/col)
[...]
linear algebra completed 64760 of 6442144 dimensions (1.0%, ETA 8h43m
215M rels
Code:
matrix is 6671510 x 6671738 (2418.3 MB) with weight 640096824 (95.94/col)
sparse part has weight 567230375 (85.02/col)
[...]
linear algebra completed 66759 of 6671738 dimensions (1.0%, ETA 9h28m
210M rels
Code:
matrix is 6881379 x 6881605 (2496.6 MB) with weight 660645774 (96.00/col)
sparse part has weight 585663806 (85.11/col)
[...]
linear algebra completed 72597 of 6881605 dimensions (1.1%, ETA 10h 3m)
205M rels
Code:
matrix is 7102309 x 7102534 (2579.8 MB) with weight 682640424 (96.11/col)
sparse part has weight 605254018 (85.22/col)
[...]
near algebra completed 71317 of 7102534 dimensions (1.0%, ETA 10h53m)
200M rels
Code:
matrix is 7405037 x 7405262 (2691.5 MB) with weight 711821792 (96.12/col)
sparse part has weight 631510830 (85.28/col)
[...]
linear algebra completed 74878 of 7405262 dimensions (1.0%, ETA 11h54m)
195M rels
Code:
matrix is 7779754 x 7779979 (2833.7 MB) with weight 749219145 (96.30/col)
sparse part has weight 665027723 (85.48/col)
[...]
linear algebra completed 77887 of 7779979 dimensions (1.0%, ETA 13h25m)
190M rels
Code:
matrix is 8305557 x 8305782 (3029.3 MB) with weight 800256398 (96.35/col)
sparse part has weight 711056605 (85.61/col)
[...]
 linear algebra completed 87238 of 8305782 dimensions (1.1%, ETA 15h43m)
185M rels
Code:
found 338230 cycles, need 3940439

 too few cycles, matrix probably cannot build
 filtering wants 1000000 more relations
Sieving the 220M relations took 158 hours or about 3.5 hours per 5M relations.


I didn't specify TD, which numbers of relations should I chose for the density comparisons?
bur is offline   Reply With Quote
Old 2021-05-19, 19:03   #30
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

5×1,187 Posts
Default

Quote:
Originally Posted by bur View Post
I didn't specify TD, which numbers of relations should I chose for the density comparisons?
It might be interesting to find the best TD for each number of relations. In theory, the difference should be even more pronounced than with a constant TD.
henryzz is offline   Reply With Quote
Old 2021-05-19, 19:18   #31
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

23·3·211 Posts
Default

Your comparison of 3.5 hrs per 5M rels shows that any oversieving past 190M is inefficient. This surprises me- I would have expected 195 or 200 to be the "sweet spot", where the sieve time spent would be more than or equal to LA time saved.

But, even 195M vs 190M only saves 2hr 20 min LA time at the cost of ~3.5hr sieve time.

If these were all default density, I wonder whether the 96 or the 85 density is the target number- I don't have msieve logs handy to look it up myself, so I'll edit this message later today to correct myself about which of the densities from your logs is the one msieve controls directly. If default is 96 at this size, I doubt TD is going to do much; try TD 100 or 104 or 110 on the 195M relations set to see if you can save another hour of LA time.

Your data also helps someone like Ed, who uses a large farm of ~20 machines to sieve, but just one to LA. Your data at 190.....220 can help him choose how much to sieve.

I think I'll make the params file 190M target; as you say, filtering more than once isn't a big deal if that turns out to not be enough for a C161 or C162. I'll add a note that recommends 200M if sieving on multiple machines.

What CPU architecture is used for these tests? Older CPUs take relatively longer to do the LA section, so might prove to be 3.5hr faster at 195M because the entire LA portion is taking 50% longer. Sieving is less sensitive to CPU architecture than LA. My personal experience is with sandy bridge, ivy bridge, haswell generations of Xeon, all rather old by now.
VBCurtis is offline   Reply With Quote
Old 2021-05-19, 22:55   #32
charybdis
 
charybdis's Avatar
 
Apr 2020

72×11 Posts
Default

Quote:
Originally Posted by VBCurtis View Post
If these were all default density, I wonder whether the 96 or the 85 density is the target number- I don't have msieve logs handy to look it up myself, so I'll edit this message later today to correct myself about which of the densities from your logs is the one msieve controls directly. If default is 96 at this size, I doubt TD is going to do much; try TD 100 or 104 or 110 on the 195M relations set to see if you can save another hour of LA time.
Actually, it's neither. There will be a line from earlier in the filtering that matches TD, looking like this:
Code:
weight of 9242904 cycles is about 924731720 (100.05/cycle)
The default in the latest msieve is density 90, and bur's figures match what I see in my logs for 90.

Re general c165 params: lpb 31/31 is definitely worth testing too, unless you already have data showing 31/32 is faster. I also notice you didn't include adjust_strategy 2, which would probably give a boost of a couple percent. Strategy 2 makes A=28 usable but I don't think it'll be optimal yet at this size. Maybe by c170.
charybdis is offline   Reply With Quote
Old 2021-05-20, 07:45   #33
bur
 
bur's Avatar
 
Aug 2020
79*6581e-4;3*2539e-3

3·139 Posts
Default

Quote:
Originally Posted by henryzz View Post
It might be interesting to find the best TD for each number of relations. In theory, the difference should be even more pronounced than with a constant TD.
So I'll use TD = 90, 100, 110, 120? Which number of rels would be interesting, all I tested so far?

It would make 28 tests, but since filtering is single-threaded I could run 10 simultaneously. Would this work with all processes accessing the same rels.dat?


VBCurtis, it was run on a i10-10900K with 16 GB RAM. Nothing else demanding was running at the same time.


BTW, I am just factoring a C147 with your experimental params.c145, should I keep the relations to do similar tests?

Last fiddled with by bur on 2021-05-20 at 07:47
bur is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Some CADO-NFS Work At Around 175-180 Decimal Digits EdH CADO-NFS 127 2020-10-07 01:47
Sigma parameter in ecm storm5510 Information & Answers 4 2019-11-30 21:32
PrimeNet error 7: Invalid parameter ksteczk PrimeNet 6 2018-03-26 15:11
Parameter Underestimation R.D. Silverman Cunningham Tables 14 2010-09-29 19:56
ECM Work and Parameter Choices R.D. Silverman Cunningham Tables 11 2006-03-06 18:46

All times are UTC. The time now is 02:39.


Sat Nov 27 02:39:25 UTC 2021 up 126 days, 21:08, 0 users, load averages: 1.71, 1.40, 1.31

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.