138
Network-on-Chip
consider communication timing. To capture both timing of application communication and communication volume, communication dependence and
computation model (CDCM) was proposed by Marcon et al. (2005a, 2005b),
which maps applications on regular NoC under bandwidth constraint and
minimizes average communication delay. Marcon et al. (2008) compared different algorithms for obtaining low-energy mappings onto NoCs using a
CWM. They also proposed two heuristics, largest communication first (LCF)
and greedy incremental (GI) for low-energy mapping using CWM. UMARS, a
unified mapping, routing, and slot allocation algorithm presented by Hansson
et al. (2005), couples mapping, path allocation, and time slot allocation to minimize communication energy. This technique maps cores onto the NoC topology, routes the communication, and allocates time division multiplexed access
(TDMA) time slots on network channels so that application constraints are
met. SMAP (Saeidi et al. 2007) is a simulation-based environment, which performs application mapping and task routing for a two-dimensional (2D) meshbased NoC to minimize the execution time and communication energy. In this
technique, the highest priority task is mapped at the center and other tasks are
mapped from the mapped tasks spirally to the boundaries of the mesh-based
NoC by placing highly communicating cores as close as possible to each other.
Spiral is a mapping algorithm proposed by Mehran et al. (2007), which reduces
the cumulative energy consumption of communication links and the overall
system execution time. In this mapping technique, the high-priority resources
are mapped spirally from the center to the boundaries of the mesh-based NoC
by placing highly communicating cores as close as possible to each other as in
the work of Saeidi et al. (2007). A simulated annealing (SA)-based application
mapping technique proposed by Harmanani and Farah (2008) for a 2D meshbased NoC minimizes the area requirement and the maximum bandwidth. It
also proposes an efficient routing algorithm that selects a route among alternative paths based on the network state and occupancy of queues. Cluster-based
technique combined with SA was proposed by Lu et al. (2008) for application
mapping onto a 2D mesh-based NoC. In this technique, mapping is done
cluster-wise, instead of node-wise, to reduce the mapping complexity.
Clustering is a technique to partition nodes into groups according to the physical distance among them in the network topology. Clustering exploits the
knowledge about the network architecture and communication demand of
applications. Therefore, in this mapping technique, first a cluster-based core to
node initial mapping is done and then a SA technique is applied upon it to find
good mapping solution. Elmiligi et al. (2008a, 2008b, 2009) analyzed different
approaches to minimize the total communication energy by inserting some
permissible longer links and by-passing some routers of application-specific
NoC. In this process, by network partitioning, the area cost is reduced by
reducing both the router area and the number of links. Elmiligi et al. (2009)
proposed an efficient methodology to choose the most power-efficient application-specific NoC architecture. They compared different topologies taking
only one application benchmark and reported the best one, but that topology