C 1
C 2
. . .
C n I 1
I 2
. . .
I m
259
Testing of Network-on-Chip Architectures
Core part
IO part
Figure 8.8
Particle structure.
part (IO part). An example of a particle structure is shown in Figure 8.8. The
core part is a permutation of core numbers C 1 through C n . It corresponds to
the order in which the scheduling procedure (noted next) attempts to assign
time slots to the cores. The next part is an array of size equal to the number
of cores. If there are m I/O pairs, an individual entry in I/O pair is an integer
in the range of 1 to m. To evaluate the fitness of a particle, start with the first
core in the core part. It is scheduled from time zero. Appropriate resources
of the NoC (links) are reserved for the purpose. At a certain point, suppose
that up to core i in the core order part has been scheduled. The scheduling
time of the core i + 1 is determined by consulting the I/O pair part. If the
corresponding I/O pair is k, the next available time slot for k is determined,
so that the resources are available to schedule the test of core i + 1. When
all cores are scheduled, the highest time for any of the I/O pairs constitutes
the overall test time for the NoC. The overall testing time forms the fitness
function.
8.3.4.2 Evolution of Generations
The particles evolve through generations to create new particles that are
expected to result in overall test scheduling time closer to the optimum. In
the first generation, the initial population is created randomly and the fitness
of individual particles is evaluated. The local best (lbest k ) of each particle is
set to be the same as the initial particle. The global best (gbest i ) of a generation is the particle giving the minimum test time. Successive generations are
evolved through a series of operations called swap operation. The local best
of each particle and the global best of the generation are modified if the corresponding values in the current generation are less than in the previous
generation.
Swap operator: For a particle P, core as well as I/O pair part are indexed
by 0 to N − 1 (N being the number cores). Let the swap operator SO j,k
(0 ≤ j, k ≤ N − 1) swap the jth and kth positions of particle P to create a new particle P New . For example, consider the particle P = {0, 4,
3, 6, 1, 5, 7}, where a number represents the core number. The swap
operator SO 5,6 swaps the cores at positions 5 and 6, creating a new
particle P New = {0, 4, 3, 6, 5, 1, 7}. Similar swaps can also be applied to
the I/O pair part.
C 2
. . .
C n I 1
I 2
. . .
I m
259
Testing of Network-on-Chip Architectures
Core part
IO part
Figure 8.8
Particle structure.
part (IO part). An example of a particle structure is shown in Figure 8.8. The
core part is a permutation of core numbers C 1 through C n . It corresponds to
the order in which the scheduling procedure (noted next) attempts to assign
time slots to the cores. The next part is an array of size equal to the number
of cores. If there are m I/O pairs, an individual entry in I/O pair is an integer
in the range of 1 to m. To evaluate the fitness of a particle, start with the first
core in the core part. It is scheduled from time zero. Appropriate resources
of the NoC (links) are reserved for the purpose. At a certain point, suppose
that up to core i in the core order part has been scheduled. The scheduling
time of the core i + 1 is determined by consulting the I/O pair part. If the
corresponding I/O pair is k, the next available time slot for k is determined,
so that the resources are available to schedule the test of core i + 1. When
all cores are scheduled, the highest time for any of the I/O pairs constitutes
the overall test time for the NoC. The overall testing time forms the fitness
function.
8.3.4.2 Evolution of Generations
The particles evolve through generations to create new particles that are
expected to result in overall test scheduling time closer to the optimum. In
the first generation, the initial population is created randomly and the fitness
of individual particles is evaluated. The local best (lbest k ) of each particle is
set to be the same as the initial particle. The global best (gbest i ) of a generation is the particle giving the minimum test time. Successive generations are
evolved through a series of operations called swap operation. The local best
of each particle and the global best of the generation are modified if the corresponding values in the current generation are less than in the previous
generation.
Swap operator: For a particle P, core as well as I/O pair part are indexed
by 0 to N − 1 (N being the number cores). Let the swap operator SO j,k
(0 ≤ j, k ≤ N − 1) swap the jth and kth positions of particle P to create a new particle P New . For example, consider the particle P = {0, 4,
3, 6, 1, 5, 7}, where a number represents the core number. The swap
operator SO 5,6 swaps the cores at positions 5 and 6, creating a new
particle P New = {0, 4, 3, 6, 5, 1, 7}. Similar swaps can also be applied to
the I/O pair part.