For each vertex s ∊ S do
Begin
s.toggle = T;
s.weight = T t,S ;
d[s] = ∞;
s.parent = UNDEFINED;
End
d[start] = 0;
For each edge e = (u,v) ∊ L do
Begin
e.toggle = T;
e.weight = T t,L ;
End
F TC,u = 0;
Put all vertices of S in minpriority queue Q based on d values;
While Q is not empty do
Begin
u = Extract_Min(Q);
For each edge e = (u,v) outgoing from u do
Begin
If (d[u] + e.weight < d[v]) then
Begin
d[v] = d[u] + e.weight;/* This affects the queue Q */
Update F TC,u ;
v.toggle = N;
e.toggle = N;
u.weight = T l,S ;
e.weight = T l,L ;
v.parent = u;
End;
End;
End;
Return F TC,u ;
End.
243
Testing of Network-on-Chip Architectures
Figure 8.4 shows a four node NoC along with the links. Starting with node S 1 ,
unicast testing of components proceeds in the following sequence: S 1 , I 1 , I 2 , S 2 ,
′
′
′
′
I 1 , S 3 , I 2 , I 5 , I 5 , I 3 , S 4 , I 3 , I 4 , and finally I 4
′ . Accordingly, the test time requirement
increments in the following sequence: T t,S , T t,S + T l,S + T t,L , T t,S + 2T l,S + 2T t,L ,
2T t,S + 3T l,S + 2T t,L + T l,L , 2T t,S + 5T l,S + 3T t,L + 2T l,L , 3T t,S + 6T l,S + 3T t,L + 3T l,L ,
3T t,S + 8T l,S + 4T t,L + 4T l,L , 3T t,S + 10T l,S + 5T t,L + 5T l,L , 3T t,S + 12T l,S + 6T t,L + 6T l,L ,
3T t,S + 14T l,S + 7T t,L + 7T l,L , 4T t,S + 16T l,S + 6T t,L + 9T l,L , 4T t,S + 19T l,S + 8T t,L +
11T l,L , 4T t,S + 21T l,S + 9T t,L + 12T l,L , and 4T t,S + 24T l,S + 10T t,L + 14T l,L . The same is
Begin
s.toggle = T;
s.weight = T t,S ;
d[s] = ∞;
s.parent = UNDEFINED;
End
d[start] = 0;
For each edge e = (u,v) ∊ L do
Begin
e.toggle = T;
e.weight = T t,L ;
End
F TC,u = 0;
Put all vertices of S in minpriority queue Q based on d values;
While Q is not empty do
Begin
u = Extract_Min(Q);
For each edge e = (u,v) outgoing from u do
Begin
If (d[u] + e.weight < d[v]) then
Begin
d[v] = d[u] + e.weight;/* This affects the queue Q */
Update F TC,u ;
v.toggle = N;
e.toggle = N;
u.weight = T l,S ;
e.weight = T l,L ;
v.parent = u;
End;
End;
End;
Return F TC,u ;
End.
243
Testing of Network-on-Chip Architectures
Figure 8.4 shows a four node NoC along with the links. Starting with node S 1 ,
unicast testing of components proceeds in the following sequence: S 1 , I 1 , I 2 , S 2 ,
′
′
′
′
I 1 , S 3 , I 2 , I 5 , I 5 , I 3 , S 4 , I 3 , I 4 , and finally I 4
′ . Accordingly, the test time requirement
increments in the following sequence: T t,S , T t,S + T l,S + T t,L , T t,S + 2T l,S + 2T t,L ,
2T t,S + 3T l,S + 2T t,L + T l,L , 2T t,S + 5T l,S + 3T t,L + 2T l,L , 3T t,S + 6T l,S + 3T t,L + 3T l,L ,
3T t,S + 8T l,S + 4T t,L + 4T l,L , 3T t,S + 10T l,S + 5T t,L + 5T l,L , 3T t,S + 12T l,S + 6T t,L + 6T l,L ,
3T t,S + 14T l,S + 7T t,L + 7T l,L , 4T t,S + 16T l,S + 6T t,L + 9T l,L , 4T t,S + 19T l,S + 8T t,L +
11T l,L , 4T t,S + 21T l,S + 9T t,L + 12T l,L , and 4T t,S + 24T l,S + 10T t,L + 14T l,L . The same is