Algorithm-based fault tolerance for dense matrix factorizations

Dense matrix factorizations like LU, Cholesky and QR are widely used for scientific applications that require solving systems of linear equations, eigenvalues and linear least squa-res problems. Such computations are normally carried out on supercomputers where the ever-growing scale induces a fast decrease of the Mean Time To Failure (MTTF). This pa-per proposes a new algorithm-based fault tolerant (ABFT) approach, designed to survive fail-stop failures during dense matrix factorizations in extreme conditions such as the ab-sence of any reliable components, and the possibility of loos-ing both data and checksum from a single failure. Both left and right factorization results are protected by ABFT algo-rithms, and fault-tolerant algorithms derived from this solu-tion can be directly applied to a wide range of dense matrix factorizations, with minor modifications. Theoretical anal-ysis shows that the overhead is sharply decreasing with the number of computing units and the problem size. We im-plemented the ABFT versions of LU based on ScaLAPACK as a demonstration. Experimental results on the Kraken supercomputer validate the theoretical evaluation. Categories and Subject Descriptors System Software [Software approaches for fault toler-ance and resilience]: Software for high-performance com-putin