Square Root Parallelization

[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?

[Gimarel]

You can do something like

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.

[charybdis]

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.

[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.

[EdH]

Originally Posted by Gimarel

You can do something like

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.

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.

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. . .

[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.

[EdH]

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.

[EdH]

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."

[frmky]

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.

[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.

[EdH]

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.