142
Network-on-Chip
3
1
6
4
8
5
2
7
Core number
Router number
0
1
2
3
4
5
6
7
Figure 5.7
A particle structure.
themselves. Edges connecting a core node to dummy nodes and the edges
between dummy nodes are assigned a cost 0. Let N be the number of cores
present in the core graph for mapping cores onto the topology graph, after
connecting dummy nodes, if required. For these N cores, there are N node
positions in the topology graph. A particle is a permutation of numbers from
1 to N, which shows the placement of cores to the node positions of the topology graph. The overall communication cost is influenced by the position of
cores in a particle. The overall communication cost forms the fitness function. Fitness of a particle p i is equal to the overall communication cost after
placement of cores of the core graph to different routers as specified by the
particle.
5.6.2 evolution of generations
In the general DPSO framework, let the position of a particle (in an
n-dimensional space) at kth iteration be p k = < p k ,1 , p k ,2 ,, p k n
, >. For ith particle, the quantity is denoted as p k
i . Let pbest i be the local best solution that
particle i has seen so far and gbest k be the global best particle of iteration k.
The new position of particle i is calculated as follows:
i
i
i
p = [s I s (p → pbest ) ⊕ × (p → gbest )] × p k
× ⊕ ×
s
k+1
1
2
k
3
k
k
In the above equation, a → b represents the minimum length sequence of
swapping to be applied on components of a to transform it to b. For example, if a = <1, 3, 4, 2> and b = <2, 1, 3, 4>, a → b = swap(3, 4)>. The operator ⊕ is the fusion operator. Applied on two swap
sequences, a ⊕ b is equal to the sequence in which the sequence of swaps
in a is followed by the sequence of swaps in b. The constants s 1 , s 2 , s 3 are
the inertia, self-confidence, and swarm confidence values, respectively. The
quantity s i ×(a → b) means that the swaps in the sequence a → b will be
applied with a probability s i . I is the sequence of identity swaps, such as
. It corresponds to the inertia of the
particle to maintain its current configuration. The final swap corresponding to s 1 I s 2 (p k → pbest
i ) s 3 (p k → gbest k
i
× ⊕ ×
⊕ ×
) is applied on particle p k to
generate p k
i +1 .
In reference to the application mapping problem, for a particle p, the router
associated with a core is identified by the position index of the core in  p.
The indexing of the position takes values between 0 and N – 1 (N being the