303
Reconfigurable Network-on-Chip Design
10.3.8 iterative reconfiguration
In this section, a heuristic algorithm is presented to perform reconfiguration.
For each application, it attempts to finalize the positions of cores, so that the
communication cost for the application can be reduced further. It may be noted
that in the proposed architecture, a core can get attached to any of the four routers surrounding it. It is assumed that the global mapping phase has attached the
core to the router at the upper right position. The local reconfiguration phase
will evaluate other three positions and shift the core to the most suitable router.
The algorithm Heuristic_Configure performs this job. It picks up each application by turn and generates its reconfiguration information. For an application
A i represented by the core graph G i = (C i , E i ), it first computes the communication cost of each of its edges. The edges are sorted in a descending order of
the communication cost. The first edge [e =
(
c
j
i ,
c
k
i )] is taken. Since it is having
the highest communication cost, reducing distance between the corresponding cores is expected to have good impact on communication cost improvement of the application. It then attempts to find the best location for c i
j . It can
move to any of the four neighboring router positions. The core gets attached
to the router resulting in the minimum cost of edge e. The core position gets
locked, and in the corresponding router, only one more core position is available. The same operation is carried out with core c i
k . The process continues till
all cores get locked to some router positions.
Algorithm Heuristic_Reconfigure
Input: Mapping of core graphs G 1 ,G 2 ,... G n corresponding to applications
A 1 , A 2 ,... A n
Output: Reconfigured mappings
Begin
For each application core graph G i = (C i , E i ) of A i do
Begin
Mark all cores of C i as unlocked
For each edge e = (c i
j , c i
k ) ∈ E i do
Begin
Communication cost of e = bandwidth (e) * hopdistance between routers to which cores c i
j and c i
k
are mapped
End For
Sort all edges in E i on decreasing communication cost
For each edge e = (c i
j , c i
k ) ∈ E i picked up in order do
Begin
If c i
j and c i
k are both locked then continue with
next edge
If c i
j and c i
k are both mapped to same router then
Mark both cores as locked