Clusters! In! Space!

[CRGreathouse]

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.

[bsquared]

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?

[retina]

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?

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 5x10¹⁶ 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.

[xilman]

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

[TimSorbet]

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?

[retina]

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.

[TimSorbet]

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.

[retina]

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.

[bsquared]

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?

[bsquared]

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.

[xilman]

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