141
Application Mapping on Network-on-Chip
proposed by Sahu et al. (2011a, 2011b) to map applications onto butterfly fat
tree- and mesh-of-tree-based NoCs, respectively. In this technique, a K–L
partitioning scheme was used by Sahu et al. (2010) to identify the closeness
of cores by analyzing their bandwidth or communication requirements. An
energy-aware mapping algorithm has been presented in Hu and Merculescu
(2007) that computes the network energy in terms of energy consumed per
bit transmission through the routers and the links. A bandwidth constrained
mapping has been presented in Reshadi et al. (2010).
5.6 Mapping Using Discrete PSO
PSO is a population-based stochastic technique developed by Kennedy and
Eberhart (1995), inspired by social behavior of bird flocking or fish schooling. In a PSO system, multiple candidate solutions coexist and collaborate
simultaneously. Each solution, called a particle, flies in the problem space
according to its own experience as well as the experience of neighboring
particles. It has been successfully applied in many problem areas. In a PSO,
each single solution is a particle in the search space, having a fitness value.
The quality of a particle is evaluated by its fitness. Inspired by its success in
solving problems in continuous domain, several researchers have attempted
to apply it in discrete domain as well (Wang et al. 2003). A well-known problem that was attempted to be solved using discrete PSO (DPSO) technique
is the travelling salesman problem (TSP) (Wang et al. 2003). A solution to a
TSP problem consists of a sequence of all cities, such that the total distance
travelled is minimized. Structurally, the NoC application mapping problem
is very much similar to TSP. If the router positions in the topology graph are
given unique numbers in the range 0 to number_of_routers – 1, the solution
associates each core of the application graph to one such router. Thus, the
mapping problem can also be viewed as an ordering of the cores. This leads
to a DPSO formulation of the application mapping problem.
5.6.1 Particle Structure
In application mapping, a particle corresponds to a possible mapping of
cores to the routers. An example of a particle structure is shown in Figure 5.7.
The numbers shown within circles in the boxes are the core numbers present in the core graph. The numbers outside the box are the router numbers
of the topology graph. The figure shows that core 1 is attached to router 0,
core 4 is attached to router 1, and so on. If the number of nodes (routers)
present in the topology graph is greater than the number of cores present in
the core graph, dummy nodes are added to the core graph to make the two
numbers same. Dummy nodes are connected to all core nodes and between