310
Network-on-Chip
where:
W i is the weight of ith task graph
i
avg
t x y
, and t x y denote the communication volume of edge e x,y
,
in the ith application and the average graph, respectively
The number of input task graphs is n. Once the graph has been constructed,
mapping techniques noted in Chapter 5 can be utilized to get a mapping
solution.
10.4.2.3 Topology and Route Generation
In this step, suitable topologies and routes are generated for each individual
application. Due to their varying communication requirements, the applications may have inclinations to different topologies. For a particular application, the configuration switches are set such that the number of hops between
source and destination routers for high-volume communications is as small
as possible. The basic idea is to select the heaviest communication flow yet to
be assigned a route and find a minimum hop count path for it.
All edges of an application are sorted in decreasing order of communication volume. All configuration switches are initially unconfigured. For each
edge of the application, a branch-and-bound algorithm is used to choose
the path with least cost. The communication cost component due to flow
through a router can be taken as 5, whereas that through a switch is 1. The
branch-and-bound steps for reconfiguration are carried out as follows:
1. Branch: Every path starts at the source node, which happens to be
a router. A new branch to the path is created by adding a router
or a configuration switch adjacent to the current node in the partial path. The added node must belong to the shortest path area—
routers and configuration switches located along one of the shortest
paths between source and destination nodes, as well as the neighboring configuration switches. That is, for a router node, the path
is extended by including neighboring configuration switches along
the shortest path. If the node is a configuration switch, the path is
extended by adding neighboring routers and configuration switches
along the shortest path. This, of course, is restricted by the situation
in which the switch has already been configured. In this case, the
path can be extended and also constrained by the direction determined by the current configuration.
2. Bound: A path may be bounded (i.e., discarded) if an addition of a
new node violates the bandwidth constraint of the newly added
link. In general, the bandwidth constraint of each link must be satisfied. Also, if the cost of partial path reaching a particular node is
larger than the already known partial paths to that node, this path is
Network-on-Chip
where:
W i is the weight of ith task graph
i
avg
t x y
, and t x y denote the communication volume of edge e x,y
,
in the ith application and the average graph, respectively
The number of input task graphs is n. Once the graph has been constructed,
mapping techniques noted in Chapter 5 can be utilized to get a mapping
solution.
10.4.2.3 Topology and Route Generation
In this step, suitable topologies and routes are generated for each individual
application. Due to their varying communication requirements, the applications may have inclinations to different topologies. For a particular application, the configuration switches are set such that the number of hops between
source and destination routers for high-volume communications is as small
as possible. The basic idea is to select the heaviest communication flow yet to
be assigned a route and find a minimum hop count path for it.
All edges of an application are sorted in decreasing order of communication volume. All configuration switches are initially unconfigured. For each
edge of the application, a branch-and-bound algorithm is used to choose
the path with least cost. The communication cost component due to flow
through a router can be taken as 5, whereas that through a switch is 1. The
branch-and-bound steps for reconfiguration are carried out as follows:
1. Branch: Every path starts at the source node, which happens to be
a router. A new branch to the path is created by adding a router
or a configuration switch adjacent to the current node in the partial path. The added node must belong to the shortest path area—
routers and configuration switches located along one of the shortest
paths between source and destination nodes, as well as the neighboring configuration switches. That is, for a router node, the path
is extended by including neighboring configuration switches along
the shortest path. If the node is a configuration switch, the path is
extended by adding neighboring routers and configuration switches
along the shortest path. This, of course, is restricted by the situation
in which the switch has already been configured. In this case, the
path can be extended and also constrained by the direction determined by the current configuration.
2. Bound: A path may be bounded (i.e., discarded) if an addition of a
new node violates the bandwidth constraint of the newly added
link. In general, the bandwidth constraint of each link must be satisfied. Also, if the cost of partial path reaching a particular node is
larger than the already known partial paths to that node, this path is