Disk-Based Parallel Computation, Rubik's Cube, and Checkpointing

Google Tech Talks March, 24 2008 ABSTRACT This talk takes us on a journey through three varied, but interconnected topics. First, our research lab has engaged in a series of disk-based computations extending over five years. Disks have traditionally been used for filesystems, for virtual memory, and for databases. Disk-based computation opens up an important fourth use: an abstraction for multiple disks that allows parallel programs to treat them in a manner similar to RAM. The key observation is that 50 disks have approximately the same parallel bandwidth as a _single_ RAM subsystem. This leaves latency as the primary concern. A second key is the use of techniques like delayed duplicate detection to avoid latency. For example, hash accesses accesses can be saved (even saved on disk), until there are sufficiently many pending accesses to use standard streaming techniques. We have designed a library for search problems that exploits the high parallel bandwidth while hiding the latency. We build abstractions for search that employ parallel disk-based hash arrays with the same speed as a single hash array in a single RAM subsystem. In the case of Rubik's cube, we exploited this mechanism by using seven terabytes of distributed disk in a search problem that showed that 26 moves suffice to solve Rubik's cube. Our initial efforts emphasize idempotent operations, so that we can easily recover from hardware or software faults. We next intend to apply a more general solution for fault recovery: checkpointing. This separate effort in our lab has now produced a mature, robust user-level checkpointing program has now matured. The package works successfully in tests on OpenMPI, MPICH-2, OpenMP, and parallel iPython (used in SciPy and NumPy). Our DMTCP package transparently checkpoints parallel, multi-threaded processes, with no modification either to the operating system or to the application binaries. Extrapolating from current experiments, we estimate that we can checkpoint a 1,000 node parallel computation in a matter of minutes. We are currently searching for a testbed on which to demonstrate this scalability. Speaker: Gene Cooperman