Thursday, 6 March 2008

Bubblesorting with N processors (where N is REALLY large)

I was reading this article in Slashdot, and after this comment an interesting question came to my mind: what may happen if you have a massively overpowered computer for solving a problem. By "massively" I mean that for an O(n) or O(n .log n) you have C.n or C.n.log n processors and equivalently ingent amounts of memory considering parallel memory access (usually memory is not a problem, since even if you solve problems with 1.000.000 integers, that doesn't make a dent in present computers).
So I will try to think how to implement some of this algorithms... if I have too much time (I won't) I will check if I can simulate them. Unfortunately, normal multithreading may not work optimally, since to have some real simulation I would need a per-instruction round-robin, so I don't think that will be possible.
Of course, I am not original. This is the same concept as the Chinese Lottery Cryptanalisis attack (there is even an RFC about it)

Add to Technorati Favorites

No comments: