mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Software

Reply
 
Thread Tools
Old 2005-12-18, 22:48   #1
lpmurray
 
lpmurray's Avatar
 
Sep 2002

5916 Posts
Default NEW MERSENNES AND MULTI-THREADED SOFTWARE

It seams that intel and amd will have quad - 16+core processors within the next 5 years, add that to duel processor computers which are fairly affordable and 4 processor systems which are in the reach of a few. Even a duel processor with 8 cores = 16 cores working on a number. A quad with 16 cores means throwing 64 cores at a mersenne number. with glucas and mlucas I wonder what the optimum number of cores are before they have no effect and is that software capable of searching for 100million digit numbers. Lets face it the day of the first 10million digit are coming to a close fast. Since single core computers are not getting faster anymore, the only logical next step for mersenne hunters is multi-threaded software. Software writing talents need to try and make speed advancements in the multi-threaded software thats out there for primes.
lpmurray is offline   Reply With Quote
Old 2005-12-19, 01:05   #2
moo
 
moo's Avatar
 
Jul 2004
Nowhere

809 Posts
Default

Thats easier said then done.
What really needs to be found is a new method.
LL is good to a point but if a new method was discovered that was easier to impliment on muticore systems wouldnt we be better off.
moo is offline   Reply With Quote
Old 2005-12-19, 01:17   #3
drew
 
drew's Avatar
 
Jun 2005

2×191 Posts
Default

Quote:
Originally Posted by moo
Thats easier said then done.
What really needs to be found is a new method.
LL is good to a point but if a new method was discovered that was easier to impliment on muticore systems wouldnt we be better off.
I don't think you can just conjure up a new method. *That's* what's easier said than done.

If needed, FFT operations can be adapted to multi-core systems using a divide-and-conquer approach. They won't make as efficient use of the processors as the current methods will, however, but it would still be worth it, especially as the exponents get larger.

Drew
drew is offline   Reply With Quote
Old 2005-12-19, 03:20   #4
lpmurray
 
lpmurray's Avatar
 
Sep 2002

10110012 Posts
Default

According to a benchmark for a 3.8 p4 a 100 million digit number would take 6.3 years, if software could be improved so that a duel processor with 8 cores ea could finish a number in a year. That would be just about what the first 10 million digit numbers were taking when P95 was first able to handle them, at that time the hot machines were PIII - 550. I rember re-doing a duel PII-350 tiger direct to duel PIII-550'S so i could run them right away. I had been using the tiger for 2 years 24/7 before upgrading it in 99 to run the 10million digit numbers. The other important thing is save files that people can send in if they decide they no longer want to run the 100million digit number so that months of work aren't wasted.
lpmurray is offline   Reply With Quote
Old 2005-12-19, 05:41   #5
TTn
 

2×17×239 Posts
Default wizard conjuring a spell

Quote:
I don't think you can just conjure up a new method. *That's* what's easier said than done.
I agree, it is easier said than done.
  Reply With Quote
Old 2005-12-19, 06:14   #6
moo
 
moo's Avatar
 
Jul 2004
Nowhere

809 Posts
Default

Yes i know that it its easier said then done. Im susgesting that it might be easier to find a new method then use ll in muti core envrioments. I belive from what i heard that ll relies on the results of the illiteration before to run the next test.
moo is offline   Reply With Quote
Old 2005-12-19, 06:26   #7
drew
 
drew's Avatar
 
Jun 2005

2×191 Posts
Default

Quote:
Originally Posted by moo
Yes i know that it its easier said then done. Im susgesting that it might be easier to find a new method then use ll in muti core envrioments. I belive from what i heard that ll relies on the results of the illiteration before to run the next test.
Hey Moo,

Consider a new method virtually impossible. Granted, you can't rule out the possibility, but it's certainly not easier than the alternative.

You're right in that each step relies on the previous, but that doesn't mean you can't use parallel processing within an iteration. It will require some inter-process-communication during each iteration, but since an iteration takes as long as tens of milliseconds, that's probably not an unreasonable amount of overhead.

I suppose the tricky question is how do you distribute the work when other processes are running? You wouldn't want to hold up several cores waiting for the result from one that yielded cycles to another application.

Drew

Last fiddled with by drew on 2005-12-19 at 06:35
drew is offline   Reply With Quote
Old 2005-12-19, 19:56   #8
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

91410 Posts
Default

Quote:
Originally Posted by moo
What really needs to be found is a new method.
LL is good to a point but if a new method was discovered that was easier to implement on muticore systems wouldnt we be better off.
The LLT is the faster test one can imagine for any kind of number, said Mister Silverman. I spent a lot of time reading papers about primality tests, and I think he is perfectly correct. You cannot find a faster proof.
So, the problem is to write a parallel FFT doing the squarring.
Since I still do not understand how a sequential FFT works, don't expect me to talk about a // FFT !
Guillermo did such a work. And now Ernst.
But this runs perfectly only on a pure SMP (very expensive, like the machines of IBM based on PPC). On cheaper machines, based on NUMA, it requires something even more complex: manage the memory so that threads using the same part of memory are located in the same block of processors.
Not easy ...
Tony
T.Rex is offline   Reply With Quote
Old 2005-12-19, 21:28   #9
moo
 
moo's Avatar
 
Jul 2004
Nowhere

809 Posts
Default

mabey we should look at these...
http://www.tgdaily.com/2005/12/19/ne...re_processors/
moo is offline   Reply With Quote
Old 2005-12-19, 22:06   #10
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

39216 Posts
Default

Quote:
Originally Posted by moo
That's really interesting. But not yet available, and probably never available on PCs, and available on big machines in 5 (or more) years from now. How much cores on these machines ? 2, 4 ?

What are you talking about in your previous email ? Mathematical method for proving primality or Mathematical/Computational method for coding the Mathematical method ?
The (Mathematical method) LLT is the fastest for Mersenne.
The (Mathematical method) FFT is the fastest for squarring, and has been specialized for Mersenne numbers.
Parallelizing FFT is an improvement, but (as I said in previous email) either you have a very expensive really SMP machine or you have a less expensive NUMA machine. (In fact, SMP is NUMA with a very small NUMA factor).
GLucas is parallelized FFT, but it is not scalable on NUMA machines with more than 10 or 12 CPUS. I don't know about GLucas on SMP machines.
I guess experts can parallelize FFT in order to be scalable on large NUMA machines. But it would require a lot of work !
Tony
T.Rex is offline   Reply With Quote
Old 2005-12-20, 23:56   #11
thechickenman
 
thechickenman's Avatar
 
Nov 2005
South Carolina

7×11 Posts
Default

Stupid question time...

What, EXACTLY, and without lots of tech-speak, is a dual-core machine? I thought it was like having two processors?

Wouldn't a dual-core machine be better off running two numbers at once, and doubling throughput that way?
thechickenman is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Multi-threaded factoring bchaffin Aliquot Sequences 8 2010-10-24 13:38
Stars and Mersennes David John Hill Jr Science & Technology 2 2009-12-13 09:47
Multi-Core / Multi-CPU Assignments (missing) worknplay Software 3 2008-11-05 17:26
Factoring Double mersennes Citrix Miscellaneous Math 2 2005-10-04 08:08
Prime95 a multi-threaded application? Unregistered Software 10 2004-06-11 05:31

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

Sat Oct 31 08:03:27 UTC 2020 up 51 days, 5:14, 2 users, load averages: 2.18, 1.96, 1.81

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