136
Network-on-Chip
If, at the end, the bandwidth constraints are satisfied by all the edges of the
topology graph, the mapping is successful. In such case, the overall communication cost is computed and returned; otherwise a very high-constant
MAXVALUE is returned, indicating that the mapping violates the bandwidth constraints of at least one edge. In a mesh topology, the shortest path
between two nodes always lies between the minimum quadrant involving
the nodes. Hence the algorithm restricts the minimum path search within
the quadrant only.
Procedure shortestpath(Placed)
Input: A set of router positions having cores, that is, the Placed set computed earlier
Output: Total communication cost if bandwidths are satisfied,
MAXVALUE otherwise
Begin
Initialize edge weights of Placed with total communication bandwidth for adjacent nodes and MAXVALUE for others
Sort communications in core graph with decreasing communication cost

For each communication d do

begin

Make quadrant graph Q with source(d) and dest(d) as the
corner vertices
Path = Minpath(Q)
Increase edge weights for edges in Path by the bandwidth
requirement of the communication

end

If all bandwidth constraints are satisfied

Cost = Total communication cost

Else

Cost = MAXVALUE

Return Cost

End
5.5.3 iterative improvement Phase
This phase attempts to improve upon the result obtained in the shortest path
computation phase. For this, it tries to swap the position of two cores (i.e.,
their router allotment) and check whether it leads to a better solution or not.
In case it results in a better solution, the new mapping and the corresponding cost are remembered.