Method and apparatus for template based parallel checkpointing

• US 20060236152A1
• Filed: 04/14/2005
• Published: 10/19/2006
• Est. Priority Date: 04/14/2005
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Archer, Charles Jens, Inglett, Todd Alan
• Granted Patent: US 7,478,278 B2
• Time in Patent Office: Days
• US Class Current: 714/16
• CPC Class Codes: G06F 11/1438 Restarting or rejuvenating
• CPC Class Codes: G06F 11/1451 by selection of backup contents

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.

Claims

1. A parallel computer system comprising:

a) a plurality of compute nodes;

b) a plurality of I/O nodes coupled to the compute nodes;

c) a network that connects the compute nodes and the I/O nodes that supports a broadcast communication with the compute nodes; and

d) a checkpoint server that collects a parallel checkpoint of the state of the compute nodes using a rolling checksum algorithm.

2. The parallel computer system of claim 1 wherein the checkpoint server broadcasts a template of data block checksums from a previous checkpoint to all compute nodes in the cluster and the compute nodes search their own memory image for checksum matches using an rsync protocol in the rolling checksum algorithm.

3. The parallel computer system of claim 2 wherein each compute node produces a template of new data blocks with checksums that didn'"'"'t exist in the previous checkpoint and a template of references to the original data blocks that did exist in the previous checkpoint.

4. The parallel computer system of claim 3 wherein each node sends its new data block checksum template to an adjacent node in the cluster of nodes;

and compares checksums to find common data blocks between all adjacent nodes as well as its own data blocks; and

informs adjacent nodes to replace a reference to a common data block with a reference to a data block on another node.

5. The parallel computer system of claim 4 wherein each node collects reference templates from the compute nodes and storing them in the checkpoint server;

and

collects new unique data blocks and stores them to the checkpoint server.

6. The parallel computer system claim 2 wherein the I/O nodes store the data blocks to unique storage servers over network lines coupled to the I/O nodes rather than funneling the data through a network line to the checkpoint server.

7. 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 in the cluster; and

b) each compute node searching its own memory image for checksum matches.

8. The computer implemented method of claim 7 wherein the steps of each compute node searching its own memory image for checksum matches uses an rsync protocol in the rolling checksum algorithm.

9. The computer implemented method of claim 8 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.

10. The computer implemented method of claim 9 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.

11. The computer implemented method of claim 10 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.

12. The computer implemented method of claim 11 wherein the step of storing the data blocks stores the data on auxiliary storage servers instead of the checkpoint server.

13. The computer implemented method of claim 11 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.

14. The computer implemented method of claim 11 further comprising the step of sharing a subset of the reference template from a first application to a second application.

15. 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.

16. A program product comprising:

(A) a checkpoint server that collects a parallel checkpoint of the state of a cluster of compute nodes on a parallel computer system using a rolling checksum algorithm on each node; and

(B) computer-readable signal bearing media bearing the checkpoint server.

17. The program product of claim 16 wherein the computer-readable signal bearing media comprises recordable media.

18. The program product of claim 16 wherein the computer-readable signal bearing media comprises transmission media.

19. The program product of claim 16 wherein the checkpoint server broadcasts a template of data block checksums from a previous checkpoint to all compute nodes in the cluster and the compute nodes search their own memory image for checksum matches using an rsync protocol in the rolling checksum algorithm.

20. The program product of claim 19 wherein each compute node produces a template of new data blocks with checksums that didn'"'"'t exist in the previous checkpoint and a template of references to the original data blocks that did exist in the previous checkpoint.

21. The program product of claim 20 wherein each node sends its new data block checksum template to an adjacent node in the cluster of nodes;

and compares checksums to find common data blocks between all adjacent nodes as well as its own data blocks; and

informs adjacent nodes to replace a reference to a common data block with a reference to a data block on another node.

22. The program product of claim 21 wherein each node collects reference templates from the compute nodes and storing them in the checkpoint server;

and collects new unique data blocks and stores them to the checkpoint server.

23. The program product of claim 22 wherein the I/O nodes store the data blocks to unique storage servers over network lines coupled to the I/O nodes rather than funneling the data through a network line to the checkpoint server.