146
Network-on-Chip
the predicted cost of selecting router position m 1 for c i . Similarly, other k – 1
positions m 2 , m 3 ,…, m k are evaluated and the core c i is mapped onto the router
position with the minimum predicted cost. The process continues by selecting
the next core. The following algorithm enumerates the process:
Initial Mapping Algorithm: Map_Graph
Input: Core graph G, Topology graph P
Output: Mapping of G onto P
Begin
Sort edges of G on descending order of communication cost
For each router position u of P do

Mark all cores of G as unmapped

Best_Cost = ∞

Best_Mapping = Φ

Mapping = Find_Mapping (G, P, u)
Output Mapping as a particle

End for
End
Procedure Find_Mapping
Input: Core graph G, Topology graph P,
Core: core to be mapped,
Start_Posn: Position in P where first core to be mapped
Output: Mapping of all cores of G onto P with the first core mapped to
Start_Posn
Begin
Let (c 1 ,c 2 ) be the edge of G with the highest required bandwidth
Cost 1 =
Bandwidth requirement of (c 1 , c i )
∑
c ∈neighbour c 1 )
i
(
Cost 2 =
Bandwidth requirement of (c 2 , c i )
∑
ci ∈neighbour c
( 2 )
If (Cost 1 > Cost 2 ) then Core = c 1 else Core = c 2
Mapping[Start_Posn] = Core
Mark Core as mapped
While there exist unmapped cores in G do
Let (c i ,c j ) be the edge of G with highest bandwidth such that exactly
one of c i and c j is already mapped
Let c = c i if c j is already mapped else c = c j
Positions. = set of positions in P with one hop distance from already
mapped positions
Evaluate_Positions(Positions). Min_Positions = Set of. Positions with
minimum cost