143
Application Mapping on Network-on-Chip
number of routers). The index corresponds to the router number, as shown
in Figure 5.7. Let the swap operator be SO j,k (where j and k = 0, 1, . . . , N – 1)
that swaps the jth and kth positions of particle p to create a new particle p new .
For example, consider the particle p = {1, 4, 3, 6, 2, 8, 5, 7}, where the numbers
represent the core numbers of the core graph and the position r epresents
the router numbers in the topology graph. The swap operator SO 4,6 swaps
the cores at positions 4 and 6, which creates a new particle p new = {1, 4, 3, 6,
5, 8, 2, 7}.
To align a particle p i with its local best, the swap sequence is identified. Let
this be SS
l _ best
i
. Then another swap sequence is identified to align the particle with
the global best. Let this be SS
g _ best . Now the swap sequence SS
l _ best
i
i
is applied on
particle p i with a probability of s 2 . Let the modified particle be p
l _ best
i
. Then the
swap sequence SS
g _ best
i
is applied on p
l _ best
i
with a probability of s 3 . This creates a new particle p
new
i
. Its fitness is evaluated and the local best is updated
for particle i, if it is better than the previous local best for the particle. If the
best fitness in a generation is better than the global best of the previous generation, the global best is also updated.
Procedure Compute_Swap_Sequence
Input: Source sequence Sour_seq Destination sequence Dest_seq
Output: Swap sequence Swap_seq to align Sour_seq to Dest_seq
Begin
For i = 1 to total number of nodes in Sour_seq
Swap_seq[i] = Index of Sour_seq[i] in Dest_seq
End for
End
Assuming that none of the sequences are sorted, the time complexity of the
procedure Compute_Swap_Sequence is O(n 2 ), n being the number of nodes.
5.6.3 Convergence of DPSO
From Guilan et al. (2008), it can be found that the convergence condition for
this DPSO is given by
(
2
1− s
)
2
1 ) ≤ s 2 + s 3 ≤ (1 + s 1
Setting the values of s 1 = 1.0, s 2 = 0.04, and s 3 = 0.02 is observed to produce
good results for most of the applications we have experimented with. A typical trace of the evolution of a particle with these parameter settings shows
that in the process of convergence, it is safe to assume that the particle has
converged to its final value if there are no significant improvements in the
solution quality for last 100 generations.
Application Mapping on Network-on-Chip
number of routers). The index corresponds to the router number, as shown
in Figure 5.7. Let the swap operator be SO j,k (where j and k = 0, 1, . . . , N – 1)
that swaps the jth and kth positions of particle p to create a new particle p new .
For example, consider the particle p = {1, 4, 3, 6, 2, 8, 5, 7}, where the numbers
represent the core numbers of the core graph and the position r epresents
the router numbers in the topology graph. The swap operator SO 4,6 swaps
the cores at positions 4 and 6, which creates a new particle p new = {1, 4, 3, 6,
5, 8, 2, 7}.
To align a particle p i with its local best, the swap sequence is identified. Let
this be SS
l _ best
i
. Then another swap sequence is identified to align the particle with
the global best. Let this be SS
g _ best . Now the swap sequence SS
l _ best
i
i
is applied on
particle p i with a probability of s 2 . Let the modified particle be p
l _ best
i
. Then the
swap sequence SS
g _ best
i
is applied on p
l _ best
i
with a probability of s 3 . This creates a new particle p
new
i
. Its fitness is evaluated and the local best is updated
for particle i, if it is better than the previous local best for the particle. If the
best fitness in a generation is better than the global best of the previous generation, the global best is also updated.
Procedure Compute_Swap_Sequence
Input: Source sequence Sour_seq Destination sequence Dest_seq
Output: Swap sequence Swap_seq to align Sour_seq to Dest_seq
Begin
For i = 1 to total number of nodes in Sour_seq
Swap_seq[i] = Index of Sour_seq[i] in Dest_seq
End for
End
Assuming that none of the sequences are sorted, the time complexity of the
procedure Compute_Swap_Sequence is O(n 2 ), n being the number of nodes.
5.6.3 Convergence of DPSO
From Guilan et al. (2008), it can be found that the convergence condition for
this DPSO is given by
(
2
1− s
)
2
1 ) ≤ s 2 + s 3 ≤ (1 + s 1
Setting the values of s 1 = 1.0, s 2 = 0.04, and s 3 = 0.02 is observed to produce
good results for most of the applications we have experimented with. A typical trace of the evolution of a particle with these parameter settings shows
that in the process of convergence, it is safe to assume that the particle has
converged to its final value if there are no significant improvements in the
solution quality for last 100 generations.