On testing for catastrophic faults in reconfigurable arrays with arbitrary link redundancy

Fault tolerance through the incorporation of redundancy and reconfiguration is quite common. The distribution of faults can have severe impact on the effectiveness of any reconfiguration scheme; in fact, patterns of faults occurring at strategic locations may render an entire system unusable regardless of its component redundancy and its reconfiguration capabilities. Testing of catastrophic faults was given for reconfigurable arrays with 2-link redundancy; i.e., a bypass link of fixed length is provided to each element of the array in addition to the regular link.

In this paper, we study the more general case of arbitrary (but regular) link redundancy. In particular, we focus on the problem of deciding whether a pattern of k faults is catastrophic for a k-link redundant system; i.e., in addition to the regular link of length ₁ = 1, each element of the array is provided with k −1 bypass links of length ₂, ₃,… _k, respectively.

We study this problem and prove some fundamental properties which any catastrophic fault pattern must satisfy. We then show that these properties together constitute a necessary and sufficient condition for a fault pattern to be catastrophic for a k-link redundant system. As a consequence, we derive a provably correct testing algorithm whose worst-case time complexity is O(k _k); this also improves on the previous algorithm for k = 2.     

Schemes of dynamic redundancy for fault tolerance in random accessmemories

For large memory capacities, stand-by systems usually need a considerable amount of redundant hardware, not only because of the spare components, but for storing fault conditions and for carrying out the necessary reconfiguration. As alternatives, two methods of implementing fault tolerance by means of dynamic redundancy in random-access memories are proposed which allow the treatment of memory-chip faults at the interface of the memory. The memory reliability for both approaches is estimated by a simple model. These methods improve the reliability considerably compared to conventional memory fault tolerance methods, and the size of the units of reconfiguration can be tailored to the demands of the system user     

Fault tolerance of on-board digital signal processing circuits

The paper is organized in four sections. The first section introduces the nature of faults as well as their causes. The methods used to identify faults and the actions necessary to correct the situation are outlined. The second section identifies the different fault tolerance approaches to conventional computational circuits and the DSP circuits. Current research work in the area of fault tolerance of FFT, signal processing and VLSI circuits involving systolic arrays is reviewed. Since some of the techniques do not involve error correction, reconfiguration of the circuit after error detection becomes necessary and a brief look at the relevant reconfiguration strategies is appropriate. Software fault tolerance is introduced and some work applicable to computations in general is reviewed. The implementation of the methods and its consequences are described in the third section. Concluding remarks form the final section.     

Design of reconfigurable fault-tolerant VLSI/WSI processor array structures

This paper presents a new reconfiguration technique for VLSI/WSI processor arrays. The fault-tolerant capabilities of both interstitial redundancy and time redundancy are combined to provide optimal reconfiguration. Results obtained through Monte Carlo simulations show that with the proposed reconfiguration technique, a very high yield and chip area utilization is achieved. It is also shown that in the presence of harsh environments, where a high rate of transient faults occur, the proposed algorithm is more robust compared to the existing approaches.     

Design-for-testability and fault-tolerant techniques for FFT processors

In this paper, we first propose a novel design-for-testability approach based on M-testability conditions for module-level systolic fast Fourier transform (FFT) arrays. Our M-testability conditions guarantee 100% single-module-fault testability with a minimum number of test patterns. Based on this testable design, fault-tolerant approaches at the bit level and the multiply-subtract-add (MSA) module level are proposed, respectively. If the reconfiguration is performed at the bit level, then the FFT/sub BIT/ network is constructed. Two types of reconfiguration schemes (Type-I FFT/sub MSA/ and Type-II FFT/sub MSA/) are proposed at the MSA module level. Since both the design for testability (DFT) and the design for yield (DFY) issues are considered at the same time for all these proposed approaches, the resulting architectures are simpler as compared with previous works. The reliability of the FFT system increases significantly. The hardware overhead is low-about 12% and 1/2N for the FFT/sub BIT/ network and the Type-II FFT/sub MSA/ network, respectively. An experimental chip is also implemented to verify our approaches. Reliabilities and hardware overhead are also evaluated and compared with previous works.     

Characterization, testing and reconfiguration of faults in mesh networks

Achieving fault-tolerance through incorporation of redundancy and reconfiguration is quite common. The distribution of faults can have several impacts on the effectiveness of any reconfiguration scheme; in fact, patterns of faults occurring at strategic locations may render an entire VLSI system unusable regardless of its component redundancy and its reconfiguration capabilities. Such fault patterns are called catastrophic fault patterns (CFPs). In this paper, we characterize catastrophic fault patterns in mesh networks when the links are bidirectional or unidirectional. We determine the minimum number of faults required for a fault pattern to be catastrophic. We consider the problem of testing whether a fault pattern is catastrophic. When a fault pattern is not catastrophic we study the problem of finding optimal reconfiguration strategies, where optimality is with respect to either the number of processing elements in the reconfigured network (the reconfiguration is optimal if such a number is maximized) or the number of bypass links to activate in order to reconfigure the array (the reconfiguration is optimal if such a number is minimized). The problem of finding a reconfiguration strategy that is optimal with respect to the size of the reconfigured network is NP-complete, when the links are bidirectional, while it can be solved in polynomial time, when the links are unidirectional. Considering optimality with respect to the number of bypass links to activate, we provide algorithms which efficiently find an optimal reconfiguration.     

A fault-tolerant array processor designed for testability andself-reconfiguration

The design of a fault-tolerant rectangular array of processing elements (PEs) is presented in which the reconfiguration is done by means of on-chip distributed logic, without the help of any external host. Spare PEs are included in every column of the array, and faulty PEs are bypassed within a column to facilitate reconfiguration in the presence of faults. Scan paths are used to enhance the testability of the array. PEs are tested locally using near-neighbor comparisons without the need of an external host. Because the interconnections between logical neighbors are short, the speed penalty for reconfiguration is very small. Any amount of redundancy can be incorporated in the array without changing the topology of the scheme or the design of the reconfiguration switches. The scheme is well suited for very large-area, high-density chips and wafer-scale integration. In order to demonstrate the capabilities of the scheme and evaluate its performance, an experimental chip consisting of a 6×4 array was designed, fabricated, and tested. Details of the design and the implementation of the chip are presented. The scheme is also analyzed for yield and area utilization for a range of array sizes and PE survival probabilities     

仿生容错系统的可靠性分析

人工生命科学就是研究生物机体的特征，胚胎电子学介绍了新一代生物灵感容错FPGA系列，适合于人工生命的研究，胚胎电子阵列通过硬件冗余和阵列重构机构获得容错功能，本文论述和分析了根据κ-out-of-m可靠性模型的胚胎电子阵列的重构策略。讨论了行取消和细胞取消两种方案。     

基于神经网络的单通道冗余VLSI/WSI阵列重构算法

本文提出了一个基于Hopfield网络的单通道冗余VLSI/WSI阵列重构算法,根据阵列中缺陷单元的分布情况,构造相应的矛盾图模型,将阵列的重构问题转化为求矛盾图的独立集且使得独立集的顶点数恰为缺陷单元的个数,有效地解决了阵列的重构问题.实验结果表明,与传统的启发式方法相比,基于本文所提出的图论模型而采用的神经网络方法是一种简单、快速、高效的算法.     

Online Fault Tolerance for FPGA Logic Blocks

Most adaptive computing systems use reconfigurable hardware in the form of field programmable gate arrays (FPGAs). For these systems to be fielded in harsh environments where high reliability and availability are a must, the applications running on the FPGAs must tolerate hardware faults that may occur during the lifetime of the system. In this paper, we present new fault-tolerant techniques for FPGA logic blocks, developed as part of the roving self-test areas (STARs) approach to online testing, diagnosis, and reconfiguration . Our techniques can handle large numbers of faults (we show tolerance of over 100 logic faults via actual implementation on an FPGA consisting of a 20 times 20 array of logic blocks). A key novel feature is the reuse of defective logic blocks to increase the number of effective spares and extend the mission life. To increase fault tolerance, we not only use nonfaulty parts of defective or partially faulty logic blocks, but we also use faulty parts of defective logic blocks in nonfaulty modes. By using and reusing faulty resources, our multilevel approach extends the number of tolerable faults beyond the number of currently available spare logic resources. Unlike many column, row, or tile-based methods, our multilevel approach can tolerate not only faults that are evenly distributed over the logic area, but also clusters of faults in the same local area. Furthermore, system operation is not interrupted for fault diagnosis or for computing fault-bypassing configurations. Our fault tolerance techniques have been implemented using ORCA 2C series FPGAs which feature incremental dynamic runtime reconfiguration     

Reconfigurable architectures for VLSI processing arrays

The paper presents the problem of fault tolerance in VLSI array structures: its aim is to discuss architectures capable of surviving a number of random faults while keeping costs (in terms of added silicon area and of increased processing time) as low as possible. Two different approaches are presented, both based upon introduction of simple patterns of faults and by global reconfiguration techniques (rather than one-to-one substitution of faulty elements by spare ones). Various solutions are compared, and relative performances are discussed in order to determine criteria for selecting the one most suitable to particular applications.     

高冗余光纤光栅传感网络的设计与实验研究

结合无源光学器件,提出并设计了一种新型的高冗余光纤布拉格光栅(FBG)传感模块,并将设计的FBG传感模块与波分复用技术相结合,构建了高冗余FBG传感网络.以长方形铝合金板为研究对象,对高冗余FBG传感网络的可靠性进行研究,理论比较并实验分析了高冗余FBG传感阵列的适用性与可靠性.研究结果表明,利用光开关在传感阵列支路之间的切换,使得FBG传感网络更具有冗余性.这一方面能够解决使用过程中多个部位出现故障导致的某些FBG传感模块无法被计算机检测到的问题,有效提高了传感系统的可靠性、容错性;另一方面为工程应用中结构健康监测以及特殊部位监测提供了一种有效可行的监测手段.     

Improving functional density using run-time circuit reconfiguration[FPGAs]

The ability to provide flexibility and allow fine-grain circuit specialization make field programmable gate arrays (FPGA's) ideal candidates for computing elements within application-specific architectures. The benefits of gate-level specialization and reconfigurability can be extended by reconfiguring circuit resources at run-time. This technique, termed run-time reconfiguration (RTR), allows the exploitation of dynamic conditions or temporal locality within application-specific problems. For several applications, this technique has been shown to reduce the hardware resources required for computation. The use of this technique on conventional FPGA's, however, requires additional time for circuit reconfiguration. A functional density metric is introduced that balances the advantages of RTR against its associated reconfiguration costs. This metric is used to justify run-time reconfiguration against other more conventional approaches. Several run-time reconfigured applications are presented and analyzed using this approach     

Reliability with imperfect diagnostics

This paper considers the reliability of systems that accumulate faults throughout their lifetime because of imperfect diagnostics. Several experiments are referenced that show the difficulty of achieving a 100 percent diagnostic level. After explaining the assumptions and constructing the reliability estimation method, the paper proceeds to a graphical trade-off analysis that considers the effect of imperfect diagnostics on three traditional ways of achieving higher reliability: lower component fault rate, more redundancy, and redundancy with reconfiguration.     

Reliable and fast reconfigurable hierarchical interconnectionnetworks for linear WSI arrays

A self-pruning binary tree (SPBT) interconnection network architecture that tolerate faults in a wafer scale integration (WSI) environment is proposed. The goal of the SPBT network is to provide a reliable and a quickly reconfigured interconnection network architecture for linear WSI arrays. The proposed architecture uses a bottom-up approach to reconfigure a linear pipelined array on a potentially defective WSI array using a binary tree interconnection scheme. The binary tree is generated by successive formation of hierarchical modules. For N processing elements (PEs) on the wafer, reconfiguration time is O(log N). The propagation delay is bounded by Θ(log N) and is independent of the number of faulty PEs. Faults in the switching network as well as faulty processing elements are tolerated     

New algorithms for reconfiguring VLSI/WSI arrays

In this paper we present new algorithms for reconfiguring arrays of identical Processing Elements (PEs) in the presence of faults. In particular, we consider a well-studied reconfiguration model which consists of a rectangular array of PEs with spare columns of PEs on one side. In the presence of faulty PEs, reconfiguration is achieved by constructing alogical array using only the healthy non-spare and spare PEs. Note that one can always successfully reconfigure the array as long as the number of faulty PEs is no more than the number of spare PEs. The general objective, however, is to derive a logical array such that the geometric distances betweenlogical neighbors (i.e., PEs that are connected in the reconfigured array) are kept small. This criterion is motivated by the fact that shorter interconnects reduce the communication delays among the PEs, and also lead to less routing hardware. The problem of determining a reconfiguration that minimizes the length of the longest interconnect ishard and several researchers have presented sub-optimal algorithms that seem to have satisfactory performance. In this paper we develop anew efficient algorithm that can reconfigure any array with arbitrary patterns of faulty PEs. Furthermore we show that our algorithm performs better than most of the other algorithms developed for similar models.This work was supported in part by the SDIO/IST U.S. Army Research Office through Contract DAAL03-90-G-0108.     

History Index of Correct Computation for Fault-Tolerant Nano-Computing

Future nanoscale devices are expected to be more fragile and sensitive to external influences than conventional CMOS-based devices. Researchers predict that it will no longer be possible to test a device and then throw it away if it is found to be defective, as every circuit is expected to have multiple hard and soft defects. Fundamentally new fault-tolerant architectures are required to produce reliable systems that will survive with manufacturing defects and transient faults. This paper introduces the History Index of Correct Computation (HICC) as a run-time reconfiguration technique for fault-tolerant nano-computing. This approach identifies reliable blocks on-the-fly by monitoring the correctness of their outputs and forwarding only good results, ignoring the results from unreliable blocks. Simulation results show that history-based TMR modules offer a better response to fault tolerance at the module level than do conventional fault-tolerant approaches when the faults are nonuniformly distributed among redundant units. A correct computation rate of 99% is achieved despite a 13% average injected fault rate, when one of the redundant units and the decision unit are fault-free as well as when both have a low injected fault rate of 0.1%. A correct computation rate of 89% is achieved when faults are nonuniformly distributed at an average fault rate of 11% and fault rate in the decision unit is 0.5%. The robustness of the history-based mechanism is shown to be better than both majority voting and a Hamming detection and correction code.      

Applying Dynamic Reconfiguration for Fault Tolerance in Fine-Grained Logic Arrays

This paper presents the realization of a fault tolerance technique for a dynamically reconfigurable array of programmable cells. The three parts of the technique, fault detection, fault reconfiguration, and fault recovery, are implemented completely in hardware and form a self-contained system. Each of the parts can be exchanged by an alternative implementation without affecting the remaining parts too much, thus making the concept adaptable to different reconfigurable circuits. A hardware realization for the core mechanism is discussed and a prototypical design of a field-programmable gate array implementing the complete system is described. The technological development towards nanoscale feature sizes and the growing influence of deep-submicrometer effects will result in an inherent unreliability of the individual components of future circuit implementations and a higher vulnerability towards external influences. The technique discussed can be used to exploit dynamic reconfiguration capabilities of programmable arrays to alleviate system vulnerability towards these effects and thus to enhance their overall reliability.     

Reconfigurable parallel inner product processor architectures

This paper presents a novel approach for low-power high-performance inner product processor design. The processor is dynamically reconfigurable for computing inner products of input arrays with four or more combinations of array dimensions and precision. The processor mainly consists of an array of 8×8 or 4×4 small multipliers plus two or three arrays of adders. It requires very simple reconfigurable components. The whole network may be reconfigured by using a few control bits for the desired computations, and the reconfiguration can be done dynamically. The design is regular, modular, and can easily be pipelined, and most parts of the network are symmetric and repeatable. A set of low-power high-performance parallel counters is also proposed for the implementation of the design, which could lead to a significant reduction in worst case power dissipation compared with traditional binary-logic based architectures, while showing superiority in speed, VLSI area, and layout simplicity     

Performance evaluation of a reconfiguration-algorithm for memoryarrays containing clustered faults

Reconfiguration of memory arrays using spare rows and columns is useful for yield-enhancement of memories. This paper presents a reconfiguration algorithm (QRCF) for memories that contain clustered faults. QRCF operates in a branch and bound fashion similar to known optimal algorithms that require exponential time. However, QRCF repairs faults in clusters rather than individually. Since many faults are repaired simultaneously, the execution-time of QRCF does not become prohibitive even for large memories containing many faults. The performance of QRCF is evaluated under a probabilistic model for clustered faults in a memory array. For a special case of the fault model, QRCF solves the reconfiguration problem exactly in polynomial time. In the general case, QRCF produces an optimal solution with high probability. The algorithm is also evaluated through simulation. The performance and execution-time of QRCF on arrays containing clustered faults are compared with other approximation algorithms and with an optimal algorithm. The simulation results show that QRCF outperforms previous approximation algorithms by a wide margin and performs nearly as well as the optimal algorithm with an execution-time that is orders of magnitude less