Solving Rubik’s Cube and IO Bandwidth

Solving Rubiks Cube by treating disk as RAM: Gene Cooperman gave an interesting talk at Google about how he proved that Rubik’s Cube can be solved in 26 moves and how treating disk as RAM was essential for this. The Google talk is on Youtube [1]. I recommend that you read the ACM paper he wrote with Daniel Kunkle first before watching the talk. Incidentally due to the resolution of Youtube it would have been good if the notes had less than 10 lines per screen.

Here is the main page for the Rubiks Cube project with source and math [2], note that I haven’t been interested enough to read the source but I’m including the link for reference.

The main concept is that modern disks can deliver up to 100MB/s (I presume that’s from the outer tracks, I suspect that the inner tracks wouldn’t deliver that speed) for contiguous IO. Get 50 disks running at the same speed and you get 5GB/s for contiguous IO which is a typical speed for RAM. Of course that RAM speed is for a single system while getting 50 disks running at that speed will require either a well-tuned system from SGI (who apparently achieved such speeds on a single process on a single system many years ago – but I can’t find a reference) or 5+ machines from anyone else. The configuration that Gene describes apparently involves a network of machines with one disk each, he takes advantage of hardware purchased for other tasks (where the disks are mostly wasted).

I believe that SGI sells Altix machines which can have enough RAM to store all that data. It is NUMA RAM, even the “slow” access to RAM on another NUMA node should be a lot faster in most cases for sequential access and when there are seeks the benefits of NUMA RAM over disk will be dramatic. Of course the cost of a large NUMA installation is also significant, while a set of 50 quad-core machines with 500G disks is affordable by some home users.

Comments are closed.