A study was performed to evaluate the relative merits of four methods of reconfiguring a field-programmable gate array (FPGA) in response to detection of a faulty configurable logic block (CLB). As used here, “reconfiguration” signifies replacing the faulty CLB by disconnecting it and connecting, in its stead, a previously unused CLB. This study was a major part of an effort to develop a circuit-reconfiguration system (CRS) that could utilize any of the four methods to implement fault tolerance in the FPGA.

The Basic Rectangular Grid Structure of an FPGA is utilized in the four reconfiguration methods evaluated in this study. Depending on the method, the circuit implemented in the FPGA is moved one row up or down or one column to the right or left.
A typical FPGA (see figure) is an integrated circuit that includes a rectangular array of CLBs surrounded by row and column routing channels. Input/output (I/O) blocks, which include I/O pins for connections to external circuitry, lie along the edges of the FPGA integrated-circuit chip. The routing channels are wire segments of various lengths that connect CLBs to I/O blocks as well as to other CLBs. Switch matrices at the intersections of the routing channels are programmed to make the proper connections to the wire segments. The I/O blocks are also programmable and can be configured to be compatible with various I/O interface standards.

The FPGA includes a configuration memory (not shown in the figure) to store a configuration bit file that determines how the CLBs, switch matrices, and routing channels in the FPGA are used to implement a specific digital circuit — for example, a microprocessor or a digital signal-processing module. Each unique circuit is characterized by a unique bit file. Rearrangement of the bits in the file changes how the CLBs are configured, resulting in a different circuit or a new placement of the same circuit. In effect, a configuration file programs an FPGA. A configuration file can be generated by a design software tool based on schematic diagrams or on a hardware design language. The configuration file consists of configuration data and commands. Configuration data constitute the portion of the configuration file that defines the state of the programmable logic elements in the FPGA. Configuration commands specify how to use the configuration data. Once created, a configuration file is loaded into the configuration memory via a configuration port.

The basic idea of the developmental CRS is to use any of four methods of row or column replacement — row up, row down, column left, or column right: Upon notification of a fault, the circuit is reconfigured to move it one row up or down or one column to the left or right. After reconfiguration, proper operation of the circuit is verified. Implementation of the CRS includes modification of the configuration file to provide for a row-wise or column-wise replacement. The modified bit file is stored in memory until needed by the CRS. Once a fault is detected, the CRS is notified and the reconfiguration process begins. The modified bit file causes the FPGA to reconfigure itself according to the chosen row or column replacement method.

For the purpose of the study, it was assumed that faults in an FPGA could be detected by an unspecified external system and that the locations of faults could be known. The study included experiments in which the CRS was implemented for a commercially available FPGA and the FPGA was made to reconfigure itself in response to synthetic fault indications generated according to a statistically rigorous test plan. For the purpose of evaluating the relative merit of each chosen method invoked in response to fault indication, the reconfiguration time was measured from the moment of indication of a fault until reconfiguration was complete.

Analysis of the measurement data led to the conclusion that none of the methods is consistently better than any of the other three methods, regardless of the circuit congestion or location within the FPGA. That is, given a specific location of a fault in the FPGA, none of these methods is guaranteed to effect reconfiguration in the least time. Therefore, it was further concluded, that for a fault-tolerant system using reconfiguration of an FPGA, a CRS algorithm could best be formulated to use whatever replacement method is available or makes best use of available FPGA resources, without regard to circuit congestion or the direction of row or column movement.

This work was done by Jason L. Ives of the Air Force Institute of Technology. AFRL-0095

This Brief includes a Technical Support Package (TSP).
Evaluation of Four Methods of Reconfiguring an FPGA

(reference AFRL-0095) is currently available for download from the TSP library.

Don't have an account? Sign up here.

Defense Tech Briefs Magazine

This article first appeared in the April, 2009 issue of Defense Tech Briefs Magazine.

Read more articles from this issue here.

Read more articles from the archives here.