283
Application-Specific Network-on-Chip Synthesis
9.6.2.3 Evolution of Generation
Evolution of the particles is done over generations to create new particles that
are expected to give results closer to the optimum. To start with, the initial population is created randomly and the fitness of individual particles is evaluated.
The local best (pbest) of each particle is initialized to be the same as that of the
initial particle. The global best of the generation is initialized with the particle
giving the least communication cost (smallest fitness function) in the generation. The second generation results through random exchange of router positions within the particles. The local best and global best values are updated
if they give better fitness values. Further generations are created through a
series of swap operations. The local best of each particle and the global best are
modified if the corresponding values in the current generation are less than the
values in the previous generation. The local best and the global best evolution
thus center on the basic operator, swap, explained in Section 9.6.3.4.
9.6.2.4 Swap Operator
Each particle is a sequence of l probable router positions. Out of these, first n
corresponds to the selected router positions. To effect a change in the particle,
the swap operator is used. The operator takes two indices (say i and j) of particle P as inputs and creates a new particle P 1 . The particle P 1 is the same as
P, except that the positions i and j of P are interchanged in it.
Let the particle P be
r1 r3 r5 r7 r4 r2 r6 r8
where rx represents the router at position x. The indices of r1, r3, and r5 are
0, 1, and 2, respectively. The swap operator SO(3, 5) swaps positions 3 and 5
in P to generate a new particle as shown in the following:
r1 r3 r5 r2 r4 r7 r6 r8
9.6.2.5 Swap Sequence
A swap sequence is a sequence of swap operators. For example, a swap
sequence SS = {SO(1, 7), SO(3, 4)} creates particle P new working on particle P
in two steps as follows:
Let the particle P be
r3 r6 r8 r4 r1 r5 r2 r7
SO(1, 7) on particle P creates intermediate particle P int .
Let the particle P int be
Application-Specific Network-on-Chip Synthesis
9.6.2.3 Evolution of Generation
Evolution of the particles is done over generations to create new particles that
are expected to give results closer to the optimum. To start with, the initial population is created randomly and the fitness of individual particles is evaluated.
The local best (pbest) of each particle is initialized to be the same as that of the
initial particle. The global best of the generation is initialized with the particle
giving the least communication cost (smallest fitness function) in the generation. The second generation results through random exchange of router positions within the particles. The local best and global best values are updated
if they give better fitness values. Further generations are created through a
series of swap operations. The local best of each particle and the global best are
modified if the corresponding values in the current generation are less than the
values in the previous generation. The local best and the global best evolution
thus center on the basic operator, swap, explained in Section 9.6.3.4.
9.6.2.4 Swap Operator
Each particle is a sequence of l probable router positions. Out of these, first n
corresponds to the selected router positions. To effect a change in the particle,
the swap operator is used. The operator takes two indices (say i and j) of particle P as inputs and creates a new particle P 1 . The particle P 1 is the same as
P, except that the positions i and j of P are interchanged in it.
Let the particle P be
r1 r3 r5 r7 r4 r2 r6 r8
where rx represents the router at position x. The indices of r1, r3, and r5 are
0, 1, and 2, respectively. The swap operator SO(3, 5) swaps positions 3 and 5
in P to generate a new particle as shown in the following:
r1 r3 r5 r2 r4 r7 r6 r8
9.6.2.5 Swap Sequence
A swap sequence is a sequence of swap operators. For example, a swap
sequence SS = {SO(1, 7), SO(3, 4)} creates particle P new working on particle P
in two steps as follows:
Let the particle P be
r3 r6 r8 r4 r1 r5 r2 r7
SO(1, 7) on particle P creates intermediate particle P int .
Let the particle P int be