140
Network-on-Chip
network channels to efficiently route the packets of redundant communications. In the work of Yang et al. (2010b), all the nodes and the interconnections
among nodes of a 2D mesh-based NoC are abstracted as a tree. In this tree
model, the vertex with highest communication volume is selected as root
node. The vertices communicating to the root (node) are the children of that
node and so on. During mapping, the root node is placed at the center of the
mesh-based NoC, and the traversal is made from the center toward the borders of the NoC. The child nodes are placed by seeing the tree structure and
the communication volume of interconnects from the center toward the borders. Yang et al. (2010a) proposed a two-step multiapplication mapping algorithm that maps multiple applications simultaneously onto different regions of
NoC to minimize network latency and energy consumption for a set of applications. The algorithm consists of an application mapping phase followed by a
task mapping phase. The application mapping phase deals with the multiple
applications mapping to optimize the layout of multiple applications on the
NoC. After the application mapping phase, the role of task mapping phase is
to map the tasks of the application so that the average communication distance
is minimized. The task mapping of each application follows the tree modelbased mapping as described in the work of Yang et al. (2010b). LMAP is a mapping algorithm proposed by Sahu et al. (2010) to reduce both static and dynamic
costs of a mesh-based NoC. In the initial mapping phase, a Kernighan–Lin
(K–L) partitioning scheme is used to identify the closeness of cores by analyzing their bandwidth or communication requirements. This bipartitioning is
applied (recursively) until the closest two cores are left in one final partition.
After initial mapping, an iterative improvement phase is applied to arrive at a
final mapping. CastNet is an energy-aware application mapping and routing
technique for 2D NoC proposed by Tosun (2011b). Before mapping, a priority
list of the tasks is formed based on its total communication with its neighbors.
Depending on the priority list, the initial task is selected. For mapping the first
task, a set of initial node positions is selected. A set of solutions is generated by
this technique for each initial node position of the initial task. The remaining
tasks are placed on the nodes of NoC according to the priority list. After each
mapping the priority list is also updated. Finally, from the set of solutions, the
best one is taken as the solution for mapping of applications onto NoC.
All the application mapping techniques of NoC discussed above are
based on the mesh-based network architecture. But it is essential to check
the suitability of other network topology when applications are mapped
onto that. An energy-aware mapping technique was proposed by Chang
et al. (2008), which maps the IPs onto a tree-based NoC architecture such
that the total communication energy can be minimized. In this technique,
first an energy-aware mapping is formulated, and then a recursive bipartitioning algorithm is used to solve it. An application mapping heuristic
was proposed by Majeti et al. (2009) for generating an optimal tree-based
topology for multimedia applications to minimize energy consumption
while meeting the design constraints. Application mapping techniques were