%0 Journal Article
%J Parallel Computing (to appear)
%D 2019
%T Comparing the Performance of Rigid, Moldable, and Grid-Shaped Applications on Failure-Prone HPC Platforms
%A Valentin Le Fèvre
%A Thomas Herault
%A Yves Robert
%A Aurelien Bouteiller
%A Atsushi Hori
%A George Bosilca
%A Jack Dongarra
%B Parallel Computing (to appear)
%G eng
%R https://doi.org/10.1016/j.parco.2019.02.002
%0 Journal Article
%J Algorithmica
%D 2019
%T Computing dense tensor decompositions with optimal dimension trees
%A Oguz Kaya
%A Yves Robert
%B Algorithmica
%8 to appear
%G eng
%0 Conference Paper
%B 2018 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW)
%D 2018
%T Budget-Aware Scheduling Algorithms for Scientific Workflows with Stochastic Task Weights on Heterogeneous IaaS Cloud Platforms
%A Yves Caniou
%A Eddy Caron
%A Aurélie Kong Win Chang
%A Yves Robert
%K budget aware algorithm
%K multi criteria scheduling
%K workflow
%X This paper introduces several budget-aware algorithms to deploy scientific workflows on IaaS cloud platforms, where users can request Virtual Machines (VMs) of different types, each with specific cost and speed parameters. We use a realistic application/platform model with stochastic task weights, and VMs communicating through a datacenter. We extend two well-known algorithms, MinMin and HEFT, and make scheduling decisions based upon machine availability and available budget. During the mapping process, the budget-aware algorithms make conservative assumptions to avoid exceeding the initial budget; we further improve our results with refined versions that aim at re-scheduling some tasks onto faster VMs, thereby spending any budget fraction leftover by the first allocation. These refined variants are much more time-consuming than the former algorithms, so there is a trade-off to find in terms of scalability. We report an extensive set of simulations with workflows from the Pegasus benchmark suite. Most of the time our budget-aware algorithms succeed in achieving efficient makespans while enforcing the given budget, despite (i) the uncertainty in task weights and (ii) the heterogeneity of VMs in both cost and speed values.
%B 2018 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW)
%I IEEE
%C Vancouver, BC, Canada
%8 05-2018
%G eng
%R 10.1109/IPDPSW.2018.00014
%0 Journal Article
%J IEEE Transactions on Computers
%D 2018
%T Checkpointing Workflows for Fail-Stop Errors
%A Li Han
%A Louis-Claude Canon
%A Henri Casanova
%A Yves Robert
%A Frederic Vivien
%K checkpoint
%K fail-stop error
%K resilience
%K workflow
%X We consider the problem of orchestrating the execution of workflow applications structured as Directed Acyclic Graphs (DAGs) on parallel computing platforms that are subject to fail-stop failures. The objective is to minimize expected overall execution time, or makespan. A solution to this problem consists of a schedule of the workflow tasks on the available processors and of a decision of which application data to checkpoint to stable storage, so as to mitigate the impact of processor failures. To address this challenge, we consider a restricted class of graphs, Minimal Series-Parallel Graphs (M-SPGS), which is relevant to many real-world workflow applications. For this class of graphs, we propose a recursive list-scheduling algorithm that exploits the M-SPG structure to assign sub-graphs to individual processors, and uses dynamic programming to decide how to checkpoint these sub-graphs. We assess the performance of our algorithm for production workflow configurations, comparing it to an approach in which all application data is checkpointed and an approach in which no application data is checkpointed. Results demonstrate that our algorithm outperforms both the former approach, because of lower checkpointing overhead, and the latter approach, because of better resilience to failures.
%B IEEE Transactions on Computers
%V 67
%P 1105–1120
%8 08-2018
%G eng
%U http://ieeexplore.ieee.org/document/8279499/
%N 8
%0 Journal Article
%J Parallel Computing
%D 2018
%T Computing the Expected Makespan of Task Graphs in the Presence of Silent Errors
%A Henri Casanova
%A Julien Herrmann
%A Yves Robert
%K Expected makespan
%K fault-tolerance
%K scheduling
%K Scientific workflows
%K silent errors
%K Task graphs
%X Applications structured as Directed Acyclic Graphs (DAGs) of tasks occur in many domains, including popular scientific workflows. DAG scheduling has thus received an enormous amount of attention. Many of the popular DAG scheduling heuristics make scheduling deci- sions based on path lengths. At large scale compute platforms are subject to various types of failures with non-negligible probabilities of occurrence. Failures that have recently re- ceived increased attention are “silent errors,” which cause data corruption. Tolerating silent errors is done by checking the validity of computed results and possibly re-executing a task from scratch. The execution time of a task then becomes a random variable, and so do path lengths in a DAG. Unfortunately, computing the expected makespan of a DAG (and equivalently computing expected path lengths in a DAG) is a computationally dif- ficult problem. Consequently, designing effective scheduling heuristics in this context is challenging. In this work, we propose an algorithm that computes a first order approxi- mation of the expected makespan of a DAG when tasks are subject to silent errors. We find that our proposed approximation outperforms previously proposed approaches both in terms of approximation error and of speed.
%B Parallel Computing
%V 75
%P 41–60
%8 07-2018
%G eng
%R https://doi.org/10.1016/j.parco.2018.03.004
%0 Journal Article
%J Journal of Parallel and Distributed Computing
%D 2018
%T Coping with Silent and Fail-Stop Errors at Scale by Combining Replication and Checkpointing
%A Anne Benoit
%A Aurelien Cavelan
%A Franck Cappello
%A Padma Raghavan
%A Yves Robert
%A Hongyang Sun
%K checkpointing
%K fail-stop errors
%K Fault tolerance
%K High-performance computing
%K Replication
%K silent errors
%X This paper provides a model and an analytical study of replication as a technique to cope with silent errors, as well as a mixture of both silent and fail-stop errors on large-scale platforms. Compared with fail-stop errors that are immediately detected when they occur, silent errors require a detection mechanism. To detect silent errors, many application-specific techniques are available, either based on algorithms (e.g., ABFT), invariant preservation or data analytics, but replication remains the most transparent and least intrusive technique. We explore the right level (duplication, triplication or more) of replication for two frameworks: (i) when the platform is subject to only silent errors, and (ii) when the platform is subject to both silent and fail-stop errors. A higher level of replication is more expensive in terms of resource usage but enables to tolerate more errors and to even correct some errors, hence there is a trade-off to be found. Replication is combined with checkpointing and comes with two flavors: process replication and group replication. Process replication applies to message-passing applications with communicating processes. Each process is replicated, and the platform is composed of process pairs, or triplets. Group replication applies to black-box applications, whose parallel execution is replicated several times. The platform is partitioned into two halves (or three thirds). In both scenarios, results are compared before each checkpoint, which is taken only when both results (duplication) or two out of three results (triplication) coincide. Otherwise, one or more silent errors have been detected, and the application rolls back to the last checkpoint, as well as when fail-stop errors have struck. We provide a detailed analytical study for all of these scenarios, with formulas to decide, for each scenario, the optimal parameters as a function of the error rate, checkpoint cost, and platform size. We also report a set of extensive simulation results that nicely corroborates the analytical model.
%B Journal of Parallel and Distributed Computing
%V 122
%P 209–225
%8 12-2018
%G eng
%R https://doi.org/10.1016/j.jpdc.2018.08.002
%0 Journal Article
%J International Journal of High Performance Computing Applications
%D 2018
%T Co-Scheduling Amdhal Applications on Cache-Partitioned Systems
%A Guillaume Aupy
%A Anne Benoit
%A Sicheng Dai
%A Loïc Pottier
%A Padma Raghavan
%A Yves Robert
%A Manu Shantharam
%K cache partitioning
%K co-scheduling
%K complexity results
%X Cache-partitioned architectures allow subsections of the shared last-level cache (LLC) to be exclusively reserved for some applications. This technique dramatically limits interactions between applications that are concurrently executing on a multicore machine. Consider n applications that execute concurrently, with the objective to minimize the makespan, defined as the maximum completion time of the n applications. Key scheduling questions are as follows: (i) which proportion of cache and (ii) how many processors should be given to each application? In this article, we provide answers to (i) and (ii) for Amdahl applications. Even though the problem is shown to be NP-complete, we give key elements to determine the subset of applications that should share the LLC (while remaining ones only use their smaller private cache). Building upon these results, we design efficient heuristics for Amdahl applications. Extensive simulations demonstrate the usefulness of co-scheduling when our efficient cache partitioning strategies are deployed.
%B International Journal of High Performance Computing Applications
%V 32
%P 123–138
%8 01-2018
%G eng
%N 1
%R https://doi.org/10.1177/1094342017710806
%0 Conference Paper
%B Cluster 2018
%D 2018
%T Co-Scheduling HPC Workloads on Cache-Partitioned CMP Platforms
%A Guillaume Aupy
%A Anne Benoit
%A Brice Goglin
%A Loïc Pottier
%A Yves Robert
%B Cluster 2018
%I IEEE Computer Society Press
%C Belfast, UK
%8 09-2018
%G eng
%0 Conference Paper
%B 11th Workshop on Resiliency in High Performance Computing in Clusters, Clouds, and Grids
%D 2018
%T Do moldable applications perform better on failure-prone HPC platforms?
%A Valentin Le Fèvre
%A George Bosilca
%A Aurelien Bouteiller
%A Thomas Herault
%A Atsushi Hori
%A Yves Robert
%A Jack Dongarra
%X This paper compares the performance of different approaches to tolerate failures using checkpoint/restart when executed on large-scale failure-prone platforms. We study (i) Rigid applications, which use a constant number of processors throughout execution; (ii) Moldable applications, which can use a different number of processors after each restart following a fail-stop error; and (iii) GridShaped applications, which are moldable applications restricted to use rectangular processor grids (such as many dense linear algebra kernels). For each application type, we compute the optimal number of failures to tolerate before relinquishing the current allocation and waiting until a new resource can be allocated, and we determine the optimal yield that can be achieved. We instantiate our performance model with a realistic applicative scenario and make it publicly available for further usage.
%B 11th Workshop on Resiliency in High Performance Computing in Clusters, Clouds, and Grids
%S LNCS
%I Springer Verlag
%C Turin, Italy
%8 08-2018
%G eng
%0 Journal Article
%J The International Journal of High Performance Computing Applications
%D 2018
%T A Failure Detector for HPC Platforms
%A George Bosilca
%A Aurelien Bouteiller
%A Amina Guermouche
%A Thomas Herault
%A Yves Robert
%A Pierre Sens
%A Jack Dongarra
%K failure detection
%K Fault tolerance
%K MPI
%X Building an infrastructure for exascale applications requires, in addition to many other key components, a stable and efficient failure detector. This article describes the design and evaluation of a robust failure detector that can maintain and distribute the correct list of alive resources within proven and scalable bounds. The detection and distribution of the fault information follow different overlay topologies that together guarantee minimal disturbance to the applications. A virtual observation ring minimizes the overhead by allowing each node to be observed by another single node, providing an unobtrusive behavior. The propagation stage uses a nonuniform variant of a reliable broadcast over a circulant graph overlay network and guarantees a logarithmic fault propagation. Extensive simulations, together with experiments on the Titan Oak Ridge National Laboratory supercomputer, show that the algorithm performs extremely well and exhibits all the desired properties of an exascale-ready algorithm.
%B The International Journal of High Performance Computing Applications
%V 32
%P 139–158
%8 01-2018
%G eng
%N 1
%R https://doi.org/10.1177/1094342017711505
%0 Conference Paper
%B The 47th International Conference on Parallel Processing (ICPP 2018)
%D 2018
%T A Generic Approach to Scheduling and Checkpointing Workflows
%A Li Han
%A Valentin Le Fèvre
%A Louis-Claude Canon
%A Yves Robert
%A Frederic Vivien
%X This work deals with scheduling and checkpointing strategies to execute scientific workflows on failure-prone large-scale platforms. To the best of our knowledge, this work is the first to target failstop errors for arbitrary workflows. Most previous work addresses soft errors, which corrupt the task being executed by a processor but do not cause the entire memory of that processor to be lost, contrarily to fail-stop errors. We revisit classical mapping heuristics such as HEFT and MinMin and complement them with several checkpointing strategies. The objective is to derive an efficient trade-off between checkpointing every task (CkptAll), which is an overkill when failures are rare events, and checkpointing no task (CkptNone), which induces dramatic re-execution overhead even when only a few failures strike during execution. Contrarily to previous work, our approach applies to arbitrary workflows, not just special classes of dependence graphs such as M-SPGs (Minimal Series-Parallel Graphs). Extensive experiments report significant gain over both CkptAll and CkptNone, for a wide variety of workflows.
%B The 47th International Conference on Parallel Processing (ICPP 2018)
%I IEEE Computer Society Press
%C Eugene, OR
%8 08-2018
%G eng
%0 Journal Article
%J Journal of Computational Science
%D 2018
%T Multi-Level Checkpointing and Silent Error Detection for Linear Workflows
%A Anne Benoit
%A Aurelien Cavelan
%A Yves Robert
%A Hongyang Sun
%X We focus on High Performance Computing (HPC) workflows whose dependency graph forms a linear chain, and we extend single-level checkpointing in two important directions. Our first contribution targets silent errors, and combines in-memory checkpoints with both partial and guaranteed verifications. Our second contribution deals with multi-level checkpointing for fail-stop errors. We present sophisticated dynamic programming algorithms that return the optimal solution for each problem in polynomial time. We also show how to combine all these techniques and solve the problem with both fail-stop and silent errors. Simulation results demonstrate that these extensions lead to significantly improved performance compared to the standard single-level checkpointing algorithm.
%B Journal of Computational Science
%V 28
%P 398–415
%8 09-2018
%G eng
%0 Conference Paper
%B 2018 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW), Best Paper Award
%D 2018
%T Optimal Cooperative Checkpointing for Shared High-Performance Computing Platforms
%A Thomas Herault
%A Yves Robert
%A Aurelien Bouteiller
%A Dorian Arnold
%A Kurt Ferreira
%A George Bosilca
%A Jack Dongarra
%X In high-performance computing environments, input/output (I/O) from various sources often contend for scarce available bandwidth. Adding to the I/O operations inherent to the failure-free execution of an application, I/O from checkpoint/restart (CR) operations (used to ensure progress in the presence of failures) place an additional burden as it increase I/O contention, leading to degraded performance. In this work, we consider a cooperative scheduling policy that optimizes the overall performance of concurrently executing CR-based applications which share valuable I/O resources. First, we provide a theoretical model and then derive a set of necessary constraints needed to minimize the global waste on the platform. Our results demonstrate that the optimal checkpoint interval, as defined by Young/Daly, despite providing a sensible metric for a single application, is not sufficient to optimally address resource contention at the platform scale. We therefore show that combining optimal checkpointing periods with I/O scheduling strategies can provide a significant improvement on the overall application performance, thereby maximizing platform throughput. Overall, these results provide critical analysis and direct guidance on checkpointing large-scale workloads in the presence of competing I/O while minimizing the impact on application performance.
%B 2018 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW), Best Paper Award
%I IEEE
%C Vancouver, BC, Canada
%8 05-2018
%G eng
%R 10.1109/IPDPSW.2018.00127
%0 Conference Paper
%B The 47th International Conference on Parallel Processing (ICPP 2018)
%D 2018
%T A Performance Model to Execute Workflows on High-Bandwidth Memory Architectures
%A Anne Benoit
%A Swann Perarnau
%A Loïc Pottier
%A Yves Robert
%X This work presents a realistic performance model to execute scientific workflows on high-bandwidth memory architectures such as the Intel Knights Landing. We provide a detailed analysis of the execution time on such platforms, taking into account transfers from both fast and slow memory and their overlap with computations. We discuss several scheduling and mapping strategies: not only tasks must be assigned to computing resource, but also one has to decide which fraction of input and output data will reside in fast memory, and which will have to stay in slow memory. Extensive simulations allow us to assess the impact of the mapping strategies on performance. We also conduct actual experiments for a simple 1D Gauss-Seidel kernel, which assess the accuracy of the model and further demonstrate the importance of a tuned memory management. Altogether, our model and results lay the foundations for further studies and experiments on dual-memory systems.
%B The 47th International Conference on Parallel Processing (ICPP 2018)
%I IEEE Computer Society Press
%C Eugene, OR
%8 08-2018
%G eng
%0 Book Section
%B Topics in Parallel and Distributed Computing
%D 2018
%T Scheduling for Fault-Tolerance: An Introduction
%A Guillaume Aupy
%A Yves Robert
%B Topics in Parallel and Distributed Computing
%I Springer International Publishing
%P 143–170
%@ 978-3-319-93108-1
%G eng
%R 10.1007/978-3-319-93109-8
%0 Conference Paper
%B The 3rd International Workshop on Fault Tolerant Systems (FTS)
%D 2017
%T Assuming failure independence: are we right to be wrong?
%A Guillaume Aupy
%A Yves Robert
%A Frederic Vivien
%X This paper revisits the failure temporal independence hypothesis which is omnipresent in the analysis of resilience methods for HPC. We explain why a previous approach is incorrect, and we propose a new method to detect failure cascades, i.e., series of non-independent consecutive failures. We use this new method to assess whether public archive failure logs contain failure cascades. Then we design and compare several cascadeaware checkpointing algorithms to quantify the maximum gain that could be obtained, and we report extensive simulation results with archive and synthetic failure logs. Altogether, there are a few logs that contain cascades, but we show that the gain that can be achieved from this knowledge is not significant. The conclusion is that we can wrongly, but safely, assume failure independence!
%B The 3rd International Workshop on Fault Tolerant Systems (FTS)
%I IEEE
%C Honolulu, Hawaii
%8 09-2017
%G eng
%0 Conference Paper
%B IEEE International Parallel and Distributed Processing Symposium (IPDPS)
%D 2017
%T Bidiagonalization and R-Bidiagonalization: Parallel Tiled Algorithms, Critical Paths and Distributed-Memory Implementation
%A Mathieu Faverge
%A Julien Langou
%A Yves Robert
%A Jack Dongarra
%K Algorithm design and analysis
%K Approximation algorithms
%K Kernel
%K Multicore processing
%K Shape
%K Software algorithms
%K Transforms
%X We study tiled algorithms for going from a "full" matrix to a condensed "band bidiagonal" form using orthog-onal transformations: (i) the tiled bidiagonalization algorithm BIDIAG, which is a tiled version of the standard scalar bidiago-nalization algorithm; and (ii) the R-bidiagonalization algorithm R-BIDIAG, which is a tiled version of the algorithm which consists in first performing the QR factorization of the initial matrix, then performing the band-bidiagonalization of the R- factor. For both BIDIAG and R-BIDIAG, we use four main types of reduction trees, namely FLATTS, FLATTT, GREEDY, and a newly introduced auto-adaptive tree, AUTO. We provide a study of critical path lengths for these tiled algorithms, which shows that (i) R-BIDIAG has a shorter critical path length than BIDIAG for tall and skinny matrices, and (ii) GREEDY based schemes are much better than earlier proposed algorithms with unbounded resources. We provide experiments on a single multicore node, and on a few multicore nodes of a parallel distributed shared- memory system, to show the superiority of the new algorithms on a variety of matrix sizes, matrix shapes and core counts.
%B IEEE International Parallel and Distributed Processing Symposium (IPDPS)
%I IEEE
%C Orlando, FL
%8 05-2017
%G eng
%R 10.1109/IPDPS.2017.46
%0 Conference Paper
%B IEEE Cluster
%D 2017
%T Checkpointing Workflows for Fail-Stop Errors
%A Li Han
%A Louis-Claude Canon
%A Henri Casanova
%A Yves Robert
%A Frederic Vivien
%X We consider the problem of orchestrating the execution of workflow applications structured as Directed Acyclic Graphs (DAGs) on parallel computing platforms that are subject to fail-stop failures. The objective is to minimize expected overall execution time, or makespan. A solution to this problem consists of a schedule of the workflow tasks on the available processors and of a decision of which application data to checkpoint to stable storage, so as to mitigate the impact of processor failures. For general DAGs this problem is hopelessly intractable. In fact, given a solution, computing its expected makespan is still a difficult problem. To address this challenge, we consider a restricted class of graphs, Minimal Series-Parallel Graphs (M-SPGS). It turns out that many real-world workflow applications are naturally structured as M-SPGS. For this class of graphs, we propose a recursive list-scheduling algorithm that exploits the M-SPG structure to assign sub-graphs to individual processors, and uses dynamic programming to decide which tasks in these sub-graphs should be checkpointed. Furthermore, it is possible to efficiently compute the expected makespan for the solution produced by this algorithm, using a first-order approximation of task weights and existing evaluation algorithms for 2-state probabilistic DAGs. We assess the performance of our algorithm for production workflow configurations, comparing it to (i) an approach in which all application data is checkpointed, which corresponds to the standard way in which most production workflows are executed today; and (ii) an approach in which no application data is checkpointed. Our results demonstrate that our algorithm strikes a good compromise between these two approaches, leading to lower checkpointing overhead than the former and to better resilience to failure than the latter.
%B IEEE Cluster
%I IEEE
%C Honolulu, Hawaii
%8 09-2017
%G eng
%0 Conference Paper
%B 19th Workshop on Advances in Parallel and Distributed Computational Models
%D 2017
%T Co-Scheduling Algorithms for Cache-Partitioned Systems
%A Guillaume Aupy
%A Anne Benoit
%A Loïc Pottier
%A Padma Raghavan
%A Yves Robert
%A Manu Shantharam
%K Computational modeling
%K Degradation
%K Interference
%K Mathematical model
%K Program processors
%K Supercomputers
%K Throughput
%X Cache-partitioned architectures allow subsections of the shared last-level cache (LLC) to be exclusively reserved for some applications. This technique dramatically limits interactions between applications that are concurrently executing on a multicore machine. Consider n applications that execute concurrently, with the objective to minimize the makespan, defined as the maximum completion time of the n applications. Key scheduling questions are: (i) which proportion of cache and (ii) how many processors should be given to each application? Here, we assign rational numbers of processors to each application, since they can be shared across applications through multi-threading. In this paper, we provide answers to (i) and (ii) for perfectly parallel applications. Even though the problem is shown to be NP-complete, we give key elements to determine the subset of applications that should share the LLC (while remaining ones only use their smaller private cache). Building upon these results, we design efficient heuristics for general applications. Extensive simulations demonstrate the usefulness of co-scheduling when our efficient cache partitioning strategies are deployed.
%B 19th Workshop on Advances in Parallel and Distributed Computational Models
%I IEEE Computer Society Press
%C Orlando, FL
%8 05-2017
%G eng
%R 10.1109/IPDPSW.2017.60
%0 Journal Article
%J Supercomputing Frontiers and Innovations
%D 2017
%T Design and Implementation of the PULSAR Programming System for Large Scale Computing
%A Jakub Kurzak
%A Piotr Luszczek
%A Ichitaro Yamazaki
%A Yves Robert
%A Jack Dongarra
%X The objective of the PULSAR project was to design a programming model suitable for large scale machines with complex memory hierarchies, and to deliver a prototype implementation of a runtime system supporting that model. PULSAR tackled the challenge by proposing a programming model based on systolic processing and virtualization. The PULSAR programming model is quite simple, with point-to-point channels as the main communication abstraction. The runtime implementation is very lightweight and fully distributed, and provides multithreading, message-passing and multi-GPU offload capabilities. Performance evaluation shows good scalability up to one thousand nodes with one thousand GPU accelerators.
%B Supercomputing Frontiers and Innovations
%V 4
%G eng
%U http://superfri.org/superfri/article/view/121/210
%N 1
%R 10.14529/jsfi170101
%0 Conference Paper
%B 2017 Workshop on Fault-Tolerance for HPC at Extreme Scale
%D 2017
%T Identifying the Right Replication Level to Detect and Correct Silent Errors at Scale
%A Anne Benoit
%A Franck Cappello
%A Aurelien Cavelan
%A Yves Robert
%A Hongyang Sun
%X This paper provides a model and an analytical study of replication as a technique to detect and correct silent errors. Although other detection techniques exist for HPC applications, based on algorithms (ABFT), invariant preservation or data analytics, replication remains the most transparent and least intrusive technique. We explore the right level (duplication, triplication or more) of replication needed to efficiently detect and correct silent errors. Replication is combined with checkpointing and comes with two flavors: process replication and group replication. Process replication applies to message-passing applications with communicating processes. Each process is replicated, and the platform is composed of process pairs, or triplets. Group replication applies to black-box applications, whose parallel execution is replicated several times. The platform is partitioned into two halves (or three thirds). In both scenarios, results are compared before each checkpoint, which is taken only when both results (duplication) or two out of three results (triplication) coincide. If not, one or more silent errors have been detected, and the application rolls back to the last checkpoint. We provide a detailed analytical study of both scenarios, with formulas to decide, for each scenario, the optimal parameters as a function of the error rate, checkpoint cost, and platform size. We also report a set of extensive simulation results that corroborates the analytical model.
%B 2017 Workshop on Fault-Tolerance for HPC at Extreme Scale
%I ACM
%C Washington, DC
%8 06-2017
%G eng
%R 10.1145/3086157.3086162
%0 Conference Paper
%B 2017 Workshop on Fault-Tolerance for HPC at Extreme Scale
%D 2017
%T Optimal Checkpointing Period with replicated execution on heterogeneous platforms
%A Anne Benoit
%A Aurelien Cavelan
%A Valentin Le Fèvre
%A Yves Robert
%X In this paper, we design and analyze strategies to replicate the execution of an application on two different platforms subject to failures, using checkpointing on a shared stable storage. We derive the optimal pattern size~W for a periodic checkpointing strategy where both platforms concurrently try and execute W units of work before checkpointing. The first platform that completes its pattern takes a checkpoint, and the other platform interrupts its execution to synchronize from that checkpoint. We compare this strategy to a simpler on-failure checkpointing strategy, where a checkpoint is taken by one platform only whenever the other platform encounters a failure. We use first or second-order approximations to compute overheads and optimal pattern sizes, and show through extensive simulations that these models are very accurate. The simulations show the usefulness of a secondary platform to reduce execution time, even when the platforms have relatively different speeds: in average, over a wide range of scenarios, the overhead is reduced by 30%. The simulations also demonstrate that the periodic checkpointing strategy is globally more efficient, unless platform speeds are quite close.
%B 2017 Workshop on Fault-Tolerance for HPC at Extreme Scale
%I IEEE Computer Society Press
%C Washington, DC
%8 06-2017
%G eng
%R 10.1145/3086157.3086165
%0 Conference Paper
%B International Conference on Parallel Processing (ICPP)
%D 2017
%T Resilience for Stencil Computations with Latent Errors
%A Aiman Fang
%A Aurelien Cavelan
%A Yves Robert
%A Andrew Chien
%X Projections and measurements of error rates in near-exascale and exascale systems suggest a dramatic growth, due to extreme scale (109,109 cores), concurrency, software complexity, and deep submicron transistor scaling. Such a growth makes resilience a critical concern, and may increase the incidence of errors that "escape," silently corrupting application state. Such errors can often be revealed by application software tests but with long latencies, and thus are known as latent errors. We explore how to efficiently recover from latent errors, with an approach called application-based focused recovery (ABFR). Specifically we present a case study of stencil computations, a widely useful computational structure, showing how ABFR focuses recovery effort where needed, using intelligent testing and pruning to reduce recovery effort, and enables recovery effort to be overlapped with application computation. We analyze and characterize the ABFR approach on stencils, creating a performance model parameterized by error rate and detection interval (latency). We compare projections from the model to experimental results with the Chombo stencil application, validating the model and showing that ABFR on stencil can achieve a significant reductions in error recovery cost (up to 400x) and recovery latency (up to 4x). Such reductions enable efficient execution at scale with high latent error rates.
%B International Conference on Parallel Processing (ICPP)
%I IEEE Computer Society Press
%C Bristol, UK
%8 08-2017
%G eng
%0 Journal Article
%J International Journal of High Performance Computing Applications (IJHPCA)
%D 2017
%T Resilient Co-Scheduling of Malleable Applications
%A Anne Benoit
%A Loïc Pottier
%A Yves Robert
%K co-scheduling
%K complexity results
%K heuristics
%K Redistribution
%K resilience
%K simulations
%X Recently, the benefits of co-scheduling several applications have been demonstrated in a fault-free context, both in terms of performance and energy savings. However, large-scale computer systems are confronted by frequent failures, and resilience techniques must be employed for large applications to execute efficiently. Indeed, failures may create severe imbalance between applications and significantly degrade performance. In this article, we aim at minimizing the expected completion time of a set of co-scheduled applications. We propose to redistribute the resources assigned to each application upon the occurrence of failures, and upon the completion of some applications, in order to achieve this goal. First, we introduce a formal model and establish complexity results. The problem is NP-complete for malleable applications, even in a fault-free context. Therefore, we design polynomial-time heuristics that perform redistributions and account for processor failures. A fault simulator is used to perform extensive simulations that demonstrate the usefulness of redistribution and the performance of the proposed heuristics.
%B International Journal of High Performance Computing Applications (IJHPCA)
%8 05-2017
%G eng
%R 10.1177/1094342017704979
%0 Journal Article
%J IEEE Transactions on Computers
%D 2017
%T Towards Optimal Multi-Level Checkpointing
%A Anne Benoit
%A Aurelien Cavelan
%A Valentin Le Fèvre
%A Yves Robert
%A Hongyang Sun
%K checkpointing
%K Dynamic programming
%K Error analysis
%K Heuristic algorithms
%K Optimized production technology
%K protocols
%K Shape
%B IEEE Transactions on Computers
%V 66
%P 1212–1226
%8 07-2017
%G eng
%N 7
%R 10.1109/TC.2016.2643660
%0 Journal Article
%J ACM Transactions on Parallel Computing
%D 2016
%T Assessing General-purpose Algorithms to Cope with Fail-stop and Silent Errors
%A Anne Benoit
%A Aurelien Cavelan
%A Yves Robert
%A Hongyang Sun
%K checkpoint
%K fail-stop error
%K failure
%K HPC
%K resilience
%K silent data corruption
%K silent error
%K verification
%X In this paper, we combine the traditional checkpointing and rollback recovery strategies with verification mechanisms to cope with both fail-stop and silent errors. The objective is to minimize makespan and/or energy consumption. For divisible load applications, we use first-order approximations to find the optimal checkpointing period to minimize execution time, with an additional verification mechanism to detect silent errors before each checkpoint, hence extending the classical formula by Young and Daly for fail-stop errors only. We further extend the approach to include intermediate verifications, and to consider a bi-criteria problem involving both time and energy (linear combination of execution time and energy consumption). Then, we focus on application workflows whose dependence graph is a linear chain of tasks. Here, we determine the optimal checkpointing and verification locations, with or without intermediate verifications, for the bicriteria problem. Rather than using a single speed during the whole execution, we further introduce a new execution scenario, which allows for changing the execution speed via dynamic voltage and frequency scaling (DVFS). We determine in this scenario the optimal checkpointing and verification locations, as well as the optimal speed pairs. Finally, we conduct an extensive set of simulations to support the theoretical study, and to assess the performance of each algorithm, showing that the best overall performance is achieved under the most flexible scenario using intermediate verifications and different speeds.
%B ACM Transactions on Parallel Computing
%8 08-2016
%G eng
%R 10.1145/2897189
%0 Journal Article
%J Parallel Computing
%D 2016
%T Assessing the Cost of Redistribution followed by a Computational Kernel: Complexity and Performance Results
%A Julien Herrmann
%A George Bosilca
%A Thomas Herault
%A Loris Marchal
%A Yves Robert
%A Jack Dongarra
%K Data partition
%K linear algebra
%K parsec
%K QR factorization
%K Redistribution
%K Stencil
%X The classical redistribution problem aims at optimally scheduling communications when reshuffling from an initial data distribution to a target data distribution. This target data distribution is usually chosen to optimize some objective for the algorithmic kernel under study (good computational balance or low communication volume or cost), and therefore to provide high efficiency for that kernel. However, the choice of a distribution minimizing the target objective is not unique. This leads to generalizing the redistribution problem as follows: find a re-mapping of data items onto processors such that the data redistribution cost is minimal, and the operation remains as efficient. This paper studies the complexity of this generalized problem. We compute optimal solutions and evaluate, through simulations, their gain over classical redistribution. We also show the NP-hardness of the problem to find the optimal data partition and processor permutation (defined by new subsets) that minimize the cost of redistribution followed by a simple computational kernel. Finally, experimental validation of the new redistribution algorithms are conducted on a multicore cluster, for both a 1D-stencil kernel and a more compute-intensive dense linear algebra routine.
%B Parallel Computing
%V 52
%P 22-41
%8 02-2016
%G eng
%R doi:10.1016/j.parco.2015.09.005
%0 Conference Proceedings
%B Proceedings of the The International Conference for High Performance Computing, Networking, Storage and Analysis (SC'16)
%D 2016
%T Failure Detection and Propagation in HPC Systems
%A George Bosilca
%A Aurelien Bouteiller
%A Amina Guermouche
%A Thomas Herault
%A Yves Robert
%A Pierre Sens
%A Jack Dongarra
%K failure detection
%K fault-tolerance
%K MPI
%B Proceedings of the The International Conference for High Performance Computing, Networking, Storage and Analysis (SC'16)
%I IEEE Press
%C Salt Lake City, Utah
%P 27:1-27:11
%8 11-2016
%@ 978-1-4673-8815-3
%G eng
%U http://dl.acm.org/citation.cfm?id=3014904.3014941
%0 Conference Paper
%B 2016 IEEE International Parallel and Distributed Processing Symposium (IPDPS)
%D 2016
%T Optimal Resilience Patterns to Cope with Fail-stop and Silent Errors
%A Anne Benoit
%A Aurelien Cavelan
%A Yves Robert
%A Hongyang Sun
%K fail-stop errors
%K multilevel checkpoint
%K optimal pattern
%K resilience
%K silent errors
%K verification
%X This work focuses on resilience techniques at extreme scale. Many papers deal with fail-stop errors. Many others deal with silent errors (or silent data corruptions). But very few papers deal with fail-stop and silent errors simultaneously. However, HPC applications will obviously have to cope with both error sources. This paper presents a unified framework and optimal algorithmic solutions to this double challenge. Silent errors are handled via verification mechanisms (either partially or fully accurate) and in-memory checkpoints. Fail-stop errors are processed via disk checkpoints. All verification and checkpoint types are combined into computational patterns. We provide a unified model, and a full characterization of the optimal pattern. Our results nicely extend several published solutions and demonstrate how to make use of different techniques to solve the double threat of fail-stop and silent errors. Extensive simulations based on real data confirm the accuracy of the model, and show that patterns that combine all resilience mechanisms are required to provide acceptable overheads.
%B 2016 IEEE International Parallel and Distributed Processing Symposium (IPDPS)
%I IEEE
%C Chicago, IL
%8 05-2016
%G eng
%R 10.1109/IPDPS.2016.39
%0 Journal Article
%J International Journal of Networking and Computing
%D 2016
%T Scheduling Computational Workflows on Failure-prone Platforms
%A Guillaume Aupy
%A Anne Benoit
%A Henri Casanova
%A Yves Robert
%K checkpointing
%K fault-tolerance
%K reliability
%K scheduling
%K workflow
%X We study the scheduling of computational workflows on compute resources that experience exponentially distributed failures. When a failure occurs, rollback and recovery is used to resume the execution from the last checkpointed state. The scheduling problem is to minimize the expected execution time by deciding in which order to execute the tasks in the workflow and deciding for each task whether to checkpoint it or not after it completes. We give a polynomialtime optimal algorithm for fork DAGs (Directed Acyclic Graphs) and show that the problem is NP-complete with join DAGs. We also investigate the complexity of the simple case in which no task is checkpointed. Our main result is a polynomial-time algorithm to compute the expected execution time of a workflow, with a given task execution order and specified to-be-checkpointed tasks. Using this algorithm as a basis, we propose several heuristics for solving the scheduling problem. We evaluate these heuristics for representative workflow configurations.
%B International Journal of Networking and Computing
%V 6
%P 2-26
%G eng
%0 Journal Article
%J International Journal of Networking and Computing
%D 2015
%T Composing Resilience Techniques: ABFT, Periodic, and Incremental Checkpointing
%A George Bosilca
%A Aurelien Bouteiller
%A Thomas Herault
%A Yves Robert
%A Jack Dongarra
%K ABFT
%K checkpoint
%K fault-tolerance
%K High-performance computing
%K model
%K performance evaluation
%K resilience
%X Algorithm Based Fault Tolerant (ABFT) approaches promise unparalleled scalability and performance in failure-prone environments. Thanks to recent advances in the understanding of the involved mechanisms, a growing number of important algorithms (including all widely used factorizations) have been proven ABFT-capable. In the context of larger applications, these algorithms provide a temporal section of the execution, where the data is protected by its own intrinsic properties, and can therefore be algorithmically recomputed without the need of checkpoints. However, while typical scientific applications spend a significant fraction of their execution time in library calls that can be ABFT-protected, they interleave sections that are difficult or even impossible to protect with ABFT. As a consequence, the only practical fault-tolerance approach for these applications is checkpoint/restart. In this paper we propose a model to investigate the efficiency of a composite protocol, that alternates between ABFT and checkpoint/restart for the effective protection of an iterative application composed of ABFT- aware and ABFT-unaware sections. We also consider an incremental checkpointing composite approach in which the algorithmic knowledge is leveraged by a novel optimal dynamic program- ming to compute checkpoint dates. We validate these models using a simulator. The model and simulator show that the composite approach drastically increases the performance delivered by an execution platform, especially at scale, by providing the means to increase the interval between checkpoints while simultaneously decreasing the volume of each checkpoint.
%B International Journal of Networking and Computing
%V 5
%P 2-15
%8 01-2015
%G eng
%0 Journal Article
%J International Journal on High Performance Computing Applications
%D 2015
%T Efficient Checkpoint/Verification Patterns
%A Anne Benoit
%A Saurabh K. Raina
%A Yves Robert
%K checkpointing
%K Fault tolerance
%K High Performance Computing
%K silent data corruption
%K silent error
%K verification
%X Errors have become a critical problem for high performance computing. Checkpointing protocols are often used for error recovery after fail-stop failures. However, silent errors cannot be ignored, and their peculiarity is that such errors are identified only when the corrupted data is activated. To cope with silent errors, we need a verification mechanism to check whether the application state is correct. Checkpoints should be supplemented with verifications to detect silent errors. When a verification is successful, only the last checkpoint needs to be kept in memory because it is known to be correct. In this paper, we analytically determine the best balance of verifications and checkpoints so as to optimize platform throughput. We introduce a balanced algorithm using a pattern with p checkpoints and q verifications, which regularly interleaves both checkpoints and verifications across same-size computational chunks. We show how to compute the waste of an arbitrary pattern, and we prove that the balanced algorithm is optimal when the platform MTBF (Mean Time Between Failures) is large in front of the other parameters (checkpointing, verification and recovery costs). We conduct several simulations to show the gain achieved by this balanced algorithm for well-chosen values of p and q, compared to the base algorithm that always perform a verification just before taking a checkpoint (p = q = 1), and we exhibit gains of up to 19%.
%B International Journal on High Performance Computing Applications
%8 07-2015
%G eng
%R 10.1177/1094342015594531
%0 Generic
%D 2015
%T Fault Tolerance Techniques for High-performance Computing
%A Jack Dongarra
%A Thomas Herault
%A Yves Robert
%X This report provides an introduction to resilience methods. The emphasis is on checkpointing, the de-facto standard technique for resilience in High Performance Computing. We present the main two protocols, namely coordinated checkpointing and hierarchical checkpointing. Then we introduce performance models and use them to assess the performance of theses protocols. We cover the Young/Daly formula for the optimal period and much more! Next we explain how the efficiency of checkpointing can be improved via fault prediction or replication. Then we move to application-specific methods, such as ABFT. We conclude the report by discussing techniques to cope with silent errors (or silent data corruption).
%B University of Tennessee Computer Science Technical Report (also LAWN 289)
%I University of Tennessee
%8 05-2015
%G eng
%U http://www.netlib.org/lapack/lawnspdf/lawn289.pdf
%0 Journal Article
%J Journal of Parallel and Distributed Computing
%D 2015
%T Mixing LU-QR Factorization Algorithms to Design High-Performance Dense Linear Algebra Solvers
%A Mathieu Faverge
%A Julien Herrmann
%A Julien Langou
%A Bradley Lowery
%A Yves Robert
%A Jack Dongarra
%K lu factorization
%K Numerical algorithms
%K QR factorization
%K Stability; Performance
%X This paper introduces hybrid LU–QR algorithms for solving dense linear systems of the form Ax=b. Throughout a matrix factorization, these algorithms dynamically alternate LU with local pivoting and QR elimination steps based upon some robustness criterion. LU elimination steps can be very efficiently parallelized, and are twice as cheap in terms of floating-point operations, as QR steps. However, LU steps are not necessarily stable, while QR steps are always stable. The hybrid algorithms execute a QR step when a robustness criterion detects some risk for instability, and they execute an LU step otherwise. The choice between LU and QR steps must have a small computational overhead and must provide a satisfactory level of stability with as few QR steps as possible. In this paper, we introduce several robustness criteria and we establish upper bounds on the growth factor of the norm of the updated matrix incurred by each of these criteria. In addition, we describe the implementation of the hybrid algorithms through an extension of the PaRSEC software to allow for dynamic choices during execution. Finally, we analyze both stability and performance results compared to state-of-the-art linear solvers on parallel distributed multicore platforms. A comprehensive set of experiments shows that hybrid LU–QR algorithms provide a continuous range of trade-offs between stability and performances.
%B Journal of Parallel and Distributed Computing
%V 85
%P 32-46
%8 11-2015
%G eng
%R doi:10.1016/j.jpdc.2015.06.007
%0 Generic
%D 2015
%T Scheduling for fault-tolerance: an introduction
%A Guillaume Aupy
%A Yves Robert
%B Innovative Computing Laboratory Technical Report
%I University of Tennessee
%8 01-2015
%G eng
%0 Conference Paper
%B 16th Workshop on Advances in Parallel and Distributed Computational Models, IPDPS 2014
%D 2014
%T Assessing the Impact of ABFT and Checkpoint Composite Strategies
%A George Bosilca
%A Aurelien Bouteiller
%A Thomas Herault
%A Yves Robert
%A Jack Dongarra
%K ABFT
%K checkpoint
%K fault-tolerance
%K High-performance computing
%K resilience
%X Algorithm-specific fault tolerant approaches promise unparalleled scalability and performance in failure-prone environments. With the advances in the theoretical and practical understanding of algorithmic traits enabling such approaches, a growing number of frequently used algorithms (including all widely used factorization kernels) have been proven capable of such properties. These algorithms provide a temporal section of the execution when the data is protected by it’s own intrinsic properties, and can be algorithmically recomputed without the need of checkpoints. However, while typical scientific applications spend a significant fraction of their execution time in library calls that can be ABFT-protected, they interleave sections that are difficult or even impossible to protect with ABFT. As a consequence, the only fault-tolerance approach that is currently used for these applications is checkpoint/restart. In this paper we propose a model and a simulator to investigate the behavior of a composite protocol, that alternates between ABFT and checkpoint/restart protection for effective protection of each phase of an iterative application composed of ABFT-aware and ABFTunaware sections. We highlight this approach drastically increases the performance delivered by the system, especially at scale, by providing means to rarefy the checkpoints while simultaneously decreasing the volume of data needed to be checkpointed.
%B 16th Workshop on Advances in Parallel and Distributed Computational Models, IPDPS 2014
%I IEEE
%C Phoenix, AZ
%8 05-2014
%G eng
%0 Conference Paper
%B IPDPS 2014
%D 2014
%T Designing LU-QR Hybrid Solvers for Performance and Stability
%A Mathieu Faverge
%A Julien Herrmann
%A Julien Langou
%A Bradley Lowery
%A Yves Robert
%A Jack Dongarra
%X This paper introduces hybrid LU-QR algorithms for solving dense linear systems of the form Ax = b. Throughout a matrix factorization, these algorithms dynamically alternate LU with local pivoting and QR elimination steps, based upon some robustness criterion. LU elimination steps can be very efficiently parallelized, and are twice as cheap in terms of operations, as QR steps. However, LU steps are not necessarily stable, while QR steps are always stable. The hybrid algorithms execute a QR step when a robustness criterion detects some risk for instability, and they execute an LU step otherwise. Ideally, the choice between LU and QR steps must have a small computational overhead and must provide a satisfactory level of stability with as few QR steps as possible. In this paper, we introduce several robustness criteria and we establish upper bounds on the growth factor of the norm of the updated matrix incurred by each of these criteria. In addition, we describe the implementation of the hybrid algorithms through an extension of the Parsec software to allow for dynamic choices during execution. Finally, we analyze both stability and performance results compared to state-of-the-art linear solvers on parallel distributed multicore platforms.
%B IPDPS 2014
%I IEEE
%C Phoenix, AZ
%8 05-2014
%@ 978-1-4799-3800-1
%G eng
%R 10.1109/IPDPS.2014.108
%0 Generic
%D 2014
%T Efficient checkpoint/verification patterns for silent error detection
%A Anne Benoit
%A Yves Robert
%A Saurabh K. Raina
%X Resilience has become a critical problem for high performance computing. Checkpointing protocols are often used for error recovery after fail-stop failures. However, silent errors cannot be ignored, and their particularities is that such errors are identified only when the corrupted data is activated. To cope with silent errors, we need a verification mechanism to check whether the application state is correct. Checkpoints should be supplemented with verifications to detect silent errors. When a verification is successful, only the last checkpoint needs to be kept in memory because it is known to be correct. In this paper, we analytically determine the best balance of verifications and checkpoints so as to optimize platform throughput. We introduce a balanced algorithm using a pattern with p checkpoints and q verifications, which regularly interleaves both checkpoints and verifications across same-size computational chunks. We show how to compute the waste of an arbitrary pattern, and we prove that the balanced algorithm is optimal when the platform MTBF (Mean Time Between Failures) is large in front of the other parameters (checkpointing, verification and recovery costs). We conduct several simulations to show the gain achieved by this balanced algorithm for well-chosen values of p and q, compared to the base algorithm that always perform a verification just before taking a checkpoint (p = q = 1), and we exhibit gains of up to 19%.
%B Innovative Computing Laboratory Technical Report
%I University of Tennessee
%8 05-2014
%G eng
%9 LAWN 287
%0 Journal Article
%J International Journal of Networking and Computing
%D 2014
%T Performance and Reliability Trade-offs for the Double Checkpointing Algorithm
%A Jack Dongarra
%A Thomas Herault
%A Yves Robert
%K communication contention
%K in-memory checkpoint
%K performance
%K resilience
%K risk
%X Fast checkpointing algorithms require distributed access to stable storage. This paper revisits the approach based upon double checkpointing, and compares the blocking algorithm of Zheng, Shi and Kalé [23], with the non-blocking algorithm of Ni, Meneses and Kalé [15] in terms of both performance and risk. We also extend the model proposedcan provide a better efficiency in [23, 15] to assess the impact of the overhead associated to non-blocking communications. In addition, we deal with arbitrary failure distributions (as opposed to uniform distributions in [23]). We then provide a new peer-to-peer checkpointing algorithm, called the triple checkpointing algorithm, that can work without additional memory, and achieves both higher efficiency and better risk handling than the double checkpointing algorithm. We provide performance and risk models for all the evaluated protocols, and compare them through comprehensive simulations.
%B International Journal of Networking and Computing
%V 4
%P 32-41
%8 2014
%G eng
%& 32
%0 Generic
%D 2013
%T Assessing the impact of ABFT and Checkpoint composite strategies
%A George Bosilca
%A Aurelien Bouteiller
%A Thomas Herault
%A Yves Robert
%A Jack Dongarra
%K ABFT
%K checkpoint
%K fault-tolerance
%K High-performance computing
%K resilience
%X Algorithm-specific fault tolerant approaches promise unparalleled scalability and performance in failure-prone environments. With the advances in the theoretical and practical understanding of algorithmic traits enabling such approaches, a growing number of frequently used algorithms (including all widely used factorization kernels) have been proven capable of such properties. These algorithms provide a temporal section of the execution when the data is protected by it’s own intrinsic properties, and can be algorithmically recomputed without the need of checkpoints. However, while typical scientific applications spend a significant fraction of their execution time in library calls that can be ABFT-protected, they interleave sections that are difficult or even impossible to protect with ABFT. As a consequence, the only fault-tolerance approach that is currently used for these applications is checkpoint/restart. In this paper we propose a model and a simulator to investigate the behavior of a composite protocol, that alternates between ABFT and checkpoint/restart protection for effective protection of each phase of an iterative application composed of ABFT-aware and ABFT-unaware sections. We highlight this approach drastically increases the performance delivered by the system, especially at scale, by providing means to rarefy the checkpoints while simultaneously decreasing the volume of data needed to be checkpointed.
%B University of Tennessee Computer Science Technical Report
%G eng
%0 Generic
%D 2013
%T On the Combination of Silent Error Detection and Checkpointing
%A Guillaume Aupy
%A Anne Benoit
%A Thomas Herault
%A Yves Robert
%A Frederic Vivien
%A Dounia Zaidouni
%K checkpointing
%K error recovery
%K High-performance computing
%K silent data corruption
%K verification
%X In this paper, we revisit traditional checkpointing and rollback recovery strategies, with a focus on silent data corruption errors. Contrarily to fail-stop failures, such latent errors cannot be detected immediately, and a mechanism to detect them must be provided. We consider two models: (i) errors are detected after some delays following a probability distribution (typically, an Exponential distribution); (ii) errors are detected through some verification mechanism. In both cases, we compute the optimal period in order to minimize the waste, i.e., the fraction of time where nodes do not perform useful computations. In practice, only a fixed number of checkpoints can be kept in memory, and the first model may lead to an irrecoverable failure. In this case, we compute the minimum period required for an acceptable risk. For the second model, there is no risk of irrecoverable failure, owing to the verification mechanism, but the corresponding overhead is included in the waste. Finally, both models are instantiated using realistic scenarios and application/architecture parameters.
%B UT-CS-13-710
%I University of Tennessee Computer Science Technical Report
%8 06-2013
%G eng
%U http://www.netlib.org/lapack/lawnspdf/lawn278.pdf
%0 Generic
%D 2013
%T Designing LU-QR hybrid solvers for performance and stability
%A Mathieu Faverge
%A Julien Herrmann
%A Julien Langou
%A Bradley Lowery
%A Yves Robert
%A Jack Dongarra
%B University of Tennessee Computer Science Technical Report (also LAWN 282)
%I University of Tennessee
%8 10-2013
%G eng
%0 Journal Article
%J Parallel Computing
%D 2013
%T Hierarchical QR Factorization Algorithms for Multi-core Cluster Systems
%A Jack Dongarra
%A Mathieu Faverge
%A Thomas Herault
%A Mathias Jacquelin
%A Julien Langou
%A Yves Robert
%K Cluster
%K Distributed memory
%K Hierarchical architecture
%K multi-core
%K numerical linear algebra
%K QR factorization
%X This paper describes a new QR factorization algorithm which is especially designed for massively parallel platforms combining parallel distributed nodes, where a node is a multi-core processor. These platforms represent the present and the foreseeable future of high-performance computing. Our new QR factorization algorithm falls in the category of the tile algorithms which naturally enables good data locality for the sequential kernels executed by the cores (high sequential performance), low number of messages in a parallel distributed setting (small latency term), and fine granularity (high parallelism). Each tile algorithm is uniquely characterized by its sequence of reduction trees. In the context of a cluster of nodes, in order to minimize the number of inter-processor communications (aka, ‘‘communication-avoiding’’), it is natural to consider hierarchical trees composed of an ‘‘inter-node’’ tree which acts on top of ‘‘intra-node’’ trees. At the intra-node level, we propose a hierarchical tree made of three levels: (0) ‘‘TS level’’ for cache-friendliness, (1) ‘‘low-level’’ for decoupled highly parallel inter-node reductions, (2) ‘‘domino level’’ to efficiently resolve interactions between local reductions and global reductions. Our hierarchical algorithm and its implementation are flexible and modular, and can accommodate several kernel types, different distribution layouts, and a variety of reduction trees at all levels, both inter-node and intra-node. Numerical experiments on a cluster of multi-core nodes (i) confirm that each of the four levels of our hierarchical tree contributes to build up performance and (ii) build insights on how these levels influence performance and interact within each other. Our implementation of the new algorithm with the DAGUE scheduling tool significantly outperforms currently available QR factorization software for all matrix shapes, thereby bringing a new advance in numerical linear algebra for petascale and exascale platforms.
%B Parallel Computing
%V 39
%P 212-232
%8 05-2013
%G eng
%N 4-5
%0 Generic
%D 2013
%T Implementing a systolic algorithm for QR factorization on multicore clusters with PaRSEC
%A Guillaume Aupy
%A Mathieu Faverge
%A Yves Robert
%A Jakub Kurzak
%A Piotr Luszczek
%A Jack Dongarra
%X This article introduces a new systolic algorithm for QR factorization, and its implementation on a supercomputing cluster of multicore nodes. The algorithm targets a virtual 3D-array and requires only local communications. The implementation of the algorithm uses threads at the node level, and MPI for inter-node communications. The complexity of the implementation is addressed with the PaRSEC software, which takes as input a parametrized dependence graph, which is derived from the algorithm, and only requires the user to decide, at the high-level, the allocation of tasks to nodes. We show that the new algorithm exhibits competitive performance with state-of-the-art QR routines on a supercomputer called Kraken, which shows that high-level programming environments, such as PaRSEC, provide a viable alternative to enhance the production of quality software on complex and hierarchical architectures
%B Lawn 277
%8 05-2013
%G eng
%0 Generic
%D 2013
%T Multi-criteria checkpointing strategies: optimizing response-time versus resource utilization
%A Aurelien Bouteiller
%A Franck Cappello
%A Jack Dongarra
%A Amina Guermouche
%A Thomas Herault
%A Yves Robert
%X Failures are increasingly threatening the eciency of HPC systems, and current projections of Exascale platforms indicate that rollback recovery, the most convenient method for providing fault tolerance to generalpurpose applications, reaches its own limits at such scales. One of the reasons explaining this unnerving situation comes from the focus that has been given to per-application completion time, rather than to platform efficiency. In this paper, we discuss the case of uncoordinated rollback recovery where the idle time spent waiting recovering processors is used to progress a different, independent application from the system batch queue. We then propose an extended model of uncoordinated checkpointing that can discriminate between idle time and wasted computation. We instantiate this model in a simulator to demonstrate that, with this strategy, uncoordinated checkpointing per application completion time is unchanged, while it delivers near-perfect platform efficiency.
%B University of Tennessee Computer Science Technical Report
%8 02-2013
%G eng
%0 Conference Paper
%B Euro-Par 2013
%D 2013
%T Multi-criteria Checkpointing Strategies: Response-Time versus Resource Utilization
%A Aurelien Bouteiller
%A Franck Cappello
%A Jack Dongarra
%A Amina Guermouche
%A Thomas Herault
%A Yves Robert
%X Failures are increasingly threatening the efficiency of HPC systems, and current projections of Exascale platforms indicate that roll- back recovery, the most convenient method for providing fault tolerance to general-purpose applications, reaches its own limits at such scales. One of the reasons explaining this unnerving situation comes from the focus that has been given to per-application completion time, rather than to platform efficiency. In this paper, we discuss the case of uncoordinated rollback recovery where the idle time spent waiting recovering processors is used to progress a different, independent application from the sys- tem batch queue. We then propose an extended model of uncoordinated checkpointing that can discriminate between idle time and wasted com- putation. We instantiate this model in a simulator to demonstrate that, with this strategy, uncoordinated checkpointing per application comple- tion time is unchanged, while it delivers near-perfect platform efficiency.
%B Euro-Par 2013
%I Springer
%C Aachen, Germany
%8 08-2013
%G eng
%0 Generic
%D 2013
%T Optimal Checkpointing Period: Time vs. Energy
%A Guillaume Aupy
%A Anne Benoit
%A Thomas Herault
%A Yves Robert
%A Jack Dongarra
%B University of Tennessee Computer Science Technical Report (also LAWN 281)
%I University of Tennessee
%8 10-2013
%G eng
%0 Generic
%D 2013
%T Revisiting the Double Checkpointing Algorithm
%A Jack Dongarra
%A Thomas Herault
%A Yves Robert
%K checkpoint algorithm
%K communication overlap
%K fault-tolerance
%K performance model
%K resilience
%X Fast checkpointing algorithms require distributed access to stable storage. This paper revisits the approach base upon double checkpointing, and compares the blocking algorithm of Zheng, Shi and Kalé, with the non-blocking algorithm of Ni, Meneses and Kalé in terms of both performance and risk. We also extend the model that they have proposed to assess the impact of the overhead associated to non-blocking communications. We then provide a new peer-to-peer checkpointing algorithm, called the triple checkpointing algorithm, that can work at constant memory, and achieves both higher efficiency and better risk handling than the double checkpointing algorithm. We provide performance and risk models for all the evaluated protocols, and compare them through comprehensive simulations.
%B University of Tennessee Computer Science Technical Report (LAWN 274)
%8 01-2013
%G eng
%0 Conference Paper
%B 15th Workshop on Advances in Parallel and Distributed Computational Models, at the IEEE International Parallel & Distributed Processing Symposium
%D 2013
%T Revisiting the Double Checkpointing Algorithm
%A Jack Dongarra
%A Thomas Herault
%A Yves Robert
%X Abstract—Fast checkpointing algorithms require distributed access to stable storage. This paper revisits the approach base upon double checkpointing, and compares the blocking algorithm of Zheng, Shi and Kale [1], with the non-blocking algorithm of Ni, Meneses and Kale [2] in terms of both performance and risk. We also extend the model proposed in [1], [2] to assess the impact of the overhead associated to non-blocking communications. We then provide a new peer-topeer checkpointing algorithm, called the triple checkpointing algorithm, that can work at constant memory, and achieves both higher efficiency and better risk handling than the double checkpointing algorithm. We provide performance and risk models for all the evaluated protocols, and compare them through comprehensive simulations.
%B 15th Workshop on Advances in Parallel and Distributed Computational Models, at the IEEE International Parallel & Distributed Processing Symposium
%C Boston, MA
%8 05-2013
%G eng
%0 Journal Article
%J Concurrency and Computation: Practice and Experience
%D 2013
%T Unified Model for Assessing Checkpointing Protocols at Extreme-Scale
%A George Bosilca
%A Aurelien Bouteiller
%A Elisabeth Brunet
%A Franck Cappello
%A Jack Dongarra
%A Amina Guermouche
%A Thomas Herault
%A Yves Robert
%A Frederic Vivien
%A Dounia Zaidouni
%X In this paper, we present a unified model for several well-known checkpoint/restart protocols. The proposed model is generic enough to encompass both extremes of the checkpoint/restart space, from coordinated approaches to a variety of uncoordinated checkpoint strategies (with message logging). We identify a set of crucial parameters, instantiate them, and compare the expected efficiency of the fault tolerant protocols, for a given application/platform pair. We then propose a detailed analysis of several scenarios, including some of the most powerful currently available high performance computing platforms, as well as anticipated Exascale designs. The results of this analytical comparison are corroborated by a comprehensive set of simulations. Altogether, they outline comparative behaviors of checkpoint strategies at very large scale, thereby providing insight that is hardly accessible to direct experimentation.
%B Concurrency and Computation: Practice and Experience
%8 11-2013
%G eng
%R 10.1002/cpe.3173
%0 Conference Proceedings
%B IPDPS 2012, the 26th IEEE International Parallel and Distributed Processing Symposium
%D 2012
%T Hierarchical QR factorization algorithms for multi-core cluster systems
%A Jack Dongarra
%A Mathieu Faverge
%A Thomas Herault
%A Julien Langou
%A Yves Robert
%B IPDPS 2012, the 26th IEEE International Parallel and Distributed Processing Symposium
%I IEEE Computer Society Press
%C Shanghai, China
%8 05-2012
%G eng
%0 Journal Article
%J Perspectives on Parallel and Distributed Processing: Looking Back and What's Ahead (to appear)
%D 2012
%T Looking Back at Dense Linear Algebra Software
%A Piotr Luszczek
%A Jakub Kurzak
%A Jack Dongarra
%E Viktor K. Prasanna
%E Yves Robert
%E Per Stenström
%B Perspectives on Parallel and Distributed Processing: Looking Back and What's Ahead (to appear)
%8 00-2012
%G eng
%0 Generic
%D 2012
%T Unified Model for Assessing Checkpointing Protocols at Extreme-Scale
%A George Bosilca
%A Aurelien Bouteiller
%A Elisabeth Brunet
%A Franck Cappello
%A Jack Dongarra
%A Amina Guermouche
%A Thomas Herault
%A Yves Robert
%A Frederic Vivien
%A Dounia Zaidouni
%B University of Tennessee Computer Science Technical Report (also LAWN 269)
%8 06-2012
%G eng
%0 Generic
%D 2011
%T Hierarchical QR factorization algorithms for multi-core cluster systems
%A Jack Dongarra
%A Mathieu Faverge
%A Thomas Herault
%A Julien Langou
%A Yves Robert
%K magma
%K plasma
%B University of Tennessee Computer Science Technical Report (also Lawn 257)
%8 10-2011
%G eng
%0 Conference Proceedings
%B 2008 PPoPP Conference
%D 2008
%T Matrix Product on Heterogeneous Master Worker Platforms
%A Jack Dongarra
%A Jean-Francois Pineau
%A Yves Robert
%A Frederic Vivien
%B 2008 PPoPP Conference
%C Salt Lake City, Utah
%8 01-2008
%G eng
%0 Journal Article
%J International Journal of Foundations of Computer Science (IJFCS)
%D 2008
%T Revisiting Matrix Product on Master-Worker Platforms
%A Jack Dongarra
%A Jean-Francois Pineau
%A Yves Robert
%A Zhiao Shi
%A Frederic Vivien
%B International Journal of Foundations of Computer Science (IJFCS)
%V 19
%P 1317-1336
%8 12-2008
%G eng
%0 Journal Article
%J International Journal of Foundations of Computer Science (IJFCS) (accepted)
%D 2007
%T Revisiting Matrix Product on Master-Worker Platforms
%A Jack Dongarra
%A Jean-Francois Pineau
%A Yves Robert
%A Zhiao Shi
%A Frederic Vivien
%B International Journal of Foundations of Computer Science (IJFCS) (accepted)
%8 00-2007
%G eng
%0 Journal Article
%J International Journal of High Performance Computing Applications (Special Issue: Scheduling for Large-Scale Heterogeneous Platforms)
%D 2006
%T Recent Developments in GridSolve
%A Asim YarKhan
%A Keith Seymour
%A Kiran Sagi
%A Zhiao Shi
%A Jack Dongarra
%E Yves Robert
%K netsolve
%B International Journal of High Performance Computing Applications (Special Issue: Scheduling for Large-Scale Heterogeneous Platforms)
%I Sage Science Press
%V 20
%8 00-2006
%G eng
%0 Journal Article
%J Parallel Processing Letters
%D 1999
%T Algorithmic Issues on Heterogeneous Computing Platforms
%A Pierre Boulet
%A Jack Dongarra
%A Fabrice Rastello
%A Yves Robert
%A Frederic Vivien
%B Parallel Processing Letters
%V 9
%P 197-213
%8 01-1999
%G eng
%0 Journal Article
%J SIAM Annual Meeting
%D 1999
%T A Numerical Linear Algebra Problem Solving Environment Designer's Perspective (LAPACK Working Note 139)
%A Antoine Petitet
%A Henri Casanova
%A Clint Whaley
%A Jack Dongarra
%A Yves Robert
%B SIAM Annual Meeting
%C Atlanta, GA
%8 05-1999
%G eng
%0 Journal Article
%J Handbook on Parallel and Distributed Processing
%D 1999
%T Parallel and Distributed Scientific Computing: A Numerical Linear Algebra Problem Solving Environment Designer's Perspective
%A Antoine Petitet
%A Henri Casanova
%A Jack Dongarra
%A Yves Robert
%A Clint Whaley
%B Handbook on Parallel and Distributed Processing
%8 01-1999
%G eng
%0 Journal Article
%J Parallel Computing
%D 1999
%T Static Tiling for Heterogeneous Computing Platforms
%A Pierre Boulet
%A Jack Dongarra
%A Yves Robert
%A Frederic Vivien
%B Parallel Computing
%V 25
%P 547-568
%8 01-1999
%G eng
%0 Journal Article
%J Concurrency: Practice and Experience
%D 1999
%T Tiling on Systems with Communication/Computation Overlap
%A Pierre-Yves Calland
%A Jack Dongarra
%A Yves Robert
%B Concurrency: Practice and Experience
%V 11
%P 139-153
%8 01-1999
%G eng