Evaluation of FPGA Resources for Built-In Self-Test of Programmable
Logic Blocks
Charles Stroud, Ping Chen, Srinivasa Konala,
and Miron Abramovici
Dept. of Electrical Engineering
University of Kentucky
AT&T Bell Laboratories
Murray Hill, NJ
Abstract
We present a new approach for FPGA testing that exploits
the reprogrammability of FPGAs to create Built-In Self-Test
(BIST) logic only during off-line test. As a result, BIST is
achieved without area or performance penalties to the system
function implemented by the FPGA, since the FPGA is
reconfigured for normal system operation. An analysis of
Look-Up Table (LUT) based FGPA architectures yields a
general expression for the number of test sessions and
establishes the bounds on FPGA logic resources required to
minimize the number of BIST configurations required to
completely test all of the programmable logic blocks of an
FPGA.
1. Introduction
In this paper, we introduce a new approach for FPGA testing
that exploits the reprogrammability of an FPGA to create the
BIST logic by configuring it only during off-line testing. In
this way, testability is achieved without any overhead, since
the BIST logic will “disappear” when the circuit is
reconfigured for its normal system operation. In contrast,
conventional BIST approaches introduce both area overhead
(typically between 10 and 30 percent) and delay penalties.
Our approach is applicable to any in-circuit reprogrammable
FPGA, such as SRAM-based FPGAs. Its only cost is the
additional memory for storing the data required to
reconfigure the FPGA; however, this memory is usually part
of the test machine or system maintenance processor
environment which controls the BIST process, and does not
involve resources of the device or the system under test.
Reconfiguring FPGAs for system-level testing has been used
to test the other circuitry in the system [1-3]; however, these
methods do not address the testing of the FPGAs themselves.
The FPGA manufacturing test is complicated by the need to
cover all possible modes of operation and many nonclassical fault models (faults affecting the programmable
interconnect network, delay faults, etc.). Currently, tests are
generated manually by configuring several application
circuits and exercising them with test vectors developed
specifically for each circuit. These circuits share the same set
of faults, so it is sufficient to detect a fault in only one circuit.
Fault simulation to determine the fault coverage for stuck-at
faults is very expensive, since all the application circuits
must be simulated. In addition, these tests require long
application times and expensive Automatic Test Equipment
(ATE). The FPGA manufacturing tests are not reusable for
board and system-level testing, which require additional
development effort.
The traditional approach to system-level testing of FPGAs
has been to develop off-line system diagnostic routines
which test the FPGAs in the system mode of operation. The
development of these diagnostic routines can be timeconsuming and costly, particularly when the system is
difficult to test. BIST has been particularly advantageous for
field testing of digital systems by providing high faultcoverage tests at the system operating frequency (which,
otherwise, is not usually achievable by system diagnostic
software), and by reducing diagnostic run-time and
diagnostic software development. Reductions in diagnostic
run-time result in reducing the mean time to repair and
increasing the system availability, while reductions in
diagnostic code development help to reduce system
development time and cost.
Our BIST approach1 for FPGAs is applicable to all levels of
testing (wafer, package, board, and system), and all tests are
performed at the normal operating frequency, thus providing
at-speed testing. The test controller (ATE, CPU, or
maintenance processor) supplies the configurations needed
to create the BIST logic, initiates the tests, and reads the test
results (pass/fail indication and diagnostic data). Our
strategy is to use pseudoexhaustive testing [4] in order to
provide maximal fault coverage independent of the intended
system function of the FPGAs. Eliminating the need for
adding BIST circuitry (or any design-for-test logic) to the
system logic in FPGAs reduces the design interval and
1. This material is based upon work supported by
the National Science Foundation under Grant No.
MIP-9409682.
increases the system functionality that can be implemented
in each FPGA. An additional advantage is the potential of
using a lower-cost ATE for device and package level test.
Since every FPGA is individually tested, our approach
provides in-system location of defective devices; such a
diagnostic resolution is not always achievable with system
diagnostics.
In this paper, we describe the testing strategy and analyze the
architectural resources needed to provide BIST for all the
programmable logic blocks (PLBs) in an FPGA. Although
testing the PLBs using the proposed BIST configurations
will also detect many of the faults in the programmable
interconnect network, it will not provide complete coverage
for these faults. Complete testing of the programmable
interconnect will be addressed in the next phase of this
project. Testing the PLBs will also test the portion of the
FPGA programming circuitry associated with the PLBs as
well as the FPGA programming interface. We use the
AT&T Optimized Reconfigurable Cell Array (ORCA) [5]
for the initial design and implementation of the BIST
approach, but we emphasize that our technique can be
applied to any SRAM-based FPGA, such as Xilinx [6] or
Altera Flex 8000 [7] series FPGAs.
The remainder of this paper is organized as follows. Section
2 presents an overview of the proposed BIST approach.
Section 3 analyzes the FPGA logic resources needed to
implement the BIST logic and to minimize the number of
BIST configurations required to test the FPGA. Section 4
summarizes the results obtained thus far in terms of the
number of BIST configurations developed for and their
application to the ORCA device. The paper concludes in
Section 5.
Table 1: Abbreviations
PLB
Programmable Logic Block
TPG
Test Pattern Generator
ORA
Output Response Analyzer
BUT
Block (PLB) Under Test
LUT
Look-Up Table
FF
Flip-Flop
ORCA
Optimized Reconfigurable Cell Array
NTS
Number of Test Sessions
NPLB
Number of PLBs in FPGA
NTPG
Number of PLBs used as TPGs
NORA
Number of PLBs used as ORAs
NBUT
Number of PLBs under test
2. Overview of the FPGA BIST Approach
Our FPGA BIST process is a sequence of test phases, where
every phase consists of the following steps: 1) configure the
circuit, 2) initiate the test, 3) generate test patterns, 4)
analyze the responses to produce a pass/fail indication, and
5) read the test results. In step 1, the test controller interacts
with the FPGA under test to (re)configure its logic by
retrieving the BIST configuration from the configuration
storage and loading it into the FPGA. Then the test controller
initiates the test (step 2) and reads the results (step 5) using
the FPGA's boundary-scan Test Access Port [8] or other
system specific means. (Practically all recently developed
FPGAs, such as ORCA [5], XC4000 [6] and Flex8000 [7],
feature boundary scan.) Steps 3 and 4 are concurrently done
by the BIST logic within the device, and do not involve I/O
pins. Thus the I/O pins of the FPGA are not tested during
BIST, and this requires additional tests during
manufacturing testing. In system testing, the I/O pins are
tested together with the board connectivity using boundary
scan tests.
Although the same basic approach is applied at all levels of
testing, there are some differences between manufacturing
testing done at the wafer and package levels, and
maintenance/field testing done at the board and system
levels. These differences are summarized in Table 2. One
difference results from the need to reconfigure an FPGA that
has passed the in-system test for its normal system function;
hence the normal device configuration must be stored on
disk along with the BIST configurations.
Table 2: Differences in FPGA testing levels
Testing Level
Test Controller
Configuration
Storage
Functional
Reconfiguration
Wafer/Package
ATE
ATE Memory
NO
Board/System
CPU or maintenance processor
Disk or other
mass storage
YES
To support the self-test done in steps 3 and 4, some of the
logic is configured as test pattern generators (TPGs) and
output response analyzers (ORAs). Our strategy relies on
pseudoexhaustive testing in which all subcircuits of the
device are tested with exhaustive patterns. This results in
maximal fault coverage without explicit fault model
assumptions and without fault simulation. Pseudoexhaustive
testing is guaranteed to detect any fault that changes the
function of the PLB without increasing its number of states;
this set includes all single and multiple stuck-at faults. Many
FPGAs contain RAM modules, whose exhaustive testing is
impractical. For these modules we use standard RAM test
sequences, which are known to be exhaustive for the fault
models specific to RAMs [9,10].
Figure 1 shows a typical structure of a PLB, composed of a
memory block, a flip-flop (FF) block, and a combinational
output logic block; for example, this structure is featured in
the ORCA programmable function unit [5], in the XC4000
configurable logic block [6], and in the Altera Flex8000
logic element [7]. The memory blocks can be configured as
RAMs or combinational look-up tables (LUTs). In most
cases, the cell has no feedback loops and the FFs can be
directly accessed by bypassing the LUT (as shown by the
dotted line). This simple structure, where the inputs and the
outputs of every subcircuit are easy to control and to observe,
simplifies the pseudoexhaustive testing of the cell.
Output
LUT/RAM
FFs
Logic
changed so that in the next test session previous BUTs
become TPGs or ORAs, and vice versa. Clearly, we need at
least two test sessions to test all PLBs. Since testing time is
a major component of the testing cost, a major goal of the
testing strategy is to minimize the number of test sessions. In
the next section, we will analyze the relations between some
architectural features of an FPGA and the number of test
sessions needed for a complete test.
3. Evaluation of FPGA Resources
The number of test sessions (NTS) is a function of the number
of PLBs in the FPGA (NPLB) as well as the number of BUTs
(NBUT). The general expression for NTS is given by:
N TS =
N PLB
-------------N BUT
Also, the following relation must hold for any FPGA
architecture in terms of the number of PLBs required to act
as TPGs (NTPG) and ORAs (NORA) during a testing session.
N BUT + N TPG + N ORA ≤ N PLB
Figure 1. Typical FPGA PLB structure
In general, the simplest method for output response analysis
- comparison with the expected response - is difficult to use
in most BIST applications because of the expense involved
either in storing the reference response or in generating it
from a copy of the circuit under test. In the FPGA BIST
approach, however, the circuits under test are identical PLBs
and all that is needed is to create the ORAs to compare their
outputs. Unlike the signature-based compression circuits
found in most BIST applications, comparator-based ORAs
do not suffer from the aliasing problem that occurs when
some faulty circuits produce the good circuit signature. As
long as the PLBs being compared by the same ORA do not
fail the same way at the same time, no aliasing will be
encountered with the comparison-based approach. However,
if these PLBs are fed by the same faulty TPG, the applied
tests will be incomplete, and a faulty PLB may escape
detection. To avoid this problem, we configure the logic so
that different TPGs feed the PLBs being compared by the
same ORA, and all TPGs are synchronized; that is, they
generate the same test pattern at the same time.
Therefore, the strategy is to configure a group of PLBs as
pseudoexhaustive TPGs and comparison-based ORAs, and
another group as blocks under test (BUTs). Every BUT will
be repeatedly reconfigured to test it completely in its various
modes of operation. We define a test session as a sequence
of test phases that test the BUTs in every configuration. Once
the BUTs have been tested, the roles of the PLBs are
(1a)
(1b)
During most of the configurations used to completely test the
BUTs, the TPGs work as binary counters to supply
exhaustive test patterns to the m-input BUTs (not counting
the clock input). Since a PLB has more inputs than outputs,
several PLBs are needed to construct a single m-bit counter.
As explained in the previous section, different TPGs must
feed the BUTs whose outputs are compared by the same
ORA. Thus the number of TPGs required is equal to C,
where C represents the number of PLB outputs that can be
compared by a single LUT. This results in a total number of
PLBs used for TPGs, NTPG, given by:
m
N TPG = C ⋅ ---f
(2)
where f is the number of flip-flops per PLB.
Figure 2 shows the structure of the FPGA as it would be
configured during a test session. An ORA consists of a LUT
that compares the corresponding outputs from C BUTs and a
flip-flop to record the first mismatch. The feedback from the
flip-flop output to one of LUT inputs disables further
comparisons after the first error has been recorded. In
general, several ORAs may be implemented in the same
PLB, depending on the number of independent LUTs in a
PLB, L. Here we consider LUTs to be independent if their
sets of inputs are disjoint in at least one PLB configuration.
Each one of the C TPGs drives a group of n BUTs. Each
BUT has m inputs and O outputs. The C × n × O outputs
from the BUTs are compared by O groups of n ORAs, where
each ORA monitors C outputs, and the ith group of ORAs
receives the ith output from n BUTs. Then the number of
PLBs required to be configured as ORA circuits, NORA, is
given by:
O⋅n
N ORA = ----------(3)
L
The values of C and n also determine the total number of
BUTs (NBUT) as follows:
N BUT = C ⋅ n
(4)
The values of C, O, L, and f are functions of the PLB
architecture for the given FPGA being tested. By
substituting the expressions for the numbers of PLBs used
during a test session for the implementation of TPGs, ORAs,
and BUTs (given by Equations 2 through 4) into Equations
1a and 1b, we obtain the following lower bound for NTS:
O
N PLB C + ----
L
N TS ≥ -------------------------------------------------------
C N PLB – C ⋅ m
-----
f
(5)
The number of BUTs in each of the C groups, given by n, is
another one of the values of interest to be determined for a
given FPGA. The value of n used to derive Equation 5
represents the maximum value for the number of BUTs in
each of the C groups for that particular value of NTS and is
given by:
n max ≤
N PLB – C ⋅ m
----
f
------------------------------------O
C + ---L
(6)
This maximum value may be difficult to implement
practically because of routing constraints. Therefore,
substituting the value of NBUT from Equation 4 into Equation
1a, we get lower limit on n for the same value of NTS.
n ≥ n min =
N PLB
-----------------N TS ⋅ C
However, the minimum value of n given by Equation 7 does
not consider the proper balance of BUTs, TPGs, and ORAs
that must be maintained as a function of the PLB
architecture. As a result, we consider the following relation,
which is obtained by eliminating NPLB from Equations 1a
and 1b:
N BUT + N TPG + N ORA ≤ N BUT ⋅ N TS
n ≥ n arch =
C⋅ m
----f
------------------------------------------O
C ⋅ ( N TS – 1 ) – ---L
ORA
to n BUTs
LUT
FF
O outputs
m inputs
TPG
BUT
BUT
m outputs
ORA
to n BUTs
C TPGs
m inputs
(9)
This minimum value of n is a function of the structure of the
PLB and is necessary to maintain the proper balance of TPG,
ORA, and BUT functions for this BIST approach. For
example, in the ORCA PLB, there are L=2 independent
LUTs, with each LUT having C+1=5 inputs; hence C=4.
Since each PLB has m=18 inputs, the maximum number of
flip-flops required for a TPG to generate exhaustive test
patterns, f, is also 18. Finally, there are O=5 outputs from
each PLB which must be compared by the ORAs, since the
BUT
m outputs
(8)
Substituting the expressions from Equations 2 through 4 into
Equation 8 and solving for n, we obtain the minimum value
of n which will provide the proper balance of BUT, TPG, and
ORA functions for a BIST session based on the PLB
architecture (which we refer to as narch):
O outputs
TPG
(7)
LUT
FF
BUT
C+1 inputs
C groups of n BUTs
Figure 2. FPGA structure for a test session
O groups of n ORAs
carry-out signal for the ripple mode can be observed at one
of the five outputs of the PLB. Then from Equation 9 we find
that n ≥ 14 in order to achieve the minimum number of test
sessions (NTS=2). Therefore, for n=14, we obtain the
minimum values NTPG=20, NORA=35, and NBUT=56 from
Equations 2 through 4, respectively. This requires a
minimum of 111 PLBs in an ORCA to be able to completely
test all PLBs with two test sessions. Only the smallest of the
ORCA series (the AT1C03 with 100 PLBs) fails to meet this
criteria and will require three test sessions to completely test
all its PLBs. These data are summarized in Table 3 and
compared to the Xilinx 4000 and Altera Flex 8000 series
FPGAs in terms of the resource parameters for each FPGA
and the minimum resources required for NTS=2 using
Equation 9. In the case of the Xilinx series 4000 FPGAs, the
smallest four FPGAs (4002: 64 PLBs, 4003: 100 PLBs,
4004: 144 PLBs, and 4005: 196 PLBs) will require three test
sessions. In the case of the Altera Flex 8000 series FPGA, the
smallest FPGA (8282: 208 PLBs) also requires three test
sessions.
sessions is a function of both narch and nmin. As a result,
nmin(final) is given by the maximum of the two minimum
values for n in Equations 7 and 9.
m
n min ( final )
C ⋅ ----N PLB
f
= max { -----------------, ------------------------------------------ }(10)
N TS ⋅ C
O
C ⋅ ( N TS – 1 ) – ---L
The minimum and maximum values of n obtained for some
ORCA, Xilinx, and Altera FPGAs are given in Table 4 along
with the corresponding values for NTS, NTPG, NORA, and
NBUT. Note that NTPG is a function of the PLB structure and
not a function of the total number of PLBs in the FPGA. For
those cases where the total number of PLBs used for TPG,
ORA, and BUT functions is less than the total number of
PLBs in the FPGA, the unused PLBs could be used to buffer
the TPG outputs which have high fan-out. On the other hand,
when all PLBs in the FPGA are required for BIST resources,
the number of test sessions may need to be increased if
limitations in the routing resources prevent successful
implementation of the BIST configurations.
The minimum value of n is of particular importance since it
will require less logic resources as well as routing resources
in the FPGA when compared to larger values of n. This will,
in turn, provide the best opportunity for successful
placement and routing of the BIST configurations in the
FPGA during actual implementation. Therefore, the final
minimum value of n which ensures that the proper balance of
BUTs, ORAs, and TPGs is maintained while also ensuring
that the FPGA can be tested in the desired number of test
4. Experimental Results
Based on a gate level model of the ORCA 1C series PLB, we
determined that nine BIST configurations are sufficient to
completely test a BUT [11] in every functional mode of
operation. The memory requirements and the configuration
download time depend on the size of the FPGA. For the
Table 3: BIST Resource requirements for FPGAs
Parameter
Resource
ORCA
Xilinx 4000
Altera 8000
C
comparisons/LUT
4
3
4
O
outputs/PLB
5
5
3
L
LUTs/PLB
2
2
1
m
FFs/TPG=inputs/PLB
18
12
10
f
FFs/PLB
4
2
1
Minimum Requirements
ORCA
Xilinx 4000
Altera 8000
narch (for NTS=2)
14
36
40
NTPG
20
18
40
NORA
35
72
120
NBUT
56
108
160
NPLB
111
198
320
largest 1C series ORCA (the ATT1C09), approximately 16
Kbytes of storage are needed per configuration, which
means about 144 Kbytes for all nine configurations. The
same nine configurations are applied to the BUTs tested in
each of the test sessions. The configuration download time
also depends on the type of interface between the
configuration storage media and the FPGA itself. Download
time for the ORCA 1C series FPGAs varies from 2 to 35
msec. while the execution time for the BIST sequence is
approximately 15 msec. at a 10 MHz clock rate. This would
correspond to approximately 1 second of testing time
required to completely test all of the PLBs in the FPGA.
Testing time and configuration memory storage can be
reduced for system-level testing by testing the FPGA only
for the specific modes of operation in which its PLBs are
used by the system function.
A more detailed discussion of the nine BIST configurations
can be found in [11]. For FPGAs which require only two test
sessions, a total of 18 configurations would be required to
completely test all PLBs in the FPGA. These 18
configurations compare favorably with the 32 configurations
currently used to test production ORCA devices [12].
However, it should be noted that the 32 configurations used
for manufacturing include complete testing of the
programmable interconnection network, testing of the
configuration memory and its read back circuitry, and testing
of the FPGA I/O buffers. Parametric testing and speed
sorting is performed with additional configurations of the
FPGA.
5. Conclusions
We have proposed a new BIST approach for the
programmable logic blocks in SRAM-based FPGAs. Our
approach takes advantage of the reprogrammability of
FPGAs by reconfiguring the FPGA to test itself only during
off-line testing. As a result, it completely eliminates the area
overhead and the performance penalty associated with
traditional BIST techniques. Because we no longer need
testability hardware in the design, all logic resources in the
FPGA are available for system functionality. In addition,
hardware design and diagnostic software development
intervals can be reduced since the FPGA BIST approach is
generic and is applicable to all of the SRAM-based FPGAs
in the system. Since the test sequences are generic in that
they are a function of the FPGA architecture and not a
function of what is programmed into the FPGA, this
technique can also be used at every level of testing, from
wafer- and package-level manufacturing tests to board- and
system-level field tests. The BIST configurations developed
for this approach also test the portion of the programming
interface of the FPGA which is associated with the PLBs.
The exception is the programming read-back circuitry,
which can be tested by simply reading back each
configuration after it has been programmed. The BIST
Table 4: BIST resource evaluation for various FPGA architectures
Series
NPLB
nmin
nmax
NTS
NTPG
NORA
(min)
NORA
(max)
NBUT
(min)
NBUT
(max)
ATT1C03
100
9
12
3
20
23
30
36
48
ATT1C05
144
18
19
2
20
45
48
72
76
ATT1C07
196
25
27
2
20
63
68
100
108
ATT1C09
256
32
46
2
20
80
115
128
184
XC4002
64
8
8
3
18
20
20
24
24
XC4003
100
12
14
3
18
30
35
36
42
XC4005
196
22
32
3
18
55
80
66
96
XC4008
324
54
55
2
18
135
138
162
165
EPF8282
208
18
24
3
40
54
72
72
96
EPF8452
336
42
42
2
40
126
126
168
168
EPF8820
672
84
90
2
40
252
270
336
360
EPF81188
1008
126
138
2
40
378
414
504
552
configurations also test some (but not all) of the
programmable
interconnection
network.
BIST
configurations for complete testing of the interconnection
network will be developed during the next phase of this
project.
Acknowledgments
This work was also supported in part by a grant from the
University of Kentucky Center for Robotics and
Manufacturing Systems. Finally, the authors gratefully
acknowledge the support, assistance, and encouragement of
Carolyn Spivak and Al Dunlop of AT&T Bell Laboratories.
References
[1] B. Fawcett, “Applications of Reconfigurable Logic,”
Third Annual Workshop on Field-Programmable Logic
and Applications, Oxford, Sept. 1993.
[2] B. New, “Boundary-Scan Emulator for XC3000,” XAPP
Applications Handbook, Xilinx, Oct. 1992.
[3] A. Russ and C. Stroud, “Non-Intrusive Built-In Self-Test
for Field Programmable Gate Array and Multi-Chip
Module Applications”, to be published in Proc. IEEE
Automatic Test Conf., 1995.
[4] E. J. McCluskey, “Verification Testing - A
Pseudoexhaustive Test Technique,” IEEE Trans. on
Computers, Vol. C-33, No. 6, pp. 541-546, June, 1984.
[5] Optimized Reconfigurable Cell Array (ORCA) 1C Series
Field-Programmable Gate Arrays, Data Sheet, AT&T
Microelectronics, May 1994.
[6] The Programmable Logic Data Book, Xilinx, Inc., 1993.
[7] Flex 8000 Programmable Logic Device Family, Data
Sheet, Altera Corp., May 1993.
[8] “Standard Test Access Port and Boundary-Scan
Architecture,” IEEE Standard P1149.1-1990, IEEE
Standards Board, May 1990.
[9] A.J. van de Goor, Testing Semiconductor Memories
Theory and Practice, John Wiley and Sons, 1991.
[10] M.S. Abadir and H.K. Reghbati, “Functional Testing of
Semiconductor Random Access Memories,” Computing
Surveys, Vol. 15, No. 3, pp. 118-139, September 1983.
[11] P. Chen, Built-In Self-Test Configurations for Field
Programmable
Gate
Array
Logic
Blocks,
M.S.E.E.Thesis, University of Kentucky, August, 1995.
[12] C. Spivak, private communications, October, 1995.
© Copyright 2024 ExpyDoc
