Method and apparatus for template based parallel checkpointing

Abstract

A method and apparatus for a template based parallel checkpoint save for a massively parallel super computer system using a parallel checksum algorithm such as rsync. In preferred embodiments, the checkpoint data for each node is compared to a template checkpoint file that resides in the storage and that was previously produced. Embodiments herein greatly decrease the amount of data that must be transmitted and stored for faster checkpointing and increased efficiency of the computer system. Embodiments are directed a parallel computer system with nodes arranged in a cluster with a high speed interconnect that can perform broadcast communication. The checkpoint contains a set of actual small data blocks with their corresponding checksums from all nodes in the system. The data blocks may be compressed using conventional non-lossy data compression algorithms to further reduce the overall checkpoint size.

1 . A computer implemented method for checkpointing a parallel computer system comprising the steps of: 
 a) a checkpoint server broadcasting a template of data block checksums from a previous checkpoint to all compute nodes arranged in a cluster; and    b) each compute node searching its own memory image for checksum matches.    
   
   
       2 . The computer implemented method of  claim 1  wherein the steps of each compute node searching its own memory image for checksum matches uses an rsync protocol in a rolling checksum algorithm.  
   
   
       3 . The computer implemented method of  claim 2  further comprising each node performing the steps of: 
 a) producing a template of new data blocks with checksums that didn't exist in the previous checkpoint; and    b) producing a template of references to the original data blocks that did exist in the previous checkpoint.    
   
   
       4 . The computer implemented method of  claim 3  further comprising each node performing the steps of: 
 a) sending its new data block checksum template to an adjacent node in the cluster of nodes;    b) comparing checksums to find common data blocks between all adjacent nodes as well as its own data blocks; and    c) informing adjacent nodes to replace a reference to a common data block with a reference to a data block on another node.    
   
   
       5 . The computer implemented method of  claim 4  further comprising the steps of: 
 a) collecting reference templates from the compute nodes and storing them in the checkpoint server; and    b) collecting new unique data blocks and storing them to the checkpoint server.    
   
   
       6 . The computer implemented method of  claim 5  wherein the step of storing the data blocks stores the data on auxiliary storage servers instead of the checkpoint server.  
   
   
       7 . The computer implemented method of  claim 5  wherein the step of storing the data blocks stores uses the I/O nodes to store the data to unique storage servers over network lines to the I/O nodes rather than funneling the data through a network line to the checkpoint server.  
   
   
       8 . The computer implemented method of  claim 5  further comprising the step of sharing a subset of the reference template from a first application to a second application.  
   
   
       9 . A computer implemented method for restoring a memory of a parallel computer system with a stored checkpoint comprising the steps of: 
 a) a checkpoint server sends a reference template of data block checksums from a previous checkpoint to a plurality of compute nodes in a cluster;    b) the checkpoint server broadcasts data block to the nodes;    c) each node copies broadcast data according to its own template of data block checksums; and    d) the checkpoint server broadcasts a start message.    
   
   
       10 . A computer implemented method for checkpointing a parallel computer system comprising the steps of: 
 a) a checkpoint server broadcasting a template of data block checksums from a previous checkpoint to all compute nodes arranged in a cluster; and    b) each compute node searching its own memory image for checksum matches using an rsync protocol in a rolling checksum algorithm;    c) each node performing the steps of: 
 c1) producing a template of new data blocks with checksums that didn't exist in the previous checkpoint;  
 c2) producing a template of references to the original data blocks that did exist in the previous checkpoint  
 c3) sending its new data block checksum template to an adjacent node in the cluster of nodes;  
 c4) comparing checksums to find common data blocks between all adjacent nodes as well as its own data blocks; and  
 c5) informing adjacent nodes to replace a reference to a common data block with a reference to a data block on another node;  
   d) collecting reference templates from the compute nodes and storing them in the checkpoint server;    e) collecting new unique data blocks and storing them to the checkpoint server; and    f) sharing a subset of the reference template from a first application to a second application.