If (cardinality of set Min_Positions =.)

Best_Position = Min_Position[0]

Else
B est_Position = Predict_Best(Min_positions, G, P, c). Mark cc
mapped
End while
Return Mapping
End
Procedure Predict_Best
Input: Core graph G, Topology graph P,
Core: core to be mapped,
Posn: set of contending position of P
Output: Predicted best position of core amongst Posn
Begin
Min_Cost = ∞

Newly_Marked_Cores = Φ

For each position p in Posn do

Mapping[Core] = p
Newly_Marked_Cores = Newly_Marked_Cores ∪ {Core}
147
Application Mapping on Network-on-Chip
Mark Core mapped
While there exists unmapped cores in G do
Let (c i , c j ) be the edge of G with the 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 one hop distance from
already mapped positions
Evaluate_Positions(Positions)
Best_Position = First Position with minimum cost
Mapping[Best_Position] = c
Mark c mapped
End while
Cost = Total communication cost for this mapping
If Min_cost > Cost then
Min_cost = Cost
Min_posn = Φ
End If
Unmark all cores in Newly_Marked_Cores
Newly_Marked_Cores = Φ
End for
Return Min_posn
End