Delay fault testing of IP-based designs via symbolic path modeling.
Predesigned blocks called intellectual property (IP) cores are increasingly used for complex system-on-a-chip (SOC) designs. The implementation details of IP cores are often unknown or unavailable, so delay testing of such designs is difficult. We propose a method that can test paths traversing both IP cores and user-defined blocks, an increasingly important but little-studied problem. It models representative paths in IP circuits using an efficient form of binary decision diagram (BDD) and generates test vectors from the BDD model. We also present a partitioning technique, which reduces the BDD size by orders of magnitude and makes the proposed method practical for large designs. Experimental results are presented which show that it robustly tests selected paths without using extra logic and, at the same time, protects the intellectual contents of IP cores.
Introduction
While reusable predesigned circuits called intellectual property (IP) circuits or cores are becoming
increasingly popular for VLSI system-on-a-chip (SOC) designs [1, 3, 8, 11, 12, 14, 21], they present difficult
testing problems that existing methodologies cannot adequately handle. Path delay verification of IP-based
designs is among the most challenging problems because the implementation details of the IP circuits
are hidden. This is particularly the case when the paths traverse both IP circuits and user-defined
circuits. Conventional delay fault testing methods using standard scan [6, 22], boundary scan [3, 8,
21], or enhanced scan methods [7, 9] cannot test such paths effectively. We previously proposed a method
called STSTEST [12] which can test complete paths between IP and UD circuits, but requires extra scan
logic. Nikolos et al. [16] suggest calculating the delays of complete paths by measuring the delays of partial
paths. This method appears suited to delay evaluation of a prototype circuit but is impractical for production
testing of high-speed circuits due to the difficulty of accurately measuring analog delay values.
To address these problems, we propose a delay testing method dubbed symbolic path modeling-
based testing (SPMTEST) which can directly test selected complete paths between IP and UD circuits
without using extra logic. It employs an IP modeling scheme that abstracts the information of the IP cir-
cuit's paths using a special style of binary decision diagram (BDD), and protects the intellectual content of
the IP circuits. We also present an associated ATPG algorithm that generates robust delay tests for the
paths using the symbolic IP path models.

Figure

1 shows an example design where a UD circuit UDB1 and an IP circuit IPB1 form a single
combinational block. Like many delay fault testing methods [7, 9, 13, 17, 18], we assume that to sensitize
the target paths, two test patterns are applied via an enhanced scan register R1 which uses two flip-flops in
each scan cell to hold a pair of test patterns. Complete single-cycle paths exist from register R1 to that
traverse both UDB1 and IPB1, such as the one marked by the thick solid line. Neither the IP providers nor
Extra scan register
(boundary scan or STS)
Intellectual property (IP) circuit
User-defined (UD) circuits
Fig. testing of a circuit containing IP and UD blocks with boundary scan which
can test only partial paths, or selectively transparent scan which can test complete paths.
Enhanced
scan
Enhanced
scan
the system designers can generate tests for these complete paths using conventional ATPG methods for
path-delay faults. This is because UDB1's implementation details are unknown to the IP providers, while
IPB1's implementation is hidden from the system designers. For stuck-at fault testing, extra logic such as
boundary scan registers [3, 8, 21] or multiplexers are often inserted between UDB1 and IPB1. However,
precomputed tests applied to the IP circuit via such extra logic cannot detect a delay fault involving a complete
path from R1 to R2. For example, precomputed tests applied via boundary scan in Fig. 1 can sensitize
only a partial path such as the one indicated by the thick dashed line.
To allow testing of the complete paths linking UD and IP circuits, the STSTEST method [12] we
proposed previously employs a new type of scan register called a selectively transparent scan (STS) regis-
ter. With the STS register in Fig. 1 replacing the boundary scan, any complete path like the highlighted one
can be tested. In the test mode, part of the STS register on the path is made transparent, while other parts of
the STS register hold values pre-selected to satisfy the conditions required for the path sensitization. An IP
modeling technique for STSTEST is defined in [12] that can test complete paths of a specified delay range
and protect the implementation details of the IP circuits. The overhead of the STS registers can limit their
use in high-performance or area-critical circuits. This overhead tends to be more significant in designs like
Fig. 2(a) where complete paths traverse more than one IP and UD block, and STS registers need to be
inserted between every two blocks.
The SPMTEST method proposed here and illustrated in Fig. 2(b) can test complete paths without
needing extra scan registers. As in STSTEST, we require the IP providers to supply IP models that allow
system designers to generate test vectors for complete paths. Unlike STSTEST which specifies a test cube
(a) (b)
Fig. Testing complete paths that traverse multiple IP and UD blocks using (a) STSTEST which requires
extra STS registers between every two blocks, and (b) SPMTEST which requires no extra logic.
Test
IP models
based
IP models
BDD-based
(Control)
(ALU)
(ALU)
(Control)
register
register
register
Enhanced scan
registers
for each selected path in its IP models, SPMTEST abstracts all the conditions required to compute tests for
the selected paths by means of an efficient form of BDD [2]. This symbolic IP modeling technique eliminates
the need for STS registers. To handle large IP circuits, we propose a circuit partitioning technique
that decomposes the BDDs and leads to IP models of practical size. We also present an ATPG algorithm
that acts directly on the decomposed BDDs and thus can protect the IP circuit's implementation details.
Given symbolic IP models, SPMTEST finds 2-pattern robust tests for complete paths of a specified delay
range, if the tests exist. Finally, we present a CAD tool implementing SPMTEST and experimental results
which show that SPMTEST is a cost-efficient solution for the delay testing problem of IP-based designs.
The remainder of the paper is organized as follows. Section 2 introduces the BDD-based IP modeling
procedure, while Sec. 3 describes the circuit partitioning technique for large IP designs. Section 4 presents
the ATPG procedure that computes the final test vectors using the IP models. Section 5 describes
experimental results obtained with the ISCAS benchmark circuits.
Modeling
In order to allow the system designers to generate test vectors, an IP model should specify the sensitization
conditions for selected paths in the IP circuit. First we show how we construct such a model using
BDDs for the selected paths. Then we describe a path selection scheme that yields all complete paths
whose delays exceed some specified threshold.
Symbolic path modeling: The basic idea of our symbolic path modeling approach is inspired by (1)
the conditional delay model proposed by Yalcin and Hayes [23] which employs BDDs to find a critical
path, and (2) the BDD-based path-delay fault testing method in [2]. The conditional delay model demonstrates
that a hierarchical representation of path sensitization conditions can efficiently identify many false
paths. SPMTEST also exploits hierarchical structures consisting of IP and UD blocks to identify untestable
paths and to generate test vectors.
Bhattacharya et al. [2] show that BDDs can be successfully used for delay-fault ATPG, and report
promising results for many benchmark circuits. They represent each path's sensitization conditions by a
BDD from which a test vector can be derived. To avoid the difficulty of representing the rising and falling
transition values by BDDs (which can represent only 1 and 0 values explicitly), they assume that all the
off-path primary inputs have stable 0 or 1 values. This assumption allows a BDD to represent the conditions
required to sensitize the path and avoid static hazards on the path. This assumption cannot be made
for IP modeling, however, since any primary input of the IP circuits can receive transition or hazard signals
from other blocks that drive the IP circuit's inputs. Therefore, we employ an encoding technique that represents
4each signal by 2-bit values so that any signal transitions and hazard conditions can be represented by
BDDs.
For example, Fig. 3 shows the ISCAS-85 benchmark circuit c17 regarded as an IP circuit. Suppose
we want to model the highlighted paths P IP1 and P IP2 using the robust test conditions proposed in [13]. To
test a path robustly, the following conditions on the side input values of the gates along the path that need
to be satisfied. When the on-path input has a controlling final value, the side inputs must have non-controlling
stable values; when the on-path input has a non-controlling final value, the side inputs must have non-controlling
final values with arbitrary initial values. Here we use a 7-valued logic to represent the signal
values as in [5, 11, 13]; this logic is defined in Fig. 4.
. Robust test condition for
. Robust test condition for

Figure

4 also shows how the seven values are encoded for BDD representation. A similar encoding
technique was employed earlier in a delay fault testing method based on a CNF formulation of the
satisfiability problem [5]. Here v f represents a signal's final value, while v s represents the stability of the
signal, that is, v the signal is stable. Let R(P IPi ) denote the robust test condition for path P IPi . The
robust test conditions for P IP1 and P IP2 are encoded as follows:
F
R
Fig. 3 : The ISCAS benchmark circuits c17 viewed as a small IP circuit.
R
F
F
Logic values BDD encoding
(final value v f , stability v s )
Value Interpretation
F Falling transition (0,
R Rising transition (1,
f Unknown-to-0 transition (0, X)
r Unknown-to-1 transition (1, X)
Unknown (X, X)
Fig. 4 : The 7-valued logic for robust tests and the corresponding 2-bit
encoding used for BDD representation.
. R(P IP1
. R(P IP2
Note that R(P IPi ) is constructed by ANDing all v f 's and v s 's of non-X values. In order to construct
BDDs representing R(P IPi ), the primitive logic operations AND, OR, and NOT are modified to apply to
signal values of the form (v f , v s ); see Fig. 5. The same encoding scheme is found [5]. Each encoded output
value (z f , z s ) in the tables of Fig. 5 is obtained by applying the indicated logic operations to x f , x s , y f , and y s .
For example, in the AND case, z
We apply the modified logic operations to every gate in the IP circuit recursively, starting from the
primary inputs until all BDDs representing each encoded signal are obtained. Then, for each selected path
path model is constructed by ANDing the BDDs representing each component of R(P IPi ).

Figure

6 shows symbolic path models constructed for Fig. 3 in this way. The variables
of these BDDs listed at the left are the primary inputs in the form of encoded value pairs (I if , I is ). It is
not possible to reverse-engineer the symbolic path models to recover the circuit's gate-level structure, so
this modeling method protects the intellectual content of the IP circuits. Symbolic path modeling also can
easily identify untestable IP paths a priori and exclude them from the IP model. This follows from the fact
that if P IPi is untestable, the BDD for R(P IPi ) must denote the zero function. The foregoing technique can
be easily extended to handle other delay fault test conditions by using different encoding schemes. Our
Fig. Encoded logic operations for BDD construction
z f z s
defined by
is defined by (x f , x s )
is defined by
CAD tool implementing SPMTEST can also handle the hazard-free robust test conditions [10] using a 3-
bit signal encoding scheme. We focus only on robust testing with 2-bit encoding in this paper.
The ATPG procedure which we discuss later computes tests by justifying the robust test conditions
given by the symbolic path models of an IP block B via other IP or UD blocks that drive B. Consequently,
the IP block's output functions are needed for test generation, so the IP models also contain BDDs representing
functions of O jf and O js for all outputs O j 's of the IP block. The output functions of IP blocks often
must be provided to the system designers for simulation and verification of the entire system, and are not
intellectual content for many circuits such as arithmetic circuits whose functions are well known. Finally,
for each selected IP path, we include in the IP model the following path information: (1) the input and output
terminals of the path, (2) the transition direction R (rising) or F (falling) at the path terminals, and (3)
the delay of the path. Figure 7 shows an IP model constructed for the example of Fig. 3. It consists of
Fig. representing the robust test conditions for (a) P IP1 and (b) P IP2 in Fig. 3.
R(P IP1 )(a) (b)
Branch to the high child
Branch to the low child
Branch to the low child
with complement
Fig. 7 : IP model for c17 when two IP paths are selected.
)Selected IP path information
Path
ID
I/O
terminal
I/O
transition
Delay
(ns)
BDDs for the four output functions and the two selected paths, and the associated path information. We
next describe the path selection method for constructing IP models.
STSTEST introduced a path selection method for IPB's that derives all complete paths of a certain
delay range in (UDB, IPB) block pairs. The same method is used by SPMTEST. However, SPMTEST can
be also applied to any combination of IPBs and UDBs with only minor modifications to the path selection
scheme. We first describe path selection for the (UDB, IPB) case, and then generalize to other cases.
Due to the enormous number of paths in large circuits, we only test paths whose delays exceed some
specified threshold, an approach commonly employed by delay fault testing methods [13, 22]. To test such
complete paths in (UDB, IPB), therefore, we consider all IP paths that can potentially yield complete paths
exceeding the threshold when combined with certain UD paths. Figure 8 shows an example (UDB, IPB)
pair consisting of the smallest ISCAS-89/85 benchmark circuits cs27 and c17. I k denotes the k-th input port
of IPB. We compute the path delays using the Synopsys cell library [20], and treat each path as two separate
paths with rising and the falling transitions, as in [13, 17, 18].
If the IP models just include paths that meet a certain path-length threshold, they may not yield all
required complete paths. For example, suppose only the critical IP path P marked by the dashed line
exceeds the threshold delay and so is included in the IP model. Then, the critical complete path of (UDB,
IPB) indicated by thick solid line cannot be derived from path P. To avoid such problems, we select IP
paths by assuming that all UD paths have their maximum allowable delay (slack limit), which is the delay
margin for each IPB input I k left after subtracting from the clock period the longest delay of the IP paths
starting from I k . Figure 9(a) shows the maximum allowable delays (the length of the thick arrows) for one
clock period, which is formed by positioning all the IP paths to align the longest IP paths starting from
every I k with the right end of the critical IP path. From Fig. 9(a) we select IP paths that extend beyond the
IP path threshold denoted by the dashed line; in this example P 1:6 is selected. It follows from Fig. 9(a) that
all complete paths exceeding the complete-path threshold of Fig. 9(b) can be derived from the six selected
I 2
I 4
I 1
I 0
Critical path P of IPB
F
R
R
F
Fig. consisting of the ISCAS benchmark circuits cs27 and c17.
The critical complete path
R F
R
F
F
R
R F .
. g10
R
IP paths. For example, Fig. 9(b) shows six such complete paths, which are guaranteed to be tested. This
approach yields all complete paths longer than the threshold delay determined by the clock period and the
IP path threshold delay. For convenience, we represent the IP path threshold by T IP - critical IP-path delay,
where T IP denotes a threshold factor, 0 - T IP - 1. For example, if the IP provider chooses T for the
IPB of Fig. 8, a total of paths will be included in the IP model in the form shown in Fig. 7.
Next we discuss path selection for a few other IPB and UDB combinations. The above selection
scheme for (UDB, IPB) can be modified for the (IPB, UDB) pair by reversing the IP paths in Fig. 9. Since
the IPB drives the UDB in (IPB, UDB), we position all the IP paths to align the longest IP paths ending at
every output port of the IPB with the left end of the critical IP path. Then we select IP paths whose left
ends extend beyond the specified threshold. The path selection scheme for (UDB, IPB) can also be easily
extended to the case of (UDB1, IPB, UDB2), where an IPB is surrounded by two UDBs. In this case, we
assume that all paths within the UDBs have their maximum allowable delays. We position all the IP paths
such that the longest IP paths having the same I/O terminals are aligned with the right or left end of the
critical IP path. Then we select IP paths that exceed the specified threshold.
Fig. 9 : (a) IP path selection using the method in STSTEST [12]; (b) all the complete paths corresponding to
the IP paths in (a), which also exceed the complete path threshold delay.
(a)
I 1
I 2
I 4
n1-n10-n22
n3-n11-n16-n22
Slack limits
(b)
Complete path threshold delay
Clock period for (UDB, IPB)
for UD paths
I 3
n6-n11-n16-n22
Critical IP path delay
IP path threshold delay
n3-n11-n16-n22
I 1
I 2
Clock period for (UDB, IPB)
Complete path threshold delay
I 3
n6-n11-n16-n22
UD paths IP paths
n3-n11-n16-n22
n6-n11-n16-n22
I
3 Circuit Partitioning
The fact that BDD size can explode when handling large circuits limits the applications of many
BDD-based methods [2] to control circuits or relatively small datapath circuits. In order to enable
SPMTEST to handle a broad range of IP circuits, we use circuit partitioning to reduce the BDDs to a manageable
size. Functional decomposition techniques that reduce BDD size have been previously proposed
for formal design verification [15]. Here we use a structural BDD decomposition technique that partitions
an IP circuit into a set of blocks and constructs BDDs for the partitioned blocks. This approach has the
advantage of reducing the number of paths that must be included in the IP models, since a few partitioned
paths often cover a large number of paths. We can also easily adapt existing structural ATPG algorithms to
deal with partitioned BDDs.
Symbolic models for the partitioned IP paths may not identify all untestable IP paths a priori. To
alleviate this drawback, we propose an algorithm dubbed SPM-PART that maximizes the chance of untestable
paths being identified by exploiting a property of untestable paths. A untestable path P contains a
fanout point F i and a reconvergence point R j that conflict with the robust test conditions for P. Symbolic
path modeling is guaranteed to identify P as untestable, if for every on P, all paths linking F i
and R j are in the same partition. SPM-PART partitions an IP circuit in a way that maximizes the number of
and the paths linking F i and R j contained in the same partition, while limiting the partition to
a specified size. We describe SPM-PART below.
Let N i,j be the number of fanin lines to R j that have a path from F i , and let D i,j be the distance
between F i and R j in terms of the number of levels. SPM-PART first computes for every pair
defined as N i,j / D i,j . Combining an of large G(F i , R j ) can lead to a
small partition (due to a small D ij ) that contains a large number of paths linking F i and R j . SPM-PART creates
each partition B k by adding such one at a time. It first selects an F i from the primary
inputs of IPB and inserts F i into the current partition B k . SPM-PART then selects an R j that maximizes the
sum of the G(F i , R j )'s for all the F i 's in B k that have a path to R j . It inserts into B k all non-partitioned gates
in the transitive fanin region of R j to maximize the number of paths in B k linking the F i 's and R j . If the current
partition exceeds a specified size, B k+1 is set to the current partition. In this way, SPM-PART continues
to insert the next R j 's into B k , until no R j remains. The complexity of SPM-PART including the gain factor
computation is O(N 2 ).

Figure

10(a) shows a 2-bit adder viewed as an IPB and partitioned into two blocks by SPM-PART.

Figure

10(b) shows a graph whose nodes represent the F i 's and R j 's in IPB and whose edges represent the

Figure

10(c) lists the gain factors computed for every limits of each partition in
terms of I/O line numbers is set to 3/2. With a 0 as the first F i inserted in B1, we select p 0 as R i , since p 0
yields the largest gain factor G(a 0 , partition B1 indicated by A is formed by including p 0
and its transitive fanin node b 0 . Next s 0 is selected which yields the largest gain factor G(a 0 , s 0 )+G(b 0 ,
and by including s 0 and c in , B1 now becomes the partition indicated by B in Fig. 10(b).
After including c 1 , B1 exceeds the size limit, so the next nodes are added to B2. Figure 10(a) indicates by
dashed lines the final two partitions created in this way.
Observe that in Fig. 10(a), most like the ones marked by X and the paths linking F i and
R j are contained in the same partition. In this example, the symbolic path modeling can identify all the
untestable paths such as the ones highlighted. Figure 11(a) shows the same circuit but partitioned arbitrarily
without using SPM-PART. In this case, symbolic path modeling cannot identify any untestable
a 0
c in
a 1
c out
A
Fig. partition produced by the proposed algorithm; (b) fanout-reconvergence
graph and partition steps; (c) gain values computed for every
a 0
c in
a 1
c out
(a)
(b)
(c)
a 0
c in
a 0
. s 0
c out
(a) (b)
Fig. Arbitrary partition of the 2-bit adder obtained without using our algorithm;
(b) comparison of the partitions.
Partition
type
No. of
paths
in IP
model
No. of
untestable
paths
identified
BDD
size
of IP
model
partitioning
Partition of
Fig. 10(a)
Partition of
Fig. 11(a)
paths, because for all the that make the paths untestable, F i and R j are in different partitions.

Figure

11(b) compares the unpartitioned IPB with the partitions of Fig. 10(a) and 11(a). Note that the partition
of Fig. 10(a) allows all untestable paths to be identified, so the test generation procedure needs to
be run for only 74 testable paths. On the other hand, the partition of Fig. 11(a) requires the test generation
procedure to be run for all 90 paths in the IPB. Although the BDD size reduction looks minor in this small
example, very significant reductions are obtained for larger circuits, as our experiments show.
Test Generation
Assuming that the IP models for all IPBs are constructed by the method described above, system
designers can generate test vectors using the ATPG procedure SPMTEST (Fig. 12) which is an extension
of the PODEM algorithm to handle BDDs in a block framework. SPMTEST takes symbolic models of
IPBs as inputs, and creates symbolic models for UDBs. For example, Fig. 13 shows the (UDB, IPB) pair of
Fig. 8 where each block is treated as a black box specified by its symbolic model. Let P Bi denote a partial
path derived from (partitioned) block B i . SPMTEST selects a complete path P B1 -P B2 -P Bn that exceeds
the complete path threshold delay derived by the method describe in Sec. 2. For example, Fig. 13 shows
one such complete path P UD1 -P IP1 . To speed up the test generation, SPMTEST simplifies the BDDs of the
symbolic models by setting v primary input, and v
(Note that enhanced scan can assign stable values to the primary inputs.) For example,
Fig. 13 shows such values assigned for the case of P UD1 -P IP1 . Figures 14(a) and (b) show IPB's BDDs
Symbolic IP models
Create symbolic models
Select a complete path P B1 -P B2 -P Bn
Simplify BDDs by assigning initial input values
BDD-based PODEM algorithm
Select objective: one input variable of P Bi
Backtrace to a target primary input and assign a value
Evaluate BDDs using cofactor-based implication
Backtrack, if any R(P Bi
Repeat until - i =1:N R(P Bi
Repeat until all target complete paths are tested
2-pattern test cubes
Fig. test generation algorithm
UDBs
from IP providers
substantially simplified with these assigned values; compare with the original BDDs in Figs. 6(a) and 7,
respectively.
Next the BDD-based PODEM algorithm attempts to satisfy the condition - i=1:N R(P Bi which is
represented by conjunction of the BDDs for all P Bi 's symbolic path models. For each R(P Bi ), it first selects
as an objective support variable s i from R(P Bi )'s maximal cube. The backtrace step then finds a primary
input as follows: for the output function f i corresponding to s i , select f i 's support variable s i from f i 's maximal
cube; repeat this step until s i is a primary input. In the example of Fig. 13, first we select n6 as an
objective from R(P IP1 )'s maximal cube n3 f n3 s n6 f next we select g0
cube stop backtracing, since g0 f is a primary input. The next phase of SPMTEST
is a ternary implication step that evaluates all the BDDs with their variables assigned the values 0, 1, and
X. (Note that the initial values of all the BDD variables are X.) We implement ternary implication by computing
the cofactors of a BDD with respect to its non-X input values. If a resulting cofactor is constant 1
(0), the BDD evaluates to 1 (0); otherwise, the result is X. For example, given input values n3 f n3 s n6 f
1X0X, the cofactor of R(P IP1 ) with respect to n3 f n6 shown in Fig. 14(c). Since this cofactor is not
constant, R(P IP1 ) is found to be X. These steps are repeated until - i=1:N R(P Bi test
cube is obtained. For the example of Fig. 13, the test cube
Fig. 13 : The (UDB, IPB) pair of Fig. 8 represented by black boxes.
F
F
Simplified BDDs for (a) the output functions of IPB and (b) the symbolic path model of P IP1 in
Fig. 13; (c) the cofactor of (b) with respect to n3 f n6
Cofactor of
(c)
(b)
(a)
For each complete path, SPMTEST either computes a robust test or concludes that the path is
robustly untestable. Since it acts on a structure consisting of multiple (partitioned) blocks in symbolic
form, SPMTEST can handle any combination of IPBs and UDBs without needing extra scan registers.
5 Experimental Results
We have implemented the SPMTEST method in a CAD tool composed of 17,000 lines of C++ code
and an existing BDD package CUBDD [19]. We have applied it to a number of benchmark circuits, including
ISCAS-85, ISCAS-89 (combinational versions), and datapath circuits, that have been artificially paired
as UD and IP blocks. Figure 15 compares the symbolic IP models constructed by SPMTEST with and
without circuit partitioning. The first column lists the benchmark circuits regarded as IPBs, while the next
three columns give the circuit partitioning results. For the specified limits on the number of I/O lines of
each partition, the number of resulting partitioned blocks and the CPU time spent for partitioning are
listed. Next, the results of symbolic IP modeling using the partitioned IP circuits are listed for the specified
IP path delay threshold factor T IP . The untestable path identification ratio UPI is given for circuits that have
a large number of untestable paths. UPI is defined as the number of untestable IP paths identified by the IP
models divided by the number of all untestable IP paths. Then the BDD size in terms of the number of
Fig. modeling with and without circuit partitioning.
Bench-
mark
circuit
Circuit partitioning for
symbolic IP modeling
Symbolic IP modeling
With partitioning Without partitioning
I/O
limits
No. of
partitions
CPU
time
Untestable paths
identification (UPI) BDD size
CPU
cs1423 20/15 14 1.43 0.8 70.8% 10425 4.8 541812 ~2 hours
hours
Exploded >12 hours
c2670 25/25 17 2.57 0.8 93.7% 44425 29.69 Exploded >12 hours
c3540 25/25 26 14.67 0.9 72.9% 68502 62.86 Exploded >12 hours
Exploded >12 hours
c7552 25/25 38 20.61 0.8 56.1% 164055 171.2 Exploded >12 hours
nodes, and the CPU time spent for IP modeling are listed. The last two columns list the results of symbolic
IP modeling without partitioning, in which case UPI is 100%.
In all cases, IP modeling with partitioning finishes within reasonable CPU time with relatively small
BDDs. For example, modeling the largest ISCAS-85 circuit c7552 is completed in 171 seconds with BDDs
containing a total of 164K nodes. On the other hand, IP modeling for most large circuits without partitioning
either takes several hours or cannot finish due to the excessive BDD size. It is well known that BDDs
representing larger ISCAS-85 benchmark circuits such as c2670 and c7552 tend to explode, so BDD-based
methods like that of [2] have not been applied to these circuits. Furthermore, IP modeling with partitioning
can identify a large number of the untestable paths in most circuits. For example, cs9234's IP model identifies
99.9% of untestable paths with 20 partitioned blocks, which indicates that the proposed partition
algorithm is highly efficient. Some low UPI ratios for circuits like cs1196 can be explained by their structural
property that the separation of most fanout-reconvergence pairs is very large, so it is difficult to contain
such pairs within the same partition.

Figure

gives the results of applying SPMTEST to a number of (UDB, IPB) pairs whose IP models
appear in Fig. 15. Although we limit our attention to (UDB, IPB) pairs, other combinations of IPBs and
UDBs show similar results. The first two columns list the (UDB, IPB) pairs tested. The next two columns
Circuit pair UDB partition results UD/IP pair test results
UDB IPB
I/O limits
of each
partition
No. of
partitions
Complete
path
threshold T C
No. of complete paths
Tried for test
generation
Robustly
tested
28 19.22
cs1238 shift32 20/15 23 0.801 343 150 91.92
shif32 cs1238 30/30 8 0.860* 347
shift32
shift16 c5315 25/25 2 0.839 4118 558 1491.3
shift32
Fig. test generation results for benchmark circuits configured as (UDB, IPB) pairs.
show the symbolic modeling results for the UDBs. The next column lists the complete path threshold delay
factor T C for each (IPB, UDB) pair. Given T IP and the clock period T clock , T C is determined by T
D IP (1- T IP ) / T clock , where D IP is IPB's critical path delay; see Fig. 9. All testable complete paths exceeding
the threshold delay T C - T clock are guaranteed to be tested. In the cases indicated by * in column T C , we
have chosen values of T C smaller than the values calculated in the above way, because either the (IPB,
UDB) pairs have too many complete paths, or T IP = 0. The next column lists the number of complete paths
tried for test generation and the number of complete paths robustly tested. In most cases, the tried complete
paths are much fewer in number than all complete paths meeting T C , because many untestable paths are
eliminated a priori in the IP modeling step, which speeds up test generation. The fact that only a few complete
paths are robustly tested in many cases is not surprising, because the artificial (functionally meaning-
less) connections between UDBs and IPBs tend to make a large number of complete paths untestable. The
time listed in the last column of Fig. 16 is reasonable for most cases except the circuit pair containing
c2670. This large ISCAS-85 benchmark circuit is well known to have very few robustly testable paths due
to its large amount of reconvergent fanout, and so path delay testing for it is inherently very difficult.
In STSTEST [12], some untestable complete paths are robustly testable due to the STS registers,
whereas in SPMTEST, only robustly testable complete paths are considered as testable and counted in Fig.
16. Therefore, the results of SPMTEST cannot be directly compared with those of STSTEST. Comparison
with other methods is also difficult, since most delay testing methods are not aimed at IP-based designs; in
the case of [16], no experimental results are provided.
6 Conclusions
We have presented the SPMTEST method for path delay testing of designs containing IP cores, a
difficult problem not addressed by existing methods. SPMTEST can test complete paths linking IP and
user-defined blocks via a symbolic modeling technique that abstracts an IP block's paths in a compact
form. Hence it does not require extra scan logic, an advantage over STSTEST. The ATPG algorithm in
SPMTEST generates tests for the complete paths using only symbolic models, and hence protects the
implementation details of the IP blocks. Our experimental results show that for all the benchmark circuits
chosen, SPMTEST constructs compact symbolic IP models, and robustly tests all testable complete paths
of a specified delay range. Therefore SPMTEST appears to an ideal approach to path delay testing of IP-based
designs. SPMTEST has a limitation that some complex circuits such as multipliers can require IP
models of excessive size. To address this problem, we are investigating alternative symbolic modeling
approaches.


--R

"Scan Chain Design for Test Time Reduction in Core-Based ICs,"
"Test Generation for Path Delay Faults Using Binary Decision Diagrams,"
"Hierarchical Test Access Architecture for Embedded Cores in an Integrated Circuit,"
"On Variable Clock Methods for Path Delay Testing of Sequential Circuits,"
"A Satisfiability-Based Test Generation for Path Delay Faults in Combinational Circuits,"
"Robust Delay-Fault Test Generation and Synthesis for Testability Under a Standard Scan Design Methodology,"
"A Partial Enhanced-Scan Approach to Robust Delay-Fault Test Generation for Sequential Circuits,"
"Test Methodology for Embedded Cores which Protects Intellectual Property,"
"Design for Testability: Using Scanpath Techniques for Path-Delay Test and Measurement,"
"Synthesis of Robust Delay-Fault-Testable Circuits: Theory,"
"High-Coverage ATPG for Datapath Circuits with Unimplemented Blocks,"
"Delay Fault Testing of Designs with Embedded IP Cores,"
"On Delay Fault Testing in Logic Circuits,"
"Testing ICs: Getting to the Core of the Problem,"
"Partitioned ROBDDs-A Compact, Canonical and Efficiently Manipulable Representation for Boolean Functions,"
"Path Delay Fault Testing of ICs with Embedded Intellectual Property Blocks,"
"NEST: A Nonenumerative Test Generation Method for Path Delay Faults in Combinational Circuits,"
"Advanced Automatic Test Pattern Generation Techniques for Path Delay Faults,"
CUDD: CU Decision Diagram Package
Synopsys Inc.
"Testing Embedded Cores Using Partial Isolation Rings,"
A Path-Delay Test Generator for Standard Scan Designs,"
"Hierarchical Timing Analysis Using Conditional Delays,"
--TR
Robust delay-fault test generation and synthesis for testability under a standard scan design methodology
Hierarchical timing analysis using conditional delays
A satisfiability-based test generator for path delay faults in combinational circuits
Partitioned ROBDDsMYAMPERSANDmdash;a compact, canonical and efficiently manipulable representation for Boolean functions
Path delay fault testing of ICs with embedded intellectual property blocks
Logic Synthesis and Verification Algorithms
Testing ICs
Test Generation for Path Delay Faults Using Binary Decision Diagrams
Fastpath
A Partial Enhanced-Scan Approach to Robust Delay-Fault Test Generation for Sequential Circuits
Design for Testability
Scan chain design for test time reduction in core-based ICs
Testing embedded-core based system chips
High-coverage ATPG for datapath circuits with unimplemented blocks
Testing Embedded Cores Using Partial Isolation Rings
1.1 Test methodology for embedded cores which protects intellectual property
Delay Fault Testing of Designs with Embedded IP Cores
automatic test pattern generation ATPG;binary decision diagram BDD decomposition;system-on-a-chip SOC;delay fault testing;intellectual property IP core testing