278
Network-on-Chip
second. Figure 9.4b shows a floorplan for the cores. It also includes the routers (shown as circles) at the corners corresponding to the cores. Figure 9.4c
shows the floorplan with router locations found by the approach proposed
by Soumya and Chattopadhyay (2013). (It may be noted that the floorplan
is an input to the router location problem solved in this section, rather than
evolving the floorplan itself.) When the routers are located at the corners of
each core, it may require longer interconnects between the routers, or multiple hops for a communication between cores. For example, let us consider
the communication between C3 and C6. For Figure 9.4b, placing routers only
at the corners, it requires either a longer interconnect or needs to travel in
three hops (using routers attached with C3, C5, C4, and C6). However, in the
router placement approach discussed in this section (Figure 9.4c), the routers are placed on the floorplan such that smaller interconnects are needed
between the routers and the core-to-core communications also need less
number of hops. The same communication from C3 to C6 requires only a
single hop in this case. This becomes possible due to the intelligent placement of routers that also considers the link length constraint put into the
synthesis process. I n this case, it c ould obtain a 35.71% decrease in t he overall communication cost.
It is assumed that the cores corresponding to the tasks of the application
are already laid out on a two-dimensional grid, corresponding to the floorplan of the chip. Now, the routers will be inserted into this grid floorplan
of the application. Individual routers are assumed to be of size equal to the
smallest square in the grid. This essentially makes all routers to be of same
size, though the constraint can be relaxed easily by considering routers with
varying complexities, thus requiring different amount of area. The maximum allowed link length (L MAX ) is taken as another constraint. If a router is
located at grid point (i,j) and the second one at (k,m), a link can exist between
them only if the distance (i − k)
2
+ (j − m)
2
is less than L MAX .
9.6.1 iLP for Flexible router Placement
This section presents an ILP formulation for the problem of finding suitable
router locations in a given NoC floorplan.
9.6.1.1 Variables
• R is the set of probable router locations on the grid floorplan.
• For each pair of probable router locations r i and r j , let rdist ri , rj be the
distance between them.
• For each core c i and a probable router location r s , let cdist ci rs be the
distance from the center of the floorplan of c i to the router r s .
• L MAX is the maximum link length permitted between two routers or
between a core and the router associated with it.
Network-on-Chip
second. Figure 9.4b shows a floorplan for the cores. It also includes the routers (shown as circles) at the corners corresponding to the cores. Figure 9.4c
shows the floorplan with router locations found by the approach proposed
by Soumya and Chattopadhyay (2013). (It may be noted that the floorplan
is an input to the router location problem solved in this section, rather than
evolving the floorplan itself.) When the routers are located at the corners of
each core, it may require longer interconnects between the routers, or multiple hops for a communication between cores. For example, let us consider
the communication between C3 and C6. For Figure 9.4b, placing routers only
at the corners, it requires either a longer interconnect or needs to travel in
three hops (using routers attached with C3, C5, C4, and C6). However, in the
router placement approach discussed in this section (Figure 9.4c), the routers are placed on the floorplan such that smaller interconnects are needed
between the routers and the core-to-core communications also need less
number of hops. The same communication from C3 to C6 requires only a
single hop in this case. This becomes possible due to the intelligent placement of routers that also considers the link length constraint put into the
synthesis process. I n this case, it c ould obtain a 35.71% decrease in t he overall communication cost.
It is assumed that the cores corresponding to the tasks of the application
are already laid out on a two-dimensional grid, corresponding to the floorplan of the chip. Now, the routers will be inserted into this grid floorplan
of the application. Individual routers are assumed to be of size equal to the
smallest square in the grid. This essentially makes all routers to be of same
size, though the constraint can be relaxed easily by considering routers with
varying complexities, thus requiring different amount of area. The maximum allowed link length (L MAX ) is taken as another constraint. If a router is
located at grid point (i,j) and the second one at (k,m), a link can exist between
them only if the distance (i − k)
2
+ (j − m)
2
is less than L MAX .
9.6.1 iLP for Flexible router Placement
This section presents an ILP formulation for the problem of finding suitable
router locations in a given NoC floorplan.
9.6.1.1 Variables
• R is the set of probable router locations on the grid floorplan.
• For each pair of probable router locations r i and r j , let rdist ri , rj be the
distance between them.
• For each core c i and a probable router location r s , let cdist ci rs be the
distance from the center of the floorplan of c i to the router r s .
• L MAX is the maximum link length permitted between two routers or
between a core and the router associated with it.