279
Application-Specific Network-on-Chip Synthesis
• BW ij is the bandwidth requirement between cores c i and c j .
• sr s is a binary variable, which is 1 if location r s is selected to hold a
router and 0 otherwise.
m
rs
ci , a binary variable, which is 1 if core c i is connected to router at r
•
s
and 0 otherwise.
cl
rs
ci , is a binary variable, which is 1 if link exists between core c
•
i and
router at location r s and 0 otherwise.
rl ri rj is a binary variable, which is 1 if link exists between locations r
•
i
and r j and 0 otherwise.
P
rs rt
ci c j
is a binary variable, which is 1 if path exists between routers r s
• and r t , to which cores c i and c j have been attached, and 0 otherwise.
n
rs rt
i
is a binary variable, which is 1 if router r i is a part of the path
• from router r s to r t and 0 otherwise.
• l
rsrt
ri rj is a binary variable, which is 1 if the link between routers r i and r j
is part of the path from r s to r t and 0 otherwise.
D rs rt is an integer variable identifying the distance between router
• locations r s and r t , in terms of the number of hops. It can take up
values from 0 to the number of routers in the network.
9.6.1.2 Objective Function
The objective is to minimize the communication cost by selecting suitable
router locations. The objective function can be formulated as follows: If cores
c i and c j are mapped to router locations r s and r t and a path exists between
r r
them in the network, P
s t
is equal to 1. This multiplied by D r r gives the number
c c j
t
i
s
of hops of the communication from c i to c j . The number of hops multiplied
by bandwidth gives the communication cost, which has to be minimized over
all the edges in the core graph. Thus, the overall objective function is
⎞
⎛
∈
∑
E
∈
∑
R
⎜
⎜
⎝
⎟
⎟
⎠
Minimize
BW ij
D
×
P
r r
s t
r r
s t
c c j
i
e
r r
s t
ij
,
9.6.1.3 Constraints
The following is the set of constraints framed to solve the router location
selection problem:
• Mapping constraints
• Each core has to be mapped onto only one router.
∀c ∈ C,
m
rs
= 1
i
∑ ci
rs∈R
Application-Specific Network-on-Chip Synthesis
• BW ij is the bandwidth requirement between cores c i and c j .
• sr s is a binary variable, which is 1 if location r s is selected to hold a
router and 0 otherwise.
m
rs
ci , a binary variable, which is 1 if core c i is connected to router at r
•
s
and 0 otherwise.
cl
rs
ci , is a binary variable, which is 1 if link exists between core c
•
i and
router at location r s and 0 otherwise.
rl ri rj is a binary variable, which is 1 if link exists between locations r
•
i
and r j and 0 otherwise.
P
rs rt
ci c j
is a binary variable, which is 1 if path exists between routers r s
• and r t , to which cores c i and c j have been attached, and 0 otherwise.
n
rs rt
i
is a binary variable, which is 1 if router r i is a part of the path
• from router r s to r t and 0 otherwise.
• l
rsrt
ri rj is a binary variable, which is 1 if the link between routers r i and r j
is part of the path from r s to r t and 0 otherwise.
D rs rt is an integer variable identifying the distance between router
• locations r s and r t , in terms of the number of hops. It can take up
values from 0 to the number of routers in the network.
9.6.1.2 Objective Function
The objective is to minimize the communication cost by selecting suitable
router locations. The objective function can be formulated as follows: If cores
c i and c j are mapped to router locations r s and r t and a path exists between
r r
them in the network, P
s t
is equal to 1. This multiplied by D r r gives the number
c c j
t
i
s
of hops of the communication from c i to c j . The number of hops multiplied
by bandwidth gives the communication cost, which has to be minimized over
all the edges in the core graph. Thus, the overall objective function is
⎞
⎛
∈
∑
E
∈
∑
R
⎜
⎜
⎝
⎟
⎟
⎠
Minimize
BW ij
D
×
P
r r
s t
r r
s t
c c j
i
e
r r
s t
ij
,
9.6.1.3 Constraints
The following is the set of constraints framed to solve the router location
selection problem:
• Mapping constraints
• Each core has to be mapped onto only one router.
∀c ∈ C,
m
rs
= 1
i
∑ ci
rs∈R