An algorithmic approach to error localization and partial recomputation for low-overhead fault tolerance

Joseph Sloan, Rakesh Kumar, Greg Bronevetsky

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

The increasing size and complexity of massively parallel systems (e.g. HPC systems) is making it increasingly likely that individual circuits will produce erroneous results. For this reason, novel fault tolerance approaches are increasingly needed. Prior fault tolerance approaches often rely on checkpoint-rollback based schemes. Unfortunately, such schemes are primarily limited to rare error event scenarios as the overheads of such schemes become prohibitive if faults are common. In this paper, we propose a novel approach for algorithmic correction of faulty application outputs. The key insight for this approach is that even under high error scenarios, even if the result of an algorithm is erroneous, most of it is correct. Instead of simply rolling back to the most recent checkpoint and repeating the entire segment of computation, our novel resilience approach uses algorithmic error localization and partial recomputation to efficiently correct the corrupted results. We evaluate our approach in the specific algorithmic scenario of linear algebra operations, focusing on matrix-vector multiplication (MVM) and iterative linear solvers. We develop a novel technique for localizing errors in MVM and show how to achieve partial recomputation within this algorithm, and demonstrate that this approach both improves the performance of the Conjugate Gradient solver in high error scenarios by 3x-4x and increases the probability that it completes successfully by up to 60% with parallel experiments up to 100 nodes.

Original languageEnglish (US)
Title of host publication2013 43rd Annual IEEE/IFIP International Conference on Dependable Systems and Networks, DSN 2013
DOIs
StatePublished - Sep 9 2013
Event2013 43rd Annual IEEE/IFIP International Conference on Dependable Systems and Networks, DSN 2013 - Budapest, Hungary
Duration: Jun 24 2013Jun 27 2013

Publication series

NameProceedings of the International Conference on Dependable Systems and Networks

Other

Other2013 43rd Annual IEEE/IFIP International Conference on Dependable Systems and Networks, DSN 2013
CountryHungary
CityBudapest
Period6/24/136/27/13

Keywords

  • algorithmic error correction
  • error localization
  • numerical methods
  • partial recomputation
  • sparse linear algebra

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications

Fingerprint Dive into the research topics of 'An algorithmic approach to error localization and partial recomputation for low-overhead fault tolerance'. Together they form a unique fingerprint.

Cite this