CS 612 Project Proposal : Smart Data Layout for Incremental Checkpointing

����������� Checkpointing is a technique that allows for a process to save a description of its state.� It is most often used to provide fault tolerance: during normal execution, a process occasionally takes a checkpoint; if a failure occurs, the application is restarted using its most recently saved checkpoint.� For a checkpoint to be correct, it must contain a description of the program�s static position (like the value of the Instruction Counter), its dynamic position (the active stack frames), its global variables, and its dynamically allocated variables.

����������� Unfortunately, taking checkpoints adds overhead to the application�s running time: the process must copy all that information (which could be 1GB or greater) to disk.� The situation is even worse for parallel computations, because the checkpoints would be presumably saved to a network disk, and now hundreds, or even thousands, of processors would need to write their state over the network.� One proposed technique to reduce the amount that needs to be saved is termed incremental checkpointing.� This involves using the OS�s page protection mechanism to observe, at checkpoint time, which pages have changed since the last checkpoint, and to only save those.� (Lets call the set of changed pages at checkpoint i diff i .)� If there were a restart, we would need to restore the state as described in the original checkpoint, and then apply all the diffs in order, before execution could resume.

����������� One drawback to incremental checkpointing is that we are forced to work at the granularity of the OS page size.� Therefore, if just one bit on a page has changed, we still need to checkpoint the entire page.� These problems can especially arise when using dynamically allocated structures.� For example, in the following code, if matrix A does not change after the first checkpoint (if so, we describe it as a read-only structure) but B changes before every checkpoint, incremental checkpointing does not improve overhead.� We call this (for lack of a better term) the layout intermixing problem.

for (j = 0; j < 10; j++)

{

��������� A[j] = malloc ( 1 / 2 page size );

���� B[j] = malloc ( 1 / 2 page size );

}

�����������

����������� This project will involve studying smart strategies for dynamic memory layout, in an attempt to avoid the situation that we described above.� One such strategy might be to maintain two heaps, one the regular heap, one the �probably read-only� heap and require the programmer to provide information to the allocation routine as to which heap the object should be placed on.� We would still need to use the page protection mechanism for the �probably read-only� heap, because those structures will be written to at least once, but hopefully we can avoid the layout intermixing problem.�

Another strategy would be to recognize that the same static malloc call (determined by line number, maybe) is probably used to build parts of the same structure (the rows of an array, etc.), and therefore, the structures created by calls to that particular malloc should be placed next to one another.�

Clearly, there might be many other strategies worth examining.

����������� Here at Cornell, we are developing a compiler that modifies an input program by inserting application-level checkpointing code into its source.� (Application-level checkpointing means that the application�s code contains the logic to save and restore its state, as opposed to system level checkpointing, where an OS function, or an external library, provides that functionality.)�� The output of the compiler is linked with a library that includes a complete memory manager implementation, including functions for checkpointing the heap.� This memory manager currently does not provide for incremental checkpointing.

����������� This project would proceed as follows.� First, modify the memory manager so that it performed incremental checkpointing.� Then, create different versions of the memory manager that implemented each of the layout strategies above, or any other strategies you might think could be useful.� Finally, for a set of interesting benchmarks, compare the performance (i.e., checkpoint sizes and running times) using the base memory manager (non-incremental), the incremental checkpointing memory manager, and those of the smart strategies you implemented.� Once we have determined useful strategies, we will develop compiler analyses to detect and apply them automatically.

����������� The following paper, http://citeseer.nj.nec.com/plank95libckpt.html, discusses incremental checkpointing for a system-level checkpointing system.� They show that for some applications, incremental checkpointing reduces checkpoint size by greater than 80%, with a similar reduction in overhead.�� For applications where the checkpoint size did not compress, however, the incremental added to the overhead.

����������� In another paper, http://citeseer.nj.nec.com/plank95compressed.html, the same authors describe a system whereby they don�t save the entire changed page, but rather a set of diffs for each page that has changed.� This is because it is (usually) more efficient to compress the diff than to compress the entire page.