128
Network-on-Chip
such architectures. This formulation can be used for selecting the links in
use, their voltage and frequency values. The problem of minimizing energy
consumption during application execution while satisfying the performance
constraint may be a combination of some subproblems, such as mapping of
application tasks to IPs, mapping of IPs to the routers of NoC architecture,
assignment of operating voltages to IPs, and routing. Different operating voltages are assigned to IPs if they are operating at multiple voltages. A unified
approach of energy-efficient application mapping that utilizes MILP formulation of the problem has been presented by Ghosh et al. (2009), taking
care of all the subproblems, such as application mapping, operating voltage
assignment, and routing. In the work of Huang et al. (2011), the existing ILP
(Ghosh et al. 2009) is extended to find a trade-off between computation and
communication energy. In the work of Chou et al. (2008), factors that produce
network contention are analyzed. An ILP formulation for contention-aware
application mapping algorithm in a tile-based NoC is proposed to minimize inter-tile network contention. In NoC-based design, the global wires
are replaced by a network of shared links and the routers exchange data
packets simultaneously through the links. Therefore, there is traffic congestion within the links, which significantly degrades the system performance.
The network contention may be source based, destination based, and path
based. The result shows that there is a significant reduction of packet latency
by reducing the network contention, but the loss of communication energy
is high. Tosun et al. (2009) presented an ILP formulation for application mapping onto a mesh-based NoC to minimize energy consumption for different
benchmarks. However, the formulation does not include bandwidth constraints. The CPU time for different benchmarks reported in this work is also
quite high. To overcome the high CPU time, a clustering-based relaxation
for ILP formulation has been proposed by Tosun (2011a). The tasks of the
application graph are clustered suitably, as in Srinivasan et al. (2006). Based
on the number of clusters, the mesh architecture is divided into smaller sized
meshes. The ILP-based formulation of Tosun et al. (2009) is used to map the
clusters onto the corresponding sub-meshes. At the end, it merges all such
sub-meshes to determine the final solution. It is noted that the CPU time
gets improved with a sacrifice in the communication cost of the mapping
solution.
5.4 Constructive Heuristics for Application Mapping
In constructive heuristics, partial solutions are generated sequentially,
and at the end the final mapping solution is obtained. Some of the techniques
perform an additional iterative improvement phase after getting the initial
solution. In this section, we look into one of the constructive techniques,
Network-on-Chip
such architectures. This formulation can be used for selecting the links in
use, their voltage and frequency values. The problem of minimizing energy
consumption during application execution while satisfying the performance
constraint may be a combination of some subproblems, such as mapping of
application tasks to IPs, mapping of IPs to the routers of NoC architecture,
assignment of operating voltages to IPs, and routing. Different operating voltages are assigned to IPs if they are operating at multiple voltages. A unified
approach of energy-efficient application mapping that utilizes MILP formulation of the problem has been presented by Ghosh et al. (2009), taking
care of all the subproblems, such as application mapping, operating voltage
assignment, and routing. In the work of Huang et al. (2011), the existing ILP
(Ghosh et al. 2009) is extended to find a trade-off between computation and
communication energy. In the work of Chou et al. (2008), factors that produce
network contention are analyzed. An ILP formulation for contention-aware
application mapping algorithm in a tile-based NoC is proposed to minimize inter-tile network contention. In NoC-based design, the global wires
are replaced by a network of shared links and the routers exchange data
packets simultaneously through the links. Therefore, there is traffic congestion within the links, which significantly degrades the system performance.
The network contention may be source based, destination based, and path
based. The result shows that there is a significant reduction of packet latency
by reducing the network contention, but the loss of communication energy
is high. Tosun et al. (2009) presented an ILP formulation for application mapping onto a mesh-based NoC to minimize energy consumption for different
benchmarks. However, the formulation does not include bandwidth constraints. The CPU time for different benchmarks reported in this work is also
quite high. To overcome the high CPU time, a clustering-based relaxation
for ILP formulation has been proposed by Tosun (2011a). The tasks of the
application graph are clustered suitably, as in Srinivasan et al. (2006). Based
on the number of clusters, the mesh architecture is divided into smaller sized
meshes. The ILP-based formulation of Tosun et al. (2009) is used to map the
clusters onto the corresponding sub-meshes. At the end, it merges all such
sub-meshes to determine the final solution. It is noted that the CPU time
gets improved with a sacrifice in the communication cost of the mapping
solution.
5.4 Constructive Heuristics for Application Mapping
In constructive heuristics, partial solutions are generated sequentially,
and at the end the final mapping solution is obtained. Some of the techniques
perform an additional iterative improvement phase after getting the initial
solution. In this section, we look into one of the constructive techniques,