125
Application Mapping on Network-on-Chip
and tree, computing the Manhattan distance is easy. However, for irregular
topologies, computing the distance may not be that trivial. If cores c i and c j
are mapped to routers u a u
u u
s nd
s t
t , respectively, P ci cj is equal to 1. In such case,
the Manhattan distance between the routers u s and u t is multiplied by the
bandwidth requirement of the communication between the cores. Summing
this product over all the edges of the application graph gives the total communication cost of the mapping solution produced.
However, if we need to consider the link bandwidth limitation as well, two
issues are to be resolved. First, for each link the total communication scheduled through it should not exceed the limit. Second, the distance between
the cores is not simply the Manhattan distance, but it depends on the route
through which the communication takes place. To incorporate these considerations into the ILP formulation, we need to introduce a few more variables.
• L(u s ,u t ) : It is the set of links forming the path from u s to u t .
• N(u s ,u t ) : It is the set of nodes in the path from u s to u t .
• l
us ut
ui uj : It marks whether the link from u i to u j forms a part of the path
from u s to u t . It is equal to 1 if (u i ,u j ) is a part of the path, otherwise 0.
• n
us ut
i
: It marks if n i is a node on the path from u s to u t , otherwise 0.
• Lc : It is the link capacity expressed as Mbits/s.
• D us ut : It is the distance between the routers u
s and u t measured in
terms of the number of routers in the path.
While considering the bandwidth constraints for individual links, the shortest
path between two router nodes is not fixed because of the limiting link capacity.
Hence, it is necessary to determine the path that satisfies the link capacities for
individual links between the routers. For such a path, we can compute the distance (number of hops or routers) between the source and destination routers.
1. Link capacity constraint: It limits the bandwidth of individual links, so
that the traffic in each link remains within the maximum given link
capacity (Lc).
⎡
⎛
⎞ ⎞
⎤
∀( u i , u j )
∈
U
⎢
∑
BW c i cj ×
⎜ ∑
l
sut
usut
⎟
icj
≤
c ⎥
u
u
i uj ×
P c
L
(5.7)
⎢
⎜
⎟
⎥
⎣
(ci , c j )∈ E
⎝
us , ut∈U
⎠
⎦
In the above equation, if l
us ut
uiuj is 1, it implies that the link (u i ,u j ) is a
part of the path from router u s to u t . The link can be a part of other
paths also, between other pairs of routers. Hence, we need to add
all those bandwidths and ensure that the total bandwidth requirement is less than the link capacity (Lc). Otherwise, some or all paths
should be modified till all the link capacity constraints are satisfied.
Application Mapping on Network-on-Chip
and tree, computing the Manhattan distance is easy. However, for irregular
topologies, computing the distance may not be that trivial. If cores c i and c j
are mapped to routers u a u
u u
s nd
s t
t , respectively, P ci cj is equal to 1. In such case,
the Manhattan distance between the routers u s and u t is multiplied by the
bandwidth requirement of the communication between the cores. Summing
this product over all the edges of the application graph gives the total communication cost of the mapping solution produced.
However, if we need to consider the link bandwidth limitation as well, two
issues are to be resolved. First, for each link the total communication scheduled through it should not exceed the limit. Second, the distance between
the cores is not simply the Manhattan distance, but it depends on the route
through which the communication takes place. To incorporate these considerations into the ILP formulation, we need to introduce a few more variables.
• L(u s ,u t ) : It is the set of links forming the path from u s to u t .
• N(u s ,u t ) : It is the set of nodes in the path from u s to u t .
• l
us ut
ui uj : It marks whether the link from u i to u j forms a part of the path
from u s to u t . It is equal to 1 if (u i ,u j ) is a part of the path, otherwise 0.
• n
us ut
i
: It marks if n i is a node on the path from u s to u t , otherwise 0.
• Lc : It is the link capacity expressed as Mbits/s.
• D us ut : It is the distance between the routers u
s and u t measured in
terms of the number of routers in the path.
While considering the bandwidth constraints for individual links, the shortest
path between two router nodes is not fixed because of the limiting link capacity.
Hence, it is necessary to determine the path that satisfies the link capacities for
individual links between the routers. For such a path, we can compute the distance (number of hops or routers) between the source and destination routers.
1. Link capacity constraint: It limits the bandwidth of individual links, so
that the traffic in each link remains within the maximum given link
capacity (Lc).
⎡
⎛
⎞ ⎞
⎤
∀( u i , u j )
∈
U
⎢
∑
BW c i cj ×
⎜ ∑
l
sut
usut
⎟
icj
≤
c ⎥
u
u
i uj ×
P c
L
(5.7)
⎢
⎜
⎟
⎥
⎣
(ci , c j )∈ E
⎝
us , ut∈U
⎠
⎦
In the above equation, if l
us ut
uiuj is 1, it implies that the link (u i ,u j ) is a
part of the path from router u s to u t . The link can be a part of other
paths also, between other pairs of routers. Hence, we need to add
all those bandwidths and ensure that the total bandwidth requirement is less than the link capacity (Lc). Otherwise, some or all paths
should be modified till all the link capacity constraints are satisfied.