Binary delta optimization of parallel program checkpoints

Distributed computer systems (CS) are the major high-performance data processing tools.They are multiarchitectural, hierarchically structured and large-scaled means. According to statisticaldata frequency of partial faults in such systems is about 1 per several days. Check pointing isone of the most common approaches to CS fault tolerance problem.Analysis of the existing check pointing tools shows that a synchronous approach to checkpointcreation is widely used. This approach is known to create a heavy input/output load atcheckpoint time. Therefore, it is important to decrease overhead during distributed checkpointcreation.This paper considers a binary delta compression as a solution of the above-stated problem.Hash-based algorithms FHash (Fixed Hash size algorithm) and SHash (Sliding window Hashbasedalgorithm) are analyzed. Theoretical and experimental estimation of computational complexityis obtained for both of them. It is shown that the SHash algorithm is not suitable for thebinary delta compression of the checkpoints because of its high overhead.New adaptive delta compression approach, combining advantages of the well-known deltacompression types, is proposed in the work. Its effectiveness is demonstrated on the collection ofparallel programs. Proposed algorithms form the basis of the software package called HBICT.HBICT is a part of the system software of the geographically distributed multicluster computersystem that is being developed by the Center of parallel computer technologies of the SiberianState University of Telecommunications and Information Sciences and A.V. Rzhanov Institute ofSemiconductor Physics (Siberian branch of the RAS). To provide automated checkpoint compressionat creation time HBICT is integrated with the check pointing package called DMTCP.

Keywords

Authors

References