282
Network-on-Chip
9.6.2.1 Particle Structure and Fitness Function
Let l be the number of available router positions in the floorplan. For all these
l available router positions, a particle is a permutation of numbers from 0 to
l – 1. It is assumed that the router positions are numbered as 0 to l – 1. A particle identifies a set of router positions. The total communication cost forms
the fitness function. While calculating the communication cost, we consider
the locations from 0 to n (n < l) in the particle, where n represents the number
of cores in the application. Thus, only those first n router positions are used
for the mapping of cores.
Fitness of a particle P is the total communication cost due to the router
positions specified by the particle. For every particle, its fitness is calculated
as follows:
1. The distance between each pair of core and router is calculated.
2. A core is mapped to its nearest router. If the distance is more than
L MAX , the fitness of the particle is set to infinity.
3. Links are established between the routers, taking L MAX constraint
into account. No link can be of length larger than this.
4. For each edge in the core graph, the shortest path is found between
the cores in the router graph.
5. Communication cost (fitness) is calculated using the formula:
⎛
Number of hops ×
⎞
m nication cost = ∑
⎜
⎟
Com u
⎜ Bandwidth between eac ch pair ⎟
⎜
⎟
⎜
⎟
⎝
of cores in core graph
⎠
It may be noted that while identifying the shortest paths between the cores,
the capacities of constituent links and all the communications passing
through the link are to be taken into consideration. The issues such as deadlock can be taken care of later either by adding virtual channels or via communication scheduling.
9.6.2.2 Local and Global Bests
Every particle has a local best (pbest), which is one set of router positions giving minimum communication cost, among all sets of router positions that
the particle has seen so far in the evolution process. This local best partially
guides the evolution of the particle. For a particular generation, the global
best (gbest) is the particle resulting in the minimum communication cost for
that generation. It also controls the evolution of particles. The local best of
each particle and the global best are modified if the corresponding values
in the current iteration are less than the values till the previous iteration.
Network-on-Chip
9.6.2.1 Particle Structure and Fitness Function
Let l be the number of available router positions in the floorplan. For all these
l available router positions, a particle is a permutation of numbers from 0 to
l – 1. It is assumed that the router positions are numbered as 0 to l – 1. A particle identifies a set of router positions. The total communication cost forms
the fitness function. While calculating the communication cost, we consider
the locations from 0 to n (n < l) in the particle, where n represents the number
of cores in the application. Thus, only those first n router positions are used
for the mapping of cores.
Fitness of a particle P is the total communication cost due to the router
positions specified by the particle. For every particle, its fitness is calculated
as follows:
1. The distance between each pair of core and router is calculated.
2. A core is mapped to its nearest router. If the distance is more than
L MAX , the fitness of the particle is set to infinity.
3. Links are established between the routers, taking L MAX constraint
into account. No link can be of length larger than this.
4. For each edge in the core graph, the shortest path is found between
the cores in the router graph.
5. Communication cost (fitness) is calculated using the formula:
⎛
Number of hops ×
⎞
m nication cost = ∑
⎜
⎟
Com u
⎜ Bandwidth between eac ch pair ⎟
⎜
⎟
⎜
⎟
⎝
of cores in core graph
⎠
It may be noted that while identifying the shortest paths between the cores,
the capacities of constituent links and all the communications passing
through the link are to be taken into consideration. The issues such as deadlock can be taken care of later either by adding virtual channels or via communication scheduling.
9.6.2.2 Local and Global Bests
Every particle has a local best (pbest), which is one set of router positions giving minimum communication cost, among all sets of router positions that
the particle has seen so far in the evolution process. This local best partially
guides the evolution of the particle. For a particular generation, the global
best (gbest) is the particle resulting in the minimum communication cost for
that generation. It also controls the evolution of particles. The local best of
each particle and the global best are modified if the corresponding values
in the current iteration are less than the values till the previous iteration.