271
Application-Specific Network-on-Chip Synthesis
For every pair of cores v i and v j ∊ V, the binary variables GX i,j and GY i,j are
defined as follows:
⎧ 1, if X i,max > X j,max
GX i j
, = ⎨ 0, otherwise
⎩
⎧ 1, if Y i,max > Y j,max
GY i j
, = ⎨ 0, otherwise
⎩
The following two inequalities need to be satisfied for the cores to get aligned
to grid positions:
GX + X′ ≤ 1
i j
,
i j
,
′
GY i j
, + Y i j
, ≤ 1
9.5 Custom Interconnection Topology and Route Generation
The floorplan information generated so far does not include the routers in it.
The next stage of the formulation will select router locations in the floorplan
with an objective of minimizing the power consumption. Since there can be
a large number of potential locations for placement of routers, it is desirable
to reduce the number of candidate locations via some means, so that the
MILP formulation for router location identification can run faster. To start
with, bounding boxes are created for each core placed as a rectangle in the
floorplan. A bounding box is a rectangular enclosure of the core rectangle
(called a node in subsequent discussion) such that the bounding boxes of two
neighboring nodes are touching each other. Figure 9.2 shows such a situation. The bounding box of node 4 extends to the top boundary of node 3 and
so on. Once the bounding boxes are designed, a channel intersection graph (Sait
and Youssef 1994) will be constructed. The graph has vertices corresponding
to two perpendicular boundaries of the floorplan. The edges of the graph
correspond to the bounding boxes of the floorplan. Routers can be placed
at each vertex of the channel intersection graph. Figure 9.2b shows the possible placement of routers, represented as filled circles in the diagram. Many
of the routers are redundant, in the sense that they are placed very close to
each other. Hence, in the final layout, it is very much unlikely that both the
closely placed routers will be utilized to connect cores. The routers may be
removed when:
1. Routers are placed along the perimeter of the layout.
2. Routers are placed less than a specified distance apart.