mersenneforum.org Clusters! In! Space!
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2011-04-28, 22:26 #1 CRGreathouse     Aug 2006 32·5·7·19 Posts 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
2011-04-29, 03:12   #2
bsquared

"Ben"
Feb 2007

22·853 Posts

Quote:
 Originally Posted by CRGreathouse ... "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?

2011-04-29, 04:11   #3
retina
Undefined

"The unspeakable one"
Jun 2006
My evil lair

17EF16 Posts

Quote:
 Originally Posted by bsquared 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 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

2011-04-29, 08:09   #4
xilman
Bamboozled!

"πΊππ·π·π­"
May 2003
Down not across

22×2,663 Posts

Quote:
 Originally Posted by bsquared 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

 2011-04-29, 10:15 #5 Mini-Geek Account Deleted     "Tim Sorbera" Aug 2006 San Antonio, TX USA 17×251 Posts 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?
2011-04-29, 10:26   #6
retina
Undefined

"The unspeakable one"
Jun 2006
My evil lair

11·557 Posts

Quote:
 Originally Posted by Mini-Geek 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.

2011-04-29, 10:43   #7
Mini-Geek
Account Deleted

"Tim Sorbera"
Aug 2006
San Antonio, TX USA

17×251 Posts

Quote:
 Originally Posted by retina 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.

2011-04-29, 10:54   #8
retina
Undefined

"The unspeakable one"
Jun 2006
My evil lair

10111111011112 Posts

Quote:
 Originally Posted by Mini-Geek 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.

2011-04-29, 12:19   #9
bsquared

"Ben"
Feb 2007

22·853 Posts

Quote:
 Originally Posted by retina 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?

2011-04-29, 12:32   #10
bsquared

"Ben"
Feb 2007

22×853 Posts

Quote:
 Originally Posted by xilman 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.

2011-04-29, 13:04   #11
xilman
Bamboozled!

"πΊππ·π·π­"
May 2003
Down not across

22·2,663 Posts

Quote:
 Originally Posted by bsquared 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

 Similar Threads Thread Thread Starter Forum Replies Last Post storm5510 Lounge 8 2017-04-01 22:07 cuBerBruce Puzzles 3 2014-12-01 18:15 revivalfire Information & Answers 3 2008-07-18 16:06 Peter Nelson Hardware 0 2005-07-07 00:12 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