Algorithm-based fault tolerance for fail-stop failures

Zizhong Chen; Jack Dongarra

doi:10.1109/TPDS.2008.58

Algorithm-based fault tolerance for fail-stop failures

Zizhong Chen, Jack Dongarra

Research output: Contribution to journal › Article › peer-review

102 Scopus citations

Abstract

Fail-stop failures in distributed environments are often tolerated by checkpointing or message logging. In this paper, we show that fail-stop process failures in ScaLAPACK matrix-matrix multiplication kennel can be tolerated without checkpointing or message logging. It has been proved in previous algorithm-based fault tolerance that, for matrix-matrix multiplication, the checksum relationship in the input checksum matrices is preserved at the end of the computation no mater which algorithm is chosen. From this checksum relationship in the final computation results, processor miscalculations can be detected, located, and corrected at the end of the computation. However, whether this checksum relationship can be maintained in the middle of the computation or not remains open. In this paper, we first demonstrate that, for many matrix matrix multiplication algorithms, the checksum relationship in the input checksum matrices is not maintained in the middle of the computation. We then prove that, however, for the outer product version algorithm, the checksum relationship in the input checksum matrices can be maintained in the middle of the computation. Based on this checksum relationship maintained in the middle of the computation, we demonstrate that fail-stop process failures (which are often tolerated by checkpointing or message logging) in ScaLAPACK matrix-matrix multiplication can be tolerated without checkpointing or message logging.

Original language	English
Pages (from-to)	1628-1641
Number of pages	14
Journal	IEEE Transactions on Parallel and Distributed Systems
Volume	19
Issue number	12
DOIs	https://doi.org/10.1109/TPDS.2008.58
State	Published - 2008
Externally published	Yes

Funding

The authors would like to thank the anonymous reviewers for their valuable comments. This research was supported in part by the Los Alamos National Laboratory under Contract 03891-001-99 49 and the Applied Mathematical Sciences Research Program of the Office of Mathematical, Information, and Computational Sciences, US Department of Energy under Contract DE-AC05-00OR22725 with UT-Battelle, LLC.

Funders	Funder number
U.S. Department of Energy	DE-AC05-00OR22725
Los Alamos National Laboratory	03891-001-99 49

Keywords

Algorithm-based fault tolerance
Checkpointing
Fail-stop failures
Parallel matrix-matrix multiplication
ScaLAPACK

Access to Document

10.1109/TPDS.2008.58

Cite this

@article{94af61a784234f709c8b7a07cb80e038,

title = "Algorithm-based fault tolerance for fail-stop failures",

abstract = "Fail-stop failures in distributed environments are often tolerated by checkpointing or message logging. In this paper, we show that fail-stop process failures in ScaLAPACK matrix-matrix multiplication kennel can be tolerated without checkpointing or message logging. It has been proved in previous algorithm-based fault tolerance that, for matrix-matrix multiplication, the checksum relationship in the input checksum matrices is preserved at the end of the computation no mater which algorithm is chosen. From this checksum relationship in the final computation results, processor miscalculations can be detected, located, and corrected at the end of the computation. However, whether this checksum relationship can be maintained in the middle of the computation or not remains open. In this paper, we first demonstrate that, for many matrix matrix multiplication algorithms, the checksum relationship in the input checksum matrices is not maintained in the middle of the computation. We then prove that, however, for the outer product version algorithm, the checksum relationship in the input checksum matrices can be maintained in the middle of the computation. Based on this checksum relationship maintained in the middle of the computation, we demonstrate that fail-stop process failures (which are often tolerated by checkpointing or message logging) in ScaLAPACK matrix-matrix multiplication can be tolerated without checkpointing or message logging.",

keywords = "Algorithm-based fault tolerance, Checkpointing, Fail-stop failures, Parallel matrix-matrix multiplication, ScaLAPACK",

author = "Zizhong Chen and Jack Dongarra",

year = "2008",

doi = "10.1109/TPDS.2008.58",

language = "English",

volume = "19",

pages = "1628--1641",

journal = "IEEE Transactions on Parallel and Distributed Systems",

issn = "1045-9219",

publisher = "Institute of Electrical and Electronics Engineers",

number = "12",

}

TY - JOUR

T1 - Algorithm-based fault tolerance for fail-stop failures

AU - Chen, Zizhong

AU - Dongarra, Jack

PY - 2008

Y1 - 2008

N2 - Fail-stop failures in distributed environments are often tolerated by checkpointing or message logging. In this paper, we show that fail-stop process failures in ScaLAPACK matrix-matrix multiplication kennel can be tolerated without checkpointing or message logging. It has been proved in previous algorithm-based fault tolerance that, for matrix-matrix multiplication, the checksum relationship in the input checksum matrices is preserved at the end of the computation no mater which algorithm is chosen. From this checksum relationship in the final computation results, processor miscalculations can be detected, located, and corrected at the end of the computation. However, whether this checksum relationship can be maintained in the middle of the computation or not remains open. In this paper, we first demonstrate that, for many matrix matrix multiplication algorithms, the checksum relationship in the input checksum matrices is not maintained in the middle of the computation. We then prove that, however, for the outer product version algorithm, the checksum relationship in the input checksum matrices can be maintained in the middle of the computation. Based on this checksum relationship maintained in the middle of the computation, we demonstrate that fail-stop process failures (which are often tolerated by checkpointing or message logging) in ScaLAPACK matrix-matrix multiplication can be tolerated without checkpointing or message logging.

AB - Fail-stop failures in distributed environments are often tolerated by checkpointing or message logging. In this paper, we show that fail-stop process failures in ScaLAPACK matrix-matrix multiplication kennel can be tolerated without checkpointing or message logging. It has been proved in previous algorithm-based fault tolerance that, for matrix-matrix multiplication, the checksum relationship in the input checksum matrices is preserved at the end of the computation no mater which algorithm is chosen. From this checksum relationship in the final computation results, processor miscalculations can be detected, located, and corrected at the end of the computation. However, whether this checksum relationship can be maintained in the middle of the computation or not remains open. In this paper, we first demonstrate that, for many matrix matrix multiplication algorithms, the checksum relationship in the input checksum matrices is not maintained in the middle of the computation. We then prove that, however, for the outer product version algorithm, the checksum relationship in the input checksum matrices can be maintained in the middle of the computation. Based on this checksum relationship maintained in the middle of the computation, we demonstrate that fail-stop process failures (which are often tolerated by checkpointing or message logging) in ScaLAPACK matrix-matrix multiplication can be tolerated without checkpointing or message logging.

KW - Algorithm-based fault tolerance

KW - Checkpointing

KW - Fail-stop failures

KW - Parallel matrix-matrix multiplication

KW - ScaLAPACK

UR - http://www.scopus.com/inward/record.url?scp=57049092162&partnerID=8YFLogxK

U2 - 10.1109/TPDS.2008.58

DO - 10.1109/TPDS.2008.58

M3 - Article

AN - SCOPUS:57049092162

SN - 1045-9219

VL - 19

SP - 1628

EP - 1641

JO - IEEE Transactions on Parallel and Distributed Systems

JF - IEEE Transactions on Parallel and Distributed Systems

IS - 12

ER -

Algorithm-based fault tolerance for fail-stop failures

Abstract

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this