mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Msieve

Reply
 
Thread Tools
Old 2008-08-10, 17:14   #1
nuggetprime
 
nuggetprime's Avatar
 
Mar 2007
Austria

2×151 Posts
Default Multithreaded QS/NFS sieve stage

Is it possible to run the qs/nfs sieve process multithreaded with the current version of msieve?
when i run a qs job with -t 4, it uses only one of my 4 cores for sieving.
Regards,
nugget
nuggetprime is offline   Reply With Quote
Old 2008-08-10, 18:13   #2
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

32×5×79 Posts
Default

Afraid not; msieve only uses multiple threads for the linear algebra, and then only if the matrix is larger than anything the QS part can produce. I've always assumed that if you wanted more than one sieving process that you'd just run the msieve binary more than once (with relations going to a different data file each time).
jasonp is offline   Reply With Quote
Old 2008-08-10, 18:36   #3
nuggetprime
 
nuggetprime's Avatar
 
Mar 2007
Austria

2·151 Posts
Default

Thanks for the fast reply

--nugget
nuggetprime is offline   Reply With Quote
Old 2008-08-10, 18:59   #4
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Liverpool (GMT/BST)

24·13·29 Posts
Default

Quote:
Originally Posted by jasonp View Post
Afraid not; msieve only uses multiple threads for the linear algebra, and then only if the matrix is larger than anything the QS part can produce. I've always assumed that if you wanted more than one sieving process that you'd just run the msieve binary more than once (with relations going to a different data file each time).
i have always wondered why it does that
are there any disadvantages to it or is it hard to implement
henryzz is offline   Reply With Quote
Old 2008-08-10, 21:05   #5
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

32·5·79 Posts
Default

Quote:
Originally Posted by henryzz View Post
i have always wondered why it does that
are there any disadvantages to it or is it hard to implement
For the linear algebra, the lower limit on the size of the matrix is around 250k rows; even with one thread this completes in less than 10 minutes on a modern machine.

As for why sieving isn't multithreaded, that's because sieving parallelizes trivially but the machinery for writing multithreaded programs may not be trivial. If you want several threads to sieve, you have to go through all the data structures and figure out which ones can be shared, which ones need to be copied and how the threads will interact with each other. If they don't interact with each other, whoever spawns them is itself a thread so there is still some thread interactions to deal with. For very large problems that need huge factor bases and large auxiliary data, it might be beneficial to split the sieving up, but in all cases it's easier for the user to write a script that runs "msieve -l <unique_datfile> <other_options> &" in a loop.

Not to say that it's impossible to do, just that it's a low priority for me, behind bug fixes and NFS postprocessing improvements. If you do NFS sieving using GGNFS or the Franke tools, and you have multiple machines, then you have to do the parallel processing manually anyway.
jasonp is offline   Reply With Quote
Old 2008-08-11, 07:48   #6
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Liverpool (GMT/BST)

24·13·29 Posts
Default

Quote:
Originally Posted by jasonp View Post
For the linear algebra, the lower limit on the size of the matrix is around 250k rows; even with one thread this completes in less than 10 minutes on a modern machine.

As for why sieving isn't multithreaded, that's because sieving parallelizes trivially but the machinery for writing multithreaded programs may not be trivial. If you want several threads to sieve, you have to go through all the data structures and figure out which ones can be shared, which ones need to be copied and how the threads will interact with each other. If they don't interact with each other, whoever spawns them is itself a thread so there is still some thread interactions to deal with. For very large problems that need huge factor bases and large auxiliary data, it might be beneficial to split the sieving up, but in all cases it's easier for the user to write a script that runs "msieve -l <unique_datfile> <other_options> &" in a loop.

Not to say that it's impossible to do, just that it's a low priority for me, behind bug fixes and NFS postprocessing improvements. If you do NFS sieving using GGNFS or the Franke tools, and you have multiple machines, then you have to do the parallel processing manually anyway.
it would be most helpful for things like 100-digit mpqs
i understand ur reasons for not doing it
henryzz is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Multithreaded PFGW IBethune Software 5 2018-03-16 17:52
Which Work Types are Multithreaded tului Software 6 2015-11-28 21:59
Feature request: multithreaded polsel Andi47 Msieve 1 2010-02-20 01:16
Stage 1 with mprime/prime95, stage 2 with GMP-ECM D. B. Staple Factoring 2 2007-12-14 00:21
Stage 1 and stage 2 tests missing Matthias C. Noc PrimeNet 5 2004-08-25 15:42

All times are UTC. The time now is 22:46.


Mon Feb 6 22:46:33 UTC 2023 up 172 days, 20:15, 1 user, load averages: 0.84, 1.01, 1.04

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

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