Search NASA⌕ Search

SEARCH · Search NASA

Results for “Fault Tolerant Algorithms”

Search indexed NASA NTRS and DOE OSTI research on propulsion, heat transfer, battery materials and energy systems. Follow report and document links to the original sources.

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 19 records

A Log-Scaling Fault Tolerant Agreement Algorithm for a Fault Tolerant MPI

The lack of fault tolerance is becoming a limiting factor for application scalability in HPC systems. The MPI does not provide standardized fault tolerance interfaces and semantics. The MPI Forum's Fault Tolerance Working Group is proposing a collective fault tolerant agreement algorithm for the next MPI standard. Such algorithms play a central role in many fault tolerant applications. This paper combines a log-scaling two-phase commit agreement algorithm with a reduction operation to provide the necessary functionality for the new collective without any additional messages. Error handling mechanisms are described that preserve the fault tolerance properties while maintaining overall scalability.

99 GENERAL AND MISCELLANEOUS↗

Parallel reduction to hessenberg form with algorithm-based fault tolerance

This paper studies the resilience of a two-sided factorization and presents a generic algorithm-based approach capable of making two-sided factorizations resilient. We establish the theoretical proof of the correctness and the numerical stability of the approach in the context of a Hessenberg Reduction (HR) and present the scalability and performance results of a practical implementation. Our method is a hybrid algorithm combining an Algorithm Based Fault Tolerance (ABFT) technique with diskless checkpointing to fully protect the data. We protect the trailing and the initial part of the matrix with checksums, and protect finished panels in the panel scope with diskless checkpoints. Compared with the original HR (the ScaLAPACK PDGEHRD routine) our fault-tolerant algorithm introduces very little overhead, and maintains the same level of scalability. We prove that the overhead shows a decreasing trend as the size of the matrix or the size of the process grid increases.

Computer Science↗

Algorithm-Based Fault Tolerance for Convolutional Neural Networks

Convolutional neural networks (CNNs) are becoming more and more important for solving challenging and critical problems in many fields. CNN inference applications have been deployed in safety-critical systems, which may suffer from soft errors caused by high-energy particles, high temperature, or abnormal voltage. Of critical importance is ensuring the stability of the CNN inference process against soft errors. Traditional fault tolerance methods are not suitable for CNN inference because error-correcting code is unable to protect computational components, instruction duplication techniques incur high overhead, and existing algorithm-based fault tolerance (ABFT) techniques cannot protect all convolution implementations. In this paper, we focus on how to protect the CNN inference process against soft errors as efficiently as possible, with the following three contributions. (1) We propose several systematic ABFT schemes based on checksum techniques and analyze their fault protection ability and runtime thoroughly. Unlike traditional ABFT based on matrix-matrix multiplication, our schemes support any convolution implementations. (2) We design a novel workflow integrating all the proposed schemes to obtain a high detection/correction ability with limited total runtime overhead. (3) We perform our evaluation using ImageNet with well-known CNN models including AlexNet, VGG-19, ResNet-18, and YOLOv2. Here, experimental results demonstrate that our implementation can handle soft errors with very limited runtime overhead (4%~8% in both error-free and error-injected situations).

97 MATHEMATICS AND COMPUTING↗

Leveraging Qubit Loss Detection in Fault-Tolerant Quantum Algorithms

Qubit loss errors constitute a dominant source of noise in many quantum hardware systems, particularly in neutral-atom quantum computers. We develop a theoretical framework to effectively detect and correct loss errors in logical algorithms and leverage such loss information in decoding. Considering general quantum error correction codes and logical circuits, we introduce a delayed-erasure decoder for experimentally motivated error models which leverages information from delayed loss detection to accurately correct loss errors, even when the precise moment of the error is unknown. Using this decoder, we identify strategies for detecting and correcting loss errors based on the logical circuit structure. For deep circuits prior to logical measurement, we explore methods to integrate loss detection into syndrome extraction with minimal overhead, identifying optimal strategies depending on the qubit loss fraction in the noise and hardware capabilities. In contrast, we find that many key algorithmic subroutines involve frequent gate teleportation, shortening the circuit depth before logical measurement and naturally replacing qubits with no additional experimental overhead. We simulate this setting using a toy model algorithm for small-angle synthesis and find a significant performance improvement as the loss fraction increases. These results provide a path forward for advancing large-scale fault-tolerant quantum computation in systems with loss error detection.

atoms↗

Using Rollback Avoidance to Mitigate Failures in Next-Generation Extreme-Scale Systems

High-performance computing (HPC) systems enable scientists to numerically model complex phenomena in many important physical systems. The next major milestone in the development of HPC systems is the construction of the rst supercomputer capable executing more than an exa op, 10 18 oating point operations per second. On systems of this scale, failures will occur much more frequently than on current systems. As a result, resilience is a key obstacle to building next-generation extremescale systems. Coordinated checkpointing is currently the most widely-used mechanism for handling failures on HPC systems. Although coordinated checkpointing remains e ective on current systems, increasing the scale of today's systems to build next-generation systems will increase the cost of fault tolerance as more and more time is taken away from the application to protect against or recover from failure. Rollback avoidance techniques seek to mitigate the cost of checkpoint/restart by allowing an application to continue its execution rather than rolling back to an earlier checkpoint when failures occur. These techniqes include failure prediction and preventive migration, replicated computation, fault-tolerant algorithms, and softwarebased memory fault correction. In this thesis, we examine how rollback avoidance techniques can be used to address failures on extreme-scale systems. Using a combination of analytic modeling and simulation, we evaluate the potential impact of rollback avoidance on these systems. We then present a novel rollback avoidance technique that exploits similarities in application memory. Finally, we examine the feasibility of using this technique to protect against memory faults in kernel memory.

97 MATHEMATICS AND COMPUTING↗

Preserving Collective Performance Across Process Failure for a Fault Tolerant MPI

Application developers are investigating Algorithm Based Fault Tolerance (ABFT) techniques to improve the efficiency of application recovery beyond what traditional techniques alone can provide. Applications will depend on libraries to sustain failure-free performance across process failure to continue to efficiently use High Performance Computing (HPC) systems even in the presence of process failure. Optimized Message Passing Interface (MPI) collective operations are a critical component of many scalable HPC applications. However, most of the collective algorithms are not able to handle process failure. Next generation MPI implementations must provide fault aware versions of such algorithms that can sustain performance across process failure. This paper discusses the design and implementation of fault aware collective algorithms for tree structured communication patterns. The three design approaches of rerouting, lookup avoiding and rebalancing are described, and analyzed for their performance impact relative to a similar fault unaware collective algorithm. The analysis shows that the rerouting approach causes up to a four times performance degradation while the rebalancing approach can bring the performance within 1% of the fault unaware performance. Additionally, this paper introduces the reader to a set of run-through stabilization semantics being developed by the MPI Forum's Fault Tolerance Working Group to support ABFT. This paper underscores the need for care to be taken when designing new fault aware collective algorithms for fault tolerant MPI implementations.

99 GENERAL AND MISCELLANEOUS↗

Self-stabilizing Connected Components

For the problem of computing the connected components of a graph, this paper considers the design of algorithms that are resilient to transient hardware faults, like bit Hips. More specifically, it applies the technique of self-stabilization. A system is self-stabilizing if, when starting from a valid or invalid state, it is guaranteed to reach a valid state after a finite number of steps. Therefore on a machine subject to a transient fault, a self-stabilizing algorithm could recover if that fault caused the system to enter an invalid state. We give a comprehensive analysis of the valid and invalid states during label propagation and derive algorithms to verify and correct the invalid state. The self-stabilizing label-propagation algorithm performs O (V log V) additional computation and requires O (V) additional storage over its conventional counterpart (and, as such, does not increase asymptotic complexity over conventional label propagation). When run against a battery of simulated fault injection tests, the self-stabilizing label propagation algorithm exhibits more resilient behavior than a triple modular redundancy (TMR) based fault-tolerant algorithm in 80% of cases. From a performance perspective, it also outperforms TMR as it requires fewer iterations in total. Beyond the fault tolerance properties of self-stabilizing label-propagation, we believe, they are useful from the theoretical perspective; and may have other use-cases.

Sao, Piyush↗

Risk assessment of safety-critical data communication in digital safety feature control system - 205

As one of the safety-critical systems in Advanced Power Reactor-1400 (APR-1400) nuclear power plant (NPP), the Engineered Safety Feature-Component Control System (ESF-CCS) employs safety data link and network communication for transmitting safety component actuation to effectively facilitate various safety-critical field controllers. However, data communication failure risk in the ESF-CCS has yet to be fully quantified, the probability that a safety-critical system in digitalized NPP becomes unsafe due to a network failure must be evaluated to quantify the risk of digital I and C system. In this study, a fault tree model was developed to assess the data link and data network failure-induced unavailability of a safety-critical system function used to generate an automated control signal for actuating design basis accident mitigation equipment. Especially, the risk of data communication failure in a digital safety feature control system was analyzed in consideration of interconnection between safety-critical controllers and the fault-tolerant algorithm implemented in the network configuration. Based on the developed fault tree model, case studies were performed to quantitatively assess the unavailability of ESF-CCS signal generation due to safety data link and network failure and their risk effect on safety signal generation unavailability. This study is expected to provide risk information on the safety-critical data communication in a digitalized NPP instrumentation and control system. (authors)

21 SPECIFIC NUCLEAR REACTORS AND ASSOCIATED PLANTS↗

Resilient Autonomous Wind Farms: Preprint

With the advent of an increasing number of control strategies that seek to optimize wind turbine performance on a farm-level, taking account of individual wind turbine information to achieve wind farm-level objectives has become an increasingly important goal. Methods for controlling wind turbines on an individual and farm level have seen significant development, and an abundance of new implementations for gathering and using data from turbines have created potential for novel control mechanisms which can further optimize the performance and delivery characteristics of a wind farm. A key element of making these wind farms more efficient is to develop reliable algorithms that use local sensor information that is already being collected, such as supervisory control and data acquisition (SCADA) data, local meteorological stations, and nearby radars/sodars/lidars. Making use of information from all wind turbines in a wind farm can enable such approaches as determining the atmospheric conditions across the farm, improving fault-finding, and enabling more efficient overall control of farm-wide optimizations through mechanisms such as wake-steering. However, these approaches typically involve a centralized communications and control center. In order to ensure the resilient operation of the farm, it is necessary to develop an approach which distributes the calculation and communication amongst multiple nodes throughout the farm. In this fashion, a redundant, robust, and secure network can be created, which can tolerate faults in calculation, communication, and even external attacks which seek to disrupt the operation of the wind farm. This paper introduces the use of the Raft Byzantine Fault Tolerance algorithm in the implementation of autonomous control of a wind farm. This implementation will allow for fault tolerance for malfunctioning nodes, sensors, transmitters, and connectors. This approach is equally extensible to account for malicious actors. It will be shown to achieve overall consensus, provided the number of faults/malicious nodes is less than 3$n$+1, where $n$ is the number of turbine cluster faults which may occur, and to be robust in the face of multiple arbitrary faults.

autonomous↗

Resilient Autonomous Wind Farms

With the advent of an increasing number of control strategies that seek to optimize wind turbine performance on a farm level, taking into account individual wind turbine information to achieve wind-farm-level objectives has become an increasingly important goal. Methods for controlling wind turbines on an individual and farm level have experienced significant development, and an abundance of new implementations for gathering and using data from turbines have created potential for novel control mechanisms that can further optimize the performance and delivery characteristics of a wind farm. A key element of making these wind farms more efficient is to develop reliable algorithms that use local sensor information that is already being collected, such as from local meteorological stations, nearby radars, sodars, and lidars, and supervisory control and data acquisition (SCADA) data. Making use of information from all wind turbines in a wind farm can enable such approaches as determining the atmospheric conditions across the farm, improving fault-finding, and ensuring more efficient overall control of farmwide optimizations through mechanisms such as wake steering. However, these approaches typically involve a centralized communications and control center. In order to ensure the resilient operation of the farm, it is necessary to develop an approach that distributes the calculation and communication amongst multiple nodes throughout the farm. In this fashion, a redundant, robust, and secure network can be created, which can tolerate faults in calculation, communication, and even external attacks that seek to disrupt the operation of the wind farm. This paper introduces the use of the Raft-Byzantine-Fault-Tolerant algorithm in the implementation of autonomous control of a wind farm. This implementation will allow for fault tolerance for malfunctioning nodes, sensors, transmitters, and connectors. This approach is equally extensible to account for malicious actors. It will...

fault tolerance↗

Fault-tolerant grid frequency measurement algorithm during transients

Many critical electric grid operations rely on accurate grid frequency measurements. Unfortunately, the measurement accuracy can be easily undermined by power system transient faults. During a power system transient fault, the power grid voltages and currents are usually highly distorted by high-frequency components. What is worse, the power grid signals could have discontinuity during some system transient faults such as phase angle jump, and the discontinuity could result in large measurement errors to state-of-the-art grid measurement algorithms. In this study, a fault-tolerant grid frequency measurement algorithm during transients is proposed. The new algorithm consists of two stages. The first stage is a transient detector, and it can detect the occurrence of system transient faults instantaneously. The second stage is the intelligent frequency estimator, and it will adapt its measurements according to the transient detector. The performance of the algorithm is evaluated under different steady-state and transient conditions. Both dependability and security of the fault-tolerant algorithm are assessed by using PSCAD simulation data and IEEE Standard test data.

24 POWER TRANSMISSION AND DISTRIBUTION↗

Low-overhead transversal fault tolerance for universal quantum computation

Fast, reliable logical operations are essential for realizing useful quantum computers. By redundantly encoding logical qubits into many physical qubits and using syndrome measurements to detect and correct errors, we can achieve low logical error rates. However, for many practical quantum error correction codes such as the surface code, owing to syndrome measurement errors, standard constructions require multiple extraction rounds—of the order of the code distance d—for fault-tolerant computation, particularly considering fault-tolerant state preparation. Here we show that logical operations can be performed fault-tolerantly with only a constant number of extraction rounds for a broad class of quantum error correction codes, including the surface code with magic state inputs and feedforward, to achieve ‘transversal algorithmic fault tolerance’. Through the combination of transversal operations7 and new strategies for correlated decoding, despite only having access to partial syndrome information, we prove that the deviation from the ideal logical measurement distribution can be made exponentially small in the distance, even if the instantaneous quantum state cannot be made close to a logical codeword because of measurement errors. We supplement this proof with circuit-level simulations in a range of relevant settings, demonstrating the fault tolerance and competitive performance of our approach. Furthermore, our work sheds new light on the theory of quantum fault tolerance and has the potential to reduce the space–time cost of practical fault-tolerant quantum computation by over an order of magnitude.

Zhou, Hengyun [QuEra Computing, Boston, MA (United↗

A case for Virtual Machine based Fault Injection in a High-Performance Computing Environment

Large-scale computing platforms provide tremendous capabilities for scientific discovery. These systems have hundreds of thousands of computing cores, hundreds of terabytes of memory, and enormous high-performance interconnection networks. These systems are facing enormous challenges to achieve performance at such scale. Failures are an Achilles heel of these enormous systems. As applications and system software scale up to multi-petaflop and beyond to exascale platforms, the occurrence of failure will be much more common. This has given rise to a push in fault-tolerance and resilience research for HPC systems. This includes work on log analysis to identify types of failures, enhancements to the Message Passing Interface (MPI) to incorporate fault awareness, and a variety of fault tolerance mechanisms that span redundant computation, algorithm based fault tolerance, and advanced checkpoint/restart techniques. While there is much work to be done on the FT/Resilience mechanisms for such large-scale systems, there is also a profound gap in the tools for experimentation. This gap is compounded by the fact that HPC environments have stringent performance requirements and are often highly customized. The tool chain for these systems are often tailored for the platform and while the majority of systems on the Top500 Supercomputer list run Linux, these operating environments typically contain many site/machine specific enhancements. Therefore, it is desirable to maintain a consistent execution environment to minimize end-user (scientist) interruption. The work on system-level virtualization for HPC system offers a unique opportunity to maintain a consistent execution environment via a virtual machine (VM). Recent work on virtualization for HPC has shown that low-overhead, high performance systems can be realized. Virtualization also provides a clean abstraction for building experimental tools for investigation into the effects of failures in HPC and the related research on FT/Resilience mechanisms and policies. In this paper we discuss the motivation for tools to perform fault injection in an HPC context, and outline an approach that can leverage virtualization.

99 GENERAL AND MISCELLANEOUS↗

Adapting Secure MultiParty Computation to Support Machine Learning in Radio Frequency Sensor Networks

In this project we developed and validated algorithms for privacy-preserving linear regression using a new variant of Secure Multiparty Computation (MPC) we call "Hybrid MPC" (hMPC). Our variant is intended to support low-power, unreliable networks of sensors with low-communication, fault-tolerant algorithms. In hMPC we do not share training data, even via secret sharing. Thus, agents are responsible for protecting their own local data. Only the machine learning (ML) model is protected with information-theoretic security guarantees against honest-but-curious agents. There are three primary advantages to this approach: (1) after setup, hMPC supports a communication-efficient matrix multiplication primitive, (2) organizations prevented by policy or technology from sharing any of their data can participate as agents in hMPC, and (3) large numbers of low-power agents can participate in hMPC. We have also created an open-source software library named "Cicada" to support hMPC applications with fault-tolerance. The fault-tolerance is important in our applications because the agents are vulnerable to failure or capture. We have demonstrated this capability at Sandia's Autonomy New Mexico laboratory through a simple machine-learning exercise with Raspberry Pi devices capturing and classifying images while flying on four drones.

42 ENGINEERING↗