%0 Journal Article
%J ACM Transactions on Parallel Computing
%D 2015
%T Algorithm-based Fault Tolerance for Dense Matrix Factorizations, Multiple Failures, and Accuracy
%A Aurelien Bouteiller
%A Thomas Herault
%A George Bosilca
%A Peng Du
%A Jack Dongarra
%E Phillip B. Gibbons
%K ABFT
%K algorithms
%K fault-tolerance
%K High Performance Computing
%K linear algebra
%X Dense matrix factorizations, such as LU, Cholesky and QR, are widely used for scientific applications that require solving systems of linear equations, eigenvalues and linear least squares problems. Such computations are normally carried out on supercomputers, whose ever-growing scale induces a fast decline of the Mean Time To Failure (MTTF). This paper proposes a new hybrid approach, based on Algorithm-Based Fault Tolerance (ABFT), to help matrix factorizations algorithms survive fail-stop failures. We consider extreme conditions, such as the absence of any reliable node and the possibility of losing both data and checksum from a single failure. We will present a generic solution for protecting the right factor, where the updates are applied, of all above mentioned factorizations. For the left factor, where the panel has been applied, we propose a scalable checkpointing algorithm. This algorithm features high degree of checkpointing parallelism and cooperatively utilizes the checksum storage leftover from the right factor protection. The fault-tolerant algorithms derived from this hybrid solution is applicable to a wide range of dense matrix factorizations, with minor modifications. Theoretical analysis shows that the fault tolerance overhead decreases inversely to the scaling in the number of computing units and the problem size. Experimental results of LU and QR factorization on the Kraken (Cray XT5) supercomputer validate the theoretical evaluation and confirm negligible overhead, with- and without-errors. Applicability to tolerate multiple failures and accuracy after multiple recovery is also considered.
%B ACM Transactions on Parallel Computing
%V 1
%P 10:1-10:28
%8 01-2015
%G eng
%N 2
%R 10.1145/2686892
%0 Conference Paper
%B International Workshop on OpenCL
%D 2014
%T clMAGMA: High Performance Dense Linear Algebra with OpenCL
%A Chongxiao Cao
%A Jack Dongarra
%A Peng Du
%A Mark Gates
%A Piotr Luszczek
%A Stanimire Tomov
%X This paper presents the design and implementation of several fundamental dense linear algebra (DLA) algorithms in OpenCL. In particular, these are linear system solvers and eigenvalue problem solvers. Further, we give an overview of the clMAGMA library, an open source, high performance OpenCL library that incorporates the developments presented, and in general provides to heterogeneous architectures the DLA functionality of the popular LAPACK library. The LAPACK-compliance and use of OpenCL simplify the use of clMAGMA in applications, while providing them with portably performant DLA. High performance is obtained through use of the high-performance OpenCL BLAS, hardware and OpenCL-specific tuning, and a hybridization methodology where we split the algorithm into computational tasks of various granularities. Execution of those tasks is properly scheduled over the heterogeneous hardware components by minimizing data movements and mapping algorithmic requirements to the architectural strengths of the various heterogeneous hardware components.
%B International Workshop on OpenCL
%C Bristol University, England
%8 05-2014
%G eng
%0 Generic
%D 2013
%T clMAGMA: High Performance Dense Linear Algebra with OpenCL
%A Chongxiao Cao
%A Jack Dongarra
%A Peng Du
%A Mark Gates
%A Piotr Luszczek
%A Stanimire Tomov
%X This paper presents the design and implementation of sev- eral fundamental dense linear algebra (DLA) algorithms in OpenCL. In particular, these are linear system solvers and eigenvalue problem solvers. Further, we give an overview of the clMAGMA library, an open source, high performance OpenCL library that incorporates the developments pre- sented, and in general provides to heterogeneous architec- tures the DLA functionality of the popular LAPACK library. The LAPACK-compliance and use of OpenCL simplify the use of clMAGMA in applications, while providing them with portably performant DLA. High performance is ob- tained through use of the high-performance OpenCL BLAS, hardware and OpenCL-speci c tuning, and a hybridization methodology where we split the algorithm into computa- tional tasks of various granularities. Execution of those tasks is properly scheduled over the heterogeneous hardware components by minimizing data movements and mapping algorithmic requirements to the architectural strengths of the various heterogeneous hardware components.
%B University of Tennessee Technical Report (Lawn 275)
%I University of Tennessee
%8 03-2013
%G eng
%0 Journal Article
%J Concurrency and Computation: Practice and Experience
%D 2013
%T Extending the scope of the Checkpoint-on-Failure protocol for forward recovery in standard MPI
%A Wesley Bland
%A Peng Du
%A Aurelien Bouteiller
%A Thomas Herault
%A George Bosilca
%A Jack Dongarra
%X Most predictions of exascale machines picture billion ways parallelism, encompassing not only millions of cores but also tens of thousands of nodes. Even considering extremely optimistic advances in hardware reliability, probabilistic amplification entails that failures will be unavoidable. Consequently, software fault tolerance is paramount to maintain future scientific productivity. Two major problems hinder ubiquitous adoption of fault tolerance techniques: (i) traditional checkpoint-based approaches incur a steep overhead on failure free operations and (ii) the dominant programming paradigm for parallel applications (the message passing interface (MPI) Standard) offers extremely limited support of software-level fault tolerance approaches. In this paper, we present an approach that relies exclusively on the features of a high quality implementation, as defined by the current MPI Standard, to enable advanced forward recovery techniques, without incurring the overhead of customary periodic checkpointing. With our approach, when failure strikes, applications regain control to make a checkpoint before quitting execution. This checkpoint is in reaction to the failure occurrence rather than periodic. This checkpoint is reloaded in a new MPI application, which restores a sane environment for the forward, application-based recovery technique to repair the failure-damaged dataset. The validity and performance of this approach are evaluated on large-scale systems, using the QR factorization as an example. Published 2013. This article is a US Government work and is in the public domain in the USA.
%B Concurrency and Computation: Practice and Experience
%8 07-2013
%G eng
%U http://doi.wiley.com/10.1002/cpe.3100
%! Concurrency Computat.: Pract. Exper.
%R 10.1002/cpe.3100
%0 Journal Article
%J Journal of Computational Science
%D 2013
%T Soft Error Resilient QR Factorization for Hybrid System with GPGPU
%A Peng Du
%A Piotr Luszczek
%A Stanimire Tomov
%A Jack Dongarra
%K gpgpu
%K gpu
%K magma
%X The general purpose graphics processing units (GPGPUs) are increasingly deployed for scientific computing due to their performance advantages over CPUs. What followed is the fact that fault tolerance has become a more serious concern compared to the period when GPGPUs were used exclusively for graphics applications. Using GPUs and CPUs together in a hybrid computing system increases flexibility and performance but also increases the possibility of the computations being affected by soft errors, for example, in the form of bit flips. In this work, we propose a soft error resilient algorithm for QR factorization on such hybrid systems. Our contributions include: (1) a checkpointing and recovery mechanism for the left-factor Q whose performance is scalable on hybrid systems; (2) optimized Givens rotation utilities on GPGPUs to efficiently reduce an upper Hessenberg matrix to an upper triangular form for the protection of the right factor R; and (3) a recovery algorithm based on QR update on GPGPUs. Experimental results show that our fault tolerant QR factorization can successfully detect and recover from soft errors in the entire matrix with little overhead on hybrid systems with GPGPUs.
%B Journal of Computational Science
%V 4
%P 457–464
%8 11-2013
%G eng
%N 6
%R http://dx.doi.org/10.1016/j.jocs.2013.01.004
%0 Conference Proceedings
%B Proceedings of the 17th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPOPP 2012
%D 2012
%T Algorithm-Based Fault Tolerance for Dense Matrix Factorization
%A Peng Du
%A Aurelien Bouteiller
%A George Bosilca
%A Thomas Herault
%A Jack Dongarra
%E J. Ramanujam
%E P. Sadayappan
%K ft-la
%K ftmpi
%X Dense matrix factorizations, such as LU, Cholesky and QR, are widely used for scientific applications that require solving systems of linear equations, eigenvalues and linear least squares problems. Such computations are normally carried out on supercomputers, whose ever-growing scale induces a fast decline of the Mean Time To Failure (MTTF). This paper proposes a new hybrid approach, based on Algorithm-Based Fault Tolerance (ABFT), to help matrix factorizations algorithms survive fail-stop failures. We consider extreme conditions, such as the absence of any reliable component and the possibility of loosing both data and checksum from a single failure. We will present a generic solution for protecting the right factor, where the updates are applied, of all above mentioned factorizations. For the left factor, where the panel has been applied, we propose a scalable checkpointing algorithm. This algorithm features high degree of checkpointing parallelism and cooperatively utilizes the checksum storage leftover from the right factor protection. The fault-tolerant algorithms derived from this hybrid solution is applicable to a wide range of dense matrix factorizations, with minor modifications. Theoretical analysis shows that the fault tolerance overhead sharply decreases with the scaling in the number of computing units and the problem size. Experimental results of LU and QR factorization on the Kraken (Cray XT5) supercomputer validate the theoretical evaluation and confirm negligible overhead, with- and without-errors.
%B Proceedings of the 17th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPOPP 2012
%I ACM
%C New Orleans, LA, USA
%P 225-234
%8 02-2012
%G eng
%R 10.1145/2145816.2145845
%0 Conference Proceedings
%B 18th International European Conference on Parallel and Distributed Computing (Euro-Par 2012) (Best Paper Award)
%D 2012
%T A Checkpoint-on-Failure Protocol for Algorithm-Based Recovery in Standard MPI
%A Wesley Bland
%A Peng Du
%A Aurelien Bouteiller
%A Thomas Herault
%A George Bosilca
%A Jack Dongarra
%E Christos Kaklamanis
%E Theodore Papatheodorou
%E Paul Spirakis
%B 18th International European Conference on Parallel and Distributed Computing (Euro-Par 2012) (Best Paper Award)
%I Springer-Verlag
%C Rhodes, Greece
%8 08-2012
%G eng
%0 Generic
%D 2012
%T Extending the Scope of the Checkpoint-on-Failure Protocol for Forward Recovery in Standard MPI
%A Wesley Bland
%A Peng Du
%A Aurelien Bouteiller
%A Thomas Herault
%A George Bosilca
%A Jack Dongarra
%K ftmpi
%B University of Tennessee Computer Science Technical Report
%8 00-2012
%G eng
%0 Journal Article
%J Parallel Computing
%D 2012
%T From CUDA to OpenCL: Towards a Performance-portable Solution for Multi-platform GPU Programming
%A Peng Du
%A Rick Weber
%A Piotr Luszczek
%A Stanimire Tomov
%A Gregory D. Peterson
%A Jack Dongarra
%B Parallel Computing
%V 38
%P 391-407
%8 08-2012
%G eng
%0 Journal Article
%J ICCS 2012
%D 2012
%T High Performance Dense Linear System Solver with Resilience to Multiple Soft Errors
%A Peng Du
%A Piotr Luszczek
%A Jack Dongarra
%B ICCS 2012
%C Omaha, NE
%8 06-2012
%G eng
%0 Journal Article
%J Applied Parallel and Scientific Computing
%D 2012
%T An Implementation of the Tile QR Factorization for a GPU and Multiple CPUs
%A Jakub Kurzak
%A Rajib Nath
%A Peng Du
%A Jack Dongarra
%E Kristján Jónasson
%B Applied Parallel and Scientific Computing
%V 7133
%P 248-257
%8 00-2012
%G eng
%0 Generic
%D 2012
%T Providing GPU Capability to LU and QR within the ScaLAPACK Framework
%A Peng Du
%A Stanimire Tomov
%A Jack Dongarra
%B University of Tennessee Computer Science Technical Report (also LAWN 272)
%8 09-2012
%G eng
%0 Generic
%D 2011
%T Algorithm-based Fault Tolerance for Dense Matrix Factorizations
%A Peng Du
%A Aurelien Bouteiller
%A George Bosilca
%A Thomas Herault
%A Jack Dongarra
%K ft-la
%B University of Tennessee Computer Science Technical Report
%C Knoxville, TN
%8 08-2011
%G eng
%0 Journal Article
%J IEEE Cluster 2011
%D 2011
%T High Performance Dense Linear System Solver with Soft Error Resilience
%A Peng Du
%A Piotr Luszczek
%A Jack Dongarra
%K ft-la
%B IEEE Cluster 2011
%C Austin, TX
%8 09-2011
%G eng
%0 Generic
%D 2011
%T Soft Error Resilient QR Factorization for Hybrid System
%A Peng Du
%A Piotr Luszczek
%A Stanimire Tomov
%A Jack Dongarra
%K ft-la
%B University of Tennessee Computer Science Technical Report
%C Knoxville, TN
%8 07-2011
%G eng
%0 Journal Article
%J UT-CS-11-675 (also LAPACK Working Note #252)
%D 2011
%T Soft Error Resilient QR Factorization for Hybrid System
%A Peng Du
%A Piotr Luszczek
%A Stanimire Tomov
%A Jack Dongarra
%K magma
%B UT-CS-11-675 (also LAPACK Working Note #252)
%8 07-2011
%G eng
%0 Journal Article
%J Journal of Computational Science
%D 2011
%T Soft Error Resilient QR Factorization for Hybrid System with GPGPU
%A Peng Du
%A Piotr Luszczek
%A Stanimire Tomov
%A Jack Dongarra
%K ft-la
%B Journal of Computational Science
%I Workshop on Latest Advances in Scalable Algorithms for Large-Scale Systems at SC11
%C Seattle, WA
%8 11-2011
%G eng
%0 Journal Article
%J Parallel Computing (submitted)
%D 2010
%T From CUDA to OpenCL: Towards a Performance-portable Solution for Multi-platform GPU Programming
%A Peng Du
%A Rick Weber
%A Piotr Luszczek
%A Stanimire Tomov
%A Gregory D. Peterson
%A Jack Dongarra
%K magma
%B Parallel Computing (submitted)
%8 00-2010
%G eng
%0 Journal Article
%J Parallel Computing (submitted)
%D 2010
%T From CUDA to OpenCL: Towards a Performance-portable Solution for Multiplatform GPU Programming
%A Peng Du
%A Rick Weber
%A Piotr Luszczek
%A Stanimire Tomov
%A Gregory D. Peterson
%A Jack Dongarra
%B Parallel Computing (submitted)
%8 08-2010
%G eng
%0 Conference Proceedings
%B First International Workshop on Parallel Software Tools and Tool Infrastructures (PSTI 2010)
%D 2010
%T Mixed-Tool Performance Analysis on Hybrid Multicore Architectures
%A Peng Du
%A Piotr Luszczek
%A Stanimire Tomov
%A Jack Dongarra
%K magma
%B First International Workshop on Parallel Software Tools and Tool Infrastructures (PSTI 2010)
%C San Diego, CA
%8 09-2010
%G eng
%0 Conference Proceedings
%B Symposium on Application Accelerators in High-Performance Computing (SAAHPC '10)
%D 2010
%T OpenCL Evaluation for Numerical Linear Algebra Library Development
%A Peng Du
%A Piotr Luszczek
%A Jack Dongarra
%K magma
%B Symposium on Application Accelerators in High-Performance Computing (SAAHPC '10)
%C Knoxville, TN
%8 07-2010
%G eng
%0 Journal Article
%J Proc. of VECPAR'10 (to appear)
%D 2010
%T A Scalable High Performant Cholesky Factorization for Multicore with GPU Accelerators
%A Hatem Ltaeif
%A Stanimire Tomov
%A Rajib Nath
%A Peng Du
%A Jack Dongarra
%K magma
%K plasma
%B Proc. of VECPAR'10 (to appear)
%C Berkeley, CA
%8 06-2010
%G eng
%0 Journal Article
%J FOSS4G 2010
%D 2010
%T Tuning Principal Component Analysis for GRASS GIS on Multi-core and GPU Architectures
%A Peng Du
%A Matthew Parsons
%A Erika Fuentes
%A Shih-Lung Shaw
%A Jack Dongarra
%K magma
%B FOSS4G 2010
%C Barcelona, Spain
%8 09-2010
%G eng