139
Application Mapping on Network-on-Chip
may not be good for other applications. Topology design is one of the significant
factors that affects the net delay and energy consumption of an applicationspecific NoC. The topology must satisfy the design constraints. For very-high
I/O rate streaming type of application mapping, a guaranteed and highthroughput pipelined mechanism for NoC is introduced in the work of Yu
et al. (2009). They proposed a pipeline-based high-throughput low-energy
mapping algorithm that performs task allocation, pipelined task scheduling,
and communication scheduling simultaneously on the heterogeneous NoC
and minimizes the energy consumption. Onyx, a new bandwidth-constrained
application mapping, was presented by Janidarmian et al. (2009) to minimize
the overall communication cost of NoC. In this technique, a core with the highest communication bandwidth is mapped at the center. Then the ranking of
other unmapped cores is settled according to the communication volume with
mapped cores. The unmapped cores are placed at the nearest possible distance
with their related cores by looking the lozenge-shaped path with one or two
hop distances and so on till the empty tile is identified. CHMAP (Tavanpour
et al. 2009) is a chain-mapping algorithm that produces chains of connected
cores in order to introduce a method for application mapping onto a meshbased NoC. Crinkle, a mapping algorithm, was presented by Saeidi et al. (2009)
to reduce the overall communication cost. In this technique, priority lists are
prepared depending on the interconnection degree of nodes and communication bandwidth before mapping onto a mesh-based NoC. Depending on the
priority lists, the heuristic maps the tasks from the corner of 2D mesh platform
and ends on another corner in a zigzag manner. A multiobjective optimization
strategy was proposed by Tornero et al. (2009) to determine the pareto optimal
NoC configurations to optimize an average delay of the network and routing
robustness. In this technique, both the topological mapping and the routing
are considered concurrently. Wang et al. (2009, 2010) proposed a power-aware
template-based efficient mapping (TEM) algorithm for NoC to generate good
mapping solutions with low runtime under bandwidth and latency constraints. CMAP (Chen et al. 2009) is a fast constructive application mapping
algorithm that maps tasks onto NoC minimizing the total communication cost
and energy. It is a hybrid of two constructive mapping algorithms, link-based
mapping (LBMAP), and sort-based mapping (SBMAP). After comparing the
results of these two, the better one is taken as output. Citrine is a two-step 2D
mesh mapping algorithm proposed by Janidarmian et al. (2010), which uses
the mapping technique Onyx (Janidarmian et al. 2009) to retrieve the order of
cores, and then a branch-and-bound search tries to search different permutations by a lozenge-shaped rule of Onyx. RMAP is a reliability-aware application mapping technique for a mesh-based NoC proposed by Patooghy et al.
(2010). It divides the application graph into two subgraphs, which minimizes
the communication traffic between the subgraphs and maximizes the traffic
within each subgraph. Then one subgraph is mapped onto upper triangular
nodes of the NoC and the other is mapped to lower triangular nodes of the
NoC. This technique utilizes the nonuniformity of traffic distribution over the