mersenneforum.org  

Go Back   mersenneforum.org > New To GIMPS? Start Here! > Information & Answers

Reply
 
Thread Tools
Old 2011-04-28, 22:26   #1
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

32·5·7·19 Posts
Default Clusters! In! Space!

Based on Christenson's post, here's an interesting (?) question. Suppose you had an extremely large number of processors, but not enough time to trial-divide the large number you are given. Can you quickly (1) factor the number (2) check the primality of the number (3) prove the primality of the number? Obviously the three tasks deal with differently-sized numbers.

I'm being intentionally vague on the specifics to allow for flexibility, but to give some kind of idea you might consider "extremely large" to be between 10^10 (near-future whole-Earth?) and 10^50 (limit of physical realizability?) with expensive communication between nodes (100 Mbit/s and with a latency of 1 s). Each node has fast double- or quad-precision arithmetic (or equivalent integer operations) but limited memory (say, 1 GB). If it helps you can assume shared access through the slow interconnect to unlimited storage.

Alternately, as a pure thought experiment, consider 10^1000 nodes (and consequently larger numbers to factor/test/prove).


I'm curious as to what algorithms could even be used under these circumstances.

Last fiddled with by CRGreathouse on 2011-04-28 at 22:26
CRGreathouse is offline   Reply With Quote
Old 2011-04-29, 03:12   #2
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

22·853 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
... "extremely large" to be between 10^10 (near-future whole-Earth?) and 10^50 (limit of physical realizability?) with expensive communication between nodes (100 Mbit/s and with a latency of 1 s).
Just some perspective - assuming each processor is 1 cm^3, 10^50 processors would fill a sphere of radius 0.003 light years. So a latency of 1 sec clearly isn't possible on an all-all basis - opposing sides of the sphere would need at minimum 2 days to communicate.

Some interesting follow up questions: assuming the mass of each processor is 1g, would a black hole form? Of what radius? How far apart would we need to move each processor so that a black hole is not formed? What is the maximum communication latency in that case?
bsquared is offline   Reply With Quote
Old 2011-04-29, 04:11   #3
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

17EF16 Posts
Default

Quote:
Originally Posted by bsquared View Post
Just some perspective - assuming each processor is 1 cm^3, 10^50 processors would fill a sphere of radius 0.003 light years. So a latency of 1 sec clearly isn't possible on an all-all basis - opposing sides of the sphere would need at minimum 2 days to communicate.
And how would you power each processor? If each processor consumes one watt how would you expel all the waste heat?
Quote:
Originally Posted by bsquared View Post
Some interesting follow up questions: assuming the mass of each processor is 1g, would a black hole form? Of what radius? How far apart would we need to move each processor so that a black hole is not formed? What is the maximum communication latency in that case?
At 5x1016 times the mass of the Sun then the density is already high enough to form a BH. To avoid a BH forming you would need to place the processors out to a diameter of at least ~31000 light years. At least I think so. Just some quick calculations here so I could be off by a few orders of magnitude. But you have to be careful not to let them fall back in towards each other else the BH will form.

Last fiddled with by retina on 2011-04-29 at 04:16
retina is offline   Reply With Quote
Old 2011-04-29, 08:09   #4
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

22×2,663 Posts
Default

Quote:
Originally Posted by bsquared View Post
Just some perspective - assuming each processor is 1 cm^3, 10^50 processors would fill a sphere of radius 0.003 light years. So a latency of 1 sec clearly isn't possible on an all-all basis - opposing sides of the sphere would need at minimum 2 days to communicate.

Some interesting follow up questions: assuming the mass of each processor is 1g, would a black hole form? Of what radius? How far apart would we need to move each processor so that a black hole is not formed? What is the maximum communication latency in that case?
Why in hell does a processor need to be that massive?

It should be straightforward, though rather expensive today, to build a processor with reasonable performance out of at most 100M atoms. Assuming a mean atomic weight of about 10 (i.e. most structural components made out of carbon) that's only a gigadalton. Avogadro's number is 1e24 (to the precision which makes sense for this estimate) so the processor has a mass of around a femtogram. Fair enough, such a processor wouldn't have much memory, but you can put in a hell of a lot of memory in the difference between a femtogram and a gram!

I'll address the BH question in a subsequent post, unless someone beats me to it.

Paul
xilman is online now   Reply With Quote
Old 2011-04-29, 10:15   #5
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

17×251 Posts
Default

How far apart would the processors have to be to not only not form a black hole, but for the relativistic effect of time passing slower at the bottom of a gravity well relative to an observer outside of it to not detract significantly from the performance?
Mini-Geek is offline   Reply With Quote
Old 2011-04-29, 10:26   #6
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

11·557 Posts
Default

Quote:
Originally Posted by Mini-Geek View Post
How far apart would the processors have to be to not only not form a black hole, but for the relativistic effect of time passing slower at the bottom of a gravity well relative to an observer outside of it to not detract significantly from the performance?
You could always put the processors on the sphere surface only, i.e. a shell that is empty inside. No one said anything about the sphere having to be filled.
retina is offline   Reply With Quote
Old 2011-04-29, 10:43   #7
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

17×251 Posts
Default

Quote:
Originally Posted by retina View Post
You could always put the processors on the sphere surface only, i.e. a shell that is empty inside. No one said anything about the sphere having to be filled.
Either way, they're in a gravity well. Arranging them as an empty 'shell' instead of a filled 'ball' would mean that all the processors run at the same speed relative to each other, and for a given number of processors would probably greatly improve the average speed of the processors to an outside observer, but there's still a slowdown.
Mini-Geek is offline   Reply With Quote
Old 2011-04-29, 10:54   #8
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

10111111011112 Posts
Default

Quote:
Originally Posted by Mini-Geek View Post
Either way, they're in a gravity well. Arranging them as an empty 'shell' instead of a filled 'ball' would mean that all the processors run at the same speed relative to each other, and for a given number of processors would probably greatly improve the average speed of the processors to an outside observer, but there's still a slowdown.
Instead of an outside observer, make it an inside observer. Put the observer in the centre.
retina is offline   Reply With Quote
Old 2011-04-29, 12:19   #9
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

22·853 Posts
Default

Quote:
Originally Posted by retina View Post
And how would you power each processor? If each processor consumes one watt how would you expel all the waste heat?
Does it matter, given that the entire processing system soon becomes a point mass with perhaps some residual angular momentum and charge?
bsquared is offline   Reply With Quote
Old 2011-04-29, 12:32   #10
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

22×853 Posts
Default

Quote:
Originally Posted by xilman View Post
Why in hell does a processor need to be that massive?

It should be straightforward, though rather expensive today, to build a processor with reasonable performance out of at most 100M atoms. Assuming a mean atomic weight of about 10 (i.e. most structural components made out of carbon) that's only a gigadalton. Avogadro's number is 1e24 (to the precision which makes sense for this estimate) so the processor has a mass of around a femtogram. Fair enough, such a processor wouldn't have much memory, but you can put in a hell of a lot of memory in the difference between a femtogram and a gram!

I'll address the BH question in a subsequent post, unless someone beats me to it.

Paul
Well, your idea of straightforward differs slightly from mine, but I'll grant you that one could probably build a molecular level processor. No doubt CRGreathouse had something in mind when he suggested 10^50 processors in the first place (although I'm not so sure about 10^1000 ;)). As a thought experiment, I suppose we shouldn't get too worked up about how we accomplish I/O or heat removal or whether or not the mass of our processing system is sufficient to crush itself into oblivion.
bsquared is offline   Reply With Quote
Old 2011-04-29, 13:04   #11
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

22·2,663 Posts
Default

Quote:
Originally Posted by bsquared View Post
Well, your idea of straightforward differs slightly from mine, but I'll grant you that one could probably build a molecular level processor. No doubt CRGreathouse had something in mind when he suggested 10^50 processors in the first place (although I'm not so sure about 10^1000 ;)). As a thought experiment, I suppose we shouldn't get too worked up about how we accomplish I/O or heat removal or whether or not the mass of our processing system is sufficient to crush itself into oblivion.
I'd build something which bears more than a passing resemblance to an Analytical Engine and I'd use either carbon nanotubes or diamond struts for the structural components.


10^50 processors at a femtogram each is only 10^32 kg, or 50 solar masses. The Schwarzschild radius of such a black hole is about 150km. The radius scales directly as the mass so if you want some storage attached to each processor you may need to increase the dimensions by a factor of a few.

Put the processors in orbit around a main sequence G-type star and you have a power source and gravitational stabilization with a maximum latency under a thousand seconds if communications can be done at the speed of light. Use a neutron star if you want sub-second latency.

1e50 processors really isn't very big at all once you step outside a parochial planet-bound perspective.

Paul
xilman is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Space Man storm5510 Lounge 8 2017-04-01 22:07
Twin Prime Days, Prime Day Clusters cuBerBruce Puzzles 3 2014-12-01 18:15
P95 and Linux clusters revivalfire Information & Answers 3 2008-07-18 16:06
Using PCI-E based network hardware for faster math clusters Peter Nelson Hardware 0 2005-07-07 00:12
BeoWolf Clusters MrNetGuy Hardware 8 2005-02-23 05:20

All times are UTC. The time now is 19:43.

Thu Apr 22 19:43:52 UTC 2021 up 14 days, 14:24, 0 users, load averages: 1.37, 1.81, 1.88

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