{'fraction_non_alphanumeric': 0.02649051954274762, 'fraction_numerical': 0.008670454286170625, 'mean_word_length': 4.680881399870382, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A New and Efficient Algorithm-Based Fault Tolerance Scheme for A Million Way Parallelism

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.


INTRODUCTION
Fault tolerance overhead of HPC applications is critical to the efficient utilization of contemporary HPC systems. While the peak performance of contemporary HPC systems continues to grow exponentially, it is getting more and more difficult for scientific applications to achieve high performance due to both the complex architecture of and the increasing failures in these systems [28]. Schroeder and Gibson recently studied the system logs of HPC systems in Los Alamos National Laboratory and found that the mean-time-to-interrupt (MTTI) for these systems varies from about half a month to less than half a day [19] [23]. The coming Exaflops supercomputers will require the simultaneous use and control of hundreds of thousands or even millions of processing, storage, and networking elements. With this large number of elements involved, element failure will be frequent, making it increasingly difficult for applications to make forward progress. In order to use these systems efficiently and avoid restarting applications from the beginning when failure occurs, applications have to be able to tolerate failures. Fault tolerant methods attempt to enhance the utilization of system by tolerating failures occurring during the execution of applications. In this paper, we mainly discuss the fail-stop type of failures and in the processor level.
Traditional checkpointing method for the fault tolerance of HPC applications can not be scalable to a large scale. Today's long running scientific applications typically tolerate fail-stop failures by checkpointing [10] [22] [26]. Checkpointing can usually be used in different type of systems and to a wide range of applications. However, when applications such as High Performance Linpack (HPL) modify a large amount of memory between two consecutive checkpoints, checkpointing often introduces a considerable overhead when the number of processors used for computation is large [13]. Based on a balanced system model and statistics from the Computer Failure Data Repository (CFDR) [3], Gibson predicted that the effective application utilization of checkpointrestart fault tolerance will keep dropping to zero under recent technology trends [24]. Today a consensus is almost reached that it will be very difficult for checkpointing to be used as the fault tolerance method of HPC systems aimed at the Exaflops.
Conventional algorithm-based fault tolerance (algorithmic recovery) method is expected to be scalable to a large scale [14], however, will still lose its efficiency when the system scale achieves the Exaflops. Compared to the checkpointing method, the most significant advantage of algorithmic recovery is that the algorithm, for the most part, runs with little modification or stoppage to perform a checkpoint, and there is no rollback of work when failure occurs. If the amount of time to recover is approximately constant relative to the overall execution time, then this greatly decreases the fault tolerance overhead. Due to these advantages, the algorithmic recovery method is expected to be scalable to a very large scale. However, as far as we know, the effectiveness of algorithmic recovery method applied to large scale has not been carefully evaluated, no matter using theoretical analysis or experiment evaluation. In this paper, based on the construction of a model for the failure and performance of system, we have investigated a theoretical analysis to the effectiveness of algorithmic recovery method applied to large scale. We found that the efficiency of algorithmic recovery method is nearly 1/3 when the system scale achieves the Exaflops.
The inefficiency of algorithmic recovery method at large scale lies in the following two reasons. First, the algorithmic recovery method is still based on the stop-and-wait scheme, where even there is only one processor failed during the execution of applications, all the processors in system have to stop and wait for recovery of the failed processor. It is clear that this stop-and-wait fault tolerance scheme can not be scalable to a very large scale. Second, with the increasing of system scale, the mean time to failure (MTTF) of system is decreasing. However, for HPC applications with intensive computation or communication, such as HPL, the cost to recover a failed processor is increasing with the system scale. When the system scale reaches a boundary, where the time to recover failure equals to or approaches the MTTF of system, it is clear that the system efficiency will be low. For algorithmic recovery method, the scale of Exaflops could be such a boundary.
To overcome these problems, this paper proposes a new algorithm-based fault tolerance scheme for HPC applications. Our major contributions are the following three points: First, we have established a model on the failure and performance of system. Based on this model, we have investigated a theoretical evaluation of algorithmic recovery method under large scale for the first time, and indicated the impact of the ratio between floating point computing power and communication bandwidth of processors on the efficiency of HPC system. Second, we have developed a non-stop scheme to tolerate fail-stop failures occurring during the execution of applications. When failure occurs during the execution, we do not stop to wait for recovery but carry out a replacement and continue the execution. At the end of execution, this scheme can recover the correct solution with a much lower cost compared to the algorithmic recovery method. To tolerate unbounded times of failures occurring during the execution, a background accelerated recovery method is proposed to rebuild the redundancy.
Third, to demonstrate the feasibility of our new scheme to the fault tolerance for large scale HPC applications, we have incorporated our fault tolerance method to the benchmark HPL. We also have investigated a detailed efficiency analysis to this method using theoretical analysis and experiment evaluation.
Theoretical analysis demonstrates that our new fault tolerance scheme can still be effective even when the system scale achieves the Exaflops. Experiment evaluation indicates that the advantage of our scheme can be observable even in a small scale.
The rest of paper is organized as follows. Section two briefly introduces the conventional algorithm-based recovery method and demonstrates its inefficiency in the fault tolerance for Exaflops. The third part introduces our new algorithm-based fault tolerance scheme in a general framework. Section four has incorporated our scheme to the widely used benchmark HPL. In section five, a failure and performance model of system is established, based on this model, the efficiency of different fault tolerant methods under HPL has been evaluated theoretically. Section six gives some experiment results. Section seven reviews related works and provides some discussion. The last part concludes this paper and discusses some future works.

THE INEFFICIENCY OF ALGORITHM-BASED RECOVERY METHOD
In this section, first we briefly introduce the conventional algorithm-based fault tolerance scheme, then we demonstrate the inefficiency of algorithmic recovery method to tolerate fail-stop failures in large scale HPL.

Algorithm-Based Fault Recovery
Traditional algorithm based fault tolerance (ABFT) is proposed by Huang and Abraham, which uses information at the end of execution of an algorithm to detect and recover failures and incorrect calculations for fail-continue failures [5] [21]. This technique is further developed by Chen and Dongarra to tolerate fail-stop failures occurring during the execution of HPC applications [11] [12]. The idea of ABFT is to encode the original matrices using real number codes to establish a checksum type of relationship between data, and then re-design algorithms to operate on the encoded matrices to maintain the checksum relationship during the execution.
Assume there will be only one process failure, however, before the failure actually occurs, we do not know which process will fail; therefore, a scheme to handle only the lost data on the failed process actually needs to be able to handle data on any process. It seems difficult to be able to handle data on any process without saving all data on all processes somewhere. However, if we assume, at any time during the computation, the data D i on the ith process P i satisfies Where q is the total number of processes used for computation and E is data of the encoding process. Then, the lost data on any failed process would be able to be recovered from the above relationship. If the ith process failed during the execution, then all processes stop, and the lost data D i can be recovered from: In practice, this kind of special relationship is by no means natural. However, it is possible to design applications to maintain such a special checksum relationship throughout the computation, and this is one purpose of ABFT research.

Inefficiency of Algorithmic Recovery Method for Large Scale Systems
It can be seen from Eq. (2) that an algorithmic recovery process for a failed node needs to transfer data from other normal nodes.
Although this method avoids slow disk I/O, it depends on the network bandwidth of the HPC systems.
Based on a failure and performance model of computing system established in section 5.1, the efficiency of algorithmic recovery method for tolerating fail-stop failures in HPL is (see Section 5.2.1 for a detailed analysis): Where p is the number of processors including in system, λ is the failure rate of single processor, and c is the ratio between floating point computing power and the network bandwidth of processors (FLOPS/bandwidth, c has no unit).
A small c means a more balanced systems (c=1 or c=10, like Bluegene and Cray XT systems). For today's accelerator based HPC systems like Nebulae and Tianhe-1, the ratio c may exceed 200. However a smaller c may mean more total processors are needed to reach a given scale. To achieve the scale of Exaflops, a system with ratio c=100 may need 10 6 processors. However, since the interconnect bandwidths of different systems are in the same magnitude, for a system with ratio c=10 or c=1, it may need 10 7 or 10 8 processors respectively. So in Fig. 1 we give three different upper bounds (10 6 , 10 7 , 10 8 ) of the number of processors respectively.
It can be seen that, the efficiencies of the three cases are all near to 1/3 when system achieves the scale of Exaflops, which is almost the efficiency of Triple Modular Redundancy. This indicates that the algorithmic recovery method is not suitable for the fault tolerance of HPC systems at large scale, new and efficient fault tolerance scheme should be developed for the scale of Exaflops.

OUR NEW ALGORITHM-BASED FAULT TOLERANCE SCHEME
In this section, we will give some general principles for tolerating fail-stop failures in the middle of execution of applications by maintaining checksum like relationship in the algorithm instead of checkpointing or message logging.

Failure Detection and Location
Handling fault tolerance typically consists of three steps: 1) fault detection, 2) fault location, and 3) fault recovery or processing. Fail-stop process failures can often be detected and located with the aid of the runtime environment. For example, many current programming environments such as PVM [26], Globus [17], FT-MPI [16], and Open MPI [18] provide this type of failure detection and location capability. We assume the loss of partial processes in the message passing system does not cause the aborting of the survival processes, and it is possible to replace the failed processes in the message passing system and continue the communication after the replacement. However, the application is still responsible for recovering the data structures and the data of the failed processes. In the rest of this paper, we will mainly focus on how to process the lost data in the failed processes.

Failure Hot-Replacement Policy
For the simplicity of presentation, assume there will be only one process failure. Suppose at any time during the computation, the data D i on the ith process P i satisfies Then, the lost data D i on any failed process would be able to be processed from the above relationship. Assume the ith process failed during the execution, instead of stopping all the processes and recovering the lost data D i using Eq. (2), we replace the failed process with the encoding process E and continue the execution.
The original data is and the transformed data (after replacement) is Then we can establish a relationship between the transformed data and the original data as: with T is a q×q matrix in the following form, where the elements omitted in the diagonal and the ith column are all 1, and all the other elements omitted are 0.
If the operations on data are linear transformations (such as matrix operations like decomposition), then it is clear that the relationship D′ =D×T will always be kept. It can be seen that T is a nonsingular matrix. At the end of execution, the original correct solution based on D can be re-computed through the intermediate solution based on D'. It is clear that this re-computation is actually a transformation related to T.
However, since the redundancy decreases one after each replacement, there will be no redundancy available sooner or later if failures occurring times and times. To tolerate multiple and even unbounded times of failures during the execution, the redundancy has to be rebuilt in time. So we propose the following scheme of background accelerated recovery of redundancy.

Background Accelerated Recovery of Redundancy
We can rebuild redundancy E from It can be seen that the rebuild of redundancy is actually a recovery process, which is the same with the algorithmic recovery process.
If the recovery of redundancy makes all the processors stop and wait, then it will also become the bottleneck. However, since the recovery of redundancy is not the hot spot, we can carry out recovery in the background. Then the cost on the recovery of redundancy can be overlapped with the computation or communication time during the normal execution. So the recovery process will not bring new time overhead.
But this background recovery process will bring another issue: since other processes do not stop and wait for the recovery of redundancy, when the redundancy process is rebuilt, it has fallen behind other processes in progress several steps. This may cause future stop and wait when system need synchronization. To make the whole system return to a consistent and synchronized state, some faster (such as with triple speed) processors and network need to be used to accelerate the recovery and catch up with other normal processes. Since only a small number of such high end nodes are needed, the additional cost will decrease when system scale up.
In the rest of this paper, HRBR (Hot Replace Background Recovery) will be used to represent our new fault tolerance scheme based on algorithm.

Advantages of HRBR
Compared to the conventional failure recovery method, HRBR introduces the following two advantages. First, in a system when only one processor P i fails, all the other processors in system do not need to stop and wait for the recovery of data on P i . This nonstop scheme improves the efficiency of large scale systems, since the wasted cpu cycles during stop-and-wait period increase with the scale. Second, since T is a very sparse matrix, the cost of recomputing the correct solution using T can be much lower than the cost of recovery of failed processor directly, especially for those computation or communication intensive applications where each processor is allocated with a large set of data. This can be seen from the example of HPL in the next section.
In the special case in section 3.2.1, we are lucky enough to be able to process the lost data on any failed process without checkpoint due to the special checksum relationship. In practice, this kind of special relationship is by no means natural. However, it is natural to ask: is it possible to design an application to maintain such a special checksum like relationship throughout the computation on purpose?
The following section will give some general principles.

A General Framework
Assume the original application is designed to run on q processes. Let D i denotes the data on the ith computation process.
In some algorithms for matrix operations (such as the Gauss Elimination algorithm for matrix decomposition), the special checksum relationship can actually be designed on purpose. The following is a general framework for fault processing: Step 1: Add another encoding process into the application. Assume the data on this encoding process is E. For numerical computations, D i is often an array of floatingpoint numbers; therefore, at the beginning of the computation, we can create a checksum relationship among the data of all processes by initializing the data E on the encoding process as Step 2: During the execution of the application, redesign the algorithm to operate both on the data of computation processes and on the data of encoding process in such a way that the checksum relationship is always maintained during computation.
Step 3: If any process fails, then replace it with the encoding process and continue the execution.
Step 4: After each replacement of failed process, rebuild the redundancy process with the background accelerated recovery method.
Step 5: At the end of execution, the correct solution can be reconstructed through the intermediate result and the transformation matrix T. The above fault tolerance technique can be used to tolerate failstop processes failures without checkpointing or message logging. The special checksum relationship between the data on different processes can be designed on purpose by using the checksum matrices of the original matrices as the input matrices. To demonstrate the feasibility of HRBR, we will apply it to the widely used benchmark HPL in the next section.

INCORPORATING HRBR INTO HPL
In this section, we apply the algorithm-based fault tolerance technique HRBR to HPL, which is one of the most important benchmarks for supercomputing and is widely used for the ranking of supercomputers on Top500 [1]. HPL is to solve system of linear equations using the Gauss Elimination with Partial Pivoting (GEPP). For the simplicity of presentation, in this section, we only discuss the case where there is only one process failed simultaneously. However, it is straightforward to extend the result here to the multiple simultaneous process failure cases by simply using a weighted checksum scheme [12].

The Basic Idea
We will give a simple example to demonstrate the basic idea of our method. The purpose of HPL is to solve a system of linear equations: During the execution, when process P i fails and after the replacement with redundancy, the linear equations become: At the end of execution, we get the solution y as intermediate result.
Since the operations in Gauss Elimination are linear transformations, it is clear that the relationship is kept during the execution. Combining Eq. (9), (10) and (11), the correct solution x can be calculated by: If the transformation matrix T is the same as (7), then expand Eq. (12), we can get: It can be seen that since the simplicity of matrix T, the recomputing of solution x is surprisingly simple.
However, in the real implementation of HPL, the encoding of data matrix and the transformation matrix T will not be that simple. We will solve these issues in the next sections.

Two-Dimensional Block-Cyclic Data Distribution
It is well known [2] that the layout of an application's data within the hierarchical memory of a concurrent computer is critical in determining the performance and scalability of the parallel code. By using two-dimensional block-cyclic data distribution [2], HPL seeks to maintain load balance and reduce the frequency with which data must be transferred between processes.
For reasons described above, HPL organizes the onedimensional process array representation of an abstract parallel computer into a two-dimensional rectangular process grid. Therefore, a process in HPL can be referenced by its row and column coordinates within the grid. An example of such an organization is shown in Fig. 2. Global View Local (distributed) View Fig. 3. Two-dimensional block-cyclic matrix distribution.
The two-dimensional block-cyclic data distribution scheme is a mapping of the global matrix onto the rectangular process grid. There are two pairs of parameters associated with the mapping. The first pair of parameters is (m b , n b ), where m b is the row block size and n b is the column block size. The second pair of parameters is (P, Q), where P is the number of process rows in the process grid and Q is the number of process columns in the process grid.
Given an element a ij in the global matrix A, the process coordinate (p i , q j ) that a ij resides can be calculated by / mod , The local coordinate (i pi , j qj ) which a ij resides in the process (p i , q j ) can be calculated according to the following formula: For HPL, in the mapping of data onto the process grid, the right hand side b is viewed as a column vector besides the coefficients matrix A: (A|b). Fig. 3 is an example of mapping a 10×10 matrix and b onto a 2×2 process grid according to two-dimensional blockcyclic data distribution with m b =n b =2.

Encoding Data Distribution Matrix
In this section, we will construct encoding scheme which can be used to incorporate the HRBR method into the fault tolerance of HPL. The purpose of encoding is to create the checksum relationship proposed in Step 1 in Section 3.3.
Suppose the dimension of coefficients matrix A is n, n has achieved the magnitude of 2×10 6 for today's fastest supercomputer [1]. Since b is very small relative to A, we treat the redundancy of A and b separately and we mainly discuss the redundancy scheme of A in this paper. The redundancy of b can be simply viewed as there are multiple copies of b. Assume the data matrix A is originally mapped onto a P×Q process grid according to the two-dimensional block-cyclic data distribution. We adopt the same encoding scheme introduced in [12] which is developed for the conventional algorithmic recovery method. For the convenience of presentation, assume the size of the local matrices in each process is the same. We will explain our coding scheme for the matrix A with the help of the example matrix in Fig. 4. Fig. 4a shows the global view of all the elements of the example matrix. After the matrix is mapped onto a 2×2 process grid with m b =n b =1, the distributed view of this matrix is shown in Fig. 4b.
Suppose we want to tolerate a single process failure. We dedicate another P additional processes and organize the total (PQ +P) processes as a P×(Q+1) process grid with the original matrix A distributed onto the first P rows and Q columns of the process grid.
The distributed row checksum matrix A r of the matrix A is the original matrix A plus the part of data on the (Q+1)th process columns which can be obtained by adding all local matrices on the first Q process columns. Fig. 5b shows the distributed view of the row checksum matrix of the example matrix from Fig. 4. Fig. 5a is the global view of the row checksum matrix.
Generally the redundancy (in columns) of matrix A can be viewed as A*V, where V is often called the coding matrix. For the simple case of row checksum, V is an n×1 vector with Here V T denotes the transpose of matrix V. For the example matrix A in Fig. 4, the global view of redundancy A*V and the coding matrix V are as Fig. 6 shown.

Maintaining Encoding Relationship during the Execution
In this section, we will show that the encoding relationship between the original data matrix and the redundancy matrix established at the initial step can be maintained during the execution of HPL.
Solving system of linear equations using the Gauss Elimination method can also be viewed as a process of LU decomposition of the coefficients matrix. Given a matrix A, the purpose of LU decomposition is to find a lower triangular matrix L and an upper triangular matrix U such that A=L*U. Then the system of equations Ax=b is equivalent to solving Ux=L −1 b. Since L and U are both triangular matrix, then Ax=b can be solved by simple back substitution using L and U with a low cost.
The LU decomposition is a recursive process. The starting point is L 0 =I n (the identity matrix) and U 0 =A. At the end of decomposition, we get the lower triangular matrix L n =L, and the upper triangular matrix U n =U. At each of the intermediate step (L s , U s ), does the encoding relationship between the data matrix and redundancy still be maintained? Then the following conclusion can be given:

Theorem 1. In HPL, assume (A|b|AV) is the original data matrix and redundancy matrix. If at each step of the LU decomposition, we let the redundancy matrix executes the same update operations as the U matrix, then after each step (L s , U s ), the redundancy matrix is U s *V, i.e., the encoding relationship holds between the U matrix and redundancy.
Proof. If we view L 0 =I n and U 0 =A, then the initial step is After the first step of decomposition, L 0 becomes L 1 with where l 1 is a matrix and the update operations on matrix M using l 1 is equivalent to M left multiplied by matrix l 1 −1 : l 1 −1 *M. Since U 0 , L 0 −1 *b and U 0 *V execute the same update operations using l 1 , so U 0 becomes U 1 with and U 0 *V becomes So the encoding relationship is kept between the redundancy matrix and the U matrix. And it is clear that the solving of Ax=b is equivalent to the solving of Similarly, we can prove that the encoding relationship holds after each of the step (L s , U s ) with 0≤s≤n.

Failure Replacement Policy
When some process fails, assume its position in the process grid is (p, q), instead of only replacing it with the corresponding redundant process in the pth row, we replace all the p processes in the qth column with the entire column of redundant processes.
The reason that we adopt this replacement policy is as follows: if we replace the entire qth column of processes with the column of redundant processes, then in the global view of matrix A, the replacement can be viewed as some columns of A are replaced with the redundant columns A*V, and this type of replacement can be easily represented as a linear transformation of A. However, if we only replace the failed process with some redundant process, then the replacement can not be represented as a transformation of matrix A, so will bring difficulty to the deriving of transformation matrix, which can be seen in the next section.

The Deriving of Transformation Matrix
In general, we can assume that the redundancy of matrix A is A*V, where V is an n×m matrix, and can be viewed as m columns of redundancy vectors. As discussed in the above section, the replacement after failure can be viewed as the interchange of some columns of A with the m columns of redundancy vectors A*V. After the replacement, matrix A becomes A′, as discussed above, there should exist a transformation matrix T such that A′ =A*T. Then what is the form of matrix T? Lemma 1 is clear.
According to Lemma 1, it can be seen that the i 1 , i 2 ,…, i m columns of T are exactly the encoding vectors V 1 , V 2 ,…, V m respectively. The elements omitted in the diagonal of T (Eq. (22)) are all 1.
As for the example matrix A in Fig. 6, if process(0,1) fails, we replace process(0,1) and process(1,1) with the corresponding redundant processes, then the matrix A′ after replacement and the transformation matrix T are as Fig. 7 shown.
According to x=T*y and the form of T in Fig. 7, the recomputing of x can be expanded as the following: x 1 =y 1 +y 2 , x 2 =y 2 , x 3 =y 3 +y 4 , x 4 =y 4 .

THEORETICAL ANALYSIS
In this section, we will establish a model for the failure and performance of system, based on which we will theoretically analyze the efficiency of different methods for the fault tolerance of HPL, including algorithmic recovery method and HRBR.

Model of System Failure
In this paper we mainly discuss the type of fail-stop failures, and in the processor level. Suppose one computing system consists of p processors, we assume that all the processors are homogeneous, so have the same MTTF (assume as M). Then the failure rate λ of single processor is: λ=1/M. To achieve the scale of Exaflops, the number of processors included in a system is expected to be more than one million. In this paper we make an optimistic assumption that single processor's MTTF is 10 years, which is about 3.15×10 8 seconds. If a system consists of 10 6 processors, then MTTF of the system will be: 3.15×10 8 /10 6 =315 seconds. This means that there will be a failure occurring about five minutes. In contrast, many high performance scientific applications require running of hours and even days.
Suppose t is the time of failure occurs of one processor and D(t) is the failure probability distribution function for single processor, since the exponential distribution is the only continuous random distribution with a constant failure rate [6], we assume that D(t) is an exponential distribution, so The probability that there is no failure of one processor during time interval [0, t] is: 1−D(t)=e −λt . We make a simple assumption that the failures of processors in a system are independent from each other, so the probability that all the p processors in system have not failed during time interval [0, t] is: (24) The system is viewed as failed if there is one or more processors failed, so the probability that the system is failed during time interval [0, t] is exactly:

Performance Model of System Running HPL
For each processor in system, we assume that its floating point computing power is f (flops), and its memory size is m (byte). Then the total amount of memory of system is mp, and the theoretical peak performance of system is fp. According to a balanced system model and the long standing trends in top500's statistics of supercomputer [1], it is reasonable to assume that: We use the IEEE 754 double precision standard of floating point number, so the size of every number is 8 bytes. Suppose n is the matrix dimension in HPL, then the size of coefficients matrix is 8n 2 bytes, and the whole computation amount is about 2n 3 /3 times of floating point operations. According to the rule of thumb for choosing the matrix dimension [2], 80% of the total amount of memory should be filled by the coefficients matrix, so it holds that: 8n 2 =0.8pm (27) If all the processors in system are fully utilized and there is no failure occurs during the execution, the whole run time of HPL should be about: However, due to the dropping of system's MTTF, often failures will occur during the execution of applications. Fault tolerant method is adopted to tolerate failures during the execution, and this will result in extra cost in the execution time of applications and overhead in the system hardware. Suppose the execution of HPL will last T' (T' ≥ T) time under some fault tolerant method and the hardware efficiency of system under this method is e, then we can define the efficiency of this fault tolerant method as:

Efficiency of Algorithmic Recovery
As discussed above, the main overhead of algorithmic recovery method is the recovery of data on the failed processor. As for HPL, the coefficients matrix is evenly distributed onto all the processors. Suppose the size of coefficients matrix is n 2 , then the amount of data distributed onto one single processor is n 2 /p floating point numbers. As described in section 4.2, the p processors in system are organized as a P×Q process grid. In general, P and Q are slightly different. In the convenience of description, we assume that P=Q, so P=Q =p 0.5 . The recovery of any corrupted number involves the participation of Q processors using Since these Q processors can compute and communicate in parallel, it is clear that one The relationship between the efficiency of algorithmic recovery method and the system scale is as Fig. 1 shown.

Overhead of Background Accelerated Recovery
As discussed in section 3.2.2, we can reserve some faster processors and network to help the background recovery and speeding of redundancy processor. Then what is the overhead of this background accelerated recovery method? First we need the following lemma:  So it is clear that P 0 =e −λpt , P 1 =p(1−e −λt )e −λt(p−1) , and the probability that there are more than one processor failed is 1−P 0 −P 1 .
Then the following theorem can be given: Proof. Under the speed of original processor and network, the recovery time of one redundancy is t′ (from Eq. (33)). In the background accelerated recovery, assume the speed of faster processors and network is s times of the original speed, then the recovery time of one redundancy is t′/s. During the recovery of redundancy, the processors in progress have not stopped to wait. So to catch up with these processors, it will cost the redundancy processor another time of t′/(s(s−1)). So in fact the rebuild of one redundancy will cost time In the background accelerated recovery, if we adopt faster processors and network with s times of the original speed, then in expectation the rebuild time of one redundancy is equal to the MTTF of system. This means that in expectation, during the period of one processor failed, another processor can be repaired, which constitutes a balance of system.
Since there are three columns of redundancy built initially, then the system is failed only when there are more than three processors failed during one rebuild period M/p, according to Lemma 2, this probability is with t= M/p, and (1 ) ( ) .
Then it can be calculated that the probability is about 0.02, so the execution of HPL can be completed with a probability of 0.98.
It can be seen that the required speedup s is increasing with the number of processors p. When p=10 6 and c=100, s≈2.7, so we let s=3 is enough. Note that the analysis of rebuilding process here is not in detail due to its complexity, but the overhead of redundancy has already been considered.
In Eq. (49), if we let c=100 and consider three cases: n=p, n=10p and n=100p, then we can get the efficiency of HRBR as Fig.  8 shown. According to Fig. 8, in the worst case (n=p) the efficiency of HRBR is still above 0.88 when the system scale reaches one million processors, while then the efficiency of algorithmic recovery is nearly 1/3.

EXPERIMENT EVALUATION
We perform a set of experiments to verify the feasibility of HRBR method and compare its performance with the algorithmbased recovery method.
The experiments were performed on a SiCortex SC5832 supercomputer. The SC5832 has 972 nodes, 5,832 cores and 3888 GB of memory. It uses a diameter-6 Kautz graph for 2,916 links. Each node consists of six cores that implement the MIPS64 instruction set architecture (ISA). The cluster interconnect provides a maximum bandwidth of 2 GB/s. The reason that we choose SC5832 as the platform lies in that: first, it's a very balanced system (the ratio between computing power and communication bandwidth is nearly 2); second, its network is very stable, making the fluctuations in experiments nearly negligible. Our experiments are not based on a full implementation since it needs support from runtime system for failure detection and recovery. In [27] we have discussed the needed MPI feature for self-healing MPI programming.
To make things simple, we use scheduled failures during the HPL update phases. Failures were simulated by flushing the matrix data and marking the status of processes to be dead. All failures could be detected by a reduce operation on the values of process status after every update phase. And a new failure is only generated after failure handlings of the previous one has been finished. Both algorithmic recovery and HRBR method are implemented with MPICH2.
To implement background accelerated recovery of redundancy, we need some faster processors and network. We use openMP to help "build" faster processors. We initiate one process per physical core and leave a free core for each redundant process. When it needs to accelerate computation, the redundant process run in OpenMP mode with two thread, so that it seems as if it was running on a twice faster processor. As for the faster network, we add additional accelerated rows of processes in the process grid to help compute processes reduce their local matrices to redundant processes.
In the experiments we keep the local matrix size to about 3000x3000 and change the system scale up to 2300 cores. Three successive failures are scheduled in each test. The Recovery and HRBR mode are compared in the same configuration except some additional cores for HRBR acceleration.
Experiment results show that both methods get the correct results with negligible error. Table 1 shows the comparison between the performance of HRBR and algorithmic recovery method, where N is the matrix dimension and P is the number of processes totally used. It can be seen that under the scale of experiment (P ranges from the order of 10 2 to 10 3 ), the gap between the performance of HRBR and algorithmic recovery method is small, however, the advantage of HRBR is still observable.

Related Works
Conventional algorithm based fault tolerance (ABFT) uses information at the end of execution of an algorithm to detect and recover failures and incorrect calculations for fail-continue failures [5] [21]. Fail-continue failures are failures which do not halt execution. The idea of ABFT is to encode the original matrices using real number codes and then re-design algorithms to operate on the encoded matrices. In [21], Huang and Abraham proved that the encoding relationship in the input encoded matrices is preserved at the end of the computation no matter which algorithm is used to perform the computation. Therefore, processor miscalculations can be detected, located, and corrected at the end of the computation. ABFT algorithms have received wide investigation, including development for specific hardware architectures [8], efficient codes for use in ABFT [7] [25], and analysis of potential performance under more advanced failure conditions [4].
In a distributed environment such as high performance clusters, if a failed processor stops working, then we need to be able to tolerate failures in the middle of the computation, to recover the data or adopt other possible methods. Recently, the use of algorithmic methods without checkpointing to help recover during fail-stop failures has been investigated by Chen and Dongrra [11] [12]. It has been shown that this method can be applied to large scale parallel matrix operations, like matrix multiplication, Cholesky factorization, and iterative methods for solving linear equations [13][14] [15]. By incorporating this method into ScaLAPACK and HPL, experimentation demonstrates that this method has decreasing overhead in relation to overall runtime as the matrix size increases, and thus shows promise to reduce the expected runtime for HPC applications on very large matrices.

Discussion
In this paper, a new algorithm-based fault tolerant scheme for fail-stop failures has been proposed, which has combined the advantages of Huang's ABFT method [21] for fail-continue failures and Chen's algorithmic recovery method [12] for fail-stop failures. The recovery of correct solution is performed at the end of the execution, and the redundancy is recovered in background immediately when failure and replacement occur. Though in this paper we only demonstrate how to incorporate HRBR to the HPL, it is clear that HRBR can be easily extended to matrix operations such as addition, multiplication, scalar product and transposition. The advantage of HRBR lies in that it has dramatically decreased the impact of failures on the execution of applications with hot replacement. Note that if an algorithmic recovery process has no hotspot, the background recovery mechanism can also be used.
The failure modeling in this paper is not new since a lot of studies have done in this field. However, the main purpose of failure modeling is to compare the efficiency of different methods. We only discuss the single processor failure, where the failure mode like a mid-plane or rack failure has not been considered. But this kind of failures can be tolerated by carefully designing the redundancy pattern. In fact, our scheme can endure multiple nodes failure if they are not in the same row. Future work will extend the failure mode to more practical issues. Some high end system may have a longer node-MTTF than in this paper, and the failures rates of future systems may not be as high as estimated. However, if only the premise that "MTTF of system is decreasing with the increasing of system scale" holds, the proposed HRBR will stand on its own when the system scale is large enough. High end system may only postpone but not solve the scale problem.

CONCLUSION AND FUTURE WORKS
In this paper, we have presented a new algorithm-based fault tolerance scheme, hot replacement with background accelerated recovery, for HPC applications. Because no periodical checkpoint or stop-and-wait recovery is involved in this approach, process failures can often be tolerated with a very low overhead. We showed the practicality of this technique by applying it to the HPL, which is representative benchmark for supercomputers to achieve high performance and scalability. Theoretical analysis and experiment evaluation demonstrate that our new scheme can still be efficient for a million way parallelism at the Exaflops scale, when traditional checkpointing and even algorithmic recovery method failed.
There are many directions in which this work could be extended. The first direction is to extend this approach to more applications. Second, a more robust implementation of this scheme at large scale and under real circumstances should be developed. Furthermore, it is also interesting to investigate the accuracy and stability of this algorithm-based fault tolerance technique at large scale.