Algorithmic approaches to low overhead fault detection for sparse linear algebra

Joseph Sloan, Rakesh Kumar, Greg Bronevetsky

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

Abstract

The increasing size and complexity of High-Performance Computing systems is making it increasingly likely that individual circuits will produce erroneous results, especially when operated in a low energy mode. Previous techniques for Algorithm - Based Fault Tolerance (ABFT) [20] have been proposed for detecting errors in dense linear operations, but have high overhead in the context of sparse problems. In this paper, we propose a set of algorithmic techniques that minimize the overhead of fault detection for sparse problems. The techniques are based on two insights. First, many sparse problems are well structured (e.g. diagonal, banded diagonal, block diagonal), which allows for sampling techniques to produce good approximations of the checks used for fault detection. These approximate checks may be acceptable for many sparse linear algebra applications. Second, many linear applications have enough reuse that pre-conditioning techniques can be used to make these applications more amenable to low-cost algorithmic checks. The proposed techniques are shown to yield up to 2× reductions in performance overhead over traditional ABFT checks for a spectrum of sparse problems. A case study using common linear solvers further illustrates the benefits of the proposed algorithmic techniques.

Original languageEnglish (US)
Title of host publication2012 42nd Annual IEEE/IFIP International Conference on Dependable Systems and Networks, DSN 2012
DOIs
StatePublished - Oct 1 2012
Event42nd Annual IEEE/IFIP International Conference on Dependable Systems and Networks, DSN 2012 - Boston, MA, United States
Duration: Jun 25 2012Jun 28 2012

Publication series

NameProceedings of the International Conference on Dependable Systems and Networks

Other

Other42nd Annual IEEE/IFIP International Conference on Dependable Systems and Networks, DSN 2012
CountryUnited States
CityBoston, MA
Period6/25/126/28/12

Keywords

  • ABFT
  • error detection
  • numerical methods
  • sparse linear algebra

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications

Fingerprint Dive into the research topics of 'Algorithmic approaches to low overhead fault detection for sparse linear algebra'. Together they form a unique fingerprint.

Cite this