241
Testing of Network-on-Chip Architectures
S1
S2
S3
Test packets
Test
(a)
S1
S2
S3
Test packets
Test
(b)
S1
S2
S3
Test packets
Test
Test
(c)
Figure 8.3
(a,b) Unicast transport; (c) multicast transport.
by proper scheduling of tests. In the following, the problem of test transport
time minimization is taken up for both unicast and multicast environments.
8.2.4 Test Transport Time Minimization—A graph
Theoretic Formulation
The minimization of test delivery times to the NoC elements can be formulated as a graph theoretic problem in which the NoC infrastructure is represented as a graph. A NoC can be visualized as a graph G = (S,L) in which
each vertex s i ∈ S is a NoC switch and each edge l i ∈ L is an interswitch link.
Each switch is associated with a pair of values (T l,S , T t,S ) corresponding to
the switch latency and switch test time, respectively. Each link is similarly
labeled with a pair (T l,L , T t,L ) corresponding to the link latency and link test
time. Now, for each NoC component, the shortest path from an arbitrary
node to the element, traversing only the previously tested fault-free components, is determined. By repeating the process for all possible nodes in the
network and choosing the solution that requires the shortest test time, the
minimum test transport time problem can be solved.
To frame the search operation, a symbolic toggle t is defined for each of the
edges and vertices of the graph. The variable t can take up only two values: N
or T. When t = N, the cost of the associated edge/vertex is its latency term. For
t = T, the cost is the test time term. A modified version of Dijkstra’s shortest
path algorithm can be used to determine the shortest paths.
Initially, the toggle t for all edges and vertices are set to T. The algorithm
starts with an arbitrarily chosen start node of the graph. In the execution
of the search algorithm, every time an element is encountered with toggle
t = T, the cost function is updated with the test time term of the component,
and t is switched to N. However, if an element with t = N is encountered, its
latency term is used to update the cost function, and t remains unchanged.
Compared to the classic Dijkstra’s algorithm, the following differences are
incorporated into the search procedure.
1. The vertices also possess weights.
2. Weights of vertices and edges change dynamically during the graph
traversal.