252
Network-on-Chip
or
⎛
jy
∑

⎞
Z ixjy ⎜ S
−
S ix −
T ixc ’ ⋅
F ic ’ ⎟ ≥
0
(8.6)

⎜
⎟
⎝

c ’
⎠

where:
1 ≤  i,j  ≤  N c
1 ≤  x,y  ≤  N p
c,c′ ∊ F c
The constraints (8.5) and (8.6) are not linear. To linearize them, two new
binary variables K ixjy1 and K ixjy2 are introduced with the constraint that
K ixjy1  +  K ixjy2  =  1. This leads to a new constraint combining the two constraints
(8.5) and (8.6).
⎛
⎞
⎛
⎞
Z ixjy ⋅ K ixjy 1 ⎜ S ix − S jy − ∑ T jyc ⋅ F jc ⎟ + Z ixjy ⋅ K ixjy 2 ⎜ S jy − S ix − − T
⎜
⎟
⎜
∑ ixc ’ ⋅ F ic ’ ⎟ ≥ 0 (8.7)
⎟
⎝
c
⎠
⎝
c
⎠
The above constraint is still nonlinear as it contains multiplication of two
variables K and S. To transform it into a linear one, the product K ixjy1 ⋅ S ix is
replaced by a new variable M ixjy1 that takes up a value of 1 if K ixjy1  =  1 and
S ix  =  1. This can be enforced by adding three additional constraints noted as
follows:
M
≤ K
ixjy1
ixjy1
M
≤ S
ixjy1
ix
M ixjy
+ S
1 ≥ K ixjy1 ix − 1
Similar transformations are to be introduced to replace the products K ixjy1 ⋅ S jy
by M ixjy2 , K ixjy2 ⋅ S jy by M ixjy3 , and K ixjy2 ⋅ S ix by M ixjy4 .
The objective function is to minimize the overall test time of the NoC. The
overall test time is equal to the maximum of finish times for all cores. Thus,
the objective function can be written as
⎛
⎞
Minimize C = Maximum ⎜ S ix + ∑ T ixc ⋅ F ic ⎟ , for all i, x, c
⎜
⎟
⎝
c
⎠
Again, the objective function is not linear. To linearize, it is required to minimize C along with a set of constraints noted as follows:
Np
⎛
⎞
C ≥ ∑ I ix ⎜ S
⎜
ix + ∑ T ixc ⋅ F ic ⎟, for all 1 ≤ i ≤ N c
(8.8)
⎟
x=1
⎝
c
⎠