20110428, 22:26  #1 
Aug 2006
3^{2}·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 trialdivide 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 differentlysized 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 (nearfuture wholeEarth?) 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 quadprecision 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 20110428 at 22:26 
20110429, 03:12  #2  
"Ben"
Feb 2007
2^{2}·853 Posts 
Quote:
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? 

20110429, 04:11  #3  
Undefined
"The unspeakable one"
Jun 2006
My evil lair
17EF_{16} Posts 
Quote:
Quote:
Last fiddled with by retina on 20110429 at 04:16 

20110429, 08:09  #4  
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
2^{2}×2,663 Posts 
Quote:
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 

20110429, 10:15  #5 
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?

20110429, 10:26  #6 
Undefined
"The unspeakable one"
Jun 2006
My evil lair
11·557 Posts 
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.

20110429, 10:43  #7 
Account Deleted
"Tim Sorbera"
Aug 2006
San Antonio, TX USA
17×251 Posts 
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.

20110429, 10:54  #8  
Undefined
"The unspeakable one"
Jun 2006
My evil lair
1011111101111_{2} Posts 
Quote:


20110429, 12:19  #9 
"Ben"
Feb 2007
2^{2}·853 Posts 

20110429, 12:32  #10  
"Ben"
Feb 2007
2^{2}×853 Posts 
Quote:


20110429, 13:04  #11  
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
2^{2}·2,663 Posts 
Quote:
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 Gtype 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 subsecond latency. 1e50 processors really isn't very big at all once you step outside a parochial planetbound perspective. Paul 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Space Man  storm5510  Lounge  8  20170401 22:07 
Twin Prime Days, Prime Day Clusters  cuBerBruce  Puzzles  3  20141201 18:15 
P95 and Linux clusters  revivalfire  Information & Answers  3  20080718 16:06 
Using PCIE based network hardware for faster math clusters  Peter Nelson  Hardware  0  20050707 00:12 
BeoWolf Clusters  MrNetGuy  Hardware  8  20050223 05:20 