Structural Fault Testing of Embedded Cores Using Pipelining.
The purpose of this paper is to develop a global design for test methodology for testing a core-based system in its entirety. This is achieved by introducing a bypass mode for each core by which the data can be transferred from a core input port to the output port without interfering the core circuitry itself. The interconnections are thoroughly tested because they are used to propagate test data (patterns or signatures) in the system. The system is modeled as a directed weighted graph in which the accessibility (of the core input and output ports) is solved as a shortest path problem. Finally, a pipelined test schedule is made to overlap accessing input ports (to send test patterns) and output ports (to observe the signatures). The experimental results show higher fault coverage and shorter test time.
Introduction
Progress in deep submicron VLSI technology enables the integration of large predefined macros or cores
together with user defined logic (UDL) into a single chip. This leads to a design paradigm shift from
single ASIC design to system-on-chip design with full scale leverage of third-party intellectual property
(IP)[BhGV96][De97]. There are several advantages of core based design such as reduction in the overall system
design time, productivity increase, accelerating time-to-market, and increasing competitive superiority.
Design and test of core-based systems is a very important and challenging problem facing the semiconductor
industry for the next several years. A major difficulty concerns accessibility of embedded cores from the I/O
terminals of the system. This entails mapping of the stand-alone test requirements, provided by the core
vendor, into the embedded cores. The basic technique suggested by many R&D groups is to access each
embedded core for testing in isolation from the others [KoWa97, Vsi97, BhGV96]. However, there are a
number of disadvantages with the isolation approach. Isolation testing does not test the system-on-chip as a
whole, for example it does not address the testing of interconnects and interfaces between cores. It does not
consider the interaction of cores for testing such as the effect of testing one core on surrounding cores, or vice
versa (the surrounding cores also may affect the core under test). Implementing protection safeguards will be
very costly increasing the test overhead of the isolation method even further [ToPo97].
1.1 Background
Loosely speaking, a core is a highly complex logic block which is fully defined, in terms of its behavior, also
predictable and reusable [ChPa96]. Cores are distinguished into several categories in terms of design flexibility,
IP protection, test development, programmability and other characteristics. Soft cores are reusable blocks in
terms of synthesizable RTL description. Firm Cores are reusable blocks supplied in netlist of library cells
and for a range of technologies. Finally, Hard cores are reusable blocks optimized in terms of power and
performance, and supplied in layout form for a specific technology. Clearly, soft cores are the most flexible
type but hard cores provide most IP protection. From test development viewpoint, cores can be mergeable
or non-mergeable. Mergeable cores use an expandable test scheme and thus they can be merged with other
mergeable cores so that the composite structure is tested as a whole. In terms of programmability, cores can
be characterized in fully programmable (e.g. microprocessor cores), partially programmable (e.g. Application-Specific
Integrated Processors - ASIP), and little or non-programmable (e.g. ASIC cores).
There are a number of test methods that apply to ASIC cores based on Design for Test (DFT) techniques,
e.g. Scan, BIST, ScanBIST, Test points, or without DFT using precomputed testing. To facilitate test
integration there are a number of preliminary proposals from the industry, e.g using test sockets, Macro test
or core-level boundary scan [KoWa97]. We remark that the above issues are not decoupled of each other, in
fact they are related and can have significant effect on system testing. Also, the above issues apply to both
soft and hard cores. However, hard cores limit the flexibility of the designer significantly for system-level test
solutions.
The basic testing strategy suggested by industrial groups for system-on-chip is to test each embedded core
one by one rather than the system as a whole. This strategy requires accessibility, i.e. controllability and
observability of each core I/Os from the system I/Os. There are number of core isolation techniques proposed
[ImRa90] to ensure accessibility and some of them may provide good match to a particular core's internal test
method:
MUX-based isolation of each core mapping precomputed tests,
ffl A boundary scan type of approach accessing the cores within the system-on-chip - this can apply to
cores with embedded Scan or BIST DFT.
ffl A test wrapper or collar DFT hardware inserted for isolation,
In isolation method, a global BIST controller is usually employed to test schedule cores with embedded
BIST structures to shorten the test time. A test bus has also been proposed to affect accessibility. All of these
techniques proposed have a number of disadvantages. They may incur significant overhead of isolation-related
test structures. Some performance and possibly power consumption penalty is also incurred due to these
structures. Moreover, the isolation techniques do not address testing the system as a whole. Specifically, the
faults in the interfaces (interconnects, and user logic) between cores remain undetected.
The above shortcomings of isolation techniques motivate a coordinated approach to testing system-on-chip.
The basic goal is to test the system as a whole, this means testing the cores themselves as well as testing their
interface. Any type of cores in the system (e.g. soft, hard, etc.) for which a test data set is available (predefined
or deterministically/empirically computable) can be handled by our method. The main contribution of our
work is twofold. First we define the "bypass" for each core by which the data can be transferred from a core
input port to the output port without interfering with the core circuitry itself. Since the test data travel
in the existing interconnections, the core interface are thoroughly tested. Second, we model the core-port
accessibility problem as finding the shortest path in a directed weighted graph and minimize the testing time
by overlapping the time consumed to access paths. Conceptually, our method is a generalization of the scan
approach at the system level by allowing the use of system interconnects, with various bit widths, for test data
distribution and signature collection.
This paper is organized as follows. Section 2 presents the bypass mode and test overhead cost. Section
3 models the accessibility problem as finding the shortest path in a directed graph. Section 4 discusses the
algorithm to overlap execution of those paths to minimize the test time and details a design example step by
step. The experimental results are in Section 5. Finally, the concluding remarks are summarized in section 6.
Using Bypass Mode
2.1 Core Environment
We distinguish faults with respect to the core environment. Given Core A, by definition, the environment of
Core A is all the input/output connections from/to primary inputs/outputs and other cores in the system.
Using ticker lines, we have shown the environment of Core 1 in the system pictured in Figure 1.
System
Primary
Inputs
System
Primary
Outputs
Figure

1: Environment of Core 1.
We also differentiate between isolated core and isolated core environment. Isolated core refers to the core
itself (shaded core in Figure 1 for example), without any other components of the system, which is isolated
from the system by a mechanism, such as multiplexors or tri-state buffers and so on. On the other hand, as

Figure

1 shows for Core 1, the isolated core environment includes the core and all connections to/from it,
all isolated by an appropriate mechanism. This distinction plays an important role in our discussion since
for example a fault in the interconnect of a core can not be captured in isolated core testing while it may be
caught when testing the isolated core environment.
2.2 Input/Output Test
The overall objective is to use the existing wires and topology of the system to establish a path to carry test
data between two test points in the system, called source and sink. In core testing, there are two types of test
paths, that is input test path to access core input ports from system primary inputs and output test path to
access core output ports from the system primary outputs. Figure 2(a) shows a core under test (Core
these two paths and their corresponding source and sink. It also shows a general view to establish a route
between two test points using the existing wires. In Figure 2(b) the blowup picture of a core in input/output
test path (Core k) is shown. We symbolically showed that the inputs are bypassed to the output without
interfering the core circuitry which are used in the normal mode. We will shortly elaborate on matching
the bit widths (packetization) and the real implementation of bypass circuitry. The basic idea of having the
bypass mode for each core is to have an independent route around a core to carry test data (e.g. predefined
test patterns or core signatures) between port i (m i k bit wide) and port j (n j k bit wide) of that core (Core k).
Our goal is to establish the shortest path (fastest route) to carry the packets of test data between source
and sink. Note that by this formulation, accessibility of the core inputs from system primary inputs and of the
core outputs from system primary outputs, are similar problems, i.e. identifying the shortest path between
source and sink.
(Under Test)
Source
Source Sink Sink
Input Test Path Output Test Path
b_in b_out
Bit length of test data
System
Primary Output
System
Primary Input
(a)
(b)
Bit-Match
port j
port i
i_k j_k

Figure

2: Test paths: (a) Input/output test paths; (b) A typical core in test paths.
The important benefit of the bypass is to take advantage of the existing connections among the cores and
the existing wires to transfer multi-bit data from source to sink. This, in the worst case, will be equivalent to
the conventional scan which transfers the patterns serially using a separate routing in the system. Considering
the multi-bit interconnections among the cores and the fact that we do not use a separate scan chain, we
expect the average case to be quite superior in terms of time and comparable in terms of hardware overhead.
The "bypass" mode that we use here is different from identity mode (I-mode) introduced by Abadir and
Breuer [AbBr85] in many ways. In [AbBr85] the authors define the I-mode and I-path for RTL components
(e.g. ALU's, MUXes and Registers) to transfer data unaltered from one port to another. For example, for
an adder having one data value as zero creates the I-mode. In our approach, we have physical bypass routes
through which the data is transferred from one point to another. Additionally, the I-mode and many other
mode definitions, including transfer mode (T-mode) and sensitized mode (S-mode), all control components
to efficiently realize one form of partial scan test. These modes and I-paths are used for transmitting data
from scan registers to the input ports of a block under test and transmitting signatures to scan registers to
be shifted out. Our approach does not use scan registers at all. It offers totally different test methodology
by allowing the use of system interconnects, with various bit widths, for test data distribution and signature
collection.
We would like also to point out that many core providers, such as Philips [MABD98][Mari98], have already
devised the bypass mode as a part of P1500 core test standardization. Such standard is well justified by
providing considerable flexibility to the designer with a reasonable cost. Additionally, the bypass mode can
be easily incorporated within soft and hard cores by core providers [MABD98]. If a core does not come with
bypass mode, this mode and the required bit-match circuitry (explained in this section) should be added
externally by a designer for the benefit of testing.
2.3 Packetizing Technique for Data Transfer

Figure

2(a) clearly shows that the bit width of inputs/outputs of cores change in a path between two test
points. This requires sort of bit matching. Let's assume that we need to transfer a b bit pattern between
source and sink.
In general, to transfer b bit test data from port i (m i k bit) to port j (n j k bit) of Core k we need to packetize
data (to match the available bit width) and send it in several iterations. For example, a core with a
bit input port test data in 4 iterations. We assume that data packetization and transfer
is synchronized with the system clock. Note also that from Core k point of view it does not matter how b-bit
data gets to its inputs. If they all come at once (e.g. or through many packets (e.g. b ?
number of iterations (cycles) that Core k consumes to bypass data will not change. However, it will affect the
n/m Stages
S/P circuit (m <= n)
m-bit
m-bit
m-bit

Figure

3: Serial-to-Parallel (S/P) bit match circuit.
scheduling of bypass activities. Before we discuss this we present the cost (hardware and time overhead) due
to bypass and bit matching circuit. For simplicity, we have not shown i k and j k subscripts in the bit width
variables.
2.3.1 Case 1: Input - Output (m - n) - Serial-to-Parallel

Figure

3 shows the first type of the bit-match circuit required to assemble a larger pattern from different
packets of data. The circuit consists of d n
e stages of cascaded m-bit registers (e.g. D flip flops) controlled by
the same clock. The circuit, which is like a shift register bank of m bits, has a serial-to-parallel (S/P) behavior
whose worst case (in terms of time) corresponds to equivalent to the traditional scan-in discipline.
Note that the d n
e packets of m bit data will be parallelized to n bit in d n
cycles. For a b-bit data
we need to iterate d b
times (overall d n
Briefly, based on this implementation, to
bypass b-bit data from an m-bit input port to an n-bit output port of a core we have the following cost values:
Time Cost: d b
Area
(1)
Where DFF denotes a D-type flip flop which is one possible implementation of 1-bit register. These equations
clearly shows that depending on b the participating core may spend less or more time in bypassing data and
some of the output wires (out of n) may not be needed. For example, suppose the
data is transferred in 1 cycle using two out of eight available output wires. If the data is transferred in
8 cycles using all eight wires.
2.3.2 Case 2: Input ? Output (m ? n) - Parallel-to-Serial

Figure

4 shows the second type of the bit-match circuit required to disassemble a large pattern to different
packets of data. The circuit consists of n stages of parallel d m
multiplexors and 1-bit registers
(e.g. D flip flops) controlled by the same clock. The circuit has a parallel-to-serial (P/S) behavior whose worst
case (in terms of time) corresponds to equivalent to the traditional scan-out discipline. Multiplexors
need dlog
e)e bit for select lines. Since the actual data to be transferred depends on b we assumed a
self-starting counter (controlled by the test controller) controls the number of iterations actually needed.
Note that the d m
e packets of n bit data will be produced in d m
clock cycles. For a b-bit data we need
to iterate d b
Briefly, based on this implementation, to bypass b-bit
data from an m-bit input port to an n-bit output port of a core we have the following cost values:
m/n
m/n
m/n
Log m/n
Stages
P/S circuit (m > n)
1-bit
1-bit
1-bit
Counter
Self-starting

Figure

4: Parallel-to-Serial (P/S) bit match circuit.
Time Cost: d b
Area
(2)
Again depending on b the participating core may spend less or more time in bypassing data and some of
the input wires or MUX inputs (out of m) may not be needed. For example, suppose 2. If
the data is transferred in 1 cycle using two out of eight available input wires. If the data is
transferred in 8 cycles using all eight wires.
Equations 2 and 1 can be joined together as follows:
Time Cost: d b
minfm;ng
e cycles
Area
2.3.3 Complete Bypass Circuitry
In addition to the S/P or P/S bit match circuit, the complete bypass circuitry includes tri-state buffers and
few additional logic gates to control the core activities as shown in Figure 5. Tri-state buffers are needed to
protect the core when it bypasses data. This is a safeguard mechanism to ensure that in bypass mode the core
does not receive any new data and so does not change the state.
Note that many input ports can be bypassed to a single output port but one at a time. Logically speaking
we have
1. Although in Figure 5 we showed the bypass circuitry for bypassing port i to
port j only, "\Delta \Delta \Delta" shows that we may have additional bypass routes. This will be decided by the shortest path
algorithm that we will explain in section 3. In summary, any new routes to bypass an input port to port j
adds, one AND gate, one buffer and one entry to the NOR gate. The introduction of the glue logic
among cores in order to bypass test data may slightly degrade the timing characteristics of the core due to its
additional delay. In our experiments, using 0.8-micron CMOS library in the COMPASS Design Automation
tool [Comp93], this additional delay was less than 3.5 nano-second.
(S/P or P/S)
Bit Match
(Port
port
3-State Buffer
Enable
Core k with port i to port bypass circuit
BUS
(Port i)
Input
stop_k

Figure

5: Core bypass circuit (only port i to port j bypass is shown).
Mode stopk bypassk Function of Core k
Run Bypass

Table

1: Different modes of each modified core.
When bypass the core accepts the inputs and forwards the output to the output port. The core
performs its functionality in this mode, thus we call it "normal mode". When core is under test (even in
still it has to perform its normal functionality. bypass on the other hand, disconnects the
input to the core and bypasses data to the output port based on the selected route determined by bypass ij k .
The test controller has to make sure (by
there will not be any conflict of bypassing different input ports to one output port simultaneously. Signal
allows the global "clock" to reach the core and if stop masks the clock and so the core does
not leave its present state. This signal can be used in interactive testing to freeze the system temporarily to
read out the core outputs. This issue is not pursued in this paper. Note that, for the purpose of the normal
or bypassing operations we could have considered bypass . However, we intentionally separated them
for each core to provide the capability of bypassing data even when the core is under test. By doing so, we
will be able to bypass data through Core k to test other cores even when Core k itself is under test. This will
reduce the overall test time specifically when the application test time for a core is too long. We will clarify
this later in section 4. Table 1 summarizes the operation modes.
2.4 Cost Calculation for Source-Sink Paths
In the previous section we presented two cost functions for time and area (see Equation 3) of the bypass
circuitry pertaining to single cores. In this work we decided to focus only on the test time optimization. Other
heuristics can be proposed based on the area cost to look at the system testing from another angle.
Based on Equation 3, when core k participates in a test path (by bypassing data between
and test data between source and sink its time overhead will be proportional
Source
(1st test point)
(2nd test point)
ij_k
b: bitwidth of test data (input pattern OR output signature)
Cycles
i_k j_k

Figure

The pipeline-like structure for each source-sink path.
Cycles
Cores
(a)
Char.
Interface Cost: High
Cycles
Cores
(c)
Char.
Interface Cost: Low
Cycles
Cores
(b) C2
. Char. Function: 2(2C1
Interface Cost: Medium
Source
(1st test point)
(2nd test point)

Figure

7: An example of bypass scheduling.
e cycles. However, the distribution of its -cycle activities is another issue. The
whole path, as shown in Figure 6 is similar to a pipeline system with N stages in which each stage requires
cycles. The difference, however, with conventional pipelines is in the scheduling method. In conventional
pipelining [Ston90], we define the pipeline clock period to be equal to the slowest stage delay and then schedule
the activities accordingly. In our problem, we don't want to devise too many registers in the interface between
cores to pile up all data packets. Instead, we have to implement an innovative mechanism by which the
bypassing is performed as soon as a packet of the appropriate size is ready.
To make this point clear let's consider the example of Figure 7 in which the sink is an input port of a core
under test and requires a test data. There are three cores in the source-sink path with time cost
of 4, 4 and 2, respectively. These cost values correspond to the time overhead required to packetize (serial
to parallel or parallel to serial) the test data. For example, 16-bit test data would be dis-assembled into four
packets (of 4-bit each) in 4 cycles to transfer through Core 1. Three bypass scheduling choices are shown.
We used space-time table similar to the reservation table [Ston90] in pipelining. Each row corresponds to
a core and each column corresponds to a time step. An entry (C1, C2 or C3) in the table shows that the
corresponding core is bypassing a packet of data in that cycle. For example, in all three schedules shown in
this figure Core 1 bypasses a packet of 4-bit data in the first four cycles. In Figure 7(a), we are not taking
advantage of the pipeline-like structure at all. Activity of one core starts when the previous one is finished.
More importantly, we need an expensive hardware interface between cores to pile up all packets (at most four
packets of 4-bit data) of data before sending it to the next core in the path, obviously a bad choice. Figure 7(b)
pictures a case that we need cheaper interface (at most two packets of 4-bit data) and it consumes 7 cycles.

Figure

7(c) pictures the superior choice which minimizes the cost (e.g. registers used anyway in bit match
circuits) and the data transfer time into 6 cycles. We will shortly show that finding such optimized schedule is
possible by constructing the characteristic function of the path and factorizing it as much as possible starting
from the outside without changing the order of core variables. These functions are shown also in Figure 7.
From above argument and example, it's clear that for a given shortest path the bounds for total bypass
scheduling time for a path consists of N cores are:
Upper Bound:
e cycles
Lower
where i and j are assumed to be single specific input and output ports of Core k, respectively, through which
data is bypassed.
2.4.1 Path Characteristic Function
The bounds presented in equation 4 can be used as data transfer time evaluation heuristics to identify the
shortest path between two test points. Although, the upper and lower bound may suggest different solutions.
For example, suppose there are two paths between a source and a sink. The first path has four cores with
's equal to 4, 4, 3 and 3. The second path has three cores with 's equal to 6, 1 and 1. The upper
bound selects the second path as shortest (cost of 6 compared to 4 while the
lower bound heuristic chooses the first path as the shortest (cost of 4 compared to 6
Briefly speaking, the overall time cost of bypass scheduling depends on the time distribution of activities
among cores. This example shows that we need a mechanism to evaluate the actual time needed for bypass
scheduling when the data is packetized based on the available bit widths and transferred from one core to
another. This is needed not only for overall time evaluation but also to have the complete bypass schedule for
the test controller in test session to tell cores how to behave. To do this, we defined the path characteristic
function (pcf).
The pcf is written by starting from
then factorizing the coefficients starting from the
outmost possible factor and continuing inside. Any other type of factorizing would lead to different sub-optimal
schedule. In the example of Figure 7 we start from equation 4C1 This corresponds to
the schedule of Figure 7 (a). We interpret each "+" in the pcf as sign of sequential activity. So, the function
here means, first Core 1 has to bypass data for 4 cycles, then Core 2 bypasses data for 4 cycles, and finally
data for 2 cycles. If we factorize 2 out to become 2(2C1+2C2+C3) the pcf corresponds to the
schedule of Figure 7 (b). Note that the factor out of the parenthesis reflects the number of repetitions of that
sequencing, each starts p cycles after another where p is the largest coefficient inside the parentheses (2 for
this pcf). Finally, if we continue factorizing the terms to: 2(2(C1 +C2)+C3), the pcf corresponds to Figure
7 (c) which consumes less time (6 cycles) and requires cheaper interface. According to 2(2(C1
suggests a schedule in which Core 2 bypasses data after Core 1. This sequence is repeated twice followed by
bypassing data by Core 3. Finally, the whole thing is repeated twice. Briefly, the general formula for a pcf
function is:
I
Note that in this function superscript r denotes the level factorized in the function. R r is the coefficient
outside of the parenthesis after factoring it out and f
I are the factorized terms inside the rth
f r

Table

2: Example of pcf recursive formula.
level of parenthesis. The form of the inner-most terms will be as f 0
similar to 2C1 or C3 terms
appeared in example of Figure 7. The following recursive formula is a simple way of computing the overall
scheduling time (T (f r )) based on the pcf function:
I
As an example, consider the pcf corresponding to the example of Figure 7 (c), which is 2(2(C1+C2)+C3).

Table

shows how we get T (f r as the overall scheduling time:
Graph Modeling and Shortest Path Problem
Our objective is to model the port accessibility of cores within a system as a directed weighted graph in which
the shortest path between any two points (called source and sink) reflects the fastest route to transfer packets
of data between those two points. From testing perspective, with such model we can find the fastest route to
transfer test data (predefined or random pattern) from the system primary inputs to any of the core input
ports. Similarly, we can find the fastest route to transfer test data (signature) from any of the core output
ports to the system primary output.
Equation 3 defines the cost associated with bypassing data from P ort i to P ort j of a core. So, in our graph
modeling, a node corresponds to a port and an edge corresponds to the interconnects between ports or the
bypass possibilities. Those edges reflecting the bypass choices form a bipartite subgraph for each core whose
cost (weight) will be determined based on Equation 3. The cost of an edge corresponding to the bypass delay
shows the time required to transfer the packetized data from one point to another. The time cost of the
existing interconnections between cores is assumed to be zero since no additional circuit/delay for packetizing
or transfer-control is needed.

Figure

8(a) shows a system, made of four cores with different ports and bit widths, under test. For
consistency, we showed the test pattern generator (TPGR) and signature analyzer (MISR) also as cores. The
system has four cores, two primary inputs (going to Core 1 and Core 4) and three primary outputs (from Core
2, Core 3 and Core 4).

Figure

8(b) shows the corresponding Core Bypass Graph (CBG). Recall from Equation 3 that the time cost
depends on the bit width of test data (b) that we desire to transfer. So, depending on the bit width of test
data (b) different cost values should be used in finding the shortest paths. As an example, in Figure 8(b) near
each edge we have shown two cost values. The cost values outside parenthesis are t ij
e
showing the time overhead to transfer 8-bit test data. Similarly, the cost values inside parenthesis are t ij
TPGR MISR1616816816168164 Sink
(a)
Global
Global
Source
(b)
TPGR MISR
Time Cost:
Global
Global Source

Figure

8: A core-based system: (a) Bit widths; (b) The CBG graph.
for
repeat f
Select an unmarked vertex vq such that sq is minimal;
Mark vq
foreach(unmarked vertex
until (all vertices are marked);

Figure

9: Dijkstra Algorithm
d
e reflecting the time overhead to transfer 16-bit test data. All edges without a cost value
correspond to the existing interconnect between cores and are assumed to have time cost of zero because if we
ignore resistance and capacitance of wires, any packet of data will be transferred almost immediately.
As for the shortest path algorithm itself, there are many well-known solutions proposed in the literature,
graph theory and operation research texts. Some of them are, Bellman, Dijkstra Bellman-Ford and Liao-Wong
algorithms [DeMi94] [BoMu76] whose running time is between O(n 2 ) to O(n 3 ), where n is the number of nodes
or edges, and their capability is between finding single shortest path to finding the shortest path between all
pairs. In our work, we have used Dijkstra algorithm which is a greedy algorithm providing an exact solution
with computational complexity of O(jEj+jV jlogjV and jEj are total number of nodes and
edges in the graph, respectively. This is one of the fastest among such algorithms. Cycles are also considered
in the Dijkstra Algorithm.
The pseudocode of the algorithm is shown in Figure 9. The algorithm keeps a list of tentative shortest
paths, which are then iteratively refined. Initially, all vertices are unmarked and fs
Thus, the path weights to each vertex are either the weights on the edges from the source or infinity. Then,
the algorithm iterates the following steps until all vertices are marked. It selects and marks the vertex that is
head of a path from the source whose weight is minimal among those paths whose heads are unmarked. The
corresponding tentative path is declared final. It updates the other (tentative) path weights by computing the
minimum between the previous (tentative) path weights and the sum of the (final) path weight to the newly
marked vertex plus the weights on the edges from that vertex. Details can be found in many graph theory
and synthesis books [BoMu76] [DeMi94].
Our shortest test path algorithm is summarized in Figure 10. The algorithm first constructs the CBG
graph and finds the time cost values corresponding to the edges in CBG. Then, it uses the Dijkstra algorithm
Construct the Core Bypass Graph (CBG);
Compute the time cost values, i.e.
e
Apply DIJKSTRA algorithm to find all input test shortest paths (1 - i - Nin k );
Apply DIJKSTRA algorithm to find all output test shortest paths (1

Figure

10: The shortest path algorithm applied to CBG.
TPGR MISR
Global
Global
Source
Time Cost:
Input Test Shortest Paths:
Output Test Shortest Paths:

Figure

11: Four input/output shortest paths for Core 1 using Dijkstra Algorithm.
to find all the input/output test shortest paths.
To show the process, we continue our running example by applying the Dijkstra algorithm to the CBG
graph of Figure 8(b) for Core 1 only. Note carefully that Core 1 has two 8-bit and two 16-bit ports. So, we
consider the appropriate cost of edges accordingly. That is the cost values outside parenthesis when a test
point is the core 8-bit port and the cost values inside parenthesis when a test point is the core 16-bit port.
The result is summarized in Figure 11 that shows the shortest paths between global source and core input
ports, with thick solid and broken lines. Figure 11 also shows the shortest paths between two output ports of
1 and the global sink using the two different dotted lines.
4 The Structural Testing
After we find all the shortest paths for all core input/output ports, we have to apply the bypass scheduling
method explained in section 2 for each core. Finally, using some path scheduling method we have to combine
these path schedules to overlap the test activities and minimize the test time as much as possible.
The different steps of structural test process are summarized in the pseudocode of Figure 12. Briefly, the
algorithm finds the best schedule of each input test path and schedules it according to the factorized form
of the characteristic function. For the highest concurrency (test time minimization) the scheduling of each
test path starts from the first possible time step, that is "1" for the input test paths transferring the test
patterns to the core under test and "the time step that the core output signature becomes ready" for the test
output paths. In this work, we have employed a simple As Soon As Possible scheduling method and consider
scheduling the cores in order. Each path is scheduled in a pipeline fashion as explained in section 4 while the
ASAP strategy is used to overlap the path execution times.
STRUCTURAL TEST (Input/Output Test Shortest
Construct and factorize the characteristic functions for input test paths;
Construct and factorize the characteristic function for output test paths;
for (all Core
schedule ASAP the input test paths (1 - i - Nin k )
based on the available bypass/connections;
test pathsg;
Ttest application ;
for (all Core
schedule ASAP the output test paths (1
based on the available bypass/connections;

Figure

12: Structural Test Algorithm
4.1 Possible Extensions
We have considered only unidirectional interconnects and buses in this work. In our graph modeling an n-bit
bidirectional bus is modeled as two p-bit and q-bit (p buses.
Although such extension of our graph model is straight forward, the shortest-path formulation needs to be
changed such that it can also decide for the best value of p and q in order to minimize the transfer time and
bit-match overhead. At the moment, we can take the bidirectional buses into account only if the values for p
and q are fixed (e.g. n=2). We don't address the general case in this paper but intend to consider it in near
future.
Not pursued in this paper, more sophisticated scheduling methods can be implemented for higher perfor-
mance. For example, we can relax the above two assumptions, i.e. ASAP and fixed ordering. Moreover, by
selecting a set of k disjoint (not necessarily the shortest) paths is selected to bypass test data for k different
pairs of points concurrently, the test time will be reduced even further. For systems using few busses (e.g.
VSI alliance bus wrapper design in which mainly three busses are responsible for connecting all cores in the
system) our test scheme shows lower efficiency but can be still used to find the best order of bus access to
optimize the test time.
4.2 Completing the Running Example

Figure

13 shows all the input and output test shortest paths to all four cores in our example. The time cost
is shown within the shaded circles attached to each core in the path.

Figures

14 (a) through (d) show the complete schedules for the shortest paths of Core 1 through Core 4,
respectively. We assumed that Core 1, 2, 3 and 4 require 9, 9, 11 and 25 cycles, respectively as test application
time (the shaded area in Figures 14). Note also that to clarify the role of signals introduced before in section 2
we listed all signals. A "0" in this table means that signal is not active (low logic level). All other entries ("1",
"2", "3" and "4") show an active signal (high logic level) is applied in the corresponding time step. We used
different symbols (1 through 4) to refer to the core under test. For example, entries "4" show the signals to be
active when Core 4 is under test. All empty locations in this table correspond to "\Theta" (don't care situation)
and can be used for logic optimization in implementation of this test controller. Note that some of bypass ij k
signals are defined "0" to guarantee
data conflict on port j .

Figure

15 shows the final schedule according to the scheduling method explained before. This scheduling is
po1
po1
po1
po1
po2
po2
po2
MISR
TPGR
TPGR
TPGR
TPGR
TPGR
TPGR
MISR
MISR
MISR
MISR
MISR
MISR
(a)
(b)
(c)
(d)
Infinity
Infinity
Infinity
Infinity
Infinity Infinity
Infinity
Infinity
Infinity
Infinity
Infinity
44
Infinity
Infinity
TPGR
Infinity 4Core 4

Figure

13: All the input/output shortest paths.
basically obtained by overlapping the four schedules of Figure 14 and some time adjustment when some port
or bypassing route is not available.
This schedule shows that in the structural test session the input data packets (test patterns) and the
output data packets (signatures) are somehow scrambled to overlap the activities and test data transfer in
the test session. The importance of core capability to bypass when it executes a test pattern is clear in this
figure. More specifically, when a core is under test, the bypass routes can transfer test data for other cores.
This kind of overlapping reduces the test time dramatically. Note also in Figure 15 bypass 12 1 , bypass 22 2 and
bypass 12 3 are omitted because the corresponding bypass routes are never needed. This removals will reduce
the hardware overhead of the bypass circuitry.
5 Experimental Results
In this section, we demonstrate our approach using a system made of four cores. The circuits have been
synthesized from high level descriptions using the SYNTEST synthesis system [HPCN92]. Logic level synthesis
is done using the ASIC Synthesizer from the COMPASS Design Automation suite of tools with a 0.8-micron
CMOS library [Comp93]. Fault coverage curves are found for the resulting logic level circuits using AT&T's
GENTEST fault simulator [Gent93]. The probability of aliasing within the MISRs is neglected, as are faults
within the TPGRs and other test circuitry.
Since standard core benchmarks have not been introduced yet we decided to design ourselves four example
circuits as cores, all with eight bit wide datapaths. The first core (Core 2) evaluates a third degree polynomial.
Our other examples implement three high level synthesis benchmarks: a differential equation solver (Core
TPGR
MISR
stop_4
stop_3
stop_2
stop_1
send_port_1
read_port_1
read_port_2
read_port_3
send_port_2
Cores Signal Name 17
Under Test
Time Steps
TPGR
MISR
stop_4
stop_3
stop_2
stop_1
send_port_1
read_port_1
read_port_2
read_port_3
send_port_2
Cores Signal Name 17
Under Test22
Time Steps
(a) Bypass schedule for Core 1 (b) Bypass schedule for Core 2
TPGR
MISR
stop_4
stop_3
stop_2
stop_1
send_port_1
read_port_1
read_port_2
read_port_3
send_port_2
Cores Signal Name 17
Under Test
Time Steps
TPGR
MISR
stop_4
stop_3
stop_2
stop_1
send_port_1
read_port_1
read_port_2
read_port_3
send_port_2
Cores Signal Name 17
Under
Time Steps
(c) Bypass schedule for Core 3 (d) Bypass schedule for Core 4

Figure

14: Bypass schedules for four cores.
TPGR
MISR
stop_4
stop_3
stop_2
stop_1
send_port_1
read_port_1
read_port_2
read_port_3
4 44
Cores Signal Name
Time Steps222

Figure

15: Complete bypass schedule (pipelined fashion) for all four cores.
Core Circuit Normal Transistor Total Faults Fault Test
Name Schedule Count Faults Detected Coverage Time
Poly 9 8684 899 804 89.43 932

Table

3: Statistics for four cores when tested separately.
Full Scan Test Structural Test
Parameter Value Parameter Value
Test
Overhead Output 4484 Bit Match 3548
Test Controller 1045 Test Controller 6062
Test
Per Pattern Core 2 101 Core 2 (Overlapped) 15
One Iteration 501 One Iteration 34
Fault Coverage 88.44% Fault Coverage 91.43%
Test Test
Statistics [Transistor] [Transistor]
Test Time 57363 Test Time 9180

Table

4: Comparison between scan and our proposed structural test.
and the Facet example (Core 1) [GDWL92], and a fifth order elliptical filter (Core 4) [KuWK85]. Note that
each core consists of the datapath and controller both are made testable using BIST applied by SYNTEST
in integrated fashion [HPCN92][NoCP97]. Also, to fit the cores in the port specification as Figure 8(a) shows
we grouped or replicated the actual inputs/outputs of the circuit.

Table

3 summarizes the transistor count, fault coverage and the test time for each core when tested as a
non-embedded circuit separately. Note that the test time has been expressed in terms of "clock cycle". We
execute the corresponding schedule of the core until the fault coverage curve is saturated. For example, for
Diffeq core, the schedule consists of 11 cycles and the fault simulation process requires 70 iterations (each for
a set of random patterns) until the curve is saturated.
We then put these fours together and obtained the fault simulation of the whole system based on "scan"
and our "structural" test. Table 4 summarizes the fault coverage statistics for these two methods.
In scan testing, the order of cores in the scan-in and scan-out chain affects the test time. In our experiments
we assumed a single scan-in chain with the order 4. In the single scan-out
chain the order is assumed to be Core 1. The lower fault coverage of scan is
expected because that method can not capture the interconnect faults. Our proposed structural test approach
requires slightly more test circuitry (about 5.4%) than full scan mainly due to its test controller. Overall, the
structural test overhead is 23.18% of the system cost in this example.
Note that the test methods for individual cores (datapath and controller) achieve fault coverage in the range
of of 87.97% to 92.81% (see Table 3). Thus, regardless of method employed for system testing achieving very
high fault coverage in this system, without redesigning the cores, would not be possible. Using our structural
Multiple-chain Structural Test
Test Controller [Trans.] 4810 6062
Test Time [Cycle] 15390 9180
Tester Pin

Table

5: Comparison between multiple-chain scan and our method.
test approach, the fault coverage has increased by almost 3% mainly due to detecting the interconnect faults.
The real advantage of our structural method is the test time since by bypass scheduling we overlap transferring
test data between test points using the existing interconnections. This resulted in almost 84% test time
reduction compared to scan.
Note that in Table 4 we compared our method with single-chain scan. Using multiple-chain scan, obviously,
will improve the test time with the expense of more overhead for control and wiring. To be more specific,
the result of using the maximum number of scan chains, four in this example - one chain for each core - is
summarized in Table 5. The basic idea of using multiple chains is to apply scan to different partitions in
parallel. Independent multiple chains require dedicated control which increases the test control overhead by a
factor of almost 4. The overall test overhead circuitry remain quite high. More importantly, independent chains
require separate scan-in, scan-out, core-select and test=normal which increases the tester pins to 4
for four chains compared to one (test=normal) in our method. Test time reduction depends on the bottleneck
core; the one with the largest test time which itself depends on inputs/outputs bit width, core execution time
and number of test patterns required. In fact, in our example the bottleneck core is Core 1 with 48 bits
inputs/outputs and requires about 270 test patterns. This resulted in test time of 15390 cycles which is still
67.5% higher than our proposed structural core testing method.
6

Summary

We have proposed a test methodology for testing a core-based system in its entirety. A "bypass" mode circuitry
is added to each core and is used to transfer test data from a source (data generation point) to a sink (data
consumption point) through the existing interconnections. The system is modeled as a directed weighted
graph in which the accessibility (of the core input and output ports) is solved as a shortest path problem.
The test data distribution and collection of signatures are scrambled in a pipelined fashion to minimize test
time. The experimental results are promising in terms of test time and quality testing of the interconnections
among cores.



--R

"A Knowledge Based System for Designing Testable VLSI Chips,"
"Finding Defects with Fault Models,"

Testability Concepts for Digital ICs
"A Unifying Methodology for Intellectual Property and Custom Logic Testing,"
Graph Theory With Applications
"Test methodology for embedded cores which protects intellectual property,"
"Testability Analysis and Insertion for RTL Circuits Based on Pseudorandom BIST,"
"Testing Systems on a Chip,"
"User Manuals for COMPASS VLSI V8R4.4,"
Synthesis and optimization of digital circuits
"User Manuals for GENTEST S 2.0,"
Introduction to Chip and System Design
"SYNTEST: An Environment for System-Level Design for Test,"
"Direct Access Test Scheme - Design of Block and Core Cells for Embedded ASICs,"
"TestSockets: A Framework for System-On-Chip Design,"
VLSI and Modern Signal Processing
"A Structured and Scalable Mechanism for Test Access to Embedded Reusable Cores,"
"A Structured and Scalable Mechanism for Test Access to Embedded Reusable Cores,"
"A Scheme for Integrated Controller-Datapath Fault Testing,"
"Test Synthesis in the Behavioral Domain,"
"Test Responses Compaction in Accumulators with Rotate Carry Adders,"
Application Specific Integrated Circuits
High Performance Computer Architecture
"Testing Embedded Cores Using Partial Isolation Rings,"
"0.8-Micron CMOS VSC450 Portable Library,"
Version 1.0
--TR

--CTR
Tomokazu Yoneda , Hideo Fujiwara, Design for Consecutive Testability of System-on-a-Chip with Built-In Self Testable Cores, Journal of Electronic Testing: Theory and Applications, v.18 n.4-5, p.487-501, August-October 2002
Tomokazu Yoneda , Masahiro Imanishi , Hideo Fujiwara, Interactive presentation: An SoC test scheduling algorithm using reconfigurable union wrappers, Proceedings of the conference on Design, automation and test in Europe, April 16-20, 2007, Nice, France
Tomokazu Yoneda , Kimihiko Masuda , Hideo Fujiwara, Power-constrained test scheduling for multi-clock domain SoCs, Proceedings of the conference on Design, automation and test in Europe: Proceedings, March 06-10, 2006, Munich, Germany
Mohammad Hosseinabady , Abbas Banaiyan , Mahdi Nazm Bojnordi , Zainalabedin Navabi, A concurrent testing method for NoC switches, Proceedings of the conference on Design, automation and test in Europe: Proceedings, March 06-10, 2006, Munich, Germany
Rainer Dorsch , Hans-Joachim Wunderlich, Reusing Scan Chains for Test Pattern Decompression, Journal of Electronic Testing: Theory and Applications, v.18 n.2, p.231-240, April 2002
rika Cota , Luigi Carro , Marcelo Lubaszewski, Reusing an on-chip network for the test of core-based systems, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.9 n.4, p.471-499, October 2004
rika Cota , Luigi Carro , Marcelo Lubaszewski , Alex Orailolu, Searching for Global Test Costs Optimization in Core-Based Systems, Journal of Electronic Testing: Theory and Applications, v.20 n.4, p.357-373, August 2004
Qiang Xu , Nicola Nicolici, Modular and rapid testing of SOCs with unwrapped logic blocks, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.13 n.11, p.1275-1285, November 2005
shortest path;structural testing;pipelined test schedule;at-speed testing;bypass mode