Erasure coding for fault-oblivious linear system solvers

DOI10.1137/15M1041511MaRDI QIDQ2964445zbMATH OpenOpenAlexFDO

Authors Yao Zhu, David F. Gleich, Ananth Grama

Publication date 27 February 2017

Published in SIAM Journal on Scientific Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1412.7364

zbMATH Keywords

algorithm based fault toleranceerasure codingfault oblivious computationlinear system solvers

Mathematics Subject Classification ID

Iterative numerical methods for linear systems (65F10) Parallel numerical computation (65Y05) Distributed systems (68M14) Reliability, testing and fault tolerance of networks and computer systems (68M15)

Abstract: Dealing with hardware and software faults is an important problem as parallel and distributed systems scale to millions of processing cores and wide area networks. Traditional methods for dealing with faults include checkpoint-restart, active replicas, and deterministic replay. Each of these techniques has associated resource overheads and constraints. In this paper, we propose an alternate approach to dealing with faults, based on input augmentation. This approach, which is an algorithmic analog of erasure coded storage, applies a minimally modified algorithm on the augmented input to produce an augmented output. The execution of such an algorithm proceeds completely oblivious to faults in the system. In the event of one or more faults, the real solution is recovered using a rapid reconstruction method from the augmented output. We demonstrate this approach on the problem of solving sparse linear systems using a conjugate gradient solver. We present input augmentation and output recovery techniques. Through detailed experiments, we show that our approach can be made oblivious to a large number of faults with low computational overhead. Specifically, we demonstrate cases where a single fault can be corrected with less than 10% overhead in time, and even in extreme cases (fault rates of 20%), our approach is able to compute a solution with reasonable overhead. These results represent a significant improvement over the state of the art.

Recommendations

• Publication:4893157
• A new and faster Gaussian elimination based fault tolerant systolic linear system solver
• scientific article; zbMATH DE number 653400
• Sparse random erasure code: a fault tolerance scheme for large-scale storage system
• Numerical recovery strategies for parallel resilient Krylov linear solvers.

Cites work

• A Flexible Inner-Outer Preconditioned GMRES Algorithm
• A mathematical introduction to compressive sensing
• Algorithm-Based Fault Tolerance for Matrix Operations
• Application of the implicitly updated Arnoldi method with a complex shift-and-invert strategy in MHD
• Computational Science – ICCS 2005
• Flexible conjugate gradients
• Flexible Inner-Outer Krylov Subspace Methods
• Inexact Krylov Subspace Methods for Linear Systems
• Low-distortion subspace embeddings in input-sparsity time and applications to robust linear regression
• Scalable failure masking for stencil computations using ghost region expansion and cell to rank remapping
• Sparse matrix test problems
• The Idea behind Krylov Methods
• The Lanczos and Conjugate Gradient Algorithms
• The University of Florida sparse matrix collection
• Theory of Inexact Krylov Subspace Methods and Applications to Scientific Computing
• Three-way arrays: rank and uniqueness of trilinear decompositions, with application to arithmetic complexity and statistics

Cited in

(2)

• A minimally intrusive low-memory approach to resilience for existing transient solvers
• Coding Approaches to Fault Tolerance in Linear Dynamic Systems

Describes a project that uses

Uses Software

• MapReduce
• SparseMatrix
• Harwell-Boeing sparse matrix collection

This page was built for publication: Erasure coding for fault-oblivious linear system solvers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2964445)