137
Application Mapping on Network-on-Chip
Procedure iterative_improvement(G, P)
Input: The application core graph G and the topology graph P
Output: Best communication cost and mapping via swapping
Begin
Bestcommcost = shortestpath(Placed) /* Find the communication cost
for current placement */
Bestmapping = Placed
For i = 1 to number of nodes in topology graph do
For j = i + 1 to number of nodes in topology graph do
begin
Ptemp = Placed
Swap nodes w i and w j in Ptemp
commcost = shortestpath(Ptemp)
If (commcost < bestcommcost)
begin
Bestmapping = Ptemp
Bestcommcost = commcost
end
end
Return Bestcommcost, Bestmapping
End.
5.5.4 Other Constructive Strategies
PMAP, a two-phase mapping algorithm for placing clusters onto processors,
was presented by Koziris et al. (2000), where highly communicating clusters
are placed on adjacent nodes of the processor network. Each cluster contains
all tasks that are to be executed in the same processor having zero interconnection overhead to increase parallelism. A tool, SUNMAP, was presented by
Murali and Micheli (2004b) to automatically select the best standard topology
for a given application and produce a mapping of cores onto that topology. It
minimizes the average communication delay, area, power dissipation subject
to bandwidth and area constraints. MOCA is a two-phase heuristic for lowenergy mesh-based on-chip interconnection architecture proposed by
Srinivasan and Chatha (2005) to reduce the communication energy considering the bandwidth and latency constraints. In the first phase, the cores are
mapped to different routers of the mesh by invoking a bipartitioning-based
slicing tree generation technique. In the second phase, it attempts to find a
minimal path from source to destination for each traffic trace. It does not give
good solution when latency constraints are considered. All the mapping techniques proposed earlier use the communication weighted model (CWM) to
account for the overall communication volume of each channel. It does not