检索结果-内蒙古大学图书馆

Generalized algorithm-based fault tolerance: Error correction via Kalman estimation

IEEE TRANSACTIONS ON COMPUTERS 1998年第6期47卷 639-655页

作者： Redinbo, GR Univ Calif Davis Dept Elect & Comp Engn Davis CA 95616 USA

An extension to algorithm-based fault tolerance (ABFT) methodologies shows how parity values dictated by a real convolutional code can be employed by Kalman estimation techniques to perform real number correction for protecting linear processing systems, intermittent failures appearing in the output samples are detected and corrected using only the syndromes normally generated in ABFT schemes. The algebraic structure of a real convolutional code provides separation needed by recursive Kalman state estimators to affect mean-square error correction. State and parity measurement equations model faults and computational noise in both the linear processing and parity generation subassemblies, and, in a departure from previous models, the noise sources are considered time-varying. The Kalman one-step estimator which makes decisions on all parity values up to the present point is determined, and it separates naturally into detection and correction operations permitting corrective action only when the detection levels exceed thresholds based on roundoff noise energy. The detector/corrector uses efficient multirate block processing techniques as determined by the real convolutional code. A smoothed fixed-lag Kalman estimator which uses parity values for a fixed amount beyond the point of interest is needed to complete the correction. It employs one-step estimator quantities and implementation simplifications are possible. Examples showing the correction behavior and mean-square error performance are presented, and the size of overhead calculations for detection and correction is estimated. A protected processing system is constructed by introducing additional subassemblies, mostly comparators, with the detection and correction parts already described. Under the usual assumptions of at most a single subassembly failure, no improperly detected or corrected data leave the overall protected configuration.

关键词： algorithm-based fault tolerance fault-tolerant linear processing Kalman recursive filtering mean-square error estimation real convolutional codes real number error correction time-varying fault models totally self-checking comparators

来源：评论

学校读者我要写书评

暂无评论

Concurrent error detection in fast unitary transform algorithms

Concurrent error detection in fast unitary transform algorit...

引用

International Conference on Dependable Systems and Networks (DSN 2001)

作者： Redinbo, GR Univ Calif Davis Dept Elect & Comp Engn Davis CA 95616 USA

ISBN: (纸本)0769511023

Discrete fast unitary transform algorithms, of which the fast Fourier transform (FFT) and fast discrete Cosine transform (DCT) are practical examples, are highly susceptible to temporary calculation failures because of their interconnected computational flows. Many error detection techniques for FFT algorithms have been reported, but fault tolerance issues for other important transforms have not been addressed as vigorously. A general design and analysis approach for all fast unitary transforms is presented. It relies on fundamental linear algebra methods coupled with associated dual space representations that are natural descriptions of real parity values. Basic output error patterns from single computational errors are used to define an equal-sized group of dual space basis vectors on which practical parity weighting functions maybe evaluated. An iterative design approach leads to complete single error detection capabilities. FFT and fast DCT examples are given.

关键词： algorithm-based fault tolerance numerical error detection real number parity values fast Fourier transform fast discrete cosine transform

来源：评论

学校读者我要写书评

暂无评论

algorithm-based fault tolerance: a review

引用

MICROPROCESSORS AND MICROSYSTEMS 1997年第3期21卷 151-161页

作者： Vijay, M Mittal, R Indian Inst Technol Dept Comp Sci & Engn Madras 600036 Tamil Nadu India

The need for reliability of computers has been increasing, as computers have been put to use in more and more practical applications. Multiprocessor architectures have provided elegant solutions for certain computationally expensive problems which find wide-ranging applications in areas such as defense and industry. Since computer-intensive applications are run on these architectures, the probability that some computations will incur error is not negligible. Hence fault tolerance plays an important role in the design of multiprocessor architectures. In this paper, we review a low-cost scheme for adding fault tolerance in multiprocessor architectures, called algorithm-based fault tolerance (ABFT). The concurrent error detecting and correcting capabilities of this scheme are demonstrated with the help of examples. Various issues of interest, the areas open to research and the limitations of ABFT are also pointed out. (C) 1997 Elsevier Science B.V.

关键词： algorithm-based fault tolerance fault tolerance multiprocessor architectures space redundancy time redundancy

来源：评论

学校读者我要写书评

暂无评论

Mantissa-preserving operations and robust algorithm-based fault tolerance for matrix computations

引用

IEEE TRANSACTIONS ON COMPUTERS 1996年第4期45卷 408-424页

作者： Dutt, S Assaad, FT Dept. of Electr. Eng. Minnesota Univ. Minneapolis MN USA

A system-level method for achieving fault tolerance called algorithm-based fault tolerance (ABFT) has been proposed by a number of researchers. Many ABFT schemes use a floating-point checksum test to detect computation errors resulting from hardware faults. This makes the tests susceptible to roundoff inaccuracies in floating-point operations, which either cause false alarms or lead to undetected errors. Thresholding of the equality test has been commonly used to avoid false alarms;however, a good threshold that minimizes false alarms without reducing the error coverage significantly is difficult to find, especially when not much is known about the input data. Furthermore, thresholded checksums will inevitably miss lower-bit errors, which can get magnified as a computation such as LU decomposition progresses. Here we develop a theory for applying integer mantissa checksum tests to ''mantissa-preserving'' floating-point computations. This test is not susceptible to roundoff problems and yields 100% error coverage without false alarms. For computations that are not fully mantissa-preserving, we show how to apply the mantissa checksum test to the mantissa-preserving components of the computation and the floating-point test to the rest of the computation. We apply this general methodology to matrix-matrix multiplication and LU decomposition (using the Gaussian elimination (GE) algorithm), and find that the accuracy of this new ''hybrid'' testing scheme is substantially higher than the floating-point test with thresholding, and also that its time overhead with respect to the floating-point test is nominal (15% and 9.5% on the average for matrix multiplication and LU decomposition, respectively). The hybrid test can also be easily applied to other computations like matrix inversion that use the GE algorithm. We prove that the mantissa-based integer checksum test for both matrix multiplication and LU decomposition is able to detect at least three errors in the floating-poi

关键词： algorithm-based fault tolerance floating-point checksum test hybrid checksum test mantissa checksum test mantissa-preserving operations matrix multiplication LU decomposition roundoff errors thresholding

来源：评论

学校读者我要写书评

暂无评论

Efficient techniques for the analysis of algorithm-based fault tolerance (ABFT) schemes

引用

IEEE TRANSACTIONS ON COMPUTERS 1996年第4期45卷 499-503页

作者： Nair, VSS Abraham, JA Banerjee, P UNIV TEXAS COMP ENGN RES CTRAUSTINTX 78712 UNIV ILLINOIS CTR RELIABLE & HIGH PERFORMANCE COMPURBANAIL 61801

This paper presents a model which can be used to characterize the diagnosability of algorithm-based fault Tolerant (ABFT) systems. In the model, the relationship between processors computing useful data, the output data, and the check processors is defined in terms of matrix entries. Necessary and sufficient conditions for detecting and locating faults in the processors are derived, and based on them, efficient algorithms to evaluate the fault detection and location capabilities oi the system are developed.

关键词： multiprocessor systems faults and errors system-level diagnosis algorithm-based fault tolerance modeling and analysis

来源：评论

学校读者我要写书评

暂无评论

Analysis and randomized design of algorithm-based fault tolerant multiprocessor systems under an extended model

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 1997年第7期8卷 757-768页

作者： Yajnik, S Jha, NK PRINCETON UNIV DEPT ELECT ENGNPRINCETONNJ 08544

Reliability of compute-intensive applications can be improved by introducing fault tolerance into the system. algorithm-based fault tolerance (ABFT) is a low-cost scheme which provides the required fault tolerance to the system through system level encoding. In this paper, we propose randomized construction techniques, under an extended model, for the design of ABFT systems with the required fault tolerance capability. The model considers failures in the processors performing the checking operations.

关键词： algorithm-based fault tolerance concurrent error detection concurrent fault location randomized algorithms fault diagnosis transient faults

来源：评论

学校读者我要写书评

暂无评论

Decoding real-number convolutional codes: Change detection, Kalman estimation

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 1997年第6期43卷 1864-1876页

作者： Redinbo, GR Department of Electrical and Computer Engineering University of California Davis CA USA

Convolutional codes which employ real-number symbols are difficult to decode because of the size of the alphabet and the numerical and roundoff noise inherent in arithmetic operations. Such codes find applications in both channel coding for communication systems and in fault-tolerance support for signal processing subsystems. A new method for error correction, based on optimum mean-square recursive Kalman estimation techniques incorporates time-varying models for the system and associated disruptive noise sources. The underlying common model for communications and fault tolerance applications assumes the system operates nominally with low levels of channel or numerical and roundoff noise, occasionally experiencing temporarily larger noise statistics. A time-varying Kalman estimation structure which uses single-step and fixed-lag smoothing predictors can correct errors to within the nominal low-noise levels. Correction actions may be activated only when larger activity is detected, so methods for detecting possible error situations are developed. However, misdetection is not a serious problem because the Kalman correction methods only track significant errors in the data. Two activity detection techniques are examined;one is based on likelihood ratio tests while another uses clipped samples and binary pattern matching. Several examples showing simulated mean-square error performance and decoded waveforms from error injection experiments are presented.

关键词： algorithm-based fault tolerance change detection channel coding fault tolerance Kalman recursive estimation mean-square error correction real-number codes time-varying error models

来源：评论

学校读者我要写书评

暂无评论

Extending backward error assertions to tolerance of large errors in floating point computations

引用

IEEE TRANSACTIONS ON COMPUTERS 1997年第4期46卷 505-510页

作者： Fitzpatrick, P NATL UNIV IRELAND UNIV COLL CORK NATL MICROELECT RES CTR CORK IRELAND

The use of backward error assertions combined with iterative refinement has been suggested for the correction of small fault induced errors in the floating point solution of linear systems. We extend this to the corre... 详细信息

关键词： fault tolerance algorithm-based fault tolerance backward error assertions floating point computation

来源：评论

学校读者我要写书评

暂无评论

Graceful degradation in algorithm-based fault tolerant multiprocessor systems

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 1997年第2期8卷 137-153页

作者： Yajnik, S Jha, NK PRINCETON UNIV DEPT ELECT ENGN PRINCETON NJ 08544 USA

algorithm-based fault tolerance (ABFT) is a technique which improves the reliability of a multiprocessor system by providing concurrent error detection and fault location capability to it. It encodes data at the system level and modifies the algorithm to operate on the encoded data in order to expose both transient and permanent faults in any processor. Work done till now in this area takes care of only the fault detection and location part of the problem. However, if spare processors are not available, then after a faulty processor has been located, the work initially assigned to it has to be mapped to some nonfaulty processors in the system in such a way that the fault tolerance capability of the system is still maintained with as small a degradation in performance as possible. In this paper, we propose an integrated deterministic solution to the above problem which combines concurrent error detection and fault location with graceful degradation. There exists no previous deterministic ABFT method for the design of general t-fault locating systems, even for the case of t = 1. We propose a general method for designing one-fault locating/s-fault detecting systems. We use an extended model for representing ABFT systems. This model considers the processors computing the checks to be a part of the ABFT system, so that faults in the check_computing processors can also be detected and located using a simple diagnosis algorithm, and the checks can be mapped to other nonfaulty processors in the system.

关键词： algorithm-based fault tolerance concurrent error detection concurrent fault location fault diagnosis graceful degradation transient faults

来源：评论

学校读者我要写书评

暂无评论

algorithm-based fault-tolerance FOR FFT NETWORKS (VOL 43, PG 849, 1994)

引用

IEEE TRANSACTIONS ON COMPUTERS 1994年第10期43卷 1248-1248页

作者： WANG, SJ JHA, NK PRINCETON UNIV DEPT ELECT ENGNPRINCETONNJ 08544

algorithm-based fault tolerance (ABFT) is a low-overhead system-level fault tolerance technique. Many ABFT schemes have been proposed in the past for fast Fourier transform (FFT) networks. In this paper, a new ABFT scheme for FFT networks is proposed. We show that the new approach maintains the high throughput of previous schemes, yet needs lower hardware overhead and achieves higher fault converge than previous schemes by J.Y. Jou et al. (1988) and D.I. Tao et al. (1990)

关键词： algorithm-based fault tolerance Fast Fourier Transform Concurrent error detection hardware redundancy schemes transient errors.

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：