134
Network-on-Chip
3. Unfolding: Some of the routers and links in the network may need to
sustain very high traffic load, more than their capacity. This may happen as the communication requirements are decided by the application.
Unfolding technique uses duplicate resources (i.e., duplicate routers
and links) so that the extra traffic can be carried through the network.
5.5 Constructive Heuristics with Iterative Improvement
These methods attempt to solve the mapping problem by first constructing
a candidate solution that satisfies all the bandwidth requirements. The solution is then improved using an iterative approach to obtain solutions with
less overall communication cost. One of the very prominent works in this
category is the NMAP algorithm proposed by Murali and Micheli (2004a).
The algorithm, though presented for mesh topology, can also be extended to
other topologies. The algorithm has three phases as follows:
• Initialization phase: It computes an initial mapping.
• Minimum path computation phase: It identifies the minimum cost
available path between two mapped cores.
• Iterative improvement phase: It invokes the second phase for each
pair-wise swapping of mapped core positions.
5.5.1 initialization Phase
This phase constructs an initial mapping solution for the application on a mesh
topology. To start with, the cores are sorted based on their communication
demands. The core with the highest communication demand is placed at one
of the mesh nodes having the maximum number of neighbors. Let the core
having the highest communication be c 1 and let it be associated with router u j .
Next, the core having maximum communication with c 1 is identified; let it be c 2 .
The core c 2 is placed at one of the neighbors of u j , so that the communication
cost is the minimum. Since, at this time, only one core has been placed, c 2 can
get mapped to any of the neighbors of u j . However, in general, at any stage
of the algorithm, let R be the set of cores already mapped and W be the set of
corresponding router positions. Let c k be an unmapped core with the maximum communication requirement with the cores in R. Then, c k is chosen as the
next candidate for mapping. The core c k can be mapped to any of the available
router positions. Associating c k with router r m will incur a certain communication cost. For all available mapping positions, the communication costs are
evaluated. The core is mapped to the router position resulting in the minimum
communication cost. The procedure is repeated until all the cores are mapped.
Network-on-Chip
3. Unfolding: Some of the routers and links in the network may need to
sustain very high traffic load, more than their capacity. This may happen as the communication requirements are decided by the application.
Unfolding technique uses duplicate resources (i.e., duplicate routers
and links) so that the extra traffic can be carried through the network.
5.5 Constructive Heuristics with Iterative Improvement
These methods attempt to solve the mapping problem by first constructing
a candidate solution that satisfies all the bandwidth requirements. The solution is then improved using an iterative approach to obtain solutions with
less overall communication cost. One of the very prominent works in this
category is the NMAP algorithm proposed by Murali and Micheli (2004a).
The algorithm, though presented for mesh topology, can also be extended to
other topologies. The algorithm has three phases as follows:
• Initialization phase: It computes an initial mapping.
• Minimum path computation phase: It identifies the minimum cost
available path between two mapped cores.
• Iterative improvement phase: It invokes the second phase for each
pair-wise swapping of mapped core positions.
5.5.1 initialization Phase
This phase constructs an initial mapping solution for the application on a mesh
topology. To start with, the cores are sorted based on their communication
demands. The core with the highest communication demand is placed at one
of the mesh nodes having the maximum number of neighbors. Let the core
having the highest communication be c 1 and let it be associated with router u j .
Next, the core having maximum communication with c 1 is identified; let it be c 2 .
The core c 2 is placed at one of the neighbors of u j , so that the communication
cost is the minimum. Since, at this time, only one core has been placed, c 2 can
get mapped to any of the neighbors of u j . However, in general, at any stage
of the algorithm, let R be the set of cores already mapped and W be the set of
corresponding router positions. Let c k be an unmapped core with the maximum communication requirement with the cores in R. Then, c k is chosen as the
next candidate for mapping. The core c k can be mapped to any of the available
router positions. Associating c k with router r m will incur a certain communication cost. For all available mapping positions, the communication costs are
evaluated. The core is mapped to the router position resulting in the minimum
communication cost. The procedure is repeated until all the cores are mapped.