More Web Proxy on the site http://driver.im/

research-article

Public Access

Resilient Matrix Multiplication of Hierarchical Semi-Separable Matrices

Authors:

Xiaoye LiAuthors Info & Claims

FTXS '15: Proceedings of the 5th Workshop on Fault Tolerance for HPC at eXtreme Scale

Pages 19 - 26

https://doi.org/10.1145/2751504.2751507

Published: 15 June 2015 Publication History

Abstract

The hierarchical semi-separable (HSS) matrix factorization has useful characteristics for representing low-rank operators on extreme scale computing systems. To prepare for the higher error rates anticipated with future architectures, this paper introduces new fault-tolerant algorithms for HSS matrix multiplication that maintain efficient performance in the presence of high error rates. The measured runtime overhead for error checking and data preservation using the Containment Domains library is exceptionally small and encourages the use of frequent, fine-grained error checking when using algorithm based fault tolerance.

References

[1]

A. Avizienis, J.-C. Laprie, B. Randell, and C. Landwehr. Basic concepts and taxonomy of dependable and secure computing. Dependable and Secure Computing, IEEE Transactions on, 1(1):11--33, Jan 2004.

Digital Library

[2]

Greg Bronevetsky and Bronis de Supinski. Soft error vulnerability of iterative linear algebra methods. In Proceedings of the 22nd Annual International Conference on Supercomputing, ICS '08, pages 155--164, New York, NY, USA, 2008. ACM.

Digital Library

[3]

Zizhong Chen and J. Dongarra. Algorithm-based fault tolerance for fail-stop failures. Parallel and Distributed Systems, IEEE Transactions on, 19(12):1628--1641, Dec 2008.

Digital Library

[4]

J. Chung, I. Lee, M. Sullivan, J. H. Ryoo, D. W. Kim, D. H. Yoon, L. Kaplan, and M. Erez. Containment domains: A scalable, efficient, and flexible resilience scheme for exascale systems. In Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis (SC). IEEE., 2012.

Digital Library

[5]

P. Du, P. Luszczek, and J. Dongarra. High Performance Dense Linear System Solver with Soft Error Resilience. In Proc. of 2011 IEEE International Conference on Cluster Computing, pages 272--280, 2011.

Digital Library

[6]

Kuang-Hua Huang and J.A. Abraham. Algorithm-based fault tolerance for matrix operations. Computers, IEEE Transactions on, C-33(6):518--528, June 1984.

Digital Library

[7]

Y. Jia, G. Bosilca, P. Luszczek, and J. Dongarra. Parallel Reduction to Hessenberg Form with Algorithm-Based Fault Tolerance. In Proc. of SC13, Denver, CO, USA, November 17--21 2013.

Digital Library

[8]

Y. Jia, P. Luszczek, G. Bosilca, and J. Dongarra. CPU-GPU Hybrid Bidiagonal Reduction With Soft Error Resilience. In Proc. of ScalA'13 (4th Workshop on Latest Advances in Scalable Algorithms for Large-Scale Systems), Denver, CO, USA, November 17--21 2013.

Digital Library

[9]

Franklin T. Luk and Haesun Park. An Analysis of Algorithm-Based Fault Tolerance Techniques. J. Parallel and Distributed Computing, 5:172--184, November 1988.

Digital Library

[10]

Franklin T. Luk and Haesun Park. Fault-Tolerance Matrix Trianglations on Systolic Arrays. Computers, IEEE Transactions on, 37(11):1434--1438, November 1988.

Digital Library

[11]

P.G. Martinsson. A fast randomized algorithm for computing a hierarchically semiseparable representation of a matrix. SIAM J. Matrix Analysis and Applications, 32(4):1251--1274, 2011.

Digital Library

[12]

F.-H. Rouet, X.S. Li, and P. Ghysels. A distributed-memory package for dense hierarchically semi-separable matrix computations using randomization. ACM Trans. Mathematical Software, 2015. (submitted).

[13]

Manu Shantharam, Sowmyalatha Srinivasmurthy, and Padma Raghavan. Fault tolerant preconditioned conjugate gradient for sparse linear system solution. In Proceedings of the 26th ACM International Conference on Supercomputing, ICS '12, pages 69--78, New York, NY, USA, 2012. ACM.

Digital Library

[14]

M. Snir, R. W. Wisniewski, J. A. Abraham, S. V. Adve, S. Bagchi, Pavan Balaji, J. Belak, P. Bose, F. Cappello, B. Carlson, Andrew A. Chien, P. Coteus, N. A. Debardeleben, P. Diniz, C. Engelmann, M. Erez, S. Fazzari, A. Geist, R. Gupta, F. Johnson, Sriram Krishnamoorthy, Sven Leyffer, D. Liberty, S. Mitra, T. S. Munson, R. Schreiber, J. Stearley, and E. V. Hensbergen. Addressing failures in exascale computing. 2013.

[15]

Vilas Sridharan and Dean Liberty. A Study of DRAM Failures in the Field. In Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis, SC '12, pages 76:1--76:11, Los Alamitos, CA, USA, 2012. IEEE Computer Society Press.

Digital Library

[16]

CD Team. Containment Domains API v0.1 (C++), 2014.

[17]

GVR Team. Global View Resilience, API Documentation R0.8.1-rc0. Technical Report TR-2014-05, University of Chicago, University of Chicago, 2014.

[18]

S. Wang, X.S. Li, J. Xia, Y. Situ, and M.V. de Hoop. Efficient parallel algorithms for solving linear systems with hierarchically semiseparable structures. SIAM J. Scientific Computing, 35(6):C519--C544, 2013.

[19]

Panruo Wu and Zizhong Chen. FT-ScaLAPACK: Correcting Soft Errors On-line for ScaLAPACK Cholesky, QR, and LU Factorization Routines. In Proceedings of the 23rd International Symposium on High-performance Parallel and Distributed Computing, HPDC '14, pages 49--60, New York, NY, USA, 2014. ACM.

Digital Library

[20]

J. Xia. Randomized sparse direct solvers. SIAM J. Matrix Anal. Appl., 34(1):197--227, 2013.

Digital Library

[21]

Z. Zheng, A. A. Chien, and K. Teranishi. Fault Tolerance in an Inner-outer Solver: A GVR-enabled Case Study. In Proc. of VECPAR'14 11th International Meeting on High Performance Computing for Computational Science, Eugene, Oregon, USA, June 30-July 3 2014.

Cited By

Agullo EAltenbernd MAnzt HBautista-Gomez LBenacchio TBonaventura LBungartz HChatterjee SCiorba FDeBardeleben NDrzisga DEibl SEngelmann CGansterer WGiraud LGöddeke DHeisig MJézéquel FKohl NLi XLion RMehl MMycek PObersteiner MQuintana-Ortí ERizzi FRüde USchulz MFung FSpeck RStals LTeranishi KThibault SThönnes DWagner AWohlmuth B(2022)Resiliency in numerical algorithm design for extreme scale simulationsInternational Journal of High Performance Computing Applications10.1177/1094342021105518836:2(251-285)Online publication date: 1-Mar-2022
https://dl.acm.org/doi/10.1177/10943420211055188
Samfass PWeinzierl TReinarz ABader M(2021)Doubt and Redundancy Kill Soft Errors—Towards Detection and Correction of Silent Data Corruption in Task-based Numerical Software2021 IEEE/ACM 11th Workshop on Fault Tolerance for HPC at eXtreme Scale (FTXS)10.1109/FTXS54580.2021.00005(1-10)Online publication date: Nov-2021
https://doi.org/10.1109/FTXS54580.2021.00005
Reinarz AGallard JBader M(2018)Influence of A-Posteriori Subcell Limiting on Fault Frequency in Higher-Order DG Schemes2018 IEEE/ACM 8th Workshop on Fault Tolerance for HPC at eXtreme Scale (FTXS)10.1109/FTXS.2018.00012(79-86)Online publication date: Nov-2018
https://doi.org/10.1109/FTXS.2018.00012

Index Terms

Resilient Matrix Multiplication of Hierarchical Semi-Separable Matrices
1. Computing methodologies
  1. Modeling and simulation

Recommendations

Silent Data Corruption Resilient Two-sided Matrix Factorizations
PPoPP '17: Proceedings of the 22nd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming

This paper presents an algorithm based fault tolerance method to harden three two-sided matrix factorizations against soft errors: reduction to Hessenberg form, tridiagonal form, and bidiagonal form. These two sided factorizations are usually the ...
Silent Data Corruption Resilient Two-sided Matrix Factorizations
PPoPP '17

This paper presents an algorithm based fault tolerance method to harden three two-sided matrix factorizations against soft errors: reduction to Hessenberg form, tridiagonal form, and bidiagonal form. These two sided factorizations are usually the ...
Fault tolerant communication-optimal 2.5D matrix multiplication

In future computing systems, handling faults efficiently at the algorithmic level is expected to become more and more important. In this paper, we illustrate that in practice classical algorithm-based fault tolerance (ABFT) cannot protect all exponent ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

FTXS '15: Proceedings of the 5th Workshop on Fault Tolerance for HPC at eXtreme Scale

June 2015

78 pages

ISBN:9781450335690

DOI:10.1145/2751504

General Chair:
Nathan DeBardeleben
Los Alamos National Laboratory, USA
,
Program Chairs:
Nathan DeBardeleben
Los Alamos National Laboratory, USA
,
Franck Cappello
Argonne National Laboratory and UIUC, USA
,
Robert Clay
Sandia National Laboratories, USA

Copyright © 2015 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

University of Arizona: University of Arizona
SIGARCH: ACM Special Interest Group on Computer Architecture

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 15 June 2015

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

U.S. Department of Energy

Conference

HPDC'15

Sponsor:

University of Arizona
SIGARCH

HPDC'15: The 24th International Symposium on High-Performance Parallel and Distributed Computing

June 15, 2015

Oregon, Portland, USA

Acceptance Rates

FTXS '15 Paper Acceptance Rate 9 of 15 submissions, 60%;

Overall Acceptance Rate 16 of 25 submissions, 64%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
311
Total Downloads

Downloads (Last 12 months)58
Downloads (Last 6 weeks)12

Reflects downloads up to 10 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Agullo EAltenbernd MAnzt HBautista-Gomez LBenacchio TBonaventura LBungartz HChatterjee SCiorba FDeBardeleben NDrzisga DEibl SEngelmann CGansterer WGiraud LGöddeke DHeisig MJézéquel FKohl NLi XLion RMehl MMycek PObersteiner MQuintana-Ortí ERizzi FRüde USchulz MFung FSpeck RStals LTeranishi KThibault SThönnes DWagner AWohlmuth B(2022)Resiliency in numerical algorithm design for extreme scale simulationsInternational Journal of High Performance Computing Applications10.1177/1094342021105518836:2(251-285)Online publication date: 1-Mar-2022
https://dl.acm.org/doi/10.1177/10943420211055188
Samfass PWeinzierl TReinarz ABader M(2021)Doubt and Redundancy Kill Soft Errors—Towards Detection and Correction of Silent Data Corruption in Task-based Numerical Software2021 IEEE/ACM 11th Workshop on Fault Tolerance for HPC at eXtreme Scale (FTXS)10.1109/FTXS54580.2021.00005(1-10)Online publication date: Nov-2021
https://doi.org/10.1109/FTXS54580.2021.00005
Reinarz AGallard JBader M(2018)Influence of A-Posteriori Subcell Limiting on Fault Frequency in Higher-Order DG Schemes2018 IEEE/ACM 8th Workshop on Fault Tolerance for HPC at eXtreme Scale (FTXS)10.1109/FTXS.2018.00012(79-86)Online publication date: Nov-2018
https://doi.org/10.1109/FTXS.2018.00012

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents