3. After a directed edge is traversed, the edge in the opposite direction
is traversed as soon as possible.
4. All toggles t must be set to N by the end of the algorithm. This
ensures that all the edges and switches are tested by the end of the
algorithm.
Depending upon whether unicast or multicast transport is employed, the
test cost function has to be computed differently. In the following, the two
strategies are presented for minimum cost test scheduling—one for unicast
and the other one for multicast.
8.2.4.1 Unicast Test Scheduling
The problem of unicast test scheduling can be stated as follows:
Given the graph G(S,L) and the pairs (T l,S , T t,S ) and (T l,L , T t,L ) and assuming
that only one vertex or edge with toggle t = T can be visited at a time, determine a graph traversal sequence that covers all vertices and edges and has a
minimum associated test cost function F TC,u .
The restriction that only one toggle can be switched at a time ensures
unicast transport. The unicast cost function F TC,u can be defined recursively
as follows: If F
old
TC , u be the cost before the current NoC element is tested and
F
new
TC , u be the cost after including the test cost of the current NoC element, then
F
new
old
TC , u = F TC , u +
∑ T l , L + ∑ T l , S + {
Tt t , L if current element is a link
Tt ,S if current element is a switch
L ∈ Links in the e path
S ∈ Swiches in the path
In the following, the unicast test scheduling algorithm is presented. As in
Dijkstra’s algorithm, d[u] denotes the distance of the current test source to the
switch u under test. It represents the test injection time corresponding to u.
At the end of the algorithm, the switch s min corresponding to the minimum
value of F TC,u is selected as the final source.
Algorithm Unicast
Input: G(S,L) and the pairs (T l,S , T t,S ) and (T l,L , T t,S ).
Output: s min corresponding to the minimum test time F TC,u .
Begin
For each s ∊ S do Unicast_min(S, L, s, weight)
/* weight contains the test pairs (T l,S , T t,S ) and (T l,L , T t,S ) */
Find s min corresponding to minimum F TC,u
End
Procedure Unicast_min(S, L, start, w)
Begin
242
Network-on-Chip
is traversed as soon as possible.
4. All toggles t must be set to N by the end of the algorithm. This
ensures that all the edges and switches are tested by the end of the
algorithm.
Depending upon whether unicast or multicast transport is employed, the
test cost function has to be computed differently. In the following, the two
strategies are presented for minimum cost test scheduling—one for unicast
and the other one for multicast.
8.2.4.1 Unicast Test Scheduling
The problem of unicast test scheduling can be stated as follows:
Given the graph G(S,L) and the pairs (T l,S , T t,S ) and (T l,L , T t,L ) and assuming
that only one vertex or edge with toggle t = T can be visited at a time, determine a graph traversal sequence that covers all vertices and edges and has a
minimum associated test cost function F TC,u .
The restriction that only one toggle can be switched at a time ensures
unicast transport. The unicast cost function F TC,u can be defined recursively
as follows: If F
old
TC , u be the cost before the current NoC element is tested and
F
new
TC , u be the cost after including the test cost of the current NoC element, then
F
new
old
TC , u = F TC , u +
∑ T l , L + ∑ T l , S + {
Tt t , L if current element is a link
Tt ,S if current element is a switch
L ∈ Links in the e path
S ∈ Swiches in the path
In the following, the unicast test scheduling algorithm is presented. As in
Dijkstra’s algorithm, d[u] denotes the distance of the current test source to the
switch u under test. It represents the test injection time corresponding to u.
At the end of the algorithm, the switch s min corresponding to the minimum
value of F TC,u is selected as the final source.
Algorithm Unicast
Input: G(S,L) and the pairs (T l,S , T t,S ) and (T l,L , T t,S ).
Output: s min corresponding to the minimum test time F TC,u .
Begin
For each s ∊ S do Unicast_min(S, L, s, weight)
/* weight contains the test pairs (T l,S , T t,S ) and (T l,L , T t,S ) */
Find s min corresponding to minimum F TC,u
End
Procedure Unicast_min(S, L, start, w)
Begin
242
Network-on-Chip