mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Msieve

Reply
 
Thread Tools
Old 2022-04-06, 11:55   #1
EdH
 
EdH's Avatar
 
"Ed Hall"
Dec 2009
Adirondack Mtns

2·3·751 Posts
Default 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?
EdH is offline   Reply With Quote
Old 2022-04-06, 12:43   #2
Gimarel
 
Apr 2010

22810 Posts
Default

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.
Gimarel is offline   Reply With Quote
Old 2022-04-06, 12:48   #3
charybdis
 
charybdis's Avatar
 
Apr 2020

12768 Posts
Default

Quote:
Originally Posted by EdH View Post
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.
charybdis is offline   Reply With Quote
Old 2022-04-06, 12:56   #4
swellman
 
swellman's Avatar
 
Jun 2012

31·113 Posts
Default

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.
swellman is online now   Reply With Quote
Old 2022-04-06, 13:27   #5
EdH
 
EdH's Avatar
 
"Ed Hall"
Dec 2009
Adirondack Mtns

2×3×751 Posts
Default

Quote:
Originally Posted by Gimarel View Post
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 View Post
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 View Post
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. . .
EdH is offline   Reply With Quote
Old 2022-04-06, 18:44   #6
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

5·709 Posts
Default

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.
jasonp is offline   Reply With Quote
Old 2022-04-06, 19:22   #7
EdH
 
EdH's Avatar
 
"Ed Hall"
Dec 2009
Adirondack Mtns

2×3×751 Posts
Default

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 is offline   Reply With Quote
Old 2022-04-06, 19:55   #8
EdH
 
EdH's Avatar
 
"Ed Hall"
Dec 2009
Adirondack Mtns

2×3×751 Posts
Default

Quote:
Originally Posted by jasonp View Post
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."
EdH is offline   Reply With Quote
Old 2022-04-06, 21:21   #9
frmky
 
frmky's Avatar
 
Jul 2003
So Cal

236710 Posts
Default

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 is offline   Reply With Quote
Old 2022-04-07, 01:39   #10
frmky
 
frmky's Avatar
 
Jul 2003
So Cal

32×263 Posts
Default

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.
frmky is offline   Reply With Quote
Old 2022-04-07, 03:18   #11
EdH
 
EdH's Avatar
 
"Ed Hall"
Dec 2009
Adirondack Mtns

2·3·751 Posts
Default

Quote:
Originally Posted by frmky View Post
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.
EdH is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
CADO-NFS square root paul0 Factoring 0 2020-10-06 15:27
NFS Square Root failed wreck Msieve 15 2019-08-07 22:32
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

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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, 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.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔