mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Msieve

Reply
 
Thread Tools
Old 2019-05-26, 00:46   #1
wreck
 
wreck's Avatar
 
"Bo Chen"
Oct 2005
Wuhan,China

163 Posts
Default NFS Square Root failed

When factoring R507, we meet a problem at the stage of square root.
the log is something like

Code:
Msieve v. 1.54 (SVN 1018)
Sat May 25 15:07:05 2019
random seeds: 793bae58 dd6e995c
factoring 46802612901958501868841642965751124516436202272587430374287737787818526612306217484595957815607978887434356766596560265669642422106894901815250576734687838908431237216708427946009827065503443998015551 (200 digits)
searching for 15-digit factors
commencing number field sieve (200-digit input)
R0: -489207429141011531399145000684883987953
R1: 4672294682135028058
A0: -1141622752347875247016534173692198727370239170296
A1: 606229025806036192373697162986942868196
A2: 142633534281473766366139546615926
A3: -540694411833242620565099
A4: -2965749858137203
A5: 3340680
skew 269920746.28, size 1.143e-019, alpha -7.036, combined = 4.526e-015 rroots = 3

commencing square root phase
handling dependencies 1 to 64
reading relations for dependency 1
read 20047248 cycles
cycles contain 70891558 unique relations
read 70891558 relations
multiplying 70891558 relations
GNU MP: Cannot allocate memory (size=4294914080)

C:\GNFS507\SU>
This computer has 64GB memory, and I look at the task manager each minute.
When running msieve, I close most of the other programmes, the free memory is about 50 GB.
The maximum memory msieve use is about 6GB.
I am not sure why it can not allocate 4.29GB memory.
I look at the msieve code, and found that there is a function named multiply_relations,
it is a recursive function, in our case,
index1 = 0, index2 = 70891557
The maximum recursive depth is about 27.
There are frequent memory alloc and free in this function, I am not sure
whether there is connection between the 'not enough memory' and frequent alloc and free operation.
I also record the memory and CPU msieve use each minutes,

Code:
CPU  MEM         Time    hint
6.3% 3.075,8 MB  21:08   cycles contains ...
6.5% 3.594,1 MB  21:08   
6.3% 4.185,1 MB  21:09
6.1% 5.066,1 MB  21:10
6.7% 8.190,1 MB  21:15   read 70891558 ...
7.1% 9.019,8 MB  21:16   
6.4% 1.172,6 MB  21:22   multiplying ...
6.7% 1.492,0 MB  21:24   
6.6% 2.072,8 MB  21:29
6.9% 3.025,5 MB  21:55
7.0% 4.275,5 MB  21:58
6.7% 3.261,2 MB  22:13
6.9% 5.005,1 MB  22:36
7.1% 6,045.1 MB  22:39
exit             22:50    GNU MP: Cannot allocate memory (size=4294914080)
I am trying to remove the recursive by one by one in function multiply_relations

Code:
/*
remove the recursion, to reduce the memory use.
author: boc
date:2019-05-25
*/
static void multiply_relations(relation_prod_t *prodinfo, 
			uint32 index1, uint32 index2,
			mpz_poly_t *prod) {

	/* multiply together the relations from index1 
	   to index2, inclusive. We proceed recursively to
	   assure that polynomials with approximately equal-
	   size coefficients get multiplied, and also to
	   avoid wasting huge amounts of memory in the
	   beginning when all the polynomials are small
	   but the memory allocated for them is large */

	uint32 i;
	mpz_poly_t prod1, prod2;

	if (index1 == index2) {
		/* base case of recursion */

		relation_to_poly(prodinfo->rlist + index1,
				 prodinfo->c, prod);
		return;
	}

	mpz_poly_init(&prod1);
	mpz_poly_init(&prod2);
	
	if (index1 == index2 - 1) {
		/* base case of recursion */

		/*relation_to_poly(prodinfo->rlist + index1,
				 prodinfo->c, &prod1);
		relation_to_poly(prodinfo->rlist + index2,
				 prodinfo->c, &prod2);
				 */
	}
	else {
		/* recursively compute the product of the first
		   half and the last half of the relations */

		/* uint32 mid = (index1 + index2) / 2;
		multiply_relations(prodinfo, index1, mid, &prod1);
		multiply_relations(prodinfo, mid + 1, index2, &prod2);
		remove recursive code.
		*/
	}
	
	relation_to_poly(prodinfo->rlist + index1,
				 prodinfo->c, &prod1);
	for (i = index1 + 1; i <= index2; i++) {
		relation_to_poly(prodinfo->rlist + i,
				 prodinfo->c, &prod2);
		mpz_poly_mul(&prod1, &prod2, prodinfo->monic_poly, 1);
	}

	/* multiply them together and save the result */
	/* mpz_poly_mul(&prod1, &prod2, prodinfo->monic_poly, 1); */

	for (i = 0; i <= prod1.degree; i++)
		mpz_swap(prod->coeff[i], prod1.coeff[i]);
	prod->degree = prod1.degree;
	mpz_poly_free(&prod1);
	mpz_poly_free(&prod2);
}
We try to build msieve with this patch without success,
could anybody help to build a windows x86_64 msieve binary with this code?
This code is at gnfs/sqrt/sqrt_a.c, line 300.

My rough guess is that:
1. there are some bad relations in the unique relations;
2. 64GB physical is not enough when factoring a gnfs200.

Any suggestion would be appreciate.
wreck is offline   Reply With Quote
Old 2019-05-26, 05:20   #2
frmky
 
frmky's Avatar
 
Jul 2003
So Cal

1000000001102 Posts
Default

Try running another dependency. -nc3 2,2
Try in 64-bit Linux.
Hmmm....
frmky is offline   Reply With Quote
Old 2019-05-26, 22:18   #3
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

31×97 Posts
Default

I'm having trouble compiling the newer svn versions.

Here is svn 1018 with your patch, compiled with:

make all WIN=1 WIN64=1 ECM=1 CUDA=1 NO_ZLIB=1 VBITS=64


msieve-svn1018patched.zip
ATH is offline   Reply With Quote
Old 2019-05-28, 00:38   #4
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

2·3·19·31 Posts
Default

It could be a limit in the number of limbs older versions of GMP are allowed to allocate for a single number.
jasonp is offline   Reply With Quote
Old 2019-05-28, 12:58   #5
wreck
 
wreck's Avatar
 
"Bo Chen"
Oct 2005
Wuhan,China

16310 Posts
Default

I use the following command to start dep 2.
msieve-svn1018-cuda75-sandybridge.exe -i R507.ini -l R507.log -s part-0804-2.out -nf R507.fb -nc3 "target_density=130 dep_first=16 dep_last=32" -v -t 16
That command start reading relations for dependency 16, cycles 20047610, 70899836 relations, crash after message GNU MP:Cannot allocate memory(size=4294914080)

then I change it to dep 2 and remove option -t 16, cycles 20043584, 70876804 relations, crash after the same message.

Then I change it to dep 3, cycles 20049917, 70882146 relations, crash after same message.

the cpu is i7-7820X which is Skylake structure, I download
msieve-svn1018-cuda75-haswell.exe from mersenneforum which upload by ATH, and change to dep 4, cycles 20042681, 70882146 relations, crash after same message.

I ask ATH to help me compile a new binary with the code patch I provide, and ask Kurt to do nc3, crash again.

We factor R447, R1030, R2700M, R343,R423 in the past 3 years, where R1030,R2700M,R343,R423 is factored by version "Msieve v.1.5.3 (SVN unknown)", R447 is factored by "Msieve v.1.5.4 (SVN 1018)", I guess R507 ' s -nc1 and -nc2 is the same as R447.
There is 3 point I cannot understand,
1. R447 is snfs300, its nc3 size is similar with R507, only less than 1M relations, why it not crash?
2. R1030 is gnfs199, and its nc3 relation is about 1.5 larger than R507, if GMP memory count here, why R1030 not crash?
3. When we do the sieve R343, there is s version 997 binary post on mersenneforum, I ask Kurt give it a try, but it crash when doing -nc2, whereas version "Msieve v.1.5.3 (SVN unknown)" still works. I dont know where is the difference.
I ask Kurt sieve 30M more relations, use remdup, use "Msieve v.1.5.3",option density 120 to do -nc1 -nc2 -nc3 again, to avoid bad relation, not enough memory,binary issue.The headache is
that this try will take more than 1500 hours.

About linux, I have access Ubuntu 16.04 less than 4 hours, 8GB memory, it could not use to do msieve postprocessing.
Kurt's computer(i7,64GB) is Win10, no linux system, I am not sure whether he could install Ubuntu, he also use this computer to do other reality things, so perhaps he may has some inconvienence if use ubuntu.

Thanks again to all.

Last fiddled with by wreck on 2019-05-28 at 13:03
wreck is offline   Reply With Quote
Old 2019-05-28, 15:17   #6
DukeBG
 
Mar 2018

12910 Posts
Default

This probably won't help, but worth trying if you haven't anyway.

Did you try doing it after a fresh reboot without any programs working on that machine yet? I.e. the memory is not just free, but also wasn't allocated at all by any other program yet. Maybe it needs a contiguous block of memory to allocate and the free memory is segmented after use (there are actually different kinds of free memory under the hood in windows, but I don't want to get into it right now).

Also, is this Windows 10 or some older version of Windows?

P.S. 4294914080 bytes is actually slightly below 4GB, not 4.29GB.

Last fiddled with by DukeBG on 2019-05-28 at 15:17
DukeBG is offline   Reply With Quote
Old 2019-05-28, 22:30   #7
frmky
 
frmky's Avatar
 
Jul 2003
So Cal

40068 Posts
Default

If you can post the files for download, I can try to run it here.
frmky is offline   Reply With Quote
Old 2019-05-28, 23:29   #8
Max0526
 
"Max"
Jun 2016
Toronto

10110010012 Posts
Default doesn't hurt to try safe mode

@wreck
I had a similar (not the same) problem with msieve long time ago. My message said "reallocate" instead of "allocate". Booting Windows into safe mode helped that time.
Ask Kurt to boot his Win 10 into safe boot mode: https://pureinfotech.com/safe-mode-w..._mode_msconfig and retry solving one of the dependencies. That might help. Worth a try and 2 hours instead of 1500 hours to rebuild the matrix, I guess.
I also very much doubt that four bad relations can screw up all the work so far. Does msieve not ignore them anyways?
Max0526 is online now   Reply With Quote
Old 2019-05-28, 23:43   #9
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

2×3×19×31 Posts
Default

Note also that when a GNFS job gets its relations multiplied together, each relation contributes the leading algebraic coefficient to the product, and this is always larger than the leading algebraic coefficient in SNFS jobs. So the size of the numbers to be multiplied is going to be a lot larger for GNFS jobs.

Are you sure you are linking to a 64-bit GMP when building?
jasonp is offline   Reply With Quote
Old 2019-05-28, 23:57   #10
Max0526
 
"Max"
Jun 2016
Toronto

23·31 Posts
Default GMP -param 0

Is there a chance to rebuild msieve with "-param 0" option for GMP?
There is a post from 2016 describing the problem in detail: https://www.mersenneforum.org/showpo...04&postcount=6
(also read the beginning of the thread)
Max0526 is online now   Reply With Quote
Old 2019-05-29, 05:41   #11
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

31·97 Posts
Default

-param 0 is a runtime option for GMP-ECM, not a build option for GMP or GMP-ECM.
ATH is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
All square roots failed chris2be8 Msieve 13 2020-10-14 07:08
Square Root Days davar55 Lounge 0 2016-03-16 20:19
square root crash bsquared Msieve 17 2010-04-09 14:11
Square root of 3 Damian Math 3 2010-01-01 01:56
Divisible up to Square Root davar55 Puzzles 3 2007-09-05 15:59

All times are UTC. The time now is 18:13.

Fri Jan 15 18:13:03 UTC 2021 up 43 days, 14:24, 0 users, load averages: 1.79, 1.89, 1.97

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.