135
Application Mapping on Network-on-Chip
Procedure Initialize(G, P)
Input: G(V,E)—the task graph, P(U,F)—the topology graph
Output: A mapping function map: V→U, such that map(c) gives the mapping of core c onto a router
Begin
Placed = NULL /* Initialize the set Placed to a null set */
maxs = Core in V with maximum communication
maxt = Node with maximum neighbors in U
map(maxs) = maxt /*Map core maxs to the router with maximum
neighbors */

U = U – {maxt}

V = V – {maxs}

Placed = Placed ∪ {maxt}

While (|V| > 0) do

begin

nexts = Core in V having maximum communication with
cores corresponding to routers in Placed
for all router position u j ∈U do
commcost j = 0
for all cores c k corresponding to routers in Placed do
u k = router corresponding to c k

commcost j = commcost j + comm(nexts, ck) *
hopcount(u j , u k )

nextt = Router position u j with minimum commcost

map(nexts) = nextt

U = U – {nextt}

V = V – {nexts}

Placed = Placed ∪ {nextt}

end

return map, Placed

End
5.5.2 Shortest Path Computation
This phase identifies the shortest paths for communication between the
cores placed at different routers. The set Placed is used to identify the routers
having cores associated with them. To start with, if two cores are mapped to
adjacent routers, the corresponding edge weight is set to be equal to the total
bandwidth requirement between them. The communications of the application graph are sorted in descending order of bandwidth requirement. The
first such communication is picked up. The minimum path between the corresponding router pair is identified. The weights of all edges in the topology
graph belonging to the path are incremented by the bandwidth requirement.