Take a Rubik’s cube. Shuffle it. It can be solved with at most 20 moves. That is a fascinating result!
From the article:
Finally, we were able to distribute the 55,882,296 cosets of H among a large number of computers at Google and complete the computation in just a few weeks. Google does not release information on their computer systems, but it would take a good desktop PC (Intel Nehalem, four-core, 2.8GHz) 1.1 billion seconds, or about 35 CPU years, to perform this calculation.
And now, some late-night number shuffling.
First, let’s make an educated guess of one quad-core 2.8 GHz Intel Nehalem doing about, say, 11.2 GFLOPS. Then, given 1.1 billion seconds spent for the task, the total task used up a total of about 2^63 floating point operations (an interesting power of 2, no?). Google’s computers did this in “just a few weeks” (2 weeks = 1209600 seconds), so that’s about 2^43 floating point operations per second for the mystery number of computers, i.e. the computers achieved a total of 10185 GFLOPS = ca. 10 TFLOPS. Divided with the GFLOPS per CPU, that’d mean about 909 CPUs, given the initial guesstimated specs for the Nehalems.
Yes, an easier way to calculate is to find how how many parallel units there were by calculating 1.1 billion seconds / 1209600 seconds = 909, but the above description is nicer to follow. YMMV.
So, according to my back-of-the-envelope calculations, and factoring in some uncertainties about the times, Davidson, Dethridge, Kociemba and Rokicki used a grand total of about a 1000 or so quad-core Intel Nehalem 2.8 GHz CPUs (or equivalent) for the task.
Anyway, 10 TFLOPS in itself is a nice number but really nothing special. It is not enough to reach even the 500th supercomputer position of the June 2010 list of top500.org. However, do keep in mind that the number of CPUs used for the Rubik’s cube task was obviously but a small fraction of the real ultimate Ninja CPU power that Google can harness at will.
And now, good night!