145
Application Mapping on Network-on-Chip
5.6.5.2 Initial Population Generation
For an application with n cores to be mapped onto a mesh topology having n
routers in it, the total number of possible mappings is n!. Thus, exploration of
the promising region of this huge search space depends to a great extent on
the initial population with which each PSO starts evolving. To augment the
solution quality, in the initial set of particles, some particles are included that
are generated via a deterministic mapping technique discussed in this section. For the topology with n routers, exactly n deterministically generated
particles are included. The remaining particles are generated randomly. The
deterministic particle generation works as follows.
First, the edges of the core graph are sorted on descending communication
requirements, as specified in edge label. Let e = (c 1 ,c 2 ) be the edge with the
maximum bandwidth requirement. Mapping process starts with this edge.
For core c 1 , the total bandwidth requirement is computed by summing up
the labels of all edges of c 1 to its neighbors. The same is done for c 2 . Let the
value computed for c 1 be higher than that for c 2 . The mapping process generates solutions with c 1 mapped to each router position of the topology. For
a particular placement of c 1 , the remaining cores are mapped judiciously to
obtain a good solution. Thus, a set of particles equal to the number of routers gets created. The set forms a subset of particles for the initial population.
Suppose that c 1 is mapped onto router u 1 , and in the topology graph, u 1 has
neighbors u 2 , u 3 , and u 4 . Since all these routers are one hop away from u 1 , all
of them are equally suitable for mapping of c 2 . In general, at a point during
execution of this constructive mapping algorithm, a subset of cores is already
mapped onto the routers of the topology graph. Let this set of cores be C′ and
the corresponding router set be U′. The algorithm now considers those edges of
the core graph of which exactly one vertex has already been mapped. It selects
such an edge with the highest bandwidth requirement. Let the unmapped core
of that edge be c i . We try out the mapping of c i to each router placed at a onehop distance from any router in U′ (the set of routers with already assigned
cores). For each such mapping, the cost of mapping is evaluated by considering
the subgraph consisting of cores in the set C′ ∪ { }. If there is a single mapping
c i
with the minimum cost, it is accepted for mapping of c i , and the process continues with the next candidate node selected in a similar fashion. However, if
multiple mappings of c i are of the same cost, let us assume M= {m 1 , m 2 ,, m k }
be the set of k candidate positions for c i resulting in equal mapping cost for the
subgraph with a vertex set C′ ∪ { }. To distinguish between these k positions,
c i
temporarily select m 1 to be the mapping of c i . With this, we proceed to find the
mapping for the remaining cores in a similar fashion, as noted earlier. That is,
for the next core to be mapped, the router positions neighboring to the topology subgraph U′ ∪ m 1 are evaluated. However, in this case we do not distinguish between contending positions with minimum cost values. Instead, we
take the first such position and continue with mapping of the remaining cores.
When all cores are mapped, the cost of the final mapping solution is taken as