1024 IEEE TRANSACTIONS ON VERY LARGE SCALE INTEGRATION (VLSI) SYSTEMS, VOL. 14, NO.

9, SEPTEMBER 2006

Application-Dependent Testing of FPGAs

Mehdi Tahoori, Member, IEEE

Abstract—Testing techniques for interconnect and logic re- finalized and fixed, the programmability becomes useless and
sources of an arbitrary design implemented into a field-pro- costly if further changes in the design during lifetime operation
grammable gate array (FPGA) are presented. The target fault of the system are not required.1 This is why FPGAs are very
list includes all stuck-at, open, and pair-wise bridging faults in
the mapped design. For interconnect testing, only the config- costly for high volume fixed designs compared to ASICs. FPGA
uration of the used logic blocks is changed, and the structure defect tolerance is based on the fact that some FPGA chips that
of the design remains unchanged. For logic block testing, the do not pass the application-independent test may be still usable
configuration of used logic resources remains unchanged, while for some particular fixed designs. In this case, defects are lo-
the interconnect configuration and unused logic resources are cated in some areas of the chip not used by those designs. These
modified. Logic testing is performed in only one test configuration
whereas interconnect testing is done in a logarithmic number of
FPGAs, which are good only for particular designs and do not
test configurations. This approach is able to achieve 100% fault have the general programmability of typical FPGAs, are called
coverage. application-specific FPGAs (ASFPGAs). ASFPGAs are prof-
Index Terms—Field-programmable gate array (FPGA), testing. itable for relatively large volume designs which have been com-
pletely finalized, i.e., when the final placed and routed version
is fixed. In order to achieve a high degree of reliability, this type
I. INTRODUCTION of test must achieve a very high defect coverage. So, the target
RAM-BASED field programmable gate arrays (FPGAs) are fault list must be as comprehensive as possible.
S 2-D arrays of logic blocks and programmable switch ma-
trices, surrounded by programmable input/output (I/O) blocks
Moreover, the application-dependent testing of FPGAs plays
a major role in adaptive fault tolerant based on self-repair
on the periphery. FPGAs are widely used in many applications [12]. During system operation, periodic application-dependent
such as networking, storage systems, communication, and adap- testing is performed to identify defective system components
tive computing, due to their reprogrammability, and reduced (permanent faults). High-resolution diagnosis is then exploited
time-to-market compared to full-custom designs. to precisely locate the defective resources so that efficient repair
Unlike other design styles such as application-specific inte- can be performed. Finally, the design is remapped to bypass the
grated circuits (ASICs) or microprocessor-based designs, testa- defective components. For this purpose, test time is very crucial
bility issues are not explicitly considered in the FPGA-based de- since it directly affects the down time of the system. Therefore,
sign flow. This means that the FPGA users rely on the manufac- the total number of test configurations, which dominates the
turing test of FPGAs completely. There is no internal scan inser- test time, must be minimized.
tion phase, built-in self-test (BIST) circuitry implementation, or In this paper, we present a comprehensive application-depen-
test generation in typical FPGA-based design flow. Hence, the dent testing of FPGAs for both logic and interconnect resources,
designs mapped into the FPGAs may not be fully testable. in which test vectors and configurations are automatically gen-
There are two main trends in the testing of FPGAs, appli- erated. The test is performed in two different sets of test configu-
cation-independent (manufacturing) test and application-de- rations. The first set of test configurations targets the faults in the
pendent test. In application-independent testing, which is used global interconnect whereas testing of faults in the logic blocks
as the manufacturing (production) test of these devices, all and local interconnects is performed in the second set of test
resources in the FPGA chip are tested. This test is independent configurations. For interconnect testing, the logic blocks of the
of the particular application (design) to be mapped to the FPGA FPGA used by the mapped design are reprogrammed, and the
chip. In application-dependent testing, however, the correct configuration of the interconnect remains unchanged. Hence, no
functionality of the particular application mapped into the chip extra placement and routing are necessary for test configuration
is of interest. In this test, only the FPGA resources used in the generation. The fault list includes all pairwise bridging faults, all
mapping of that design are tested. multiple stuck-at, and open faults. For logic testing (including
FPGA application-dependent testing can be used for system- local interconnects), the configurations of used logic blocks re-
level testing. It has also been used for defect tolerance in order to main unchanged while the configurations of global interconnect
improve the manufacturing yield [37]. The reprogrammability resources and unused logic blocks are modified. An exhaustive
of FPGAs results in much faster design and debug cycle com- test set which is able to cover all functional faults in logic blocks,
pared to ASIC implementation. However, once the design is inclusive of all stuck-at faults, is applied during this phase.
The rest of this paper is organized as follows. In Section II,
a review of FPGA architecture along with the previous work
Manuscript received December 12, 2005; revised April 28, 2006 and May 9,
2006. in FPGA testing is presented. In Section III, the interconnect
The author is with the Department of Electrical and Computer Engineering, 1Note that in some applications for various reasons such as changes in proto-
Northeastern University, Boston, MA 02115 USA (e-mail: mtahoori@ece.neu.
cols, fault tolerance, and temporal adaptive computing, the ability to reconfigure
edu).
the FPGA is an important feature during lifetime operation of these systems.
Digital Object Identifier 10.1109/TVLSI.2006.884053

1063-8210/$20.00 © 2006 IEEE

TAHOORI: APPLICATION-DEPENDENT TESTING OF FPGAS 1025

testing approach is presented. In Section IV, the logic testing complexity of configuration generation algorithm, it cannot be
technique is presented. Some discussion regarding the presented applied to large designs.
application-dependent testing method is presented in Section V. In our earlier publication, we presented a technique for ap-
Finally, Section VI concludes the paper. plication-dependent interconnect testing where we first intro-
duced the notion of single-term function in FPGA testing [33],
II. BACKGROUND AND PREVIOUS WORK as will be redefined and explained in Section III-A. In [31],
testing of stuck-at faults in the interconnects and logic blocks
A. Preliminaries was presented in which two test configurations for interconnect
A FPGA is a 2-D array of configurable logic blocks (CLBs) stuck-at fault testing and one test configuration for CLB stuck-at
and on-chip memory blocks within a programmable inter- fault testing were used. Since the defects in the interconnects
connection network with programmable I/O blocks on the do not manifest themselves only as stuck-at faults, open and
periphery. The FPGA is a suitable platform for implementation bridging faults must be explicitly considered in interconnect
of almost any digital design. In reprogrammable FPGAs, such testing. Testing of local bridging faults in designs mapped into
as SRAM-based FPGAs, many designs can be mapped into FPGAs was presented in [32]. An approach based on Boolean
the same silicon over the lifetime of the FPGA. These FPGAs satisfiability was used for test configuration generation. How-
use memory cells to store the functional configuration, distin- ever, the fault list was limited to bridges between adjacent wires
guishing FPGAs from other integrated circuits (ICs). at the inputs of each LUT.
CLBs consist of look-up tables (LUTs), programmable In this paper, we present an application-dependent testing ap-
sequential elements, and additional logic for speeding up the proach for all resources of the FPGA including local and global
implementation of arithmetic functions. Typically, the re- interconnects as well as the logic resources. In this paper, un-
sources within each CLB are divided into a number of identical like the previous work, a comprehensive fault list including all
logic slices. Interconnection between these logic blocks are possible bridging faults, open, stuck-at, and functional faults is
provided by the interconnection network (inter-CLB or global targeted.
interconnects). Inter-CLB resources include programmable Application-dependent diagnosis (fault localization) is also
switch blocks, buffers, and wiring channels connecting switch very crucial to many domains in which application-dependent
blocks and CLBs. The interconnect resources inside CLBs are testing is used. For instance, in adaptive reliable computing
called intra-CLB (local) interconnects. Intra-CLB interconnects based on online self-repair, the existence of faults in the
include programmable multiplexers and wires inside CLBs. system is first identified (application-dependent test) and faulty
In this paper, the terms “CLB” and “logic block” are used resources are precisely diagnosed afterwards (application-de-
interchangeably. pendent diagnosis). Then, the design is remapped to avoid
There are two basic FPGA architectures. In the segmented faulty resources.
routing scheme, the interconnection network consists of a 2-D
array of identical switch matrices, and an abundance of line seg- C. Fault Models
ments, with a variety of length, size, and speed [36]. Switch ma- For FPGA interconnect testing we consider stuck-at faults,
trices, which consist of programmable switches, provide selec- opens and shorts. An open fault can be a programmable switch
tive and configurable connectivity among the line segments. In stuck-open or an open on a line segment. A programmable
the multiplexer-based architectures, the programmable switches switch stuck-open fault causes the switch to be permanently
are replaced by programmable multiplexers that provide a more open regardless of the value of the SRAM cell controlling it.
deterministic routing structure [3]. In order to provide fast in- A short fault can be a switch stuck-closed or a bridging fault
terconnection, the majority of line segments and programmable between two routing resources. A switch stuck-closed fault
switches and/or multiplexers are buffered. In both cases, the causes the switch to be permanently closed regardless of the
number of programmable elements in the interconnection net- value of memory cell controlling that switch. For bridging
work is far more than the number of programmable elements in faults, wired bridging fault models (wired-OR and wired-AND)
the logic blocks. as well as dominant bridging faults are considered [4], [27].
For FPGA logic testing, mainly stuck-at faults are consid-
B. Previous Work ered. However in this paper, functional fault model is consid-
Application-independent (manufacturing) testing of FPGAs ered which is super-set of stuck-at faults and contains any faulty
has been described in [1], [7], [13], [26], [28], [30], and [34]. behavior that changes the functionality of the logic function im-
These techniques target the faults in the entire FPGA for all pos- plemented in the logic resources.
sible configurations. Application-dependent testing of FPGAs
has been addressed in [5], [16], [17], [24], and [25]. III. INTERCONNECT TESTING
A new FPGA architecture with design for testability features The interconnect resources in FPGAs can be categorized
is presented in [25]. In the technique presented in [5], every CLB as inter-CLB and intra-CLB resources. Inter-CLB routing
used in the mapped design is reconfigured as transparent logic resources provide interconnections among CLBs whereas
followed by flip-flops in order to construct scan chains. Also, intra-CLB resources are located inside each CLB. Detecting
fanout branches of a net are tested in different test configura- faults within inter-CLB routing resources is addressed in this
tions, i.e., dependent logic cones are tested in different config- section. For inter-CLB interconnect test, the configuration of
uration, resulting in a number of test configurations. Due to the routing resources remains unchanged while the configuration
1026 IEEE TRANSACTIONS ON VERY LARGE SCALE INTEGRATION (VLSI) SYSTEMS, VOL. 14, NO. 9, SEPTEMBER 2006

Theorem 1: For a single-term function , if the applied

input vector is the activating input , all sensitized stuck-at and
bridging faults are detected.
Proof: Consider a fault (stuck-at or bridging fault) such
that it is sensitized. This means that if is a stuck-at fault ,
is set to by applying , and if is a bridging fault ,
, and are set to different values. In order to detect , it is only
sufficient to propagate the fault to the output. Since the fault
Fig. 1. Single-term function with activating input pattern. is already sensitized, the fault term, the term corresponding to
the faulty inputs , is different from the original term , i.e.,
. Because the original term is the activating term and
of logic resources is modified. Testing of intra-CLB intercon- the value of the fault term is different from the value of the
nects along with logic resources are discussed in Section IV. original term , as is a single-term. Hence,
For this purpose, the configuration of used logic resources the fault-free output is different from the faulty output and the
(inclusive of intra-CLB interconnects) is kept unchanged while fault is detected.
the configuration of inter-CLB interconnects as well as unused The interesting testing property of single-term functions
logic resources are changed. holds for any combinational network of single-term functions,
The separation between inter-CLB and intra-CLB is made as expressed by the following theorem.
because in contemporary FPGAs the programmable logic re- Theorem 2: Consider a network of single-term functions ,
sources are not limited to LUTs; other logic resources such and the input pattern , such that the values of the inputs of
as carry generation/propagation logic and cascade chains are every function form the activating input of that function. Then,
included in CLBs. For inter-CLB interconnect testing, these all the sensitized faults are detected. In other words, for every
logic elements, if used in the original configuration, will be by- net with value , stuck-at is detected, and for each pair
passed. Therefore, no fault masking (causing undetected faults) of nets, and , with , the bridging fault between
can occur due to existence of this circuitry in the interconnect and is detected.
test mode. Proof: In order to detect the fault, the fault effect must be
More than 80% of the transistors in an FPGA are used in the propagated from the fault site to the primary outputs. The proof
interconnect network. Also, more than eight metal layers are ex- is based on an induction on the number of functions on the fault
ploited for the wiring channels in the interconnection network propagation path from the fault site to the primary outputs. The
[6], [35]. Hence, the majority of the defects in an FPGA chip are basis of the induction, only one function in the fault propagation
located in the interconnection network. These defects manifest path, is expressed in Theorem 1, and therefore, is proven. Con-
themselves as open and short (bridging) faults. Note that short sider a fault propagation path with 1 functions. Based
to the power rails in the interconnects are considered as conven- on Theorem 1, the fault effect at the input of the first function
tional stuck-at faults. on this path will be propagated to its output since the values ap-
pearing at the inputs of this function form its activating input.
A. Testability of Single-Term Functions The fault effect appearing at the output of the first function along
A single-term function is a logic function which has only one the path behaves as a stuck-at fault at the corresponding input
minterm or only one maxterm. In other words, the value of only of the second function along the path (the one connected to the
one term in the truth table is different from the value of all other output of the first function). Now, the situation is a fault prop-
terms. The general form of a single-term function is a logic AND agation path of 1 functions with a stuck-at fault at the fault
or a logic OR function with possibly some inversions at the in- site. Based on the induction hypothesis, the fault effect will ap-
puts and/or the output. The input combination corresponding to pear at the primary outputs.
this specific minterm (or maxterm) is called the activating input. Fig. 2 shows an example of a network of single-term functions
For a single-term function, if the applied input vector is the ac- with test vector 100011. This test vector results in activating in-
tivating input, all sensitized faults are detected. A fault is sensi- puts at the inputs of all single-term functions in this logic net-
tized if the values of the signals at the fault site are different from work. All sensitized faults, i.e., stuck-at- for all the nets with
faulty values. An example of a single-term function is shown in value and bridging faults for all pairs with opposite values,
Fig. 1, which is an OR function with inversions at the second are detected.
and fourth inputs. This function has only one maxterm. Since Note that the sensitized faults (stuck-at and bridging) are to-
the activating input (0101) is applied, ( stuck-at-1 fault), tally dependent on the particular single-term function and the
, , , and are detected. Moreover, the bridging corresponding activating input vector. For example in the ex-
faults between and , , , and ample of Fig. 1, or are not sensitized and will not
are also detected. If this function is implemented in a LUT, the be detected by the activating input vector. For a given fault list
above mentioned faults in the inputs and output of that LUT will for the pin faults (e.g., inputs and output of a LUT), different
be detected. single-term functions must be implemented to cover all faults.
The following theorem generalizes the previous example and This issue is addressed in Section III-B in details.
expresses the conditions for detectability of faults in single-term Corollary 1: If the conditions of Theorem 2 hold, the fault
functions. effect will appear on all reachable primary outputs.
TAHOORI: APPLICATION-DEPENDENT TESTING OF FPGAS 1027

Fig. 3. Sequential logic network of single-term functions.

Fig. 2. Logic network of single-term functions.

Proof: Consider the logic cone(s) originating from the fault

site(s) towards the primary outputs. Based on Theorem 1 and 2,
for any function in the fault cone that the fault effect appears
at its input, the fault effect will be propagated to its output as
well. Therefore, the fault effect will be propagated to all primary
outputs that are structurally reachable from the original fault
site. Fig. 4. Sequential network of single-term functions with feedbacks.
Corollary 2: If the conditions of Theorem 2 hold, all possible
combinations of multiple faults which are sensitized will be de-
tected. binational circuit satisfying those conditions. Therefore, based
Proof: Based on Theorem 1 and 2, the fault effect ap- on Theorem 2, all sensitized faults will be propagated to the
pearing at the input of any function will be propagated to primary outputs and/or captured in bistable(s) by the first appli-
its output. In other words, no fault masking occurs in such cation of the clock pulse. Any fault captured in a bistable be-
logic network with the given conditions for the primary input haves as a stuck-at fault at the data output of that bistable in
vector. Therefore, the fault effects corresponding to multiple the next clock cycle. This fault will be captured in the next rank
faults (e.g., multiple stuck-at faults, multiple bridging faults, of bistables or will be propagated to the primary outputs in the
combination of stuck-at and bridging faults) will be propagated next clock cycle. Therefore, in order to propagate the fault ef-
in the fault cones corresponding to each fault and appear at the fect captured in the first rank of the bistables in the first clock
reachable primary outputs. cycle, at most clock cycles are required to propagate this fault
Similar testability properties exist in sequential networks of effect, level by level, to the primary outputs, where is equal to
single-term functions. However, the initial state of the circuit, the maximum number of bistables from any path from primary
which is set by the primary input vector and the present value of inputs to the primary outputs (maximum sequential depth).
bistables (data flip-flop or latches) must satisfy the conditions of An example of a sequential circuit with single-term functions
Theorem 2. Moreover, the same input vector must be applied to which satisfies all these conditions is shown in Fig. 3. The preset
the circuit for a number of clock cycles to ensure that the fault values of the flip-flops are also shown. Here, two test clock cy-
effect captured in any bistable will be propagated to the primary cles must be applied and the test vector (1101) must remain un-
outputs. The number of these test clock cycles depends on the changed during these two clock cycles.
maximum sequential depth of the network, which is the number Note that the same fault detection properties hold for a se-
of bistables along the longest path from any primary input to quential network of single-term functions with feedbacks. As
any reachable primary output. The following lemma formally an example, consider a sequential network of single-term func-
expresses these conditions for a sequential network. tions with feedbacks shown in Fig. 4. In this example, , ,
Lemma 1: Consider a sequential network consisting of only , , and are followed by flip-flops in their corresponding
single-term combinational functions and data flip-flops (D-FF) logic blocks. The preset value of FF2, FF4, and FF9 should be
or latches. If the primary input vector and the preset values of the set to 1, while the preset value of FF5 and FF7 must be set to 0.
latches (or flip-flops) are set such that the value appearing at the The required number of test clock cycles is four, as the longest
inputs of each single-term function form its activating input, all path of the circuit is through L2, L3, L7, L4, and L8, where L8
the sensitized faults will be detected provided the same primary is not sequential and, hence, the maximum sequential depth is
input vector is kept unchanged for clock cycles, where is four.
equal to the sequential depth of this circuit.
Proof: Since the initial state of the bistables are set such B. Test Configuration Generation
that to satisfy the conditions of the Theorem 2, the behavior of As explained in Section III-A, single-term functions guar-
this circuit in the first clock cycle is exactly similar to a com- antee the detection of all sensitized faults if the appropriate pri-
1028 IEEE TRANSACTIONS ON VERY LARGE SCALE INTEGRATION (VLSI) SYSTEMS, VOL. 14, NO. 9, SEPTEMBER 2006

Fig. 5. Logarithmic test set to activate all possible bridging, open, and stuck-at
faults for six wires.

mary input vector is applied. In order to detect all faults in the

fault list, faults must be sensitized using a set of single-term
functions and test vectors. These single-term functions are im- Fig. 6. Algorithm 1: Test vector and configuration generation algorithm.
plemented in all LUTs used in the user design. The single-term
functions implemented in the user LUTs correspond to a test
configuration which detect the interconnect faults sensitized in function, based on its activating input value and the value of its
that test configuration. The objective is to come up with a min- output net, the particular single-term function can be identified.
imum number of test configurations such that all faults in the For each flip-flop used in the design, its preset value is set to
fault list are sensitized and, hence, detected in at least one test the value of the net driving its data input. The values of primary
configuration. We first discuss the target fault list and then de- input nets form the test vector for that configuration. Note that
scribe test vector and configuration generation method. only one test vector is used per each test configuration. For se-
Testing for bridging faults has always been a challenging quential designs, this test vector must remain unchanged during
issue, particularly for ASICs. This is mainly due to the fact all test clock cycles, which is equal to the maximum sequential
that finding an appropriate fault list for bridging faults is not depth of the design. It needs to be mentioned that the present
as straightforward as that for stuck-at faults. The number of all value of individual bistables (flip-flops or latches) in the CLBs is
possible single stuck-at faults in a circuit is linear with the size of part of the configuration data, similar to the LUT configuration.
the circuit whereas the number of all pairwise bridging faults is Therefore, the initial state of the flip-flops can be individually
quadratic with the size of the circuit. This list is quite intractable set as a part of FPGA configuration. In other words, there is no
for large circuits. To solve this problem, inductive fault analysis need to control these flip-flops from primary inputs to change
methods have been proposed which try to extract a tractable their present value.
fault list for bridging faults from physical layout information Since these test configurations target faults in inter-CLB
[8] by selecting a subset of bridging faults with high proba- interconnect, any additional logic resources in CLBs (such as
bility of occurrence. However, these methods are very time-con- carry generation/propagation XORs, multipliers, etc.), if used,
suming and cannot be easily applied for large circuits. As a re- will be bypassed. In other words, the used CLBs are configured
sult, bridging fault testing is not explicitly addressed in the test only as LUTs followed by flip-flops (if those flip-flops are
flow. originally used in the user configuration). This is done to avoid
However, activating all possible faults (stuck-at, open, and fault masking due to additional logic in the CLBs. Here, we
pairwise bridging faults) for nets (wires) can be easily per- assume that nets extend from an LUT output to LUT input(s).
formed using only test vectors. These vectors These set of test configurations guarantee the detection of all
are columns of binary representations of numbers 1 to using stuck-at, open, and bridging faults (all pairs) in the intercon-
bits and called Walsh codes. This concept was nects. Since this technique detects all possible pairwise bridging
originally used for bus interconnect testing [9], [14], [15]. Fig. 5 faults, there is no need to extract probable bridging fault list
shows these test vectors for six wires . from the layout information using time-consuming inductive
We exploit these Walsh vectors in FPGA application-depen- fault analysis methods. However, the number of test configura-
dent test generation in order to activate all faults. Each Walsh tions can be further reduced if a particular fault list (i.e., smaller
vector is converted into the fault-free values of nets in a test con- than the comprehensive fault list) is used. This is because the
figuration. Based on the fault-free values of the nets in each test number of test configurations is logarithmic to the number of
configuration, single-term functions to be implemented in the faults in the fault list.
LUTs of a mapped design can be obtained. Hence, each Walsh Note that the computational complexity of this automatic test
vector correspond to a test configuration and the same faults that configuration generation algorithm is , where
are detected by that Walsh vector are sensitized and detected in is the number of LUTs and is the number of nets in the de-
the corresponding single-term test configuration. sign. The required number of test configuration for 100% fault
The pseudocode for the test configuration generation algo- coverage is only .
rithm is shown in Fig. 6 (Algorithm 1). All nets in the mapped As an example, consider a sequential mapped design shown
design are first considered as a row for the Walsh table. For in Fig. 7 with 4 LUTs and 14 nets. Fig. 8 shows the test
nets in the circuit, Walsh codes (columns) vectors and configurations generated using this approach for
are generated. For each vector, the value of each net is consid- this design. This circuit has 14 nets and Walsh codes give
ered as the activating input value for the LUT driven by that the following 4 vectors for these 14 nets:
net. Since each LUT is supposed to implement a single-term , , , and
TAHOORI: APPLICATION-DEPENDENT TESTING OF FPGAS 1029

TABLE I
TEST CONFIGURATIONS FOR ISCAS’89 CIRCUITS
MAPPED INTO XILINX VIRTEX FPGAS

Fig. 7. Sequential design with 4 LUTs and 14 nets.

2) Detection of Bridging Fault: Consider a bridging fault be-

tween two arbitrary nets A and B. Algorithm 1 guarantees that
opposite values assigned into these nets (case 1: 0,
1, or case 2: 1, 0) in at least one test configuration.
Fig. 8. Test vector and configurations for the circuit of Fig. 7.
Depending on the values of these two signals in that test con-
figuration and the particular bridging fault model (wired-AND,
wired-OR, or dominance), one of these nets gets a faulty value.
. Each of these vectors is converted to a test For example, in case 1 if it is a wired-AND fault, then B becomes
configuration by interpreting the value of each net in each test faulty, or if it is a B-dominant fault, A becomes faulty. Since
vector as the activating value for that net. conditions of Theorem 2 are guaranteed to be satisfied by Algo-
The preset value of each value is also determined based on rithm 1, then the value of the faulty signal will be propagated to
the activating value of the net connected to its data input. The reachable primary outputs and detected. Therefore, all pairwise
configuration of each LUT is determined by the activating input wired-OR, wired-AND, and dominant bridging faults will be de-
values for its input nets and the value of its output net. For ex- tected.
ample, in the first configuration, the activating input values of
LUT L3 are and its output is . Since this is a single-term C. Results
function, it should be of AND type and . If the Table I shows the number of test configurations required for
output net is , such as L3 in the third configuration, the single comprehensive application-dependent testing of the ISCAS’89
term function is OR type. sequential circuits mapped into Xilinx Virtex FPGAs. The
second column shows the number of CLBs used for mapping
Proof of Fault Coverage
each circuit. The third column shows the number of faults
The proof of open, stuck-at, and bridging fault detection is (pairwise bridging faults, opens, and single stuck-at faults)
given below. Therefore, 100% fault coverage w.r.t. the fault list in the fault list. The last column shows the number of test
given in Section II-C is achieved. configurations for 100% fault coverage (stuck-at, opens, and
1) Detection of Open and Stuck-At Faults: For any inter-CLB bridging faults).
net in the design, Algorithm 1 will assign it to both 0 and 1 in two
distinct test configurations. Since the single-term implementa- D. Upper-Bounds on Number of Test Configurations
tions of all LUTs are derived from the assigned values of the Here we estimate the maximum number of test configura-
nets, the conditions of Theorem 2 (as well as Lemma 1) will tions for application-dependent interconnect testing for any
be satisfied. Then, based on this theorem, both stuck-at-1 and FPGA device. For this purpose, we calculate the upper bound
stuck-at-0 faults on all nets will be detected. Moreover, since on the number of nets for an arbitrary design to be implemented
each net is assigned to opposite values and both stuck-at faults on an FPGA device with LUTs. Based on that, we figure out
on the net are detected, the open fault will also be detected. the upper bound on the number of required test configurations
1030 IEEE TRANSACTIONS ON VERY LARGE SCALE INTEGRATION (VLSI) SYSTEMS, VOL. 14, NO. 9, SEPTEMBER 2006

TABLE II
MAXIMUM NUMBER OF TEST CONFIGURATIONS FOR XILINX VIRTEX II FPGAS

Fig. 9. (a) Original configuration. (b) BIST configuration to test used logic
blocks.

A. BIST Scheme

to detect all inter-CLB interconnect faults, as described in The key point of this approach is to keep the configuration of
Section III-B. used logic blocks unchanged while applying test and observing
Assume that the FPGA device has LUTs, and each LUT the outputs of these logic blocks by exploiting inter-CLB in-
has inputs. The upper bound on the number of nets for any de- terconnects and unused logic blocks. In this scheme, each used
signs to be mapped into this FPGA is , which is ba- logic block will be exhaustively (or super-exhaustively) tested
sically allocating one separate net for each input and the output while all these logic blocks are tested concurrently. Since the
of every LUT in the FPGA. Note that this is a loose upper bound number of the inputs of each logic block is very small (less than
since the LUT outputs are connected to the inputs of other LUTs, ten inputs for each logic slice), it is practical to apply an exhaus-
and there are fanouts in the circuit. Using this upper bound on tive test (all possible input combinations) or a super-exhaustive
the number of nets, the upper bound on the number of test con- test (all possible input transitions) for testing each used logic
figurations based on the approach of Section III-B is as follows: block.
. The global interconnect is reprogrammed in such a way that
Table II shows these upper bounds on the number of inter- the test signals are routed to each logic block. In other words, a
connect test configurations for Xilinx Virtex II FPGA series common bus which is routed using available unused routing re-
[36]. The number of LUTs for each device is shown in the sources in the test configuration directly connects the test signals
second column. Note that these LUTs have four inputs ( to each logic block. The size of the bus is equal to the number
4). The upper bounds on the number of nets are shown in the of logic block inputs to apply an exhaustive test for each logic
third column. The fourth column shows the number of all pair- block. This parallel connection allows testing the entire set of
wise bridging faults associated with the maximum number of logic blocks concurrently. The test signals can be connected to
nets. Note that the number of faults ranges from 3.3 10 to the primary inputs for an off-chip test or to a test pattern gen-
1.08 10 depending on the size of the FPGA device. As can erator implemented using unused on-chip resources for a BIST
be shown in this table, the number of test configuration for 100% implementation.
fault coverage ranges from 12 to 19. This confirms that this ap- The logic block outputs are observed through an internal re-
proach is absolutely tractable for the large FPGAs. sponse compactor. This way, the outputs of many logic blocks
can be observed using a small number of off-chip outputs. The
response compactor can be combined with a response predictor
IV. LOGIC TESTING
such that a unique pass/fail signal can be generated. Since the
This section describes the approach for testing faults located user configuration of the logic blocks are known at the test time,
inside the logic blocks, intra-CLB interconnects as well as the response predictor can be precomputed and stored in the un-
logic resources, used by the mapped design. In this approach, used logic blocks (LUT bit locations or on-chip memory).
the original configuration of the used logic blocks is preserved, A BIST version of this test scheme is shown in Fig. 9. There
whereas the configuration of the global interconnects and are three main components in this BIST scheme, namely test
unused logic blocks are changed to exhaustively (and even pattern generator, parity predictor, and parity checker modules.
super-exhaustively) test all used logic blocks. This way, each 1) Test Pattern Generator (TPG): A linear feedback shift
logic block is tested in the same conditions it is used in the register (LFSR) modified as a De Bruijn counter [21], imple-
application configuration. On the other hand, changing the mented in the unused logic blocks, generates the exhaustive se-
configuration of the inter-CLB interconnects and unused logic quence. It is also possible to generate a super-exhaustive test to
blocks allows us to facilitate the access to each logic block. This be able to also detect delay faults in the logic blocks by using
approach can be framed as a BIST mechanism as described two LFSRs generating all possible transitions. Due to the small
next. number of logic block inputs which usually ranges from 3 to 5
TAHOORI: APPLICATION-DEPENDENT TESTING OF FPGAS 1031

per LUT (10–12 for a logic slice), an exhaustive or super-ex-

haustive testing of the logic block is performed with only a
small number of vectors. Moreover, since these test patterns are
generated on-chip, the test application time is also very small
compared to off-chip test application alternatives. All functional
faults inclusive of stuck-at faults are covered by this test.
2) Parity Predictor: An additional logic block generates a
parity bit of the outputs of the logic blocks used in the user ap-
plication for each input combination of logic blocks. Hence, the
number of inputs of this parity predictor block is equal to the
number of inputs of the logic blocks since all logic blocks ob-
tain the same set of inputs from the test pattern generator in the
test mode. This parity predictor block stores the precomputed
parity of all user logic blocks for each input combination. There-
fore, unlike general combinational circuits where parity predic-
tion can be expensive [23], only one extra logic block is required
to implement the parity prediction circuitry. For each input com-
bination of the logic blocks, the parity bit according to the ex- Fig. 10. Test partitioning in logic BIST.
pected outputs of all logic blocks is precomputed (obtained by
simulation) and stored in the corresponding bit location of the
LUT(s) implementing the parity predictor. As a result, the con- ample of partitioning using multiple LFSRs and parity checkers
figuration of the parity predictor block stores the precomputed is shown in Fig. 10 ( are the original used logic
parity bits. blocks). The number and the structure of the partitions can be
3) Parity Checker: The outputs of logic blocks and the parity determined based on the routing constraints, the availability of
block are checked using a parity checker. The number of inputs spare logic resources and the IOs.
of this parity checker is equal to the number of used logic blocks However in the worst case, if due to the routing complexity of
plus one, the output of the parity predictor. The simplest imple- the original design, the test signal cannot be routed to all logic
mentation of this parity checking module is a classical XOR tree. blocks, the used logic blocks can be partitioned into two subsets
If there are user logic blocks in the design and their outputs and each subset can be tested in a separate test configuration.
are denoted by , then the parity checker implements So, in this case two test configurations are required for testing
the function , using available unused logic of used logic blocks and intra-CLB interconnects. In each test
blocks. If any odd number of logic blocks produce erroneous configuration, the number of used logic blocks in that test con-
outputs, the errors will be detected by the parity checker. More figuration is always less than the total number of logic blocks
parity bits (similar to Hamming codes and extensions) can be in- in the FPGA. Hence, the BIST circuitry (TPG, parity predictor,
cluded to detect situations when even a number of logic blocks parity checker, and associated routing) will definitely fit in un-
produce errors. The parity checker is the largest module in the used logic blocks.
BIST circuitry. Unlike the other two modules, TPG and parity When the number of CLB inputs exceeds some limit such that
predictor, in which their sizes are independent of the size of the the CLB cannot be exhaustively tested (e.g., more than 20), ver-
mapped design, the size of the parity checker is a function of the ification testing [18], [19] or segment verification testing [20]
size of the mapped design (the number of user logic blocks). techniques can be used in which different segments (partitions)
The logic blocks in contemporary FPGAs contain other logic of the circuit under test (in this case user CLB) are exhaus-
components besides LUTs, such as carry generation and prop- tively tested. Such segmentation reduces the total number of test
agation logic, cascade chains, and programmable multiplexers vectors required for testing and make pseudoexhaustive testing
[3], [36]. In the presented technique, all the resources in the user tractable.
logic blocks, inclusive of all logic resources and local intercon-
nect, will be tested exhaustively. Since the configuration of used B. Implementation
logic blocks are preserved, and the width of TPG is chosen to When dealing with FPGAs and not with ASICs, the hardware
generate tests for all used inputs of logic blocks, all used logic resources (unused logic blocks and interconnect) already exist
resources and intra-CLB interconnect are tested. and any BIST circuitry is usually considered as free [29]. How-
One problem with this approach could be the routing con- ever, the BIST circuitry must be small enough to fit in the unused
gestion since the test signals (LFSR outputs) must be routed to logic blocks. In other words, if the overhead of the BIST cir-
the inputs of all used logic blocks. This could be a potential cuitry is small then it is not necessary to partition the circuit and
problem for very large designs. In order to solve this problem, use an extra test configuration. Alternatively, it is desirable if
the presented BIST architecture can be partitioned: instead of the BIST circuitry can fit in the unused resources of the smallest
connecting the outputs of one TPG to all logic blocks, multiple FPGA device that it used to map the original user application.
TPGs can be used and the outputs of each TPG are connected Table III shows the overhead of the BIST circuitry for
to only a subset of logic blocks. Multiple parity checkers can ISCAS’89 sequential circuits mapped into Xilinx Virtex
also be used depending on the availability of I/O pins. The ex- FPGAs. In this table, the second column gives the number
1032 IEEE TRANSACTIONS ON VERY LARGE SCALE INTEGRATION (VLSI) SYSTEMS, VOL. 14, NO. 9, SEPTEMBER 2006

TABLE III by decomposition. For example, bridging faults between the re-
OVERHEAD OF BIST LOGIC TESTING sources decomposed into different test configurations cannot be
detected [5]. This situation never happens in our approach.
3) Test Time Reduction: The only difference among the test
configurations is the contents of the LUTs, which is a very small
portion of the configuration data (less than 5% of the total con-
figuration bits [36]). Therefore, test configuration loading time
can be drastically reduced by partial reconfiguration. For ex-
ample, the reconfiguration scheme in Xilinx FPGAs is frame-
based. Each CLB column is divided into a number of frames.
Some frames contain configuration bits for both logic and in-
terconnects whereas others contain only interconnect configu-
ration bits. The partial reconfiguration for loading next test con-
figuration requires loading only those frames containing logic
configuration bits.
4) Test Configuration Compression: As the only difference
among the original design and the test configurations is the con-
tents of LUTs, instead of saving the complete configuration
data for each test configurations, only the LUT contents need to
be stored for each test configuration (differential compression),
achieving up to 20 test configuration compression ratio.
5) Compatibility: This technique relies only on repro-
grammability of logic resources. This feature exists in all
families of reprogrammable (SRAM-based) FPGAs and
complex programmable logic devices (CPLDs). Hence, this
technique can be easily applied for various FPGA or CPLD
families from a variety of programmable logic vendors [3],
[36].
The presented techniques for testing interconnect and logic
of CLBs required to implement the original circuit, the third resources are also able to detect the faults that occur in the con-
column represents the number of CLBs required to implement figuration circuitry. The faults in the routing configuration bits
the entire BIST scheme with the LFSR, parity predictor, and manifest themselves as open and bridging faults in the mapped
parity checker as well as the circuit under test (original user design which will be detected in the first set of test configura-
configuration). Note that each CLB in Xilinx Virtex FPGAs tions (Section III). Faults in the logic configuration bits affect
contains four LUTs and storage elements. The overhead is the functionality of the logic blocks which will be detected in
given in the fourth column as a percentage of the initial circuit the logic BIST method (Section IV).
implementation. The overhead for bigger circuits is much Note that a bridging fault between a signal line and a configu-
smaller. For the circuits with zero overhead, it was possible to ration line will directly or indirectly affect the user application.
map the entire BIST circuitry in the unused LUTs and logic If the value of the signal line is disturbed, the user application
slices of the partially-used CLBs by the original design. Since is directly affected and depending whether this signal line is a
the increase in the CLB usage is only a few percents, the entire global interconnect or inside a CLB, it will be detected in the
BIST circuitry will still fit into the smallest FPGA device that first or second set of test configurations. If the bridging fault only
the original design would fit. disturbs the configuration line and it then affects the state of a
configuration bit, it results in a fault in the interconnect (open
or bridging fault) or logic resources (logic fault). The presented
V. DISCUSSION
test methods are able to detect this fault.
In the presented interconnect testing method, the original con- Since the logic is modified for interconnect testing and the in-
figuration of the routing resources of the design remains un- terconnect is modeled for logic testing, there might be a situation
changed. Also, the timing of the original design is preserved, in which there is a fault in the resources used to test but not used
i.e., no flip-flop is added to or removed from the original design for the application. By performing high-resolution diagnosis, it
in test configurations; only the preset values of some flip-flops can be identified whether the defective resources are used in the
are modified. The advantages of this approach are as follows. user application or not. Once the failure is diagnosed to be in
1) Reduced Test Configuration Generation Effort: There is a resource not originally utilized by the user application, then
no need to perform placement and routing for generating the test it becomes a reliability and test quality issue. If the defective
configurations. The placement and routing of the original design resource is physically very close to user resources, then based
are used for the test configurations. on reliability constraints and criticality of the application, the
2) No Fault Missed: Since no partitioning of the resources design might be remapped such that the used resources by the
over multiple configurations is performed, no fault is missed application is not too close to the defective resources since the
TAHOORI: APPLICATION-DEPENDENT TESTING OF FPGAS 1033

defect might expand over time and make the neighboring re- [17] ——, “Exploiting reconfigurability for effective testing of delay faults
sources defective, as well. in sequential subcircuits of LUT-based FPGAs,” in Proc. Field Pro-
grammable Logic Conf., 2002, pp. 616–626.
[18] E. J. McCluskey and S. Bozorgui-Nesbat, “Design for autonomous
VI. CONCLUSION test,” IEEE Trans. Circuit Syst., vol. 28, no. 11, pp. 1070–1079, Nov.
1981.
In this paper, a new technique for application-dependent [19] E. J. McCluskey, “Built-in verification test,” in Proc. IEEE Int. Test
testing of FPGAs is presented. This method tests all inter- Conf., 1982, pp. 183–190.
connect as well as logic resources used by a particular user [20] ——, “Verification testing—A pseudoexhaustive test technique,” IEEE
Trans. Comput., vol. C-33, no. 6, pp. 541–546, Jun. 1984.
application implemented on an FPGA. In the first phase, only [21] ——, Logic Design Principles. Englewood Cliffs, NJ: Prentice-Hall,
the configuration of logic blocks is modified for global inter- 1986.
connect testing. Less than 20 test configurations are required [22] H. Michinishi, T. Yokohira, and T. Okamoto, “A test methodology
for interconnect structures of LUT-based FPGAs,” in Proc. Asian Test
to test the largest design implemented in the largest FPGA Symp., 1996, pp. 68–74.
device for all stuck-at, open, and pairwise bridging faults. The [23] S. Mitra and E. J. McCluskey, “Which concurrent error detection
second phase, which consists of only one test configuration, scheme to choose,” in Proc. IEEE Int. Test Conf., 2000, pp. 985–994.
[24] W. Quddus, A. Jas, and N. A. Touba, “Configuration self-test in FPGA-
tests all used logic blocks as well as local interconnects. In based reconfigurable systems,” in Proc. Int. Symp. Circuits Syst., 1999,
this phase, the configuration of original used logic blocks is pp. 97–100.
preserved and configuration of interconnects and unused logic [25] M. Renovell, P. Faure, J. M. Portal, J. Figueras, and Y. Zorian, “Is-
FPGA: A new symmetric FPGA architecture with implicit scan,” in
blocks is changed to exhaustively test all used logic blocks. Proc. IEEE Int. Test Conf., 2001, pp. 924–931.
A BIST version of the presented test configurations is also [26] M. Renovell and Y. Zorian, “Different experiments in test generation
presented. The experimental results show that the overhead of for XILINX FPGAs,” in Proc. IEEE Int. Test Conf., 2000, pp. 854–862.
[27] T. Storey and W. Maly, “CMOS bridging fault detection,” in Proc.
BIST circuitry, in terms of the number of required unused logic IEEE Int. Test Conf., 1990, pp. 842–851.
blocks, is reasonably small. [28] C. Stroud, S. Wijesuriya, C. Hamilton, and M. Abramovici, “Built-in
The presented techniques can be used either as part of a self-test of FPGA interconnect,” in Proc. IEEE Int. Test Conf., 1998,
pp. 404–411.
ASFPGA test flow, or as an online testing method in a self-re- [29] C. Stroud, S. Konala, C. Ping, and M. Abramovici, “Built-in self-test of
pair scheme for defect and fault tolerance. logic blocks in FPGAs (Finally, a free lunch: BIST without overhead!),”
in Proc. VLSI Test Symp., 1996, pp. 387–392.
[30] X. Sun, J. Xu, B. Chan, and P. Trouborst, “Novel technique for built-in-
REFERENCES self test of FPGA interconnects,” in Proc. IEEE Int. Test Conf., 2000,
[1] M. Abramovici and C. Stroud, “BIST-based detection and diagnosis pp. 795–803.
of multiple faults in FPGAs,” in Proc. IEEE Int. Test Conf., 2000, pp. [31] M. B. Tahoori, E. J. McCluskey, M. Renovell, and P. Faure, “A multi-
785–794. configuration strategy for an application dependent testing of FPGAs,”
[2] M. J. Alexander and G. Robins, “New performance-driven FPGA in Proc. VLSI Test Symp., 2004, pp. 154–159.
routing algorithms,” IEEE Trans. Comput.-Aided Des. Integr. Circuits [32] M. B. Tahoori, “Application-specific bridging fault testing of FPGAs,”
Syst., vol. 15, no. 12, pp. 1505–1517, Dec. 1996. J. Electron. Testing, Theory, Appl., vol. 20, no. 3, pp. 279–289, Jun.
[3] “Altera Data Sheets,” 2004, [Online]. Available: http://www.al- 2004.
tera.com [33] ——, “Application-dependent testing of FPGA interconnects,” in Proc.
[4] B. Chess and T. Larrabee, “Logic testing of bridging faults in CMOS Int. Symp. Defect Fault Tolerance, 2003, pp. 409–416.
integrated circuits,” IEEE Trans. Comput., vol. 47, no. 3, pp. 338–345, [34] M. B. Tahoori and S. Mitra, “Automatic configuration generation
Mar. 1998. for FPGA interconnect testing,” in Proc. VLSI Test Symp., 2003, pp.
[5] D. Das and N. A. Touba, “A low cost approach for detecting, locating, 134–139.
and avoiding interconnect faults in FPGA-based reconfigurable sys- [35] A. Takahara, T. Miyazaki, T. Murooka, M. Katayama, K. Hayashi, A.
tems,” in Proc. Int. Conf. VLSI Des., 1999, pp. 266–269. Tsutsui, T. Ichimori, and K. Fukami, “More wires and fewer LUTs:
[6] A. DeHon, “Balancing interconnect and computation in a reconfig- A design methodology for FPGAs,” in Proc. ACM Int. Symp. FPGAs,
urable computing array (or, why you don’t really want 100% LUT uti- 1998, pp. 12–19.
lization),” in Proc. ACM Int. Symp. FPGAs, 1999, pp. 69–78. [36] “The Programmable Logic Data Book,” Xilinx Inc, 2003.
[7] A. Doumar and H. Ito, “Testing the logic cells and interconnect re- [37] Xilinx Easypath Solutions 2003 [Online]. Available: http://www.
sources for FPGAs,” in Proc. Asian Test Conf., 1999, pp. 369–374. xilinx.com
[8] F. J. Ferguson and J. P. Shen, “A CMOS fault extractor for inductive
fault analysis,” IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst., Mehdi B. Tahoori (S’02–M’04) received the M.S.
vol. 7, no. 11, pp. 1181–1194, Nov. 1988. degree in electrical engineering from Stanford
[9] P. Goel and M. T. McMahon, “Electronic chip-in place test,” in Proc. University, Palo, Alto, CA, in 2002, the B.S. degree
IEEE Int. Test Conf., 1982, pp. 83–90. in computer engineering from Sharif University of
[10] I. G. Harris, P. R. Menon, and R. Tessier, “BIST-based delay path Technology, Tehran, Iran, in 2000, and the Ph.D.
testing in FPGA architectures,” in Proc. IEEE Int. Test Conf., 2001, degree in electrical engineering from Stanford
pp. 932–938. University, in 2003, under the supervision of Prof.
[11] G. Harris and R. Tessier, “Interconnect testing in cluster-based FGPA E. J. McCluskey,
architectures,” in Proc. Des. Autom. Conf., 2000, pp. 49–54. He is an Assistant Professor in the Department of
[12] W. J. Huang and E. J. McCluskey, “Column-based precompiled con- Electrical and Computer Engineering at Northeastern
figuration techniques for FPGA fault tolerance,” in Proc. IEEE Symp. University, Boston, MA. During 2002–2003, he was
Field-Programmable Custom Comput. Mach., 2001, pp. 137–146. a Research Scientist at Fujitsu Laboratories of America in advanced computer-
[13] W. K. Huang, X. T. Chen, and F. Lombardi, “On the diagnosis of aided design (CAD) research working on reliability issues in deep-submicron
programmable interconnect systems: Theory and application,” in Proc. mixed-signal VLSI designs. He has published more than 60 technical papers
VLSI Test Symp., 1996, pp. 204–209. in leading conferences and journals. His research interests include nanotech-
[14] H. Jarwala and C. W. Yau, “A new framework for analyzing test gen- nology, VLSI testing, VLSI CAD, and fault tolerant computing.
eration and diagnosis algorithms for wiring networks,” in Proc. IEEE Dr. Tahoori has been the Program Chair of the IEEE Defect and Current Based
Int. Test Conf., 1989, pp. 63–70. Testing Workshop in 2005 and 2006. He was the Guest Editor of IEEE Design
[15] W. H. Kautz, “Testing for faults in wiring networks,” IEEE Trans. and Test Special Issue on Advanced Technologies and Reliable Design for Nan-
Comput., vol. C-23, no. 4, pp. 358–363, Apr. 1974. otechnology Systems. He has served on the program committees of IEEE Inter-
[16] A. Krasniewski, “Application-dependent testing of FPGA delay faults,” national Test Synthesis Workshop and IEEE International Workshop on Design
in Proc. Euromicro. Conf., 1999, pp. 260–267. and Test of Defect-Tolerant Nanoscale Architectures.