Application-Specific Network-on-Chip Synthesis
281
− To get starting link of the path, the following constraint is
imposed. Starting router may have more than one outgoing
link, out of which one has to be selected.
∀e i j ∈ E , ∀r , r
s t ∈ R, P c
rs rt
i cj −
r
∑ l
rs rt
ri rj = 0
i ,rj ∈R
− If a link is part of the path, starting and ending routers of that
link must also be part of the path.
∀r s , r t ∈ R, ∀r i , r j ∈ R, 2 × l
s t
s
rs rt
r
r r
r rt
i rj − n i − n j ≤ 0
− Each router (except starting and ending ones) should have
equal in and out degrees.
∀ r s , r t ∈ R, ∀r
r
i
r
∈ R, r i ≠ r s , r
s t
i ≠ r t , r i ≠ r j , 2 × n i − ∑ l
rs rt
r
0
∀(ri ,r rj )∈R
i rj =
− A link can be part of the path if it would have satisfied the
link length constraint.
∀r , r ∈ R, ∀r , r ∈ R , rl − l
rs rt
s t
i j
ri rj
ri rj ≥ 0
− The distance between routers can be calculated by using
following equation:
∀ r s , r t ∈ R, D −
l
rs rt
rs rt
∑
r
= 0
( i ,r
i r
∀ r
j
j )∈R
This completes the formulation. The objective function along with the constraint set can be fed to any ILP solver to get the router positions minimizing the communication cost for the synthesized NoC. However, excepting
for very small NoCs, it takes huge amount of CPU time to arrive at the
solution. In Section 9.6.2, a particle swarm optimization (PSO)-based technique has been discussed to explore the search space for synthesizing
larger NoCs.
9.6.2 PSO for Flexible router Placement
Particle Swarm Optimization (PSO) is an optimization technique developed
around the idea of birds flocking. Originally proposed by Kennedy and
Eberhart (1995), the technique has been applied in numerous optimization
problem. In the following a PSO formulation has been presented as the flexible router placement problem.