301
Reconfigurable Network-on-Chip Design
2. Constraints for core graph edges
a. Each edge present in the core graph has to be mapped onto a
path in the NoC considered.
r
r
r r
s
t
s t
∀ ∈ ∀
, r , r ∈ R m + m −
e
E
,
P ≤ 1
i j
s t
ci
cj
ci cj
r r
r
r
s t
s
t
2 × P ≤ m + m
ci cj
ci
cj
This completes the formulation. The objective function along with the constraint set can be fed to any ILP solver to get mapping and reconfiguration
for minimizing the communication cost of NoC.
For mapping of CCG onto the reconfigurable NoC, the equations noted so
far used. The cores in the combined graph can be mapped onto any router in
the network. Therefore, the router variables r s and r t in the equations can take
any value from 1 to the number of routers present in the architecture. For the
reconfiguration phase, each core cannot have the flexibility to move from its
initial mapped position to any arbitrary router position in the network. As the
output from the mapping approach is taken as input in the Mapping phase
output is taken as input for the reconfiguration phase. Thus, the flexibility of
the attachment of a core to a router in the reconfiguration phase depends heavily on the initial core-to-router attachment and the flexibility provided by the
reconfiguration architecture (Figure 10.2). For example, if a core of combined
graph is mapped onto router R1, through the multiplexer between R1 and R5,
the mapped core can have the flexibility of moving to R5 or remain at R1 only.
If a core is mapped onto router R1, through the multiplexer present between
R1, R2, R5, and R6, the mapped core can move to any of these routers, and so
on. Therefore, the flexibility of the core moving from its initial mapped position (output of mapping phase) depends upon onto which router it has been
mapped in the initial phase of mapping. In ILP formulation, the routers in equations cannot take all the possible values in reconfiguration phase. The router
position values that are allowed for each core can only be taken in ILP for the
reconfiguration purpose. However, except for very small NoCs, it takes huge
amount of CPU time to arrive at the solution. Hence, Soumya et al. (2013) has
also proposed a PSO-based optimizer to find mapping for larger core graphs.
10.3.7 PSO Formulation
As noted in Chapter 5, PSO is a population-based stochastic technique developed by Eberhart and Kennedy in 1995, inspired by social behavior of bird
flocking or fish schooling. In a PSO system, multiple candidate solutions
coexist and collaborate simultaneously. Each solution, called a particle, flies in
the problem space according to its own experience as well as the experience
of neighboring particles. It has been successfully applied in many problem
areas. In PSO, each single solution is a particle in the search space, having a
fitness value. The quality of a particle is evaluated by its fitness. A discrete