Online BIST and BIST-based diagnosis of FPGA logic blocks

We present the first online built-in self-test (BIST) and BIST-based diagnosis of programmable logic resources in field-programmable gate arrays (FPGAs). These techniques were implemented and used in a roving self-testing areas (STARs) approach to testing and reconfiguration of FPGAs for fault-tolerant applications. The BIST approach provides complete testing of the programmable logic blocks (PLBs) in the FPGA during normal system operation. The BIST-based diagnosis can identify any group of faulty PLBs, then applies additional diagnostic configurations to identify the faulty look-up table or flip-flop within a faulty PLB. The ability to locate defective modules inside a PLB enables a new form of fault-tolerance that reuses partially defective PLBs in their fault-free modes of operation.     

Fault Tolerance of Switch Blocks and Switch Block Arrays in FPGA

A new application-independent approach for evaluating the fault tolerance of field-programmable gate-array (FPGA) interconnect structures is presented. Signal routing in the presence of faulty resources at switch block and FPGA levels is analyzed; this problem is directly related to the fault tolerance of FPGA interconnects for testing and reconfiguration at manufacturing and run-time applications. Two criteria are proposed and used as figure-of-merit for evaluating different FPGA interconnect architectures. The proposed approach is based on the number of available paths between pairs of end points and the probability to establish a one-to-one mapping between all input and output end points. A probabilistic approach is also presented to evaluate the fault-tolerant routing of the entire FPGA by connecting switch blocks in chains, as required for testing and to account for the input–output (I/O) pin restrictions of an FPGA chip. All possible interconnect faults for programmable switches and wiring channels are considered in the fault model. The proposed method is applicable to arbitrary switch block structures. Experimental results on commercial as well as academic designed FPGAs are presented and analyzed.     

A Fault Tolerant Technique for FPGAs

In this paper we present a fault tolerant (FT) technique for field programmable gate arrays (FPGAs) that is based on incrementally reconfiguring circuits and applications that have been previously placed and routed. Our technique targets both logic faults and interconnect faults, and our algorithms can be applied to either static or run-time reconfigurable FPGAs. The algorithm for reconfiguring designs in the presence of logic faults uses a matching technique. The matching technique requires no preplaced, spare logic resources and is capable of handling groups of faults. Experimental results indicate there is little or no impact on circuit performance for low numbers of reconfigured logic blocks. For interconnect faults, we present a rip-up and reroute strategy. Our strategy is based on reading back the FPGA configuration memory, so no netlist is required for rerouting around faulty resources. Experimental results indicate high incremental routability for low numbers of interconnect faults. We also lay the foundation for applying our approach to yield enhancement.     

A Fault Tolerant Approach for FPGA Embedded Processors Based on Runtime Partial Reconfiguration

The ever increasing adoption of field programmable devices in various application domains for building complex embedded systems based on FPGA processors along with the reliability issues having emerged for FPGA devices built with the latest nanometer technologies, have raised the need for new fault tolerant techniques in order to improve dependability and extend system lifetime. In addition, the runtime partial reconfiguration technology highly mature in the modern FPGA families along with the availability of unused programmable resources in most FPGA designs provide new and interesting opportunities to build advanced fault tolerance mechanisms. In this paper, we exploit the dynamic reconfiguration potential of today’s FPGA architectures and the advances in the related design support tools and we propose a fault-tolerant approach for FPGA embedded processors based on runtime partial reconfiguration. According to the proposed methodology, the processor core is partitioned into reconfigurable modules and each module is duplicated to implement a concurrent error detection mechanism. Precompiled configurations containing spare resources are generated for each duplicated module and are used to repair at runtime the defective modules. Also, a fault tolerance scheme for the proxy logic of the reconfigurable modules, which cannot move in the alternative configurations along with the rest logic, is proposed. Moreover, a compression method for the alternative partial bitstreams, which significantly reduces the high storage space requirements of the proposed approach, is presented. Two different hardware decompression schemes have been implemented in a Virtex-5 device and compared in terms of area overhead and decompression latency. Furthermore, a thorough examination has been performed, regarding how the percentage of the spare resources and their allocation in the reconfigurable regions affect the compression efficiency and the processor performance. Finally, the proposed approach has been demonstrated in three different components – ALU, multiplier-accumulator, and instruction-fetch unit – of an open-source embedded processor.     

A Region-based Fault-Tolerant Routing Algorithmfor 2D Irregular Mesh Network-on-Chip

This paper presents a deadlock-free fault-tolerant routing algorithm for irregular mesh network-on-chips based on a region-based approach. In this approach, a set of rectangular faulty regions called faulty blocks is formed for faulty nodes and a detour path is defined for each faulty block to indicate how packets must detour thefaulty block. The most recent routing algorithm on this approach is Message-Route (Holsmark and Kumar J Inf Sci Eng 23:1649–1662, 2007) which does not have restrictions on the number of tolerable faulty nodes and its distribution. However, this algorithm has three crucial problems; (1) this algorithm fails to provide complete and deadlock-free routing, (2) many nonfaulty nodes are contained in faulty blocks and thus deactivated, and (3) complex routing functions are not feasible for hardware implementation. In this paper, we give a solution for each of the above three problems. We correct the errors of Message-Route to make it complete and deadlock-free. Then, we propose a deadlock-free fault-tolerant routing algorithm which can work under small-sized faulty blocks with a simple routing control. Experimental results show that the proposed algorithm significantly reduces the size of faulty blocks and improves communication latency for both random and cluster faults. Moreover, an FPGA implementation of the proposed algorithm is also discussed.     

BIST-based test and diagnosis of FPGA logic blocks

We present a built-in self-test (BIST) approach able to detect and accurately diagnose all single and practically all multiple faulty programmable logic blocks (PLBs) in field programmable gate arrays (FPGAs) with maximum diagnostic resolution. Unlike conventional BIST, FPGA BIST does not involve any area overhead or performance degradation. We also identify and solve the problem of testing configuration multiplexers that was either ignored or incorrectly solved in most previous work. We introduce the first diagnosis method for multiple faulty PLBs; for any faulty PLB, we also identify its internal faulty modules or modes of operation. Our accurate diagnosis provides the basis for both failure analysis used for yield improvement and for any repair strategy used for fault-tolerance in reconfigurable systems. We present experimental results showing detection and identification of faulty PLBs in actual defective FPGAs. Our BIST architecture is easily scalable     

A HW/SW Co-Verification Technique for FPGA Test

Field programmable gate arrays （FPGAs） have wide and extensive applications in many areas. Due to programmable feature of FPGAs, faults of FPGAs can be easily tolerated if fault sites can be located. A hardware/software （HW/SW） co-verification technique for FPGA test is proposed in this paper. Taking advantage of flexibility and observability of software in conjunction with high-speed simulation of hardware, this technique is capable of testing each input/output block （IOB） and configurable logic block （CLB） of FPGA automatically, exhaustively and repeatedly. Fault cells of FPGA can be positioned automatically by the proposed approach. As a result, test efficiency and reliability can be enhanced without manual work.     

NEW APPROACH TO EMULATE SEU FAULTS ON SRAM BASED FPGAS简

Field Programmable Gate Arrays （FPGAs） offer high capability in implementing of com- plex systems, and currently are an attractive solution for space system electronics. However, FPGAs are susceptible to radiation induced Single-Event Upsets （SEUs）. To insure reliable operation of FPGA based systems in a harsh radiation environment, various SEU mitigation techniques have been provided In this paper we propose a system based on dynamic partial reconfiguration capability of the modern devices to evaluate the SEU fault effect in FPGA. The proposed approach combines the fault injection controller with the host FPGA, and therefore the hardware complexity is minimized. All of the SEU injection and evaluation requirements are performed by a soft-core which realized inside the host FPGA Experimental results on some standard benchmark circuits reveal that the proposed system is able to speed up the fault injection campaign 50 times in compared to conventional method.     

Detecting, diagnosing, and tolerating faults in SRAM-based field programmable gate arrays: a survey

Topics related to the faults in SRAM-based field programmable gate arrays (FPGAs) have been intensively studied in recent research studies. These topics include FPGA fault detection, FPGA fault diagnosis, FPGA defect tolerance, and FPGA fault tolerance. This paper provides a guided tour to the approaches related to these topics. These include techniques, which are applied to the FPGA and others which have been recently introduced and can be applied to today's FPGAs.     

Analysis and Evaluations of Reliability of Reconfigurable FPGAs

Many techniques have been proposed in the technical literature for repairing FPGAs when affected by permanent faults. Almost all of these works exploit the dynamic reconfiguration capabilities of an FPGA where a subset of the available resources is used as spares for replacing the faulty ones. The choice of the best reconfiguration technique depends on both the required reliability and on the architecture of the chosen FPGA . This paper presents a survey of these techniques and explains how the architectural organization of the FPGA affects the choice of a reconfiguration strategy. Subsequently, a framework is proposed for these techniques by which a fair comparison among them can be assessed and evaluated with respect to reliability. A reliability evaluation is provided for different repair strategies. To provide a comparison between these techniques FPGAs of different size are taken into account. Also the relationship between the area overhead and the overall reliability has been investigated. Considerations about time to repair and feasibility of these techniques are provided. The ultimate goal of this paper is therefore to present a state-of-the-art repair techniques as applicable to FPGA and to establish their performance for reliability.     

Enhanced FPGA reliability through efficient run-time faultreconfiguration

The expanded use of field programmable gate arrays (FPGA) in remote, long life, and system-critical applications requires the development and implementation of effective, efficient FPGA fault-tolerance techniques. FPGA have inherent redundancy and in-the-field reconfiguration capabilities, thus providing alternatives to standard integrated circuit redundancy-based fault-recovery techniques. Runtime reliability can be enhanced by using such unique features. Recovery from permanent logic and interconnect faults without runtime computer-aided design (CAD) support can be efficiently performed with the use of fine-grained and physical design partitioning. Faults are localized to small partitioned blocks that have fixed interfaces to the surrounding portions of the design, and the affected blocks are reconfigured with previously generated, functionally equivalent block instances that do not use the faulty resources. This technique minimizes the post-fault-detection system downtime, while requiring little area overhead. Only the finely located faulty portions of the FPGA are removed from use. In addition, the end user need not have access to CAD tools, making the algorithm completely transparent to system users. This approach has been efficiently implemented on a diverse set of FPGA architectures. The algorithm's flexibility is also apparent from the variable emphases that can be placed on system reliability, area overhead, timing overhead, design effort, and system memory. Given user-defined emphases, the algorithm can be modified to specific application requirements. Experiments using random s-independent and s-correlated fault models reveal that the approach enhances system reliability, while minimizing area and timing overhead     

Recovery Time and Fault Tolerance Improvement for Circuits mapped on SRAM-based FPGAs

The rapid adoption of FPGA-based systems in space and avionics demands dependability rules from the design to the layout phases to protect against radiation effects. Triple Modular Redundancy is a widely used fault tolerance methodology to protect circuits against radiation-induced Single Event Upsets implemented on SRAM-based FPGAs. The accumulation of SEUs in the configuration memory can cause the TMR replicas to fail, requiring a periodic write-back of the configuration bit-stream. The associated system downtime due to scrubbing and the probability of simultaneous failures of two TMR domains are increasing with growing device densities. We propose a methodology to reduce the recovery time of TMR circuits with increased resilience to Cross-Domain Errors. Our methodology consists of an automated tool-flow for fine-grain error detection, error flags convergence and non-overlapping domain placement. The fine-grain error detection logic identifies the faulty domain using gate-level functions while the error flag convergence logic reduces the overwhelming number of flag signals. The non-overlapping placement enables selective domain reconfiguration and greatly reduces the number of Cross-Domain Errors. Our results demonstrate an evident reduction of the recovery time due to fast error detection time and selective partial reconfiguration of faulty domains. Moreover, the methodology drastically reduces Cross-Domain Errors in Look-Up Tables and routing resources. The improvements in recovery time and fault tolerance are achieved at an area overhead of a single LUT per majority voter in TMR circuits.     

Dependability evaluation of Altera FPGA-based embedded systems subjected to SEUs

Dependability evaluation of embedded systems due to the integration of hardware and software parts is difficult to analyze. In this paper, we have proposed an experimental method to determine sensitivity to soft errors in an embedded system exploiting Altera SRAM-based FPGAs. The evaluation is performed using both the hardware and software parts of the embedded system in a single framework. To do this, the HDL hardware model of the target system as well as the C-written software codes of the target system, are required. Both permanent and transient faults are injected into the partially- or fully-synthesizable hardware of the target system and this can be performed during the design cycle of the system. The fault injection is composed of injecting SEUs into user design memory, and used configuration memory of the exploited FPGA. Using the experimental results, the sensitivity of Altera FPGAs to SEU faults are analyzed and derived. The analytical results reveal that the configuration memory is more significant than design memory to the SEUs due to the relative number of SRAM bits. Moreover, in this framework, in the case of injecting SEUs into user memory, the fault injection experiments are accelerated by the cooperation between a simulator and the FPGA.     

On constructing the minimum orthogonal convex polygon for the fault-tolerant routing in 2-D faulty meshes

The rectangular faulty block model is the most commonly used fault model for designing fault-tolerant, and deadlock-free routing algorithms in mesh-connected multicomputers. The convexity of a rectangle facilitates simple, efficient ways to route messages around fault regions using relatively few or no virtual channels to avoid deadlock. However, such a faulty block may include many nonfaulty nodes which are disabled, i.e., they are not involved in the routing process. Therefore, it is important to define a fault region that is convex, and at the same time, to include a minimum number of nonfaulty nodes. In this paper, we propose an optimal solution that can quickly construct a set of minimum faulty polygons, called orthogonal convex polygons, from a given set of faulty blocks in a 2-D mesh (or 2-D torus). The formation of orthogonal convex polygons is implemented using either a centralized, or distributed solution. Both solutions are based on the formation of faulty components, each of which consists of adjacent faulty nodes only, followed by the addition of a minimum number of nonfaulty nodes to make each component a convex polygon. Extensive simulation has been done to determine the number of nonfaulty nodes included in the polygon, and the result obtained is compared with the best existing known result. Results show that the proposed approach can not only find a set of minimum faulty polygons, but also does so quickly in terms of the number of rounds in the distributed solution.     

Configuration relocation and defragmentation for run-time reconfigurable computing

Due to its potential to greatly accelerate a wide variety of applications, reconfigurable computing has become a subject of a great deal of research. By mapping the compute-intensive sections of an application to reconfigurable hardware, custom computing systems exhibit significant speedups over traditional microprocessors. However, this potential acceleration is limited by the requirement that the speedups provided must outweigh the considerable cost of reconfiguration. The ability to relocate and defragment configurations on field programmable gate arrays (FPGAs) can dramatically decrease the overall reconfiguration overhead incurred by the use of the reconfigurable hardware. We therefore present hardware solutions to provide relocation and defragmentation support with a negligible area increase over a generic partially reconfigurable FPGA, as well as software algorithms for controlling this hardware. This results in factors of 8 to 12 improvement in the configuration overheads displayed by traditional serially programmed FPGAs.     

New techniques for efficiently assessing reliability of SOCs

In this paper we propose an approach to speed-up Fault Injection campaigns for the evaluation of dependability properties of complex digital systems. The approach exploits FPGA devices for system emulation, and new techniques are described, allowing emulating the effects of faults and to observe faulty behavior. Thanks to its flexibility and efficiency, the approach is suitable to be applied to SOC devices. The paper points out the flexibility of the approach, able to inject different faults of different types in custom logic, memory blocks, and processor cores. The proposed approach combines the speed of hardware-based techniques, and the flexibility of simulation-based techniques. Experimental results are provided showing that speed-up figures of up to 3 orders of magnitude with respect to state-of-the-art simulation-based techniques can be achieved.     

Fault isolation for nonisolated blocks

We consider circuits represented as interconnections of logic blocks. In such circuits, the goal of fault isolation is to identify which one of the blocks is faulty based on a faulty output response produced by the circuit. We study this issue and demonstrate that perfect or close-to-perfect fault isolation is possible with tests that propagate fault effects through pairs of blocks. We relate this phenomenon to the numbers of fault effects observed on the circuit outputs for faults in different blocks. For cases where fault isolation is not perfect, we insert observation points to ensure perfect fault isolation. We also study the number of tests required to achieve perfect fault isolation. The study is performed for single stuck-at faults in combinational (or full scan) blocks.     

Board-level built-in self-repair method of RAM

This paper describes the method of built-in self-repairing of RAM on board, designs hardware circuit, and logic for the RAM’s faults self-repairing system based on FPGA. The key technology is that it utilizes FPGA to test RAM according to some algorithm to find out failure memory units and replace the faulty units with FPGA. Then it can build a memory that has no fault concern to external controller, and realizes the logic binding between external controller and RAM. Micro Controller Unit (MCU) can operate external RAM correctly even if RAM has some fault address units. Conventional MCS-51 is used to simulate the operation of MCU operating external memory. Simulation shows FPGA can complete the faulty address units’ mapping and MCU can normally read and write external RAM. This design realizes the RAM’s built-in self-repairing on board.