  Fault tolerance overhead of high performance computing (HPC) applications is
becoming critical to the efficient utilization of HPC systems at large scale.
HPC applications typically tolerate fail-stop failures by checkpointing.
Another promising method is in the algorithm level, called algorithmic
recovery. These two methods can achieve high efficiency when the system scale
is not very large, but will both lose their effectiveness when systems approach
the scale of Exaflops, where the number of processors including in system is
expected to achieve one million. This paper develops a new and efficient
algorithm-based fault tolerance scheme for HPC applications. When failure
occurs during the execution, we do not stop to wait for the recovery of
corrupted data, but replace them with the corresponding redundant data and
continue the execution. A background accelerated recovery method is also
proposed to rebuild redundancy to tolerate multiple times of failures during
the execution. To demonstrate the feasibility of our new scheme, we have
incorporated it to the High Performance Linpack. Theoretical analysis
demonstrates that our new fault tolerance scheme can still be effective even
when the system scale achieves the Exaflops. Experiment using SiCortex SC5832
verifies the feasibility of the scheme, and indicates that the advantage of our
scheme can be observable even in a small scale.
