253
Testing of Network-on-Chip Architectures
The above constraint is still not linear. To linearize this, it is necessary to
replace the product I ix ⋅S ix by an additional binary variable R ix with the following constraints:
R ix ≤ I ix
R ix ≤ S ix
R ix ≥ I ix + S ix − 1
This completes the ILP formulation for the core test scheduling problem. All
constraints and objective function are now linear in nature. However, the
solution takes a considerably large amount of CPU time prohibiting its usage
only to small NoCs having a few cores.
8.3.3 Heuristic Algorithms
Ahn and Kang (2006) has proposed a NoC test scheduling strategy using
multiple test clocks. Cota et al. (2004) is one of the first works to suggest
the usage of on-chip networks to transport test data for cores. Cota and
Liu (2006) proposed a set of heuristic algorithms for different versions of
the core test scheduling problem. The first one is a technique that uses a
dedicated routing path for the test packets to move through the NoC. All
tests are applied with full pipeline in a nonpreemptive fashion. The heuristic starts by creating an ordered list of cores and I/O pairs. The cores are
sorted in decreasing order of test time. I/O pairs are permuted and every
permutation is tried out. Different permutations of I/O pairs represent different priorities of their allocation to a core. That is, if core C i is the next one
to be scheduled, the I/O pairs I 1 and I 2 are free, and I 1 appears earlier than
I 2 in the current permutation, C i will be tested via interface I 1 . For each permutation, attempt is made to assign the next core to the first available I/O
pair. If no I/O pair is free, current time is updated to the next most recent
time tag, at which some already scheduled core finishes its testing. At that
time, the resources allocated to the core will become free, and thus may
make the testing of new core possible. If an I/O pair is available, a routing
path is created and the algorithm checks if it conflicts with any other path
for the cores currently being tested. In case of a conflict, the next core in the
sequence is considered. If all cores are tried out and none of them could
be scheduled, the current time will be updated. All the remaining cores
are again tried out for scheduling. The process continues till all cores are
scheduled.
If the system has N c number of cores and M number of I/O pairs, the complexity of the algorithm is O(M!N c ). To explore larger search space, it is suggested that some other core orders be tried out. The proposed algorithm tries
out a user-defined number of core permutations. The overall algorithm is
detailed as follows:
Testing of Network-on-Chip Architectures
The above constraint is still not linear. To linearize this, it is necessary to
replace the product I ix ⋅S ix by an additional binary variable R ix with the following constraints:
R ix ≤ I ix
R ix ≤ S ix
R ix ≥ I ix + S ix − 1
This completes the ILP formulation for the core test scheduling problem. All
constraints and objective function are now linear in nature. However, the
solution takes a considerably large amount of CPU time prohibiting its usage
only to small NoCs having a few cores.
8.3.3 Heuristic Algorithms
Ahn and Kang (2006) has proposed a NoC test scheduling strategy using
multiple test clocks. Cota et al. (2004) is one of the first works to suggest
the usage of on-chip networks to transport test data for cores. Cota and
Liu (2006) proposed a set of heuristic algorithms for different versions of
the core test scheduling problem. The first one is a technique that uses a
dedicated routing path for the test packets to move through the NoC. All
tests are applied with full pipeline in a nonpreemptive fashion. The heuristic starts by creating an ordered list of cores and I/O pairs. The cores are
sorted in decreasing order of test time. I/O pairs are permuted and every
permutation is tried out. Different permutations of I/O pairs represent different priorities of their allocation to a core. That is, if core C i is the next one
to be scheduled, the I/O pairs I 1 and I 2 are free, and I 1 appears earlier than
I 2 in the current permutation, C i will be tested via interface I 1 . For each permutation, attempt is made to assign the next core to the first available I/O
pair. If no I/O pair is free, current time is updated to the next most recent
time tag, at which some already scheduled core finishes its testing. At that
time, the resources allocated to the core will become free, and thus may
make the testing of new core possible. If an I/O pair is available, a routing
path is created and the algorithm checks if it conflicts with any other path
for the cores currently being tested. In case of a conflict, the next core in the
sequence is considered. If all cores are tried out and none of them could
be scheduled, the current time will be updated. All the remaining cores
are again tried out for scheduling. The process continues till all cores are
scheduled.
If the system has N c number of cores and M number of I/O pairs, the complexity of the algorithm is O(M!N c ). To explore larger search space, it is suggested that some other core orders be tried out. The proposed algorithm tries
out a user-defined number of core permutations. The overall algorithm is
detailed as follows: