mersenneforum.org Square Root Parallelization
 Register FAQ Search Today's Posts Mark Forums Read

 2022-04-06, 11:55 #1 EdH     "Ed Hall" Dec 2009 Adirondack Mtns 2·3·751 Posts Square Root Parallelization The section about the Square Root phase in README.nfs describes running parallel instances for separate dependencies on separate machines. Is there a reason they can't be done as several threads on a single machine? Can they be run within the same directory, or are there intermediate files that collide?
 2022-04-06, 12:43 #2 Gimarel   Apr 2010 22810 Posts You can do something like Code: for i in $(seq 1 16); do msieve -v -nc3 "dep_first=$i dep_last=$i" & done wait and grep the factors from msieve.log. This works for me. 2022-04-06, 12:48 #3 charybdis Apr 2020 12768 Posts Quote:  Originally Posted by EdH The section about the Square Root phase in README.nfs describes running parallel instances for separate dependencies on separate machines. Is there a reason they can't be done as several threads on a single machine? Can they be run within the same directory, or are there intermediate files that collide? Yes they can be run in the same directory, though you might want to keep the log files separate. On large jobs you may run into memory issues because the square root uses a similar amount of RAM to the linear algebra.  2022-04-06, 12:56 #4 swellman Jun 2012 31·113 Posts I remember both Greg and Ryan have run sqrt in parallel sometime in the past but with Greg saying it’s harder than it looks (or something to that effect). Personally I’m willing to wait it out. If it takes two weeks to get through LA, what’s another 6 hours? It is still an intriguing idea. I just finished a job yesterday in which LA took 8 days but sqrt took another 20 hours. Which was a little annoying. 2022-04-06, 13:27 #5 EdH "Ed Hall" Dec 2009 Adirondack Mtns 2×3×751 Posts Quote:  Originally Posted by Gimarel You can do something like Code: for i in$(seq 1 16); do msieve -v -nc3 "dep_first=$i dep_last=$i" & done wait and grep the factors from msieve.log. This works for me.
Thanks! I have the scripts that currently work for a single thread, and this gives me a method to add the extra threads and confirms it works.
Quote:
 Originally Posted by charybdis Yes they can be run in the same directory, though you might want to keep the log files separate. On large jobs you may run into memory issues because the square root uses a similar amount of RAM to the linear algebra.
I'm working with smaller (c15x-c16x) numbers and a fair amount of RAM (40+ GB) on a couple machines. But, historically, I rarely get the 50/50 success to work in my favor. When each try takes a half-hour and it gets to dependency 5, I get impatient. I'm parsing the log file and they're not kept, so I can probably get along with the clutter of a single log. I'm also looking at whether to pkill other instances if one succeeds, but I don't think there's any time difference between success and failure, other than the normal variance, so there may not be any real gain to that approach.
Quote:
 Originally Posted by swellman I remember both Greg and Ryan have run sqrt in parallel sometime in the past but with Greg saying it’s harder than it looks (or something to that effect). Personally I’m willing to wait it out. If it takes two weeks to get through LA, what’s another 6 hours? It is still an intriguing idea. I just finished a job yesterday in which LA took 8 days but sqrt took another 20 hours. Which was a little annoying.
I think running it across multiple machines would be too troublesome due to the file transfers, but as Gimarel posted, keeping it on a single machine might be pretty simple, as long as I keep track of memory needs.

Thanks for all the help. Now I just need to implement it. . .

 2022-04-06, 18:44 #6 jasonp Tribal Bullet     Oct 2004 5·709 Posts If memory serves, the Factoring As A Service project added patches to the 2015-era Msieve source which allowed the square root to run in parallel, because they were working on huge AWS nodes and the rest of their pipeline finished up so quickly.
 2022-04-06, 19:22 #7 EdH     "Ed Hall" Dec 2009 Adirondack Mtns 2×3×751 Posts Thanks everyone! A localized version of what Gimarel posted seems to be working great for my setup. Since I was already basing my scripts on the finishing of the Square Root operation, what I have set up now, is to start and release 15 threads which don't wait (&) and then delay for a couple minutes prior to starting the 16th thread, which will hold the script until it is finished. By then the other 15 should have had their chances to return factors. The only foreseeable issue, might be the rare occasion when the first 16 dependencies come up short. I could add threads, but for now I'll stick with 16.
2022-04-06, 19:55   #8
EdH

"Ed Hall"
Dec 2009

2×3×751 Posts

Quote:
 Originally Posted by jasonp If memory serves, the Factoring As A Service project added patches to the 2015-era Msieve source which allowed the square root to run in parallel, because they were working on huge AWS nodes and the rest of their pipeline finished up so quickly.
Wow! They mention being able to do the Square Root phase for their 512-bit RSA modulus in ten minutes via parallelization. That's how long it took my 140 digit number.

BTW, for that c140, my 16 invocations of SR returned five, p98 factor... p43 factor" and eleven instances of "no factor found."

 2022-04-06, 21:21 #9 frmky     Jul 2003 So Cal 236710 Posts With 34-bit sqrts taking longer and plenty of memory available on the machines I use, I've been thinking about implementing a threaded sqrt. It looks like FaaS is released under the LGPL, but I'll contact them to see if they might release the msieve changes. If so, I'll put them in my development branch.
 2022-04-07, 01:39 #10 frmky     Jul 2003 So Cal 32×263 Posts It's now implementing in my development branch at https://github.com/gchilders/msieve_...cuda-nfsathome Running -nc3 without multiple threads uses the standard code while running with 2 or more threads uses the FaaS code.
2022-04-07, 03:18   #11
EdH

"Ed Hall"
Dec 2009

2·3·751 Posts

Quote:
 Originally Posted by frmky It's now implementing in my development branch at https://github.com/gchilders/msieve_...cuda-nfsathome Running -nc3 without multiple threads uses the standard code while running with 2 or more threads uses the FaaS code.
Excellent! Thanks! I hope to be trying it out by Friday.

 Similar Threads Thread Thread Starter Forum Replies Last Post paul0 Factoring 0 2020-10-06 15:27 wreck Msieve 15 2019-08-07 22:32 davar55 Lounge 0 2016-03-16 20:19 bsquared Msieve 17 2010-04-09 14:11 Damian Math 3 2010-01-01 01:56

All times are UTC. The time now is 00:08.

Sat May 21 00:08:15 UTC 2022 up 36 days, 22:09, 0 users, load averages: 1.85, 2.13, 1.83